| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 100 | 68 | 32 | 30 | 230 | 8/25 |
A. 雷暴（storm）
对每种颜色记录最左/右/上/下即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m,kk;
int lf[maxn],rt[maxn],up[maxn],dw[maxn];
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m>>kk;memset(lf,0x3f,sizeof(lf));memset(up,0x3f,sizeof(up));for(int i=1,x;i<=n;i++){for(int j=1;j<=m;j++){cin>>x;lf[x]=min(lf[x],j),rt[x]=max(rt[x],j);up[x]=min(up[x],i),dw[x]=max(dw[x],i);}}for(int i=1;i<=kk;i++){if(!rt[i]){cout<<0<<'\n';}else{int t=max(dw[i]-up[i]+1,rt[i]-lf[i]+1);cout<<t*t<<'\n';}}return 0;
}
}
int main(){return asbt::main();}
B. 神力 (god)
不得不写写我考场上的做法了。
首先考虑一个 DP：\(f_{i,j}\) 表示到第 \(i\) 步走到了 \(j\) 的概率，于是转移是显然的。但是我们发现这样会算重，因为如果在第 \(i\) 步到了 \(j\)，那么在第 \(k>i\) 步到 \(j\) 的概率就不应该算入了。于是我们再定义 \(g_{i,j,k}\) 表示第 \(i\) 步在 \(0\)，第 \(j\) 步在 \(k\) 的概率。于是我们可以统计答案，但是是 \(O(n^3)\) 的。拼几个特殊性质可以得 \(68pts\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int mod=1e9+7;
il int pls(int x,int y){return x+y<mod?x+y:x+y-mod;
}
il void add(int &x,int y){x=pls(x,y);
}
il int sub(int x,int y){return x<y?x-y+mod:x-y;
}
il void mns(int &x,int y){x=sub(x,y);
}
il int qpow(int x,int y=mod-2){int res=1;while(y){if(y&1){res=res*1ll*x%mod;}x=x*1ll*x%mod,y>>=1;}return res;
}
int n,p,q,a[5005],b[10005],g[305][305][605],f[305][605];
int C[5005][5005],pp[5005],qq[5005];
il bool chk1(){for(int i=1;i<=n;i++){if(a[i]==1){return 0;}}return 1;
}
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n>>p;for(int i=1;i<=n;i++){cin>>a[i];}if(p==100){for(int i=1;i<=n;i++){cout<<0<<' ';}cout<<1<<' ';for(int i=1;i<=n;i++){cout<<0<<' ';}return 0;}if(p==0){int cur=n+1;b[n+1]=1;for(int i=1;i<=n;i++){cur+=a[i];b[cur]=1;}for(int i=1;i<=2*n+1;i++){cout<<b[i]<<' ';}return 0;}p=p*1ll*qpow(100)%mod,q=(1-p+mod)%mod;if(chk1()){for(int i=0;i<=n;i++){C[i][0]=1;for(int j=1;j<=i;j++){C[i][j]=pls(C[i-1][j-1],C[i-1][j]);}}pp[0]=qq[0]=1;for(int i=1;i<=n;i++){pp[i]=pp[i-1]*1ll*p%mod;qq[i]=qq[i-1]*1ll*q%mod;}for(int i=n;i;i--){int ans=0;for(int j=i;j<=n;j++){ans=(C[j-1][i-1]*1ll*pp[j-i]%mod*qq[i]+ans)%mod;}cout<<ans<<' ';}cout<<1<<' ';for(int i=1;i<=n;i++){cout<<0<<' ';}return 0;}for(int i=0;i<=n;i++){g[i][i][n+1]=1;for(int j=i+1;j<=n;j++){for(int k=1;k<=2*n+1;k++){g[i][j][k]=(g[i][j-1][k]*1ll*p+g[i][j-1][k-a[j]]*1ll*q)%mod;}}}f[0][n+1]=1;for(int i=1;i<=n;i++){for(int j=1;j<=2*n+1;j++){f[i][j]=(f[i-1][j]*1ll*p+f[i-1][j-a[i]]*1ll*q)%mod;}}for(int i=1;i<=2*n+1;i++){int ans=0;for(int j=0;j<=n;j++){for(int k=0;k<j;k++){mns(f[j][i],f[k][i]*1ll*g[k][j][n+1]%mod);}add(ans,f[j][i]);}cout<<ans<<' ';}return 0;
}
}
int main(){return asbt::main();}
考虑正解，我们发现那个 \(f\) 的 DP 不好统计答案的原因就是前面的操作会影响后面，这提示我们倒过来 DP。设 \(f_{i,j}\) 表示经过后 \(i\) 个操作走到了离原点距离为 \(j\) 的概率。此时唯一受影响的就是 \(j=0\) 的情况，强制令 \(f_{i,0}=1\) 即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=5e3+5,mod=1e9+7;
il int pls(int x,int y){return x+y<mod?x+y:x+y-mod;
}
il void add(int &x,int y){x=pls(x,y);
}
il int sub(int x,int y){return x<y?x-y+mod:x-y;
}
il void mns(int &x,int y){x=sub(x,y);
}
il int qpow(int x,int y=mod-2){int res=1;while(y){if(y&1){res=res*1ll*x%mod;}x=x*1ll*x%mod,y>>=1;}return res;
}
int n,p,q,a[maxn],f[maxn][maxn<<1];
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n>>p;p=p*1ll*qpow(100)%mod,q=sub(1,p);for(int i=1;i<=n;i++){cin>>a[i];}f[n+1][n+1]=1;for(int i=n;i;i--){for(int j=1;j<=2*n+1;j++){f[i][j]=(f[i+1][j]*1ll*p+f[i+1][j-a[i]]*1ll*q)%mod;}f[i][n+1]=1;}for(int i=1;i<=2*n+1;i++){cout<<f[1][i]<<' ';}return 0;
}
}
int main(){return asbt::main();}