一次比一次差是要闹哪样啊，次次都看错题什么状态啊，下次是不是就爆零了啊......
可能是最近知识学得太快了吧，什么都来不及深究就马上考试or进入下一个专题，做题也仅限于学长讲过的（没讲过的直接死亡（某数位dp））
集训还有10天，不知不觉过去这么长时间了，我承认最近确实有点浮躁，做题总是静不下心
再这样可能真的要退役了吧（笑），可是我不想啊
所以接下来努力吧，尽管努力并不一定有回报，但不尝试又怎么知道结果呢
以上
T1：建设城市（city）
和之前一道考试题很像啊......但是数据强了很多，然而我还是只会打n^2暴力，加上特判总共获(pian)得(dao)了70pts
正解很明显的容斥啊......考试时候总想着需要枚举每个人而不敢打容斥（其实对每个人的枚举合并就能得到一个非常简单的柿子了）
考完才发现对每个人的枚举是一样的，也就是说只需要枚举重合的人就好了
全集是c(m-1,n-1)，容斥掉有超过k的，枚举超过的天数，对于天数i，超过i天的方案即为C(n,i)*C(m-i*k-1,n-1)(把)
容斥一发，奇减偶加就好了
#include<bits/stdc++.h> #define int long long #define cri const register int #define re register using namespace std; const int mod=998244353; int jie[10000010],ni[10000010]; inline int c(cri x,cri y){ if(x<y||x<0||y<0) return 0; return 1ll*jie[x]*ni[y]%mod*ni[x-y]%mod; } inline int qpow(int a,int b){ int ans=1; for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ans=1ll*ans*a%mod; return ans; } signed main(){ int n,m,k,ans; scanf("%lld%lld%lld",&n,&m,&k); if(n>m||m>1ll*n*k){ puts("0"); return 0; } jie[0]=1; for(int i=1;i<=m;i++) jie[i]=1ll*jie[i-1]*i%mod; ni[m]=qpow(jie[m],mod-2); for(int i=m;i>=1;i--) ni[i-1]=1ll*ni[i]*i%mod; ans=c(m-1,n-1); //cout<<ans<<endl; for(int i=1,j=-1;i<=m;i++,j=-j) ans=(ans+1ll*j*c(n,i)*c(m-i*k-1,n-1)%mod+mod)%mod; printf("%lld",ans); }
T2：轰炸行动（bomb）
全场最水，然而半个机房由于看错题喜提10分的好成绩
仔细看题我们发现在一条链上的两两都不能同时轰炸，一个强联通分量上的同理
然后我们建图，tarjan，拓扑就好了
#include<bits/stdc++.h> #define ll long long #define cri const register int #define re register using namespace std; int num,cnt,dcc,fa[1000010],to[2000010],la[2000010],bl[1000010]; int dfn[1000010],low[1000010],sta[1000010],top,size[1000010],fr[1000010]; inline void add(cri x,cri y){ to[++cnt]=y; fr[cnt]=x; la[cnt]=fa[x]; fa[x]=cnt; } int tos[1000010],las[1000010],cnts,du[1000010],dp[1000010],v[1000010]; inline void adds(cri x,cri y){ tos[++cnts]=y; las[cnts]=fa[x]; fa[x]=cnts; } void tarjan(cri x){ dfn[x]=low[x]=++num; sta[++top]=x;v[x]=1; for(int i=fa[x];i;i=la[i]) if(!dfn[to[i]]){ tarjan(to[i]); low[x]=min(low[to[i]],low[x]); } else if(v[to[i]])low[x]=min(low[x],dfn[to[i]]); if(low[x]==dfn[x]){ int y;dcc++; do{ y=sta[top--]; bl[y]=dcc; size[dcc]++; v[y]=0; }while(y!=x); //puts(""); } } signed main(){ int n,m,x,y,ans=0; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&x,&y); add(x,y); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); memset(fa,0,sizeof fa); for(int i=1;i<=cnt;i++) if(bl[to[i]]!=bl[fr[i]]) adds(bl[fr[i]],bl[to[i]]),du[bl[to[i]]]++; queue<int>q; for(int i=1;i<=dcc;i++) if(!du[i]) q.push(i); while(!q.empty()){ x=q.front();q.pop(); dp[x]+=size[x]; ans=max(ans,dp[x]); for(int i=fa[x];i;i=las[i]){ du[tos[i]]--; dp[tos[i]]=max(dp[tos[i]],dp[x]); if(!du[tos[i]]) q.push(tos[i]); } } printf("%d",ans); }
T3：石头剪刀布（rps）
神dp，考场上一度以为是np完全不可做（现在我也这么认为），打了骗分想骗20然而只弄到10分
由于我们根本无法完全分析出最优决策，模拟or考虑顺序绝对吃屎
我们思考有没有方法可以不考虑对手的顺序，于是我们得到了这样的dp定义：dp[i][j][k][now]表示出现了i个石头，j个剪刀，k个布，下一次出now的概率
等等怎么想到的？发生了什么？（反正我想不到啊喂）
但dp数组显然无法直接转移，我们考虑辅助数组g[i][j][k]，表示出现了i个石头，j个剪刀，k个布的概率
显然有g[i][j][k]+=g[i-1][j][k]*r[t]+g[i][j-1][k]*s[t]+g[i][j][k-1]*p[t]
f数组也有相似转移，即
f[i][j][k][l]+=f[i-1][j][k][l]*r[t]+f[i][j-1][k][l]*s[t]+f[i][j][k-1]*p[t]+g[i][j][k]*(r[t]+s[t]+p[t])
复杂度O(n^4)
#include<bits/stdc++.h> #define ll long long #define cri const register int #define crs const register short #define re register using namespace std; int n; long double ans,f[55][55][55][5],sjb[4][55],c[55][55]; signed main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%Lf%Lf%Lf",&sjb[1][i],&sjb[3][i],&sjb[2][i]); for(int j=1;j<=3;j++) sjb[j][i]/=300; } c[0][0]=1; for(int i=1;i<=n;i++){ c[i][0]=1; for(int j=1;j<=i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1]; } f[0][0][0][0]=1; for(int t=1;t<=n;t++) for(int i=t;i>=0;i--) for(int j=t-i;j>=0;j--) for(int k=t-i-j;k>=0;k--) for(int now=(t==i+j+k?0:3);now>=0;now--){ f[i][j][k][now]+=(i?f[i-1][j][k][now]:0)*sjb[1][t]+(j?f[i][j-1][k][now]:0)*sjb[2][t]+(k?f[i][j][k-1][now]:0)*sjb[3][t]; if(now) f[i][j][k][now]+=f[i][j][k][0]*sjb[now][t]; } for(int i=0;i<n;i++) for(int j=0;j+i<n;j++) for(int k=0;i+j+k<n;k++) ans+=max(f[i][j][k][1]+f[i][j][k][2]*3,max(f[i][j][k][2]+f[i][j][k][3]*3,f[i][j][k][3]+f[i][j][k][1]*3))/(c[n][i+j+k]*c[n-i-j-k][1]); printf("%.15Lf",ans); }