发现写比赛题解是一种很好的发泄情绪的方式。
小贴士：比赛当天是国际 47 日，据说在这天 \(\bmod 47\) 会有大运发生。
97+30+25=152，rk17
A.共享单车
本题原题
这个数据赛时是 \(O(n^2)\) 可过的，还有神秘假做法，不过赛后加了 \(hack\) 卡掉了前者（没卡掉后者）。
显然想到我们可以写一个类似于 \(f_i\) 表示最新一个在 \(i\) 买的 \(dp\)，不过状态要复杂点：
- 由于有两类单车，所以要分成两类，同时对于当前为 \(C\) 的情况，两个都可以，所以还要再加一类
- 对于前两类，我们首先贪心地希望购买次数最少；在这个基础上，显然我们希望另一种单车的失效时间最晚，因此不需要再加状态了。
时间复杂度 \(O(n)\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e6+5;
int T,n,m,dp[N],fa[N],fb[N],ga[N],gb[N],nxa[N],nxb[N],nxc[N];
string s;
inline void prmax(int &a,int &b,int x,int y){if(y<b) a=x,b=y;else if(y==b) a=max(a,x);
}
inline void solve(){cin>>n>>m>>s;nxa[n]=nxb[n]=nxc[n]=n+1;for(int i=n-1;~i;i--){nxa[i]=(s[i]=='A'?i+1:nxa[i+1]);nxb[i]=(s[i]=='B'?i+1:nxb[i+1]);nxc[i]=(s[i]=='C'?i+1:nxc[i+1]);}for(int i=0;i<=n;i++) fa[i]=fb[i]=0,dp[i]=ga[i]=gb[i]=1e9;dp[0]=0;for(int i=0;i<n;i++){fa[i]=min(fa[i],n),fb[i]=min(fb[i],n);if(nxa[i]<=fa[i]) prmax(fb[fa[i]],gb[fa[i]],nxa[i]+m-1,ga[i]+1);else dp[fa[i]]=min(dp[fa[i]],ga[i]);if(nxb[i]<=fb[i]) prmax(fa[fb[i]],ga[fb[i]],nxb[i]+m-1,gb[i]+1);else dp[fb[i]]=min(dp[fb[i]],gb[i]);if(s[i]!='B') prmax(fb[i+1],gb[i+1],i+m,dp[i]+1);if(s[i]!='A') prmax(fa[i+1],ga[i+1],i+m,dp[i]+1);}cout<<min({dp[n],ga[n],gb[n]})<<"\n";
}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>T;while(T--) solve();return 0;
}
B.同余
原题 是本题时间限制的 2.5 倍，这是好的，避免了我们卡 25 分钟，但是没能避免我们卡 10 分钟。这就是单线程吗！
显然只需要考虑 \(m\in Prime\) 的情况。
考虑有没有能够不枚举质数个数就得到答案的方法。考虑对集合内的元素两两作差，对所有差值分解质因数（可以通过预处理做到 \(O(\omega)\)，即质因数种类数）。根据鸽笼原理，我们可以保证答案一定 \(\ge\dfrac{|S|}2\)，所以一种质数假如想要成为 \(m\)，他就必须出现 \(\ge\dfrac{|S|^2}4\) 次。而我们一共有 \(O(|S|^2\omega)\) 个质因数，所以我们只需要枚举 \(O(\omega)\) 个质数就可以了。单次时间复杂度 \(O(|S|\omega+|S|^2\omega)\)。
显然有一种思路是随机挑 \(O(|S|)\) 个数对进行统计，选取出现得最多的几个判断，就可以将时间复杂度降至 \(O(|S|\omega)\)。
但是由于是多组询问，随机算法在正确性和可拓展性上都难以为继，考虑寻找一种一定正确、可拓展性强的方法进行计算。一个经典 trick 是分组。我们考虑只计算所有的 \(|S_i-S_{i+1}|\) 和 \(|S_i-S_{i+2}|\)（\(S\) 不一定有序）。可以证明，可行的 \(p\) 出现次数一定 \(\ge\dfrac{|S|}4\)。因为假如一个 \(p\) 对应的答案 \(\ge\dfrac{|S|}2\)，那么我们无论如何安排这些数，他们在上述情况下都会出现至少 \(\dfrac{|S|}4\) 次，顶多差个极小的常数。此时，我们仍然可以保证时间复杂度是 \(O(|S|\omega)\)。
我们现在的目标是把 \(|S|\) 干掉。使用数据结构一类的东西维护显然是困难的，操作分块的话时间复杂度无法接受。考虑利用均摊的思想，让每次用 \(O(|S|\omega)\) 处理出的质数都可以用于处理 \(O(|S|)\) 次询问，这样均摊单次复杂度就是 \(O(\omega)\) 了。
我们每次让它向后处理 \(\dfrac{|S|}4\) 次询问，相应的，我们将 \(S\) 分成多个长为 \(6\) 的段，每个段内部两两配对。同理，我们可以证明可能的 \(p\) 都必须出现 \(\ge\dfrac{|S|}6\) 次。这样我们就能把时间复杂度均摊到 \(O(n+q\omega)\) 了。
第一次写的时候唐了，多写了个可删堆，所以在细节处存在一些神秘调参。
#include<bits/stdc++.h>
using namespace std;
char buf[1<<20],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
template<typename T>
inline void read(T &x){x=0;char c=getchar();bool fl=0;while(c>57||c<48) fl=(c=='-'),c=getchar();while(c>=48&&c<=57)x=(x<<1)+(x<<3)+c-48,c=getchar();x=(fl?-x:x);
}
template<typename T>
inline void write(T x){if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar(x%10+48);
}
const int V=1e7+5,N=1500005;
int n,q,ve[V][8],cnt,tp[V],pr[N],sk[N],tpc;
int vp[N],vc[V],gp[N],gpt,a[N],ans[N];
unordered_set<int>st;
bitset<V>vs;
struct erase_priority_queue{priority_queue<int>qa,qb;inline int size(){return qa.size()-qb.size();}inline void insert(int x){qa.push(x);}inline void erase(int x){qb.push(x);while(qb.size()&&qa.top()==qb.top()) qa.pop(),qb.pop();}inline int top(){return qa.size()?qa.top():0;}inline void clear(){while(qa.size()) qa.pop();while(qb.size()) qb.pop();}
}qc;
int main(){read(n),read(q);for(int i=2;i<=n;i++) if(!vs[i]){pr[++cnt]=i;for(int j=i;j<=n;j+=i) ve[j][tp[j]++]=cnt,vs[j]=1;}for(int i=1;i<=q;i++) read(a[i]);for(int id=1,jd=1;id<=q;id=jd+1){jd=min(q,id+(int)st.size()/4),tpc=gpt=0;for(int x:st) sk[++tpc]=x;for(int i=1;i<tpc;i++) for(int j=i+1;j<=min((i-1)/6*6+6,tpc);j++){int num=abs(sk[j]-sk[i]);for(int k=0;k<tp[num];k++){if(tpc/6<=3&&!vp[ve[num][k]]) gp[++gpt]=ve[num][k];vp[ve[num][k]]++;if(vp[ve[num][k]]==tpc/6-3) gp[++gpt]=ve[num][k];}}for(int i=1;i<tpc;i++) for(int j=i+1;j<=min((i-1)/6*6+6,tpc);j++){int num=abs(sk[j]-sk[i]);for(int k=0;k<tp[num];k++) vp[ve[num][k]]=0;}for(int pc=1;pc<=gpt;pc++){qc.clear();int p=pr[gp[pc]];for(int i=1;i<=tpc;i++){if(vc[sk[i]%p]) qc.erase(vc[sk[i]%p]);qc.insert(++vc[sk[i]%p]);}for(int i=id;i<=jd;i++){if(st.count(a[i])){st.erase(a[i]);qc.erase(vc[a[i]%p]--);if(vc[a[i]%p]) qc.insert(vc[a[i]%p]);}else{st.insert(a[i]);if(vc[a[i]%p]) qc.erase(vc[a[i]%p]);qc.insert(++vc[a[i]%p]);}ans[i]=max(ans[i],qc.top());if(pc==gpt){if(st.size()) ans[i]=max(ans[i],1);if(st.size()==2){int x=0,y=0;for(int nw:st) y=x,x=nw;if(x>y) swap(x,y);ans[i]=(y-x>1)+1;}}}if(pc<gpt) for(int i=jd;i>=id;i--){if(st.count(a[i])) st.erase(a[i]);else st.insert(a[i]);}for(int i=jd;i>=id;i--) vc[a[i]%p]=0;for(int i=1;i<=tpc;i++) vc[sk[i]%p]=0;}if(!gpt) for(int i=id;i<=jd;i++){if(st.count(a[i])) st.erase(a[i]);else st.insert(a[i]);if(st.size()) ans[i]=max(ans[i],1);if(st.size()==2){int x=0,y=0;for(int nw:st) y=x,x=nw;if(x>y) swap(x,y);ans[i]=(y-x>1)+1;}}}for(int i=1;i<=q;i++) write(ans[i]),putchar('\n');return 0;
}
C.交换
原题 一度只有整整 2 发 AC。
不在本人能力范围内，把 25 分暴力放在这里。
#include<bits/stdc++.h>
using namespace std;
const int N=55;
int n,m,p,ans,a[N];
int dp[N][1<<16];
inline void dfs(int x){if(x>n){ans++;return;}for(int i=0;i<(1<<m);i++){int fl=0;for(int j=1;j<x;j++) if(a[j]>i&&__builtin_popcount(a[j]^i)>1){fl=1;break;}if(!fl) a[x]=i,dfs(x+1);}
}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m>>p;if(m<=4){int num=1<<m;dp[0][0]=1;for(int id=1;id<=n;id++) for(int s=1;s<(1<<num);s++)for(int i=0;i<num;i++) if(s&(1<<i)){int fl=0;for(int j=i+1;j<num;j++)if((s&(1<<j))&&__builtin_popcount(i^j)>1) fl=1;if(!fl) dp[id][s]=(0ll+dp[id][s]+dp[id-1][s^(1<<i)]+dp[id-1][s])%p;}for(int s=0;s<(1<<num);s++) ans=(ans+dp[n][s])%p;}else dfs(1);cout<<ans;return 0;
}