Preface
抛开整个八月完全没写代码不谈，就 CF 来说感觉已经有一万年没打了
由于 NJU CS 预推免有机试，想着恢复下手感就现场打了这场，没想到 2h Div1 能出四题
看来摆烂确实有助于水平提高啊，这下不得不多摆烂会了
A. Against the Difference
直接 DP，令 \(f_i\) 表示前 \(i\) 个位置的答案，钦定 \(f_i\) 不降
转移的话就是找到最靠右的位置 \(j\)，满足 \([j,i]\) 中当前的数 \(a_i\) 出现次数恰为 \(a_i\) 次，拿个 vector 随便维护即可
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,a[N],f[N],num[N]; vector <int> pos[N];
int main()
{for (scanf("%d",&t);t;--t){scanf("%d",&n);for (RI i=1;i<=n;++i) pos[i].clear();for (RI i=1;i<=n;++i){scanf("%d",&a[i]);pos[a[i]].push_back(i);num[i]=(int)pos[a[i]].size();}for (RI i=1;i<=n;++i){f[i]=f[i-1];if (num[i]<a[i]) continue;f[i]=max(f[i],f[pos[a[i]][num[i]-a[i]]-1]+a[i]);}printf("%d\n",f[n]);}return 0;
}
B. For the Champion
思博题
考虑先用 4 次操作，即 \(x,y\) 各加两次 \(10^9\)，把当前位置移动到所有点的右上方，此时可以列出关于 \(X+Y\) 的一个方程
然后再用 4 次操作，即将 \(y\) 减去四次 \(10^9\)，把当前位置移动到所有点的右下方，此时可以列出关于 \(X-Y\) 的一个方程
联立即可得到 \(X,Y\) 的值
#include<cstdio>
#include<iostream>
#include<vector>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=105,LEN=1e9;
int t,n;
signed main()
{for (scanf("%lld",&t);t;--t){scanf("%lld",&n);int xpy_max=-1e18,ymx_min=1e18;for (RI i=1;i<=n;++i){int x,y; scanf("%lld%lld",&x,&y);xpy_max=max(xpy_max,x+y);ymx_min=min(ymx_min,y-x);}int tmp,A,B;printf("? R %lld\n",LEN);fflush(stdout); scanf("%lld",&tmp);printf("? R %lld\n",LEN);fflush(stdout); scanf("%lld",&tmp);printf("? U %lld\n",LEN);fflush(stdout); scanf("%lld",&tmp);printf("? U %lld\n",LEN);fflush(stdout); scanf("%lld",&A);printf("? D %lld\n",LEN);fflush(stdout); scanf("%lld",&tmp);printf("? D %lld\n",LEN);fflush(stdout); scanf("%lld",&tmp);printf("? D %lld\n",LEN);fflush(stdout); scanf("%lld",&tmp);printf("? D %lld\n",LEN);fflush(stdout); scanf("%lld",&B);A=A+xpy_max-4LL*LEN;B=B-ymx_min-4LL*LEN;int X=(A+B)/2,Y=(A-B)/2;printf("! %lld %lld\n",X,Y); fflush(stdout);}return 0;
}
C. By the Assignment
感觉很套路的一个题啊
简单手玩一下会发现题目的限制等价于：偶环上所有数都相同，奇环上所有数都必须为 \(0\)
因此可以考虑用并查集维护所有值一样的点以及它们对应的值
具体实现时，可以先求出原图的 DFS 生成树，此时所有非树边都是返祖边
加入一条非树边时，相当于将对应两点树上路径上的所有点连成一个集合，钦定并查集连边的方向后直接暴力的复杂度就是对的（因为最多合并 \(O(n)\) 次）
判掉无解的情况后，最后答案就是 \(V\) 的未确定的集合数量次方
当然这题也能用点双+染色来写，但感觉不如这种方法简单好写
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,mod=998244353;
int t,n,m,V,vis[N],dep[N],anc[N],fa[N],val[N],flag;
vector <int> v[N]; vector <pair <int,int>> E;
inline void DFS(CI now,CI lst=-1)
{vis[now]=1;for (auto to:v[now]){if (vis[to]){if (to!=lst) E.push_back({now,to});continue;}anc[to]=now;dep[to]=dep[now]+1;DFS(to,now);}
}
inline int getfa(CI x)
{return x!=fa[x]?fa[x]=getfa(fa[x]):x;
}
inline int merge(CI a,CI b)
{if (a==-1&&b==-1) return -1;if (a==-1&&b!=-1) return b;if (a!=-1&&b==-1) return a;if (a==b) return a; else return flag=0,-1;
}
inline void link(int x,int y)
{x=getfa(x); y=getfa(y);fa[x]=y; val[y]=merge(val[x],val[y]);
}
int main()
{for (scanf("%d",&t);t;--t){scanf("%d%d%d",&n,&m,&V);for (RI i=1;i<=n;++i){scanf("%d",&val[i]);v[i].clear(); vis[i]=0;}for (RI i=1;i<=m;++i){int x,y; scanf("%d%d",&x,&y);v[x].push_back(y); v[y].push_back(x);}E.clear(); dep[1]=1; DFS(1); flag=1;for (RI i=1;i<=n;++i) fa[i]=i;for (auto [x,y]:E){int dlt=dep[y]-dep[x];while (getfa(x)!=getfa(y)){x=getfa(x);link(x,anc[x]);}if (dlt%2==0) val[getfa(y)]=merge(val[getfa(y)],0);}if (!flag) { puts("0"); continue; }int ans=1;for (RI i=1;i<=n;++i) vis[i]=0;for (RI i=1;i<=n;++i){int x=getfa(i);if (vis[x]) continue;vis[x]=1;if (val[x]==-1) ans=1LL*ans*V%mod;}printf("%d\n",ans);}return 0;
}
D1. From the Unknown (Easy Version)
挺有意思的一个题，D1 感觉还是很好想的
考虑先问 \(n\) 个 \(1\)，根据回答我们一定可以确定答案的一个可能范围 \(W\in [L,R]\)
通过打表不难发现 \(2L\ge R\) 始终成立，因此我们可以用如下方法进行第二次询问
\[L,1,L,2,L,3,\dots,L,R-L-1,L,R-L
\]
不难发现一定存在一个分界点 \((L,M)\)，使得它之前的相邻一对数分为一组，它之后的所有数单独分组
因此我们可以用 \(2\times (R-L)\) 的长度唯一确定 \(W\)，最坏情况 \(L=50000,R=99999\)，符合长度限制
#include<cstdio>
#include<iostream>
#include<vector>
#include<assert.h>
#define RI register int
#define CI const int&
using namespace std;
const int N=100000;
int t;
int main()
{/*int mxd=0,ml,mr;for (RI k=2;k<=100000;++k){int L=(n+k-1)/k,R=n/(k-1);while (R>=L&&(n+R-1)/R!=k) --R;if (L>R) continue;assert(2*L>=R);if (R-L>mxd) mxd=R-L,ml=L,mr=R;}printf("%d %d\n",ml,mr);*/for (scanf("%d",&t);t;--t){printf("? %d ",N);for (RI i=1;i<=N;++i)printf("1%c"," \n"[i==N]);fflush(stdout);int k; scanf("%d",&k);if (k==1){printf("! %d\n",N); fflush(stdout);continue;}int L=(N+k-1)/k,R=N/(k-1);while (R>=L&&(N+R-1)/R!=k) --R;if (L==R){printf("! %d\n",L); fflush(stdout);continue;}printf("? %d ",2*(R-L));for (RI i=R-L;i>=1;--i)printf("%d %d%c",L,i," \n"[i==1]);fflush(stdout); scanf("%d",&k);printf("! %d\n",R-(k-(R-L))); fflush(stdout);}return 0;
}
D2. From the Unknown (Hard Version)
其实比赛的时候 D2 的思路基本全出来了
但因为参数要写暴力找就偷懒没写（其实是太困了早早睡觉去了）
考虑第一次询问改为问 \(N\) 个 \(B\)，根据回答可以分为两种情况：
- 回答为 \(0\)，此时说明 \(W\in[1,B-1]\)，不难发现第二次问 \(B^2\) 个 \(1\) 就可以唯一确定 \(W\)；
- 回答不为 \(0\)，此时可以解出 \(W\in \displaystyle \left[B\cdot \left(\left\lfloor\frac{N - 1}{r} + 1\right\rfloor \right), B\cdot \left(\left\lfloor\frac{N - 1}{r - 1} + 1\right\rfloor \right) - 1\right]=[L,R]\)；
因此暴力枚举所有可能的 \(N,B\)，使得 \(N+\max(B^2,2\times (R-L))\) 的值最小即可
取 \(N=11343,B=116\) 得到最大询问长度为 \(24799\le 25000\)，可以通过
#include<cstdio>
#include<iostream>
#include<vector>
#include<assert.h>
#define RI register int
#define CI const int&
using namespace std;
const int N=11343,B=116;
int t;
int main()
{for (scanf("%d",&t);t;--t){printf("? %d ",N);for (RI i=1;i<=N;++i)printf("%d%c",B," \n"[i==N]);fflush(stdout);int k; scanf("%d",&k);if (k==0){printf("? %d ",B*B);for (RI i=1;i<=B*B;++i)printf("1%c"," \n"[i==B*B]);fflush(stdout); scanf("%d",&k);for (RI W=1;W<B;++W)if ((B*B+W-1)/W==k){printf("! %d\n",W); fflush(stdout);break;}} else{int L=-1,R=-1;for (RI W=B;W<=100000;++W)if ((N+(W/B)-1)/(W/B)==k){if (L==-1) L=W; R=W;}if (L==R){printf("! %d\n",L); fflush(stdout);continue;}printf("? %d ",2*(R-L));for (RI i=R-L;i>=1;--i)printf("%d %d%c",L,i," \n"[i==1]);fflush(stdout); scanf("%d",&k);printf("! %d\n",R-(k-(R-L))); fflush(stdout);}}return 0;
}
Postscript
最后事实证明打 CF 对 NJU 的机试也并没有什么太大的帮助