杂记（一）

UVA1451 平均值 Average

题目地址

Description

给定一个长度为n的01串，选一个长度至少为L的连续子串，使得子串中数字的平均值最大。如果有多解，子串长度应尽量小；如果仍有多解，起点编号尽量小。序列中的字符编号为1~n，因此[1,n]就是完整的字符串。$1\le n\le 100000,1\le L\le 1000$。

Solution 1

设01串的前缀和为sum，则[l,r]的平均值可以表示为$\dfrac{sum[r]-sum[l-1]}{r-(l-1)}$，该式可以看作是点(l-1,sum[l-1])和(r,sum[r])的斜率表达式，那么题意就可以转化为：给定n+1个节点（l-1的范围和r的范围取并后的集合大小是n+1），要求选出两个节点使得他们的横坐标之差至少为L，且斜率最大，若有多解取横坐标之差最小的，若还有多解取横坐标较小的。
对于每个点x，我们只考虑横坐标比x小的点，那么显然我们取到的决策点就是过x且与左边所有点的下凸包的切点，因此我们需要在枚举x的过程中动态维护x-1的下凸包（注意，不是维护x的凸包）。
那么如何快速找到这个切点呢？比较直接的想法是直接二分，这并没有问题，复杂度是$O(n\log n)$也可以接受，但实际上由于sum是随着x的增大而单调不降的，所以很容易证明这个问题具有决策单调性，也就是说随着x的增大决策点是单调不降的，因此我们可以用一个单调队列，尾部维护凸包，头部维护决策点。

Source Code

int main() {
    int T = fast_IO::read();
    while (T--) {
        int n = fast_IO::read(), L = fast_IO::read();
        scanf("%s", s + 1);
        for (int i = 1; i <= n; ++i)sum[i] = sum[i - 1] + (s[i] ^ 48);
        //max{(sum[j]-sum[i-1])/(j-(i-1))|j>=i+L-1}
        int ansl = 1, ansr = L;
        int head = 0, tail = 0;
        for (int i = 0; i <= n - L; ++i) {
            while (tail - head > 1 && (sum[i - 1] - sum[q[tail - 2] - 1]) * (i - q[tail - 1]) >= (sum[i - 1] - sum[q[tail - 1] - 1]) * (i - q[tail - 2]))--tail;
            q[tail++] = i;
            while (tail - head > 1 && (sum[i + L - 1] - sum[q[head + 1] - 1]) * (i + L - q[head]) >= (sum[i + L - 1] - sum[q[head] - 1]) * (i + L - q[head + 1]))++head;
            ll tmp = (sum[i + L - 1] - sum[q[head] - 1]) * (ansr - ansl + 1) - (sum[ansr] - sum[ansl - 1]) * (i + L - q[head]);
            if (tmp > 0 || (tmp == 0 && i + L - q[head] < ansr - ansl + 1)) {
                ansl = q[head];
                ansr = i + L - 1;
            }
        }
        printf("%d %d\n", ansl, ansr);
    }
    return 0;
}

Solution 2

还有一种比较明显的解法是二分平均值，验证只需要将每个元素都减去平均值，判断有没有一个长度至少为len的区间使得区间和为0即可。

七夕祭

题目地址

Description

有n行m列个摊位，可以对任意相邻摊位进行交换，而且行列分别首尾相邻，指定其中的T个摊位，问能否通过交换使得每行或每列的指定摊位个数一样多，并求最小交换次数。

$1\le n,m\le 100000，0\le T\le \min(n\cdot m, 100000)$

Solution

首先，我们一定可以通过相邻互换将任何一个摊位移到任何一个位置，因此要判断能否使得每行的指定摊位数一样多或每列的指定摊位数一样多，只需要看T是否整除n、m。
当T整除n、m的时候，我们就可以分别求出每行、每列应该分别为$\dfrac{n}{T},\dfrac{m}{T}$个指定摊位。显然，行方向上的移动不改变列上的值，列方向上的移动不改变行上的值，因此行列是独立的，分开处理，这样实际上就是个一维的问题而不是二维的。
那么现在来考虑单独的行（列也一样）该如何计算，首先我们得到每行的指定摊位数$a_i$。由于行首尾相连，所以一行实际上是一个简单环。考虑移动的过程可以拆成多个移动，每次只移动一个单位，所以我们可以将所有的移动进行拆分，这样的话在每个相邻点连的边上会有一个转移的数量和方向，我们不妨规定$a_i\to a_{i-1}$的方向为正方向，设从某个点i沿着正方向移动的摊位数为$x_i$。那么就可以写出我们的目标函数：

$$\left|x_1\right|+\left|x_2\right|+\left|x_3\right|+...+\left|x_{n-1}\right|+\left|x_n\right|$$

现在我们的目的就是使目标函数最小。
考虑到函数中变元较多，我们列出这些变元之间的关系。
令$w=\dfrac{T}{n}$，即最终每行的指定摊位数，那么就可以得到如下方程组：

$$\begin{cases} a_1-x_1+x_2=w\\ a_2-x_2+x_3=w\\ ...\\ a_{n-1}-x_{n-1}+x_n=w\\ a_n-x_n+x_1=w \end{cases}$$

显然，该方程组的秩为n-1，我们无法直接求出所有的x，但是我们不妨设$x_1$为自由元，那么其他的x都可以用$x_1$表示：

$$\begin{cases} x_1=x_1\\ x_2=x_1-(a_1-w)\\ x_3=x_1-(a_1+a_2-2w)\\ ...\\ x_{n-1}=x_1-(a_1+a_2+...+a_{n-2}-(n-2)w)\\ x_n=x_1-(a_1+a_2+...+a_{n-1}-(n-1)w) \end{cases}$$

不难看出，右式中减号后面的部分有明显的规律，我们记为$c$
那么目标函数就变形为

$$\left|x_1-c_1\right|+\left|x_1-c_2\right|+\left|x_1-c_3\right|+...+\left|x_1-c_{n-1}\right|+\left|x_1-c_n\right|$$

这里面不确定的只有$x_1$，那么问题就转化为：数轴上有n个点，坐标分别为$c_1,c_2,…,c_n$，现在要在数轴上选一点，使得各点到这个点的距离之和最小，这就是一个经典问题了。
首先给出结论：$x_1$取的是$c$的中位数，下面给出一种证明方法。
假设$c$已排好序，根据绝对值不等式$\left|a\right|+\left|b\right|\ge\left|a+b\right|$，有如下推导

$$\begin{align} &\left|x_1-c_1\right|+\left|x_1-c_2\right|+\left|x_1-c_3\right|+...+\left|x_1-c_{n-1}\right|+\left|x_1-c_n\right|\\ &=\left|x_1-c_1\right|+\left|c_n-x_1\right|+\left|x_1-c_2\right|+\left|c_{n-1}-x_1\right|...\\ &\ge (c_n-c_1)+(c_{n-1}-c_2)+... \end{align}$$

若不等号左式能取到右式，则说明右式为下确界，即为我们要求的最值。
那么可不可以取到呢？我们取中位数，则右式中每一个括号内的一对c与中位数差的绝对值之和正好是其差的绝对值，因此右式是左式的下确界，且在$x_1$取$c$的中位数时目标函数值最小。

到此，这道题的算法就完全分析清楚了。

Source Code

int row[N], col[N];
ll sum[N];
ll solve(int *a, int n, int w) {
    for (int i = 1; i <= n; ++i)a[i] -= w;
    ll ans = 0;
    sum[1] = 0;
    for (int i = 1; i < n; ++i)sum[i + 1] = sum[i] + a[i];
    sort(sum + 1, sum + n + 1);
    for (int i = 1; i <= n; ++i)
        ans += abs(sum[n + 1 >> 1] - sum[i]);
    return ans;
}

int main() {
    int n = fast_IO::read(), m = fast_IO::read(), k = fast_IO::read();
    for (int i = 1; i <= k; ++i) {
        ++row[fast_IO::read()];
        ++col[fast_IO::read()];
    }
    if (k % n && k % m)puts("impossible");
    else if (k % n == 0 && k % m == 0) {
        printf("both ");
        printf("%lld", solve(row, n, k / n) + solve(col, m, k / m));
    }
    else if (k % n == 0) {
        printf("row ");
        printf("%lld", solve(row, n, k / n));
    }
    else {
        printf("column ");
        printf("%lld", solve(col, m, k / m));
    }
    return 0;
}

几何学中的欧拉公式

$$V-E+F = 2$$

其中V为顶点数，E为边数，F为面数

组合数中的几个公式

$$k\begin{pmatrix}n\\k\end{pmatrix}=n\begin{pmatrix}n-1\\k-1\end{pmatrix}\\ \sum\limits_{i=0}^n\begin{pmatrix}n\\i\end{pmatrix}(k-1)^{n-i}=k^n$$

随机排列

在随机排列的时候用random_shuffle是可以被卡掉的。
使用如下方式排列

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
shuffle(a + 1, a + n + 1, rng);