今天迎来了WZZX的模拟。打开pdf的时候我特别震惊，出题的竟然是神仙KCZ！没错，就是那个活跃于各大OJ，在各大OJ排名靠前（LOJ Rank1），NOI2018 Rank16进队的kczno1！！！（无限膜拜%%%）
然而KCZ神仙出的题使我挂的特别惨……
T1.rps
期望得分100，实际得分30.
这道题一开始没看出来咋做，先去做后面的题了。
结果我整场基本都在拍第二题的期望DP，然后还没对orz。
大概剩了40分钟回来想这道题。发现，如果赢家确定了那么其实所有比赛的结果都被确定了，那么序列的大致情况我们就知道了。然后我自己画了几棵树，发现其实一场比赛参与的情况其实是成一个杨辉三角的……
好像有点奇怪，可以自己画几棵看一下，然后就会发现，如果你以这次的赢家为起点，三个一循环轮番转来转去，你就能确定在总人数=2^n的时候，合法的情况和对于合法情况每次的赢家是谁了。（不过好像没人这么做……可能我是个毒瘤吧orz）
然后我就自以为能做这道题了……然后我就贪心的输出字典序小的，写完的时候考试快结束了也没来得及再试几组数据，结果考试结束之后SZQ告诉我说这是错的……凉凉。
回来自己手画了几棵确实发现贪心是错的，然后自己画了大概1个点找规律，尝试了好多种情况还是没办法，于是就放弃了，学了一种更暴力的方法。
上面的思路没问题，就是我们可以先随便的把这个区间大致求出来。之后对其进行类似归并排序的操作，对于当前两个区间，暴力枚举第一个不一样的，如果有的话就暴力交换两个区间。
这样之后就可以过了……orz，暴力大法好啊……虽然说我写的莫名其妙特别慢，比别人的慢10倍，还是开了1.5s才跑过去的。
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<iostream> #include<queue> #include<set> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 100005; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } int r,p,s,n,maxn,cnt,f[50][50],g[50][3]; char h[1500000]; bool pd[1500000]; void cal() { f[1][1] = 1; rep(i,2,21) rep(j,1,i) f[i][j] = f[i-1][j] + f[i-1][j-1]; rep(i,1,n+1) { rep(j,1,i) { int k = j % 3; if(!k) k = 3; g[i][k] += f[i][j]; } } } void print(char c,int a) { if(a == n) { h[++cnt] = c; return; } if(c == 'S') print('P',a+1),print('S',a+1); if(c == 'P') print('P',a+1),print('R',a+1); if(c == 'R') print('S',a+1),print('R',a+1); } void solve() { if(r == g[n+1][1] && p == g[n+1][3] && s == g[n+1][2]) print('R',0); else if(r == g[n+1][3] && p == g[n+1][2] && s == g[n+1][1]) print('S',0); else if(s == g[n+1][3] && p == g[n+1][1] && r == g[n+1][2]) print('P',0); else { printf("IMPOSSIBLE "); return 0; } } void merge(int l,int r,int len) { if(len == 1) return; int mid = (l+r) >> 1; merge(l,mid,len>>1),merge(mid+1,r,len>>1); rep(i,l,mid) { if(h[i] <= h[mid-l+i+1]) continue; rep(j,l,mid) swap(h[j],h[mid-l+j+1]); return; } } int main() { // freopen("rps.in","r",stdin); // freopen("rps.out","w",stdout); r = read(),p = read(),s = read(); while(1<<n < r+p+s) n++; cal(),solve(); merge(1,cnt,cnt); rep(i,1,cnt) printf("%c",h[i]);enter; return 0; }
T2.vote
期望得分70，实际得分20.
这道题一开始感觉是个期望DP，然后自己写了转移方程，写上去之后发现数不对……然后改了改能把样例过了，不过一直不知道咋对拍有点慌……
然后出分了发现自己凉凉，莫名挂掉。然后这本来是一个O（n^3）的算法结果T了5个点orz。
看了题解发现真心巧妙。我们把所有人按照概率从小到大排序，可以证明一定取得是一段连续前缀和一段连续后缀。
我们假设有一个孩子，ta被选中了而ta的前后有人没被选中，我们能保证选择ta前后的人一定不劣。我们以两个人为例，其中一个是待选择的，其概率为p，另一个是已经选定的，概率为q，是一个常量。
这两个人对概率的贡献是f(p) = p * (1-q) + (1-p) * q,即f(p) = (1-2*q) * p + q,是一个关于p的一次函数，所以这个人移动到左或者右一定不劣，具体往哪边移就是斜率控制了。
然后我们只要进行从前向后和从后向前两次概率DP，然后每次计算对应两次积之和，取最大值即可。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<cstring> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') #define pr pair<int,int> #define mp make_pair #define fi first #define sc second using namespace std; typedef long long ll; const int M = 2005; const int N = 10000005; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >='0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } int n,k,m; double p[M],pre[M][M],suf[M][M],ans,cur; int main() { n = read(),k = read(); rep(i,1,n) scanf("%lf",&p[i]); sort(p+1,p+1+n); pre[0][0] = 1,suf[n+1][0] = 1; rep(i,1,n) { rep(j,1,n) pre[i][j] = p[i] * pre[i-1][j-1] + (1-p[i]) * pre[i-1][j]; pre[i][0] = (1-p[i]) * pre[i-1][0]; } per(i,n,1) { rep(j,1,n) suf[i][j] = p[i] * suf[i+1][j-1] + (1-p[i]) * suf[i+1][j]; suf[i][0] = (1-p[i]) * suf[i+1][0]; } m = k >> 1; rep(i,0,k) { cur = 0; rep(j,0,m) cur += pre[i][j] * suf[n+1+i-k][m-j]; ans = max(ans,cur); } printf("%.9lf ",ans); return 0; }
T3.factory
期望得分10，实际得分20。
这题我确实不会，看数据范围大概是网络流或者状压DP。我啥也不会就写了一个特判和一个求二分图补图的最大匹配，然后骗了20.
这题的题解我也确实没看懂……std是用C++11写的也没看明白……（话说为啥版本不同就感觉像换了个语言啊orz）
把题解抄在这里吧……
考虑问题的一个弱化版本:判断是否任意一个极大匹配都是完美匹配。 观察发现，任意一个极大匹配都是完美匹配(a) iff 任意一个联通块都是左右
点数相等的完全二分图(b)。
证明:
从b推出a是显然的，下面只用证明从a推出b。
反证法。
假设存在一张二分图，存在一个联通块不是左右点数相等的完全二分图， 同时满足任意一个极大匹配都是完美匹配。
如果这个联通块左右点数不相等，那么它就不存在完美匹配，显然矛盾。
否则这个联通块不是完全二分图，设左边的a点和右边的b点之间没有边， 随便找一条从a到b的简单路径，记作p。选择p上的奇数边，再随便选一些 边构造一个极大匹配，那么这个极大匹配必定是完美匹配。把奇数边改成 偶数边，其他的边不变，那么除了a,b以外的点都在匹配上，所以得到了一 个非完美匹配的极大匹配，矛盾。
Q.E.D.
std：
#include<bits/stdc++.h> using namespace std; template <typename T> void chmin(T &x,const T &y) { if(x>y)x=y; } typedef pair<int,int> pii; #define rep(i,l,r) for(int i=l;i<=r;++i) const int N=30+2,U=2e5; int n; char s[N][N]; int dp[U][N]; pii q[N*2];int m,cnt[N*2],w[N*2]; bool vis[N*2]; pii operator +(const pii &a,const pii &b) { return pii(a.first+b.first,a.second+b.second); } pii operator *(const pii &a,int x) { return pii(a.first*x,a.second*x); } void operator +=(pii &a,const pii &b) { a=a+b; } int sqr(int x) { return x*x; } int main() { freopen("factory.in","r",stdin);freopen("factory.out","w",stdout); scanf("%d",&n); rep(i,1,n)scanf("%s",s[i]+1); m=0; rep(i,1,n*2)vis[i]=0; rep(i,1,n*2) if(!vis[i]) { deque<int>nq; auto push=[&](int x) { if(!vis[x]){nq.push_back(x);vis[x]=1;} }; push(i); pii now=pii(0,0); while(!nq.empty()) { int x=nq.front();nq.pop_front(); if(x<=n) { ++now.first; rep(y,1,n) if(s[x][y]=='1')push(y+n); } else { ++now.second; rep(y,1,n) if(s[y][x-n]=='1')push(y); } } //cerr<<i<<" "<<now.first<<" "<<now.second<<endl; q[++m]=now; } sort(q+1,q+m+1); // rep(i,1,m)cerr<<q[i].first<<" "<<q[i].second<<endl; int m0=m;m=1; cnt[1]=1; rep(i,2,m0) { if(q[i]==q[m])++cnt[m]; else { q[++m]=q[i]; cnt[m]=1; } } // cerr<<m<<endl; // rep(i,1,m)cerr<<cnt[i]<<" ";cerr<<endl; // rep(i,1,m)cerr<<q[i].first<<" "<<q[i].second<<endl; w[1]=1; rep(i,2,m+1)w[i]=w[i-1]*(cnt[i-1]+1); rep(s,0,w[m+1]-1) rep(i,0,n)dp[s][i]=N*N; dp[0][0]=0; cerr<<w[m+1]<<endl; rep(s,0,w[m+1]-1) { pii sum=pii(0,0); rep(i,1,m)sum+=q[i]*(s%w[i+1]/w[i]); // cerr<<sum.first<<" "<<sum.second<<endl; if(sum.first==sum.second) { rep(i,0,sum.first-1)chmin(dp[s][sum.first],dp[s][i]+sqr(sum.first-i)); } rep(i,1,m) if(s%w[i+1]/w[i]<cnt[i]) rep(j,0,n)chmin(dp[s+w[i]][j],dp[s][j]); } int sum=0; rep(i,1,n) rep(j,1,n)sum+=s[i][j]=='1'; printf("%d ",dp[w[m+1]-1][n]-sum); }