【考试总结】2022-03-07
分裂
我使用一种调整法通过了本题，而事实证明，这样子的调整法跑得快，正确率也是非常高
具体而言，先求出来最大的 \(x\) 满足 \(x!\le n\)，这时候有的球的数量是 \(x!\)，调整分为两个局面
对于 \(\text{球数}< n\) 的局面，随机一个权值 \(x\) 并让它变为 \(x+1\)，消耗 \(x\) 现有的数量或者使得总球数不少于 \(n\)
对于 \(\text{球数}> n\) 的局面，随机一个权值 \(x\) 并让它变为 \(x-1\)，消耗 \(x\) 现有的数量或者使得总球数不大于 \(n\)
Code Display
mt19937_64 Rand(260823);
inline int random(int l,int r){return Rand()%(r-l+1)+l;}
bool f[5010][5010];
int g[5010][5010];
int ton[400010];
signed main(){
freopen("split.in","r",stdin); freopen("split.out","w",stdout);
f[1][1]=g[1][1]=1;
for(int i=1;i<5000;++i){
for(int j=1;j<=5000;++j) if(f[i][j]){
for(int k=1;k<=g[i][j];++k){
int nxt=j-k+k*(i+1);
if(nxt>5000) break;
f[i+1][nxt]=1; ckmax(g[i+1][nxt],k*(i+1));
}
}
}
int T=read(); while(T--){
int n=read();
int d=1,fac=1;
while(fac<=n/d) fac*=d,++d;
if(fac==n){
puts("1");
print(d-1); print(n); putchar('\n');
}else if(n<=5000){
vector > ans;
for(int i=5000;i>=1;--i) if(f[i][n]){
int ni=i,nj=n,Go=0;
while(ni){
if(g[ni][nj]!=Go) ans.emplace_back(ni,g[ni][nj]-Go);
Go=g[ni][nj]/ni;
nj=nj+Go-g[ni][nj];
--ni;
}
break;
}
if(ans.size()){
print(ans.size()); putchar('\n');
for(auto t:ans) print(t.fir),print(t.sec),putchar('\n');
}else puts("-1");
}else{
ton[d-1]=fac;
int sum=fac;
set now; now.insert(d-1);
while(sum!=n){
int Del=-1,ins=-1;
if(sumt){
if(random(0,4)){
int Mxd=min(1+(sum-n)/(t-1),ton[t]/t);
ton[t]-=t*Mxd;
ton[t-1]+=Mxd;
if(ton[t-1]) ins=t-1;
sum-=Mxd*(t-1);
if(!ton[t]) Del=t;
break;
}
}
}
if(~Del) now.erase(Del);
if(~ins) now.insert(ins);
}
print(now.size()); putchar('\n');
for(auto t:now) print(t),print(ton[t]),putchar('\n'),ton[t]=0;
}
}
return 0;
}
未来
将 \(r\) 视为 \(0\)，\(g\) 视为 \(1\)，\(b\) 视为 \(2\)，那么一次操作可以表示为将 \(a_i\) 变成 \(3-(a_i+a_{i+1})\mod 3\)
这样子就可以考虑每个 \(i\) 向 \(j\) 的贡献了，如果 \(a_i\) 向 \(a_j(j
由于是在 \(\mod 3\) 意义下进行计算，那么就对于 \(\binom{3^i}{k},k\neq 0,3^i\) 结果都是 \(0\)，可以忽略这些贡献
那么将 \(m\) 进行三进制分解，每次扫描走 \(3^i\) 带来的贡献即可
时间复杂度 \(\Theta(n\log m)\)
Code Display
const int N=5e5+10;
int a[2][N],n,m;
inline int encode(char s){
if(s=='r') return 1;
else if(s=='g') return 0;
else return 2;
}
inline char decode(int s){
if(!s) return 'g';
else if(s==1) return 'r';
else return 'b';
}
char s[N];
signed main(){
freopen("future.in","r",stdin); freopen("future.out","w",stdout);
n=read(); m=read(); scanf("%s",s);
int cur=0;
rep(i,0,n-1) a[cur][i]=encode(s[i]);
while(m){
int stp=1;
while(stp<=m/3) stp*=3;
while(m>=stp){
rep(i,0,n-1) a[cur^1][i]=3-(a[cur][i]+a[cur][(i+stp)%n]),a[cur^1][i]=(a[cur^1][i]%3+3)%3;
cur^=1;
m-=stp;
}
}
rep(i,0,n-1) putchar(decode(a[cur][i]));
putchar('\n');
return 0;
}
回忆
强调数据范围 \(n\times m\le 40\)，那么 \(\min(n,m)\le 6\)，令 \(m\) 为较小的一维
设 \(f_{i,S,s_1,s_2,s_3,\max}\) 表示到了完成了前 \(i\) 行的统计，最后一行的状态是 \(S\)，最后一行可能产生的至多 \(3\) 个联通块大小为 \(s_1,s_2,s_3\)，历史联通块最值是 \(\max\) 的概率
这里状态表示成 \(m\) 位 \(4\) 进制数字，\(0/1/2\) 表示属于联通块在最小表示法意义下的标号，而 \(3\) 不连通
转移枚举 \(i+1\) 行的所有状态，暴力合并得到新的最小表示法即可，使用 std::map 维护后 \(4\) 维，状态数其实是很小的，可以通过
Code Display
const int N=50;
int a[N][N],n,m,b[N][N];
map,int> dp[N][4100];
inline vector decode(int S){
vector res={0};
for(int i=1;i<=m;++i) res.push_back(S%4),S/=4;
return res;
}
inline int encode(vector S){
int res=0,bas=1;
for(auto t:S) res+=bas*t,bas<<=2;
return res;
}
struct DSU{
int fa[20],siz[N];
inline void init(int n){rep(i,1,2*m) siz[i]=i>m,fa[i]=i;}
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void merge(int x,int y){
x=find(x); y=find(y); if(x==y) return ;
fa[x]=y; siz[y]+=siz[x];
return ;
}
}T;
signed main(){
freopen("memory.in","r",stdin); freopen("memory.out","w",stdout);
n=read(); m=read(); rep(i,1,n) rep(j,1,m) a[i][j]=read();
if(m>n){
rep(i,1,n) rep(j,1,m) b[j][i]=a[i][j];
memset(a,0,sizeof(a));
swap(n,m);
rep(i,1,n) rep(j,1,m) a[i][j]=b[i][j];
}
dp[0][encode(vector(m,3))][{0,0,0,0}]=1;
int S=1<>(j-1)&1) ava[j]=1,ckmul(per,a[lin+1][j]);
else ckmul(per,del(1,a[lin+1][j]));
}
if(!per) continue;
for(int st=0;st ar=decode(st);
for(auto t:dp[lin][st]){
int s[3]={},his; tie(s[0],s[1],s[2],his)=t.fir;
T.init(2*m);
int lst[3]={-1,-1,-1};
for(int e=1;e<=m;++e) if(ar[e]!=3){
if(~lst[ar[e]]) T.merge(e,lst[ar[e]]);
lst[ar[e]]=e;
}
for(int e=1;e<=m;++e) if(ar[e]!=3) T.siz[T.find(e)]=s[ar[e]];
map id;
for(int e=1;e<=m;++e) if(ava[e]){
if(ar[e]!=3) T.merge(e+m,e);
if(ava[e-1]) T.merge(e-1+m,e+m);
if(ava[e+1]) T.merge(e+1+m,e+m);
}
int ndcnt=0,ns[3]={};
for(int e=1;e<=m;++e) if(ava[e]&&!id.count(T.find(e+m))){
ns[ndcnt]=T.siz[T.find(e+m)];
id[T.find(e+m)]=ndcnt++;
ckmax(his,T.siz[T.find(e+m)]);
}
vector New_st;
for(int e=1;e<=m;++e){
if(!ava[e]) New_st.emplace_back(3);
else New_st.emplace_back(id[T.find(e+m)]);
}
ckadd(dp[lin+1][encode(New_st)][{ns[0],ns[1],ns[2],his}],mul(t.sec,per));
}
}
}
}
int ans=0;
for(int i=0;i