CF2038
有 \(n\) 个人合作完成一个任务，这个任务需要 \(k\) 的工作量，完成任务后，第 \(i\) 个人会收到 \(a_i\) 的报酬，而完成一个单位的工作量会产生 \(b_i\) 的代价。若一个人的报酬小于代价，那么他绝对不会工作。
\(n\) 个人依次决定自己的工作量，每个人都会最大化自己的收益。如果总工作量小于 \(k\)，那么所有人都拿不到报酬。
问每个人会工作多少。
只要能少工作就少工作，贪心即可。
给你一个长为 \(n\) 的序列 \(a_{1\sim n}\)。你可以进行以下操作任意次：
- 选择一个 \(i\)，
a[i] -= 2, a[i % n + 1]++;
问能否使序列的各个项最终非负且相等。若能，输出最小步数。
\(n\le 2\times 10^5,~a_i\le 10^9\)
设最后序列的所有值等于 \(p\)。由于 \(p+1\) 可以转移到 \(p\)，并且操作是无序的，因此 \(p\) 具有单调性。考虑二分答案。
如果一个 \(a_i>p\)，那么至少要给它减少到 \(p\)。如果奇偶性不同，那么减少到 \(p-1\)。暴力从 \(1\) 做到 \(n\)，如果不合法就再转一轮，直到彻底不合法或者合法停止。发现这样做的复杂度其实是对的，因为一个 \(a_i\) 最多贡献到后 \(30\) 项。
给定一个序列 \(a_{1\sim n}\)。你需要从中选出下标互不相同的八项 \(a,b,c,d,e,f,g,h\)，满足 \((a,b),(c,d),(e,f),(g,h)\) 构成一个四边平行于坐标轴的长方形。构造一种方案，使得长方形面积最大，或者报告无解。
\(n\le 2\times 10^5\)
md 原题翻译错了，没写平行于坐标轴，让我对着一个真黄题想了 \(20\) 分钟，服了。
注意到 \(8\) 个数可以分为 \(4\) 对相等的数字。因此记录出现至少两次的数字，然后选最大次大和最小次小作为 \(8\) 个数即可。
给定一个长为 \(n\) 的序列 \(a_{1\sim n}\)，你需要将序列划分为任意段，满足每段的按位或单调不降。问划分方案数对 \(998244353\) 取模的结果。
\(n\le 2\times 10^5\)
注意到，固定右端点后，不同的区间按位或只有 \(\log n\) 种。因此怎么做都行。可以先二分出每种按位或结果对应的左端点区间，然后把当前下标挂在区间两端，采用刷表法&树状数组进行转移即可。
然而这种做法太难写了，而且不知道为什么卡常。因此这里介绍另一种 dp 转移方法。先设 \(f_{i,j}\) 表示前 \(i\) 个数字划分成了若干段，最后一段为 \(j\) 的方案数。考虑转移，考察前缀内的最后一段区间 \([k,i]\)，对于 \([k,i-1]\) 是合法区间的情况，我们从 \(f_{i-1,j'}\) 直接转移到 \(f_{i,j'\oplus a_i}\)。
【先咕了，等会】
记 \(v_i\) 表示桶的水面高度，\(l_i\) 表示桶左边的管道高度，\(r_i\) 表示桶右边的管道高度。
容易想到一种贪心策略：从最右边的桶开始，一直扔粘土直到堵住，然后下一个桶继续扔到堵住，直到最左边。发现 hack 不掉，应该是对的。
考虑怎么维护。扔粘土可以看作倒水。然后有一些桶的水面会通过管道连在一起，而无论什么操作都不会发生连通块的分裂，因此可以用并查集维护。每次加水先线段树二分找到最靠右的 \(v<l\) 的一个连通块，然后加水直到 \(v=r\)（找下一个）或者 \(v=l\)（合并连通块）或者本次的水用完了（炸掉最右边的桶）。总操作次数应该是 \(O(n)\) 的。
给定两个长为 \(n\) 的序列 \(a_{1\sim n},b_{1\sim n}\)，对每个 \(1\le k\le n\) 求出
\[
\sum_{S\subseteq \{1,2,\cdots,n\}\wedge |S|=k}\max(\min_{i\in S}a_i,\min_{i\in S}b_i)
\]
\(n\le 2\times 10^5,\ a_i\le 10^6\)
一个 \(\max\) 套两个 \(\min\) 不好处理，分讨二者大小也没什么前途。考虑经典转化：\(\max(a,b)=a+b-\min(a,b)\)。因此问题转化为：
\[
\sum_{S\subseteq \{1,2,\cdots,n\}}\min{a_i}+\sum_{S\subseteq \{1,2,\cdots,n\}}\min{b_i}-\sum_{S\subseteq \{1,2,\cdots,n\}}\min\bigl\{\min(a_i,b_i)\big\}
\]
三项分别对应三个独立的序列。考虑解决一个序列的问题：
\[
\sum_{S\subseteq \{1,2,\cdots,n\}\wedge |S|=k}\min{a_i}
\]
序列显然无序，因此先对其进行升序排序，答案即：
\[
ans_k=\sum_{i=1}^{n}a_i\binom{n-i}{k-1}
\]
题解说如果足够熟练应该一眼看出来是卷积。但是我不行，所以来推式子。
\[
\begin{align*}
\sum_{i=1}^{n}a_i\binom{n-i}{k-1}&=\sum_{i=1}^{n}\frac{(n-i)!a_i}{(n-i-k+1)!(k-1)!}\\
&=\frac{1}{(k-1)!}\sum_{i=1}^{n}\frac{(n-i)!a_i}{(n-k+1-i)!}
\end{align*}
\]
是不是能看出来了:
\[
ans_k=\frac{1}{(k-1)!}[x^{n-k+1}]\Bigl(\bigl(\sum_{i=1}^{n}(n-i)!a_ix^i\big)\times \bigl(\sum_{i=0}^{n}\frac{1}{i!}\big)\Big)
\]
时间复杂度 \(O(n\log n)\)。
代码
| #include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N = 6e5 + 10;
const int MOD = 998244353;
int n;
int a[N], b[N], c[N];
int res[N], ans[N];
int inv[N], fact[N], ifact[N];
int d[N];
inline int qpow(int a, int b) {
int res = 1;
while(b) {
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
void ntt(int a[], int n, int g) {
static int inv[N];
for(int i = 0; i < n; i++) inv[i] = (inv[i >> 1] >> 1) | ((n >> 1) * (i & 1));
for(int i = 0; i < n; i++) if(i < inv[i]) swap(a[i], a[inv[i]]);
for(int k = 1; k < n; k <<= 1) {
int w0 = qpow(g, (MOD - 1) / (2 * k));
for(int i = 0; i < n; i += 2 * k) {
int w = 1;
for(int j = 0; j < k; j++) {
int x = a[i + j], y = a[i + j + k] * w % MOD;
a[i + j] = (x + y) % MOD;
a[i + j + k] = (x + MOD - y) % MOD;
w = w * w0 % MOD;
}
}
}
}
void solve(int a[]) {
sort(a + 1, a + 1 + n);
for(int i = 1; i <= n; i++) a[i] = a[i] * fact[n - i] % MOD;
ntt(a, 524288, 3);
for(int i = 0; i < 524288; i++) res[i] = a[i] * d[i] % MOD;
ntt(res, 524288, 332748118);
for(int i = 1; i <= n; i++) res[i] = res[i] * inv[524288] % MOD;
for(int i = 1; i < n - i + 1; i++) swap(res[i], res[n - i + 1]);
for(int i = 1; i <= n; i++) res[i] = res[i] * ifact[i - 1] % MOD;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
inv[1] = fact[0] = ifact[0] = 1;
for(int i = 2; i < N; i++) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
for(int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
for(int i = 1; i < N; i++) ifact[i] = ifact[i - 1] * inv[i] % MOD;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
for(int i = 1; i <= n; i++) c[i] = min(a[i], b[i]);
for(int i = 0; i < 262144; i++) d[i] = ifact[i];
ntt(d, 524288, 3);
solve(a);
for(int i = 1; i <= n; i++) ans[i] = res[i];
solve(b);
for(int i = 1; i <= n; i++) ans[i] = (ans[i] + res[i]) % MOD;
solve(c);
for(int i = 1; i <= n; i++) ans[i] = (ans[i] + MOD - res[i]) % MOD;
for(int i = 1; i <= n; i++) cout << ans[i] * (ifact[n] * fact[n - i] % MOD * fact[i] % MOD) % MOD << ' ';
cout << '\n';
return 0;
}
|
容易先想到询问 1 的数量，然后想知道连续段数量。发现可以询问 01 或者 10，但是在开头结尾等于 \(1\) 的情况下会少统计一个连续段。又发现询问 11 可以直接知道正确的连续段数。然后不难知道开头或结尾是什么字符。
转化之后是费用流板子。先咕了。
二分哈希排序。先咕了。