AT_arc153_c [ARC153C] ± Increasing Sequence
先赋值为 \(1,2,3\ldots n\)，然后找到一个 \(abs\) 等于 \(1\) 且代价相反的即可。
P7324 [WC2021] 表达式求值
首先我们对于每个下标分开考虑，考虑预处理出来 \(2^n\) 种集合 \(S\) 每种集合最后为 \(1\) 的方案数，然后每位计算的时候，我们差分后计算每个位置的答案即可，复杂度 \(O(m2^m+m^2n)\)
CF878D Magic Breeding
和上一个题类似的，我们枚举答案，把 \(\ge x\) 变成 \(1\)，然后我们考虑 \(2^k\) 种列，bitset 维护每种列的答案，转移可以 bitset 位运算转移，复杂度 \(O(\frac {q2^k}w+qk^2)\)。
AT_arc155_d [ARC155D] Avoid Coprime Game
我们考虑 dp，设我们当前在 \(x\)，那么我们考虑一个 \(a_i\) 和 \(x\) 的关系。
- \(x\nmid a_i\)，\(x\) 变成 \(\gcd(x,a_i)\)。
- 否则我们考虑 \(x\) 的倍数的奇偶以及操作次数的奇偶性即可。
我们考虑 dp，设 \(f_{x,0/1}\) 表示当前为 \(\gcd=x\)，操作了奇数/偶数次即可。
转移我们考虑对于 \(x\) 的每个因数 \(d\)，容斥计算是否存在 \(a_i\) 使得 \(\gcd(a_i,x)=d\) 即可。
有点抽象，放个代码：
Code
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e5,M=N+5;
int n,a[M],f[M][2],cnt1[M],cnt2[M];
vector<int>vec[M];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i],++cnt1[a[i]];
for(int i=2;i<=N;++i)
for(int j=i;j<=N;j+=i) vec[j].pb(i),cnt1[i]+=cnt1[j]*(i<j);
for(int i=2;i<=N;++i){
int sz=vec[i].size(),fl=0;
for(auto v:vec[i]) cnt2[v]=cnt1[v];
for(int j=sz-1;~j;--j){
int x=vec[i][j];
if(j<sz-1&&cnt2[x]!=0){
if(!f[x][1]) f[i][0]=fl=1;
if(!f[x][0]) f[i][1]=fl=1;
}
for(auto v:vec[x]) cnt2[v]-=cnt2[x];
}
if(!fl) f[i][cnt1[i]%2]=1;
}
for(int i=1;i<=n;++i) puts(f[a[i]][0]?"Aoki":"Takahashi");
}
实际上，根据这个只需要根据 \(r\) 数组，我们就能得到唯一的笛卡尔树形态。
我们对于 \(r\) 前缀和得到 \(sr\) 数组。
我们考虑全局最小值，发现他是最后一个满足 \(sr_{i-1}=i-1\) 的 \(i\)。
然后后面的问题是类似的，递归即可，然后我们就建出笛卡尔树了，dp 是简单的。
P2481 [SDOI2010] 代码拍卖会
拆成若干段 \(111111\)，寻找循环节然后背包。
P3634 [APIO2012] 守卫
首先把不能放人的扔了，特判剩下全部放的情况。
然后套用经典贪心，只有这些被选择的点可能成为答案。
考虑怎么判断，把包含的区间删了，变成互不包含的，直接预处理一下前后缀信息即可。
LOJ 6268 分拆数
我们考虑 Ferrers 图，引一条 \(y=x\) 的线，考虑多久离开图形，不妨设为 \(h\)，则两端分别是大小不超过 \(h\) 的拆分数，即：
\[\prod_{k\ge 1}\frac 1 {1-x^k}=\sum_{h\ge 1}(\prod_{k=1}^h\frac 1 {1-x^k})^2 \]我们不难发现，当我们计算第 \(n\) 项时，\(h\le \sqrt n\)，然后后面的生成函数我们直接算就行了，代码非常短，复杂度 \(O(n\sqrt n)\)。
常数非常小，计算 \(1\sim 10^6\) 中每个数的拆分数本机下只需要 770 ms，如果只需要第 \(10^6\) 项这一项，只需要 460ms
P8340 [AHOI2022] 山河重整
某些人不会 \(O(n\sqrt n)\) 求互异拆分数还想打山河重整 /cf
AT_agc029_f [AGC029F] Construction of a tree
考察无解条件，如果对于 \({E_1,E_2,\ldots E_{n-1}}\) 的一个子集 \(S\)，能连通的所有点大小 \(|f(S)|\le |S|\) 就寄了，因为一定有环，所以 \(|f(S)|>|S|\)。
我们先找一个二分图最大匹配，如果不是 \(n-1\) 无解。
然后找到没有匹配的点 \(r\)，对于他找到他连着另外一段没有访问过的边 \(i\) 及其匹配的点 \(u\)，连接 \((r,u)\)。
如何证明这个不会把有解变成无解：直接考虑我们右边没有遍历到的集合 \(S\)，由于我们遍历到的点数比边数大 \(1\)，而且 \(S\) 连接的点 \(f(S)\) 也一定没有遍历过，所以 \(|f(S)|\le |S|\)，所以本身就是无解的。
然后就做完了。
AT_agc024_f [AGC024F] Simple Subsequence Problem
建出子序列自动机，然后构造的状态 \(f_{S,T}\) 是已经匹配了 \(S\) 在自动机上还剩下 \(T\)，由于 \(|S|+|T|\le n\)，所以状态数是 \(O(n2^n)\)，写法需要精细实现。
放个贺的代码：
Code
#include<bits/stdc++.h>
using namespace std;
const int N=21;
int n,K,ans,hb[1<<N],tr[1<<N][2],f[N][1<<N];
char c;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>K;
for(int i=0;i<=n;++i)
for(int x=0;x<(1<<i);++x) cin>>c,f[i][(1<<i)|x]=c-'0';
hb[0]=-1;
for(int S=1;S<(2<<n);++S) hb[S]=hb[S>>1]+1;
for(int S=2;S<(2<<n);++S){
if(S>>(hb[S]-1)&1) tr[S][0]=tr[tr[S][1]=S^(1<<hb[S])][0];
else tr[S][1]=tr[tr[S][0]=S^(3<<(hb[S]-1))][1];
}
for(int i=n;i;--i)
for(int A=1<<i;A<(2<<n);++A)
if(f[i][A]){
int _=A>>i,B=(A&((1<<i)-1))|1<<i;
if(tr[B][0]) f[hb[tr[B][0]]][((_<<1)<<hb[tr[B][0]])^tr[B][0]^(1<<hb[tr[B][0]])]+=f[i][A];
if(tr[B][1]) f[hb[tr[B][1]]][((_<<1|1)<<hb[tr[B][1]])^tr[B][1]^(1<<hb[tr[B][1]])]+=f[i][A];
f[0][_]+=f[i][A];
}
ans=1;
for(int S=2;S<(2<<n);++S) if(f[0][S]>=K&&hb[S]>hb[ans]) ans=S;
int j=n;
while(~ans>>j&1) --j;
while(j--) cout<<(ans>>j&1);
}
CF1103D Professional layer
首先只有不超过 \(k=11\) 个质因子，然后我们每次暴力枚举消除的质因子集合，保留代价前 \(k\) 小的即可，然后就能过了？？？
CF1476F Lanterns
经典老番，设 \(f_i\) 表示前 \(i\) 个灯的能覆盖的最长前缀是多少。
- 向右，\(f_{i-1}\ge i\)，\(f_i=\max(f_{i-1},i+p_i)\)。
- 向左，找到一个 \(t\) 满足 \(f_t\ge i-p_i-1\)，则转移有 \(f_i=\max(i-1,t+1+p_{t+1},\ldots (i-1)+p_{i-1})\)。
- 虽然朝向了一个方向，但是贡献如有，\(f_i=f_{i-1}\)。
CF713E Sonya Partymaker
首先我们来一手二分，然后不难发现如果是一条链的话就是上一个题了，但是我们发现还有 \(n\sim 1\) 的方法不好确定，我们考虑由于答案不超过 \(\max(a_{i+1}-a_i)\)，所以我们直接找出最大的区间当作 \(n\sim 1\) 的间隔，然后分讨 \(1\) 向左还是 \(2\) 向左即可。
CF1366F Jog Around The Graph
首先我们肯定是走到某个边，然后来回刷分，我们直接设 \(f_{i,j}\) 表示走了 \(i\) 条边，在 \(j\) 时最大经过的权值和即可。
然后后面的贡献是一个一次函数，建凸包即可。
CF1450H1 Multithreading (Easy Version)
首先，根据魔怔的贪心，我们可以首先每次选出相邻的两个颜色相同的配对，最后会剩下 abababab 的环，交点数量是 \(\frac {cnt_b}2\)，然后我们如果 \(b\) 在奇数下标出现 \(A\) 次，偶数下标出现 \(B\) 次，则答案是 \(\frac {|A-B|}2\)。
然后假设奇数下标有 \(A\) 个，偶数有 \(B\) 个，确定的 \(b\) 奇偶下标之差为 \(val\)，则
\[\begin{aligned} ans&=\frac 1 {2^{A+B-1}}\sum_{i=0}^A\sum_{j=0}^B[val+i-j\equiv 0\bmod 2]\frac {|val+i-j|}2\binom A i\binom B j\\ ans&=\frac 1 {2^{A+B}}\sum_{i=0}^A\sum_{j=0}^B[val+i-j\equiv 0\bmod 2]|val+i-j|\binom A i\binom B j\\ ans&=\frac 1 {2^{A+B}}\sum_{val-B\le t\le val+A,2\mid t}|t|\sum_{i=0}^A\sum_{j=0}^B[val+i-j=t]\binom A i\binom B j\\ ans&=\frac 1 {2^{A+B}}\sum_{val-B\le t\le val+A,2\mid t}|t|\sum_{i=0}^A\sum_{j=0}^B[val+i-(B-j)=t]\binom A i\binom B {B-j}\\ ans&=\frac 1 {2^{A+B}}\sum_{val-B\le t\le val+A,2\mid t}|t|\sum_{i=0}^A\sum_{j=0}^B[i+j=t+B-val]\binom A i\binom B j\\ ans&=\frac 1 {2^{A+B}}\sum_{val-B\le t\le val+A,2\mid t}|t|\binom {A+B}{t-val+B}\\ \end{aligned} \]然后做完了。
CF794G Replace All
CF2003F Turtle and Three Sequences
似乎叫 color-coding，我记得 CSP2022 的时候就有老哥 T1 用这个方法过了，给了我巨大震撼。
由于有互不相同的限制，考虑对于每个点赋值一种 \(1\sim m\) 的颜色，然后我们状压选了哪些，做 \(T\) 次，树状数组优化，复杂度 \(O(Tn2^m\log n)\)。
考虑正确率，由于只要最后成为答案的 \(m\) 个数颜色不同就成功，所以一次的正确率是 \(\frac {m!}{m^m}\)，正确率大概是 \(1-(1-\frac {m!}{m^m})^T\)。
还有一种方法是不枚举子集，分配颜色的同时钦定顺序，则复杂度为 \(O(Tnm\log n)\)，正确率变成 \(1-(1-\frac 1 {m!})^T\)。
CF1951H Thanos Snap
考虑二分，然后我们设 \(f_x\) 表示在操作 \(x\) 子树前至少要提前操作多少次才合法。
首先是假设子树内有 \(x\) 个 \(1\)，\(f_x=\max(0,sz-x)\)。
然后就是 \(f_{x}=f_{ls}+f_{rs}-1\)，这三种情况。
CF1305F Kuroni and the Punishment
首先不难发现答案不超过 \(n\)，所以有 \(>=\frac n 2\) 个点是 \(-1,1,+1\) 三种情况，随机 \(T\) 次，每次找到一个 \(a_x\)，找出 \(a_x-1,a_x,a_x+1\) 的质因数，扔进一个 set 里，最后对于 set 里面的每个数计算答案即可。
CF1951G Clacking Balls
CF566C Logistical Questions
首先我们不难发现这玩意是凸的。
所以第一个做法就是每次找到代价最小的点，走过去。
这样复杂度是 \(O(n^2)\) 的，考虑优化。
由于代价不好计算，但是我们只需要找到代价减少的那一个，我们考虑对于代价求导，算出每个节点对应的代价变化率，而这个变化率是可以简单判断的，而且计算变化率只需要考虑子树内部的点即可，此时走一步就是 \(O(n)\) 的了。
然后我们要减少步数，点分治即可。
CF1221G Graph And Numbers
\(2^3\) 容斥，然后有一个独立集计数的部分，暴搜+记忆化是 \(O(2^\frac n 2)\) 的。
CF325E The Red Button
CF1453F Even Harder
CF582D Number of Binominal Coefficients
考虑库莫尔定理，\(v_p(\binom {a+b} a)\) 恰好为在 \(p\) 进制下进位的次数，然后简单从高到滴数位 dp 即可，\(f_{i,j,0/1,0/1}\) 表示考虑到第 \(i\) 位，进位 \(j\) 次，是否达到上界，下一位是否给这一位进位。
CF1569F Palindromic Hamiltonian Path
暴搜出匹配长什么样，这个是 \(\frac 1 {(n/2)!}\binom n {n/2}\)，然后枚举全排列判断行不行，暴搜每个串的形态，这个是贝尔数。
CF193D Two Segments
从值域上考虑，计算对于对于当前的 \(r\)，每个 \(l\) 形成的连续段数量，线段树维护。
CF1625E2 Cats on the Upgrade (hard version)
建出括号序列树，然后就简单 DS 维护了。
LOJ547 「LibreOJ β Round #7」匹配字符串
标签：11,le,frac,val,记录,sum,然后,做题,binom From： https://www.cnblogs.com/Nityacke/p/18535974