2020-team1-paste
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
mianyang a
#include<bits/stdc++.h>
using namespace std;
int T,n,m,k;
vector<vector<char> > ans;
int xs[111111],ys[111111],xt[111111],yt[111111],c[111111];
void gao(int lx,int rx,int ly,int ry)
{
if(lx>rx||ly>ry)return;
int nn=rx-lx+1,mm=ry-ly+1;
if((nn%2==0&&mm%2!=0)||(nn%2==0&&mm%2==0&&nn>mm))
{
for(int i=lx;i<=rx;i++)
{
int j=ly;
if((i-lx+1)%4==1)ans[i][j]='D',j++;
if((i-lx+1)%4==2)ans[i][j]='U',j++;
for(;j<ry;j+=2)
{
ans[i][j]='R';
ans[i][j+1]='L';
}
if(j==ry)
{
if((i-lx+1)%2==1)ans[i][j]='D',j++;
if((i-lx+1)%2==2)ans[i][j]='U',j++;
}
}
}
else
{
for(int i=ly;i<=ry;i++)
{
int j=lx;
if((i-ly+1)%4==1)ans[j][i]='R',j++;
if((i-ly+1)%4==2)ans[j][i]='L',j++;
for(;j<rx;j+=2)
{
ans[j][i]='D';
ans[j+1][i]='U';
}
if(j==rx)
{
if((i-ly+1)%2==1)ans[j][i]='R',j++;
if((i-ly+1)%2==2)ans[j][i]='L',j++;
}
}
}
}
int cnt[111111],cut[111111],scut[111111];
int minr[111111];
int solve()
{
if(n%2==0)
{
for(int i=1;i<=k;i++)
{
if(c[i]==0)continue;
int l=ys[i],r=yt[i];
if(l>r)swap(l,r);
cnt[l]++;cnt[r]--;
}
for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
for(int i=1;i<=k;i++)
{
if(c[i]==1)continue;
int l=ys[i],r=yt[i];
if(l>r)swap(l,r);
minr[l]=min(minr[l],r-1);
}
for(int i=m;i>=1;i--)
{
minr[i]=min(minr[i+1],minr[i]);
}
for(int i=1;i<=m;i++)
{
}
}
else
{
for(int i=1;i<=m;i++)cnt[i]=cut[i]=0;
for(int i=1;i<=k;i++)
{
if(c[i]==0)continue;
int l=ys[i],r=yt[i];
if(l>r)swap(l,r);
cnt[l]++;cnt[r]--;
}
for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
for(int i=1;i<=m;i+=2)
{
if(cnt[i]==0)
cut[i]=1;
}
for(int i=1;i<=m;i++)
scut[i]=scut[i-1]+cut[i];
for(int i=1;i<=k;i++)
{
if(c[i]==1)continue;
int l=ys[i],r=yt[i];
if(l>r)swap(l,r);
if(cnt[r-1]-cnt[l-1]>0)
return false;
}
ans.resize(n+1);
for(int i=1;i<=n;i++)ans[i].resize(m+1);
int last=-1;
for(int j=1;j<=m;j++)
{
if(cut[j])
{
for(int i=1;i<=n;i++)
{
ans[i][j]='R';
ans[i][j+1]='L';
}
gao(1,n,last+2,j-1);
last=j;
}
}
gao(1,n,last+2,m);
return true;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin>>T;
for(int tt=1;tt<=T;tt++)
{
cin>>n>>m>>k;
for(int i=1;i<=k;i++)
{
cin>>xs[i]>>ys[i]>>xt[i]>>yt[i]>>c[i];
}
int rot=0,ok=0;
if(n==1||m==1)
{
if(m==1)rot=1,swap(n,m);
int fl=1;
for(int i=1;i<=k;i++)
{
if(rot)swap(xs[i],ys[i]),swap(xt[i],yt[i]);
if(ys[i]==yt[i]&&c[i]!=1)
{
fl=0;
break;
}
if(abs(ys[i]-yt[i])==1)
{
if(min(ys[i],yt[i])%2==1&&c[i]!=1)
{
fl=0;
break;
}
if(min(ys[i],yt[i])%2==0&&c[i]!=0)
{
fl=0;
break;
}
}
if(abs(ys[i]-yt[i])>1&&c[i]!=0)
{
fl=0;
break;
}
}
if(fl)
{
ok=1;
ans.resize(n+1);
for(int i=1;i<=n;i++)
{
ans[i].resize(m+1);
for(int j=1;j<=m;j++)
{
if(j%2==1)
ans[i][j]='R';
else
ans[i][j]='L';
}
}
}
}
else if(n==2||m==2)
{
if(m==2)rot=1,swap(n,m);
for(int i=1;i<=k;i++)
{
if(rot)swap(xs[i],ys[i]),swap(xt[i],yt[i]);
}
int fl=1;
for(int i=1;i<=k;i++)
{
if(xs[i]==xt[i]&&i!=1)
{
fl=0;
break;
}
if(xs[i]!=xt[i]&&i!=0)
{
fl=0;
break;
}
}
if(fl)
{
ok=1;
ans.resize(n+1);
for(int i=1;i<=n;i++)
{
ans[i].resize(m+1);
for(int j=1;j<=m;j++)
{
if(i%2==1)
ans[i][j]='D';
else
ans[i][j]='U';
}
}
}
else
{
ok=solve();
for(int i=1;i<=n;i++)
if(ans[1][i]!='D')
ok=0;
}
}
else
{
ok=solve();
if(!ok)
{
rot=1;
for(int i=1;i<=k;i++)
swap(xs[i],ys[i]),swap(xt[i],yt[i]);
ok=solve();
}
}
cout<<"Case #"<<tt<<": ";
if(ok)
{
cout<<"Yes"<<endl;
if(rot)
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(ans[j][i]=='U')
cout<<'L';
else if(ans[j][i]=='D')
cout<<'R';
else if(ans[j][i]=='L')
cout<<'U';
else
cout<<'D';
}
cout<<endl;
}
}
else
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<ans[i][j];
cout<<endl;
}
}
}
else cout<<"No"<<endl;
}
return 0;
}
tianti c3
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=998244353,MOD2=998244353,SHIFT=184992124;
int n,m;
int a[233],gcd[111][111];
long long dp[111][111][111][2],pwm[233];
long long solve(const vector<int> &vec,int len)
{
// cerr<<"solve "<<len;
// for(auto x:vec)cerr<<" "<<x;cerr<<endl;
int L=vec.size();
dp[0][0][0][0]=1;
for(int i=1;i<L;i++)
{
memset(dp[i],0,sizeof(dp[i]));
int pos=vec[i];
for(int j=0;j<pos;j++)//last
{
for(int k=0;k<=100;k++)//gcd
{
for(int l=0;l<=1;l++)
{
dp[i][j][k][l]+=dp[i-1][j][k][l];
dp[i][j][k][l]%=MOD;
if(j==0)
{
dp[i][pos][k][l]+=(dp[i-1][j][k][l^1]*pwm[pos-1])%MOD;
dp[i][pos][k][l]%=MOD;
}
else if(pos>=j+len)
{
dp[i][pos][k][l]+=(dp[i-1][j][k][l^1]*pwm[pos-j-len])%MOD;
dp[i][pos][k][l]%=MOD;
}
else if(k==0)
{
dp[i][pos][pos-j][l]+=dp[i-1][j][k][l^1];
dp[i][pos][pos-j][l]%=MOD;
}
else
{
dp[i][pos][gcd[pos-j][k]][l]+=dp[i-1][j][k][l^1];
dp[i][pos][gcd[pos-j][k]][l]%=MOD;
}
}
}
}
}
long long ret=0;
for(int j=1;j+len-1<=n;j++)
{
for(int k=0;k<=100;k++)
{
ret+=(dp[L-1][j][k][1]-dp[L-1][j][k][0]+MOD)%MOD*pwm[k==0?len:k]%MOD*pwm[n-(j+len-1)]%MOD;
}
}
// cerr<<"ret="<<(ret%MOD)<<endl;
return ret%MOD;
}
long long hs[111][111];
int vis[111];
signed main()
{
ios_base::sync_with_stdio(false);
for(int i=1;i<=100;i++)for(int j=1;j<=100;j++)gcd[i][j]=__gcd(i,j);
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
pwm[0]=1;
for(int i=1;i<=n;i++)
cin>>a[i],pwm[i]=pwm[i-1]*m%MOD;
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
hs[i][j]=(hs[i][j-1]*SHIFT+a[j])%MOD2;
}
}
long long ans=0;
for(int len=1;len<=n;len++)
{
memset(vis,0,sizeof(vis));
for(int i=1;i+len-1<=n;i++)
{
if(!vis[i])
{
vector<int> vec;
vec.push_back(0);
vec.push_back(i),vis[i]=1;
for(int j=i+1;j+len-1<=n;j++)
if(hs[i][i+len-1]==hs[j][j+len-1])
vec.push_back(j),vis[j]=1;
ans+=solve(vec,len);
}
}
}
cout<<(ans%MOD+MOD)%MOD;
if(T!=0)cout<<endl;
}
return 0;
}mianyang a
#include
using namespace std;
int T,n,m,k;
vector
int xs[111111],ys[111111],xt[111111],yt[111111],c[111111];
void gao(int lx,int rx,int ly,int ry)
{
if(lx>rx||ly>ry)return;
int nn=rx-lx+1,mm=ry-ly+1;
if((nn%2==0&&mm%2!=0)||(nn%2==0&&mm%2==0&&nn>mm))
{
for(int i=lx;i<=rx;i++)
{
int j=ly;
if((i-lx+1)%4==1)ans[i][j]='D',j++;
if((i-lx+1)%4==2)ans[i][j]='U',j++;
for(;j { ans[i][j]='R'; ans[i][j+1]='L'; } if(j==ry) { if((i-lx+1)%2==1)ans[i][j]='D',j++; if((i-lx+1)%2==2)ans[i][j]='U',j++; } } } else { for(int i=ly;i<=ry;i++) { int j=lx; if((i-ly+1)%4==1)ans[j][i]='R',j++; if((i-ly+1)%4==2)ans[j][i]='L',j++; for(;j { ans[j][i]='D'; ans[j+1][i]='U'; } if(j==rx) { if((i-ly+1)%2==1)ans[j][i]='R',j++; if((i-ly+1)%2==2)ans[j][i]='L',j++; } } } } int cnt[111111],cut[111111],scut[111111]; int minr[111111]; int solve() { if(n%2==0) { for(int i=1;i<=k;i++) { if(c[i]==0)continue; int l=ys[i],r=yt[i]; if(l>r)swap(l,r); cnt[l]++;cnt[r]--; } for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1]; for(int i=1;i<=k;i++) { if(c[i]==1)continue; int l=ys[i],r=yt[i]; if(l>r)swap(l,r); minr[l]=min(minr[l],r-1); } for(int i=m;i>=1;i--) { minr[i]=min(minr[i+1],minr[i]); } for(int i=1;i<=m;i++) { } } else { for(int i=1;i<=m;i++)cnt[i]=cut[i]=0; for(int i=1;i<=k;i++) { if(c[i]==0)continue; int l=ys[i],r=yt[i]; if(l>r)swap(l,r); cnt[l]++;cnt[r]--; } for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1]; for(int i=1;i<=m;i+=2) { if(cnt[i]==0) cut[i]=1; } for(int i=1;i<=m;i++) scut[i]=scut[i-1]+cut[i]; for(int i=1;i<=k;i++) { if(c[i]==1)continue; int l=ys[i],r=yt[i]; if(l>r)swap(l,r); if(cnt[r-1]-cnt[l-1]>0) return false; } ans.resize(n+1); for(int i=1;i<=n;i++)ans[i].resize(m+1); int last=-1; for(int j=1;j<=m;j++) { if(cut[j]) { for(int i=1;i<=n;i++) { ans[i][j]='R'; ans[i][j+1]='L'; } gao(1,n,last+2,j-1); last=j; } } gao(1,n,last+2,m); return true; } } int main() { ios_base::sync_with_stdio(false); cin>>T; for(int tt=1;tt<=T;tt++) { cin>>n>>m>>k; for(int i=1;i<=k;i++) { cin>>xs[i]>>ys[i]>>xt[i]>>yt[i]>>c[i]; } int rot=0,ok=0; if(n==1||m==1) { if(m==1)rot=1,swap(n,m); int fl=1; for(int i=1;i<=k;i++) { if(rot)swap(xs[i],ys[i]),swap(xt[i],yt[i]); if(ys[i]==yt[i]&&c[i]!=1) { fl=0; break; } if(abs(ys[i]-yt[i])==1) { if(min(ys[i],yt[i])%2==1&&c[i]!=1) { fl=0; break; } if(min(ys[i],yt[i])%2==0&&c[i]!=0) { fl=0; break; } } if(abs(ys[i]-yt[i])>1&&c[i]!=0) { fl=0; break; } } if(fl) { ok=1; ans.resize(n+1); for(int i=1;i<=n;i++) { ans[i].resize(m+1); for(int j=1;j<=m;j++) { if(j%2==1) ans[i][j]='R'; else ans[i][j]='L'; } } } } else if(n==2||m==2) { if(m==2)rot=1,swap(n,m); for(int i=1;i<=k;i++) { if(rot)swap(xs[i],ys[i]),swap(xt[i],yt[i]); } int fl=1; for(int i=1;i<=k;i++) { if(xs[i]==xt[i]&&i!=1) { fl=0; break; } if(xs[i]!=xt[i]&&i!=0) { fl=0; break; } } if(fl) { ok=1; ans.resize(n+1); for(int i=1;i<=n;i++) { ans[i].resize(m+1); for(int j=1;j<=m;j++) { if(i%2==1) ans[i][j]='D'; else ans[i][j]='U'; } } } else { ok=solve(); for(int i=1;i<=n;i++) if(ans[1][i]!='D') ok=0; } } else { ok=solve(); if(!ok) { rot=1; for(int i=1;i<=k;i++) swap(xs[i],ys[i]),swap(xt[i],yt[i]); ok=solve(); } } cout<<"Case #"< if(ok) { cout<<"Yes"< if(rot) { for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(ans[j][i]=='U') cout<<'L'; else if(ans[j][i]=='D') cout<<'R'; else if(ans[j][i]=='L') cout<<'U'; else cout<<'D'; } cout< } } else { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) cout< cout< } } } else cout<<"No"< } return 0; } tianti c3 #include using namespace std; #define int long long const int MOD=998244353,MOD2=998244353,SHIFT=184992124; int n,m; int a[233],gcd[111][111]; long long dp[111][111][111][2],pwm[233]; long long solve(const vector { // cerr<<"solve "< // for(auto x:vec)cerr<<" "< int L=vec.size(); dp[0][0][0][0]=1; for(int i=1;i { memset(dp[i],0,sizeof(dp[i])); int pos=vec[i]; for(int j=0;j { for(int k=0;k<=100;k++)//gcd { for(int l=0;l<=1;l++) { dp[i][j][k][l]+=dp[i-1][j][k][l]; dp[i][j][k][l]%=MOD; if(j==0) { dp[i][pos][k][l]+=(dp[i-1][j][k][l^1]*pwm[pos-1])%MOD; dp[i][pos][k][l]%=MOD; } else if(pos>=j+len) { dp[i][pos][k][l]+=(dp[i-1][j][k][l^1]*pwm[pos-j-len])%MOD; dp[i][pos][k][l]%=MOD; } else if(k==0) { dp[i][pos][pos-j][l]+=dp[i-1][j][k][l^1]; dp[i][pos][pos-j][l]%=MOD; } else { dp[i][pos][gcd[pos-j][k]][l]+=dp[i-1][j][k][l^1]; dp[i][pos][gcd[pos-j][k]][l]%=MOD; } } } } } long long ret=0; for(int j=1;j+len-1<=n;j++) { for(int k=0;k<=100;k++) { ret+=(dp[L-1][j][k][1]-dp[L-1][j][k][0]+MOD)%MOD*pwm[k==0?len:k]%MOD*pwm[n-(j+len-1)]%MOD; } } // cerr<<"ret="<<(ret%MOD)< return ret%MOD; } long long hs[111][111]; int vis[111]; signed main() { ios_base::sync_with_stdio(false); for(int i=1;i<=100;i++)for(int j=1;j<=100;j++)gcd[i][j]=__gcd(i,j); int T; cin>>T; while(T--) { cin>>n>>m; pwm[0]=1; for(int i=1;i<=n;i++) cin>>a[i],pwm[i]=pwm[i-1]*m%MOD; for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) { hs[i][j]=(hs[i][j-1]*SHIFT+a[j])%MOD2; } } long long ans=0; for(int len=1;len<=n;len++) { memset(vis,0,sizeof(vis)); for(int i=1;i+len-1<=n;i++) { if(!vis[i]) { vector vec.push_back(0); vec.push_back(i),vis[i]=1; for(int j=i+1;j+len-1<=n;j++) if(hs[i][i+len-1]==hs[j][j+len-1]) vec.push_back(j),vis[j]=1; ans+=solve(vec,len); } } } cout<<(ans%MOD+MOD)%MOD; if(T!=0)cout< } return 0; }
附加文件
- problems-e.pdf by mengbierr