目录
比赛链接
总结
知识点
B - Festival Decorating
-
\([A_i \neq 0]\) 可以作为多项式卷积里面多项式的系数
-
bitset 可以做01卷积；此时，每一侧都可以作为最外侧所枚举的：
-
for(int i=1; i<=n; ++i) f.set(x[i]); //for(int i=0; i<=m; ++i) // ans[i] = (f & (f>>i)).count(); //等价写法： for(int i=1; i<=n; ++i) ans |= f>>x[i];
-
-
bitset 的
_Find_first和_Find_next-
for(int t=f._Find_first(); t!=f.size(); t=f._Find_next(t))
-
D - Operator Precedence
- 构造题的方法：“待定系数”、列方程求解
K - Card Game
- “对所有区间询问”，可以考虑用可持久化线段树预处理“所有区间”的答案
易错点
- 注意讨论“元素相等”的边界情况（H - Sugar Sweet II）
策略
- 多想一下再开写（M刚开的时候有好几个思路上的大漏洞）
- 过题人数与难度不一定正比（G，F 开晚了；K可以开）
题解
B - Festival Decorating
做法1
-
利用容错性，只需要处理前 \(3^x\) 个元素里能否得到每一个 \(d\)
-
不考虑颜色就是简单的 FFT。考虑类似于 FFT 做字符串匹配的时候的思路，构造匹配函数：令 \(A_i\) 表示 \(i\) 位置的灯的颜色，没有灯的时候为 0，令 \(B_i = A_i\)，只需要计算 \(C_d = \sum_i [A_i > 0][B_{i + d} > 0] (A_i - B_{i+d})^2\)
- \[ C_d = \sum_i [A_i > 0][B_{i+d} > 0](A_i^2 + B_{i+d}^2 - 2A_iB_{i+d})\\ = \sum_i A_i^2 \cdot \left[ B_{i+d} > 0\right]\\ + \sum_i \left[ A_{i} > 0\right] \cdot B_{i+d}^2\\ - 2 \cdot \sum_i A_i \cdot B_{i+d} \]
做法2
- bitset，直接从小到大枚举灯的编号
i，设其它的灯出现的位置集合是f，还没有找到答案的d的集合为n_vis，我们拿出n_vis & (f >> x[i])中的所有 1 更新答案即可 - 如何得到
f：- 先记录所有灯的位置集合
all - 若颜色为
c[i]的灯数量不超过 \(T\)，直接枚举所有同色灯，然后修改all - 若颜色为
c[i]的灯数量超过 \(\sqrt T\)，这样的颜色不超过 \(\frac{n}{T}\) 个，预处理该颜色所有灯的位置g[c[i]]然后all ^= g[c[i]]
- 先记录所有灯的位置集合
- 取 \(T = \sqrt n\) 可以得到 \(O(n \sqrt n + \frac{n^2}{w})\) 的复杂度
//https://codeforces.com/group/Ro45Qpwf2L/contest/104976/submission/280692536
const int N = 250010;
int x[N], c[N], n, m;
vector<int> s[N];
bitset<250005> sum, f[1010], nvis, tmp;
int ans[N];
int pos[N], id[N], num;
int main() {
int q; rd(n), rd(q);
for(int i=1; i<=n; ++i) {
rd(x[i]), rd(c[i]);
m = max(m, x[i]), s[c[i]].PB(x[i]);
}
int B = ceil(sqrt(n));
for(int i=1; i<=n; ++i) if(s[i].size()) {
for(int v : s[i]) sum.set(v);
if(s[i].size() > B) {
id[pos[i] = ++num] = i;
for(int v : s[i])
f[num].set(v);
}
}
for(int i=1; i<=m; ++i) nvis.set(i);
for(int i=1; i<=n; ++i) {
if(s[c[i]].size() > B)
tmp = (sum^f[pos[c[i]]]);
else {
tmp = sum;
for(int v : s[c[i]]) tmp.reset(v);
}
tmp = (tmp >> x[i]) & nvis;
for (int t=tmp._Find_first();t!=tmp.size();t=tmp._Find_next(t))
ans[t] = i, nvis.reset(t);
}
while(q--) {
int d; rd(d);
printf("%d\n", (int)(ans[d]));
}
return 0;
}
D - Operator Precedence
题意：求下列方程的一组解
\[ (a_1 \times a_2) + (a_3 \times a_4) + \cdots + (a_{2n-1}\times a_{2n}) = a_1 \times (a_2 + a_3) \times (a_4 + a_5) \times \cdots \times (a_{2n-2} + a_{2n-1}) \times a_{2n} \]解：考虑令 \(a_2, a_4 \cdots a_{2n - 2} = 2, a_3, a_5 , \cdots , a_{2n-1} = -1\)，设 \(a_1 = x, a_{2n} = y\)，则
\[xy = 2x - y -2(n-2) \]令 \(x=1\) 则 \(y = 3-n\)，得到一组合法解。
//https://codeforces.com/group/Ro45Qpwf2L/contest/104976/submission/280942688
int main() {
int ts; rd(ts);
while(ts--) {
int n; rd(n);
if(n == 3) {
printf("1 -10 6 6 -10 1\n");
continue;
}
print(1), putchar(' ');
for(int i=2; i<2*n; ++i)
print(i&1 ? -1 : 2), putchar(' ');
print(3-n), putchar('\n');
}
return 0;
}
K - Card Game
设区间 \([l,r]\) 的答案为 \(ans_{l, r}\)，设 \(nxt_i\) 表示 \(a_i\) 在序列中下一次出现的位置。则：
\[ans_{l, r} = \begin{cases} ans_{nxt_l + 1, r} & nxt_l \le r\\ 1 + ans_{l + 1, r} & nxt_l > r \end{cases} \]用可持久化线段树，由 rt[nxt[l] + 1]和 rt[l+1] 的一部分，合并得到 rt[l]。具体来说，先找到 [l, nxt[l]], [nxt[l]+1, n] 这两个区间被线段树划分出来的 \(O(\log n)\) 个区间，区间及其祖先新建节点，区间的儿子继承之前的树。
//https://codeforces.com/group/Ro45Qpwf2L/contest/104976/submission/280699787
const int N = 3e5 + 10;
const int M = 60 * N;
int ls[M], rs[M], tg[M];
int ncnt;
int ql, qr, qt;
void upd(int l,int r,int &c, int u, int t) {
if(!c) c = ++ncnt;
t += tg[u];
if(ql <= l && qr >= r) {
tg[c] += qt + t;
ls[c] = ls[u], rs[c] = rs[u];
return;
}
int mid = l + r >> 1;
if(ql <= mid) upd(l, mid, ls[c], ls[u], t);
if(qr > mid) upd(mid+1, r, rs[c], rs[u], t);
}
int qry(int l,int r,int c) {
if(!c || l == r) return tg[c];
int mid = l + r >> 1;
if(ql <= mid) return qry(l, mid, ls[c]) + tg[c];
else return qry(mid+1, r, rs[c]) + tg[c];
}
int rt[N];
int n, a[N], p[N], lst[N];
int main() {
int q; rd(n), rd(q);
for(int i=1; i<=n; ++i) rd(a[i]);
for(int i=1; i<=n; ++i) lst[i] = n+1;
for(int i=n; i>=1; --i) {
p[i] = lst[a[i]];
lst[a[i]] = i;
}
for(int i=n; i>=1; --i) {
ql = i, qr = p[i] - 1, qt = 1;
upd(1, n, rt[i], rt[i + 1], 0);
ql = p[i], qr = n, qt = 0;
if(ql <= qr) upd(1, n, rt[i], rt[p[i] + 1], 0);
}
int ans = 0;
while(q--) {
int l, r; rd(l), rd(r);
l ^= ans, r ^= ans;
// printf("query: %d %d\n", l, r);
ql = r;
printf("%d\n", ans = qry(1, n, rt[l]));
}
return 0;
}