昨天考完月考，明天初赛，dcoi2017级今天终于开始停课准备noip了，大概没有比本弱校停课更晚的学校了吧。本来就够菜了，怕是要凉透哦。
DAY1
T1石头剪刀布
据说爆搜随便做，但是我觉得我的O（输出）的时间复杂度还是蛮优秀的。
游戏图画出来是一颗完全二叉树，发现如果知道了根的0,1,2情况和树的高度，不区分左右儿子的情况下可以确定出整棵树。dp求出f[i][j][0/1/2]分别表示高度为i，根为j的这种树中叶子里0,1,2的个数，这样根据输入的0,1,2的个数就可以找到这棵树了。
然后就是要字典序最小，这样知道了根和高度的树的形态可以唯一确定下来，同样用dp,g[i][0/1/2]表示高度为i的树中，字典序排名为0.1.2的树是根为多少的，rak[i][0/1/2]表示高度为i的根为0.1.2的树在高度为i的树中的排名。
有了g就可以写个递归函数直接输出答案了。
1 //Achen
2 #include<bits/stdc++.h>
3 #define For(i,a,b) for(int i=(a);i<=(b);i++)
4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
5 #define Formylove return 0
6 typedef long long LL;
7 typedef double db;
8 using namespace std;
9 int f[25][3][3],g[25][3],rak[25][3];
10 int a,b,c,n,l;
11
12 template<typename T>void read(T &x) {
13 char ch=getchar(); T f=1; x=0;
14 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
15 if(ch=='-') f=-1,ch=getchar();
16 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
17 }
18
19 int calc(int i,int j) {
20 if(i>j) swap(i,j);
21 if(i==0&&j==1) return 1;
22 if(i==1&&j==2) return 2;
23 if(i==0&&j==2) return 0;
24 }
25
26 void print(int h,int top) {
27 if(!h) {
28 if(top==0) printf("R");
29 if(top==1) printf("P");
30 if(top==2) printf("S");
31 return;
32 }
33 if(top==0) {
34 if(rak[h-1][0]<rak[h-1][2]) { print(h-1,0); print(h-1,2); }
35 else { print(h-1,2); print(h-1,0); }
36 }
37 else if(top==1) {
38 if(rak[h-1][0]<rak[h-1][1]) { print(h-1,0); print(h-1,1); }
39 else { print(h-1,1); print(h-1,0); }
40 }
41 else if(top==2) {
42 if(rak[h-1][1]<rak[h-1][2]) { print(h-1,1); print(h-1,2); }
43 else { print(h-1,2); print(h-1,1); }
44 }
45 }
46
47 #define ANS
48 int main() {
49 #ifdef ANS
50 freopen("rps.in","r",stdin);
51 freopen("rps.out","w",stdout);
52 #endif
53 read(a); read(b); read(c);
54 f[0][0][0]=1;
55 f[0][1][1]=1;
56 f[0][2][2]=1;
57 For(i,1,20) {
58 For(j,0,2) {
59 f[i][1][j]=f[i-1][1][j]+f[i-1][0][j];
60 f[i][0][j]=f[i-1][0][j]+f[i-1][2][j];
61 f[i][2][j]=f[i-1][2][j]+f[i-1][1][j];
62 }
63 }
64 g[0][0]=1; rak[0][0]=1;
65 g[0][1]=0; rak[0][1]=0;
66 g[0][2]=2; rak[0][2]=2;
67 For(h,1,20) {
68 g[h][0]=calc(g[h-1][0],g[h-1][1]);
69 g[h][1]=calc(g[h-1][0],g[h-1][2]);
70 g[h][2]=calc(g[h-1][1],g[h-1][2]);
71 rak[h][g[h][0]]=0;
72 rak[h][g[h][1]]=1;
73 rak[h][g[h][2]]=2;
74 }
75 n=1; l=0;
76 while(n<a+b+c) {
77 n<<=1; l++;
78 }
79 int ok=0;
80 For(i,0,2) if(f[l][i][0]==a&&f[l][i][1]==b&&f[l][i][2]==c) {
81 ok=1;
82 print(l,i); puts("");
83 }
84 if(!ok) puts("IMPOSSIBLE");
85 Formylove;
86 }
T1投票
如果知道了哪些人参与了投票，n^2dp随便做。
其实结论应该很套路了，但是我还是太蠢没有想到，如果是llj应该可以秒这题的。
结论就是参与投票的一定是pi最小的一部分加pi最大的一部分人。
反证，如果一个人i参与了投票，一个p比他大的人和一个p比它小的人都没参加投票，在其他投票人确定的情况下，最后答案是关于pi的一个一次函数，那么pi变小或者变大一定有一个能使函数值变大，即这种情况不合法。
1 //Achen
2 #include<bits/stdc++.h>
3 #define For(i,a,b) for(int i=(a);i<=(b);i++)
4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
5 #define Formylove return 0
6 const int N=2005;
7 typedef long long LL;
8 typedef double db;
9 using namespace std;
10 int n,k,sta[N];
11 db f[N][N],g[N][N],p[N],ans;
12
13 template<typename T>void read(T &x) {
14 char ch=getchar(); T f=1; x=0;
15 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
16 if(ch=='-') f=-1,ch=getchar();
17 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
18 }
19
20 #define ANS
21 int main() {
22 #ifdef ANS
23 freopen("vote.in","r",stdin);
24 freopen("vote.out","w",stdout);
25 #endif
26 read(n); read(k);
27 For(i,1,n) scanf("%lf",&p[i]);
28 sort(p+1,p+n+1);
29 f[0][0]=1.0;
30 For(i,1,n) {
31 f[i][0]=f[i-1][0]*(1.0-p[i]);
32 For(j,1,min(i,k/2))
33 f[i][j]=f[i-1][j-1]*p[i]+f[i-1][j]*(1.0-p[i]);
34 }
35 For(i,1,n) if(i<n-i+1) swap(p[i],p[n-i+1]);
36 g[0][0]=1.0;
37 For(i,1,n) {
38 g[i][0]=g[i-1][0]*(1.0-p[i]);
39 For(j,1,min(i,k/2))
40 g[i][j]=g[i-1][j-1]*p[i]+g[i-1][j]*(1.0-p[i]);
41 }
42 For(i,0,k) {
43 db tp=0.0;
44 For(j,0,k/2)
45 tp+=f[i][j]*g[k-i][k/2-j];
46 ans=max(ans,tp);
47 }
48 printf("%lf
",ans);
49 Formylove;
50 }
T3.工厂
我觉得这个题蛮好的。虽然我不会。
转化为一个二分图，然后我结论猜错了，瞎猜了个只要每个联通块构成回路就可以，事实上是每个联通块都是完全图才可以。
证明，题目要求转换为二分图的任意一个极大匹配都是完美匹配。显然首先不同联通块互不影响且每个联通块左右点数相等。考虑每个左右点数相等的联通块，反证，如果左边的a与右边的b没有连边，且满足任意极大匹配为完美匹配，那么找到任意一条从a到b的路径，当选择从a到b的所有奇数边时，再选一些其它边构成的极大匹配是完美匹配，即所有点都在匹配上。当选择a到b的所有偶数边，而其它边不变时，除了a、b以外的点都在匹配上，即不存在增广路（增广路，从未匹配点开始到未匹配点结束的路径，而未匹配点只有a,b），即构成了一个非完美匹配的极大匹配，矛盾，得证。
现在问题转换为，有若干个联通块，把它们划分成若干集合，每个集合的左边的点数和等于右边的点数和，使所有集合的左边点数和的平方之和最小，答案就为这个最小值减去已有的边。
发现本质不同的联通块很少（据题解所说状态最多只有172032），考虑状压dp。但是我对状压dp的理解太肤浅，发现要枚举子集，然后判断左右点是否相等，这个很不好转移。
但是题解告诉我，再开一维，f[s][i]表示s中选出了一些集合Σx=i的答案，如果s满足条件，这些集合满足条件，那么就可以用s中剩下的元素的x的和的平方的代价来转移到整个s。
也就是说，我想从一个s转移到一个s',很好办，先只管s不管i，从f[s][i]转移到所有包含s的s'的f[s'][i]，到s'那里再考虑是否可以合法地构成一个新集合，就从f[s'][i]转移到f[s'][sums']。
llj说这个叫我自己转移到我自己。这题让我想起了之前做的两道题，按理说其实会了那两道也就该会这道题了，但是当时对状压的理解比现在还肤浅，于是我很开心地又去做了一下。
一道是这个兴奋剂检查，和这道题的状态压缩方式是一样的，当时我还不懂为什么可以这样压，抄的题解，而且都写得好蠢。。用这道题的写法就优美多了。
另一道是这个学校食堂，是我做的第一道我自己转移到我自己的状压。不知道我当时的近百行丑陋转移是怎么写出来了。。。看来我还是进步了那么一丢丢的。
1 //Achen
2 #include<bits/stdc++.h>
3 #define For(i,a,b) for(int i=(a);i<=(b);i++)
4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
5 #define Formylove return 0
6 const int N=1007,up=256;
7 typedef long long LL;
8 typedef double db;
9 using namespace std;
10 int T,n,f[N][up][20],t[N],b[N],ans;
11
12 template<typename T>void read(T &x) {
13 char ch=getchar(); T f=1; x=0;
14 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
15 if(ch=='-') f=-1,ch=getchar();
16 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
17 }
18
19 int ck(int st,int s,int p) {
20 if(st+p>n||(s&(1<<p))) return 0;
21 For(i,0,p-1) if(!(s&(1<<i))&&b[st+i]<p-i)
22 return 0;
23 return 1;
24 }
25
26 void GM(int &x,int y) { if(x>y) x=y; }
27
28 //#define ANS
29 int main() {
30 #ifdef ANS
31 freopen("1.in","r",stdin);
32 //freopen("1.out","w",stdout);
33 #endif
34 read(T);
35 while(T--) {
36 read(n);
37 For(i,1,n) {
38 read(t[i]); read(b[i]);
39 }
40 memset(f,127/3,sizeof(f));
41 int inf=f[0][0][0];
42 ans=inf;
43 For(i,0,7) if(ck(1,0,i)) f[1][1<<i][i]=0;
44 For(i,1,n) For(s,0,up-1) For(j,0,14) if(f[i][s][j]!=inf) {
45 For(p,0,7) if(ck(i,s,p)) {
46 int pr=j<=7?i+j:i-(j-7);
47 int cost=(t[pr]|t[i+p])-(t[pr]&t[i+p]);
48 GM(f[i][s|(1<<p)][p],f[i][s][j]+cost);
49 }
50 For(p,0,7) if(!(s&(1<<p))) {
51 int pp=(j>=p?j-p:7+(p-j));
52 GM(f[i+p][s>>p][pp],f[i][s][j]);
53 break;
54 }
55 }
56 For(i,0,14) GM(ans,f[n+1][0][i]);
57 printf("%d
",ans);
58 }
59 Formylove;
60 }
1 //Achen
2 #include<bits/stdc++.h>
3 #define For(i,a,b) for(int i=(a);i<=(b);i++)
4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
5 #define Formylove return 0
6 const int N=5100007;
7 typedef long long LL;
8 typedef double db;
9 using namespace std;
10 int n,m,f[N],up[10],b[210],a[210][10],w[10],ans;
11
12 template<typename T>void read(T &x) {
13 char ch=getchar(); T f=1; x=0;
14 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
15 if(ch=='-') f=-1,ch=getchar();
16 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
17 }
18
19 void GM(int &a,int b) { if(a<b) a=b; }
20
21 //#define ANS
22 int main() {
23 #ifdef ANS
24 freopen("1.in","r",stdin);
25 //freopen("1.out","w",stdout);
26 #endif
27 read(n); read(m);
28 For(i,1,m) read(up[i]);
29 w[0]=1;
30 For(i,1,m) w[i]=w[i-1]*(up[i]+1);
31 For(i,1,n) {
32 read(b[i]);
33 For(j,1,m) read(a[i][j]);
34 }
35 For(i,1,n) {
36 Rep(s,w[m]-1,0) {
37 int ss=s,fl=1;
38 For(j,1,m) {
39 if(s%w[j]/w[j-1]+a[i][j]<=up[j]) ss+=a[i][j]*w[j-1];
40 else fl=0;
41 }
42 if(fl) GM(f[ss],f[s]+b[i]);
43 }
44 }
45 For(s,0,w[m]-1) GM(ans,f[s]);
46 printf("%d
",ans);
47 Formylove;
48 }
1 //Achen
2 #include<bits/stdc++.h>
3 #define For(i,a,b) for(int i=(a);i<=(b);i++)
4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
5 #define Formylove return 0
6 const int N=35,M=2e5;
7 typedef long long LL;
8 typedef double db;
9 using namespace std;
10 int n,w[M],f[M][N],tpans;
11 char s[N];
12
13 template<typename T>void read(T &x) {
14 char ch=getchar(); T f=1; x=0;
15 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
16 if(ch=='-') f=-1,ch=getchar();
17 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
18 }
19
20 #define pr pair<int,int>
21 #define MP make_pair
22 #define fi first
23 #define se second
24 pr operator + (const pr &A,const pr &B) { return MP(A.fi+B.fi,A.se+B.se); }
25 pr operator *(const pr &A,const int &B) { return MP(A.fi*B,A.se*B); }
26
27 pr sz[N*2],S[M];
28 int fa[N*2],cnt[M],m;
29 int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); }
30 int pf(int x) { return x*x; }
31
32 void GM(int &x,int y) { if(x>y) x=y; }
33
34 #define ANS
35 int main() {
36 #ifdef ANS
37 freopen("factory.in","r",stdin);
38 freopen("factory.out","w",stdout);
39 #endif
40 read(n);
41 For(i,1,n+n) fa[i]=i;
42 For(i,1,n) sz[i]=MP(1,0);
43 For(i,n+1,n+n) sz[i]=MP(0,1);
44 For(i,1,n) {
45 scanf("%s",s+1);
46 For(j,1,n) if(s[j]=='1') {
47 tpans++;
48 int x=find(i),y=find(n+j);
49 if(x!=y) {
50 sz[x]=sz[x]+sz[y];
51 fa[y]=x;
52 }
53 }
54 }
55 For(i,1,n+n) if(find(i)==i)
56 S[++m]=sz[i];
57 sort(S+1,S+m+1);
58 int tpm=m; m=0;
59 For(i,1,tpm) {
60 if(!m||S[m]!=S[i]) { S[++m]=S[i]; cnt[m]=1; }
61 else cnt[m]++;
62 }
63 w[0]=1;
64 For(i,1,m) w[i]=w[i-1]*(cnt[i]+1);
65 For(s,0,w[m]-1) For(i,0,n) f[s][i]=(i==0?0:n*n);
66 For(s,0,w[m]-1) {
67 pr now=MP(0,0);
68 For(i,1,m) now=now+S[i]*(s%w[i]/w[i-1]);
69 if(now.fi==now.se) {
70 For(i,0,now.fi-1)
71 GM(f[s][now.fi],f[s][i]+pf(now.fi-i));
72 }
73 For(i,1,m) if(s%w[i]/w[i-1]<cnt[i]) {
74 For(j,0,n)
75 GM(f[s+w[i-1]][j],f[s][j]);
76 }
77 }
78 int ans=f[w[m]-1][n]-tpans;
79 printf("%d
",ans);
80 Formylove;
81 }
DAY2
T1wzoi
好久没做过贪心题了。。。
连续的00，11就消掉价值为10，那么每一坨1和0如果是奇数个就有剩的，剩下这样的00101011001010
把其中相邻的00,11再消掉价值还是10，剩下的01或者10价值就是5。
1 //Achen
2 #include<bits/stdc++.h>
3 #define For(i,a,b) for(int i=(a);i<=(b);i++)
4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
5 #define Formylove return 0
6 const int N=1e6+7;
7 typedef long long LL;
8 typedef double db;
9 using namespace std;
10 int n,now,cnt,cc,ans;
11 char s[N];
12
13 template<typename T>void read(T &x) {
14 char ch=getchar(); T f=1; x=0;
15 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
16 if(ch=='-') f=-1,ch=getchar();
17 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
18 }
19
20 #define ANS
21 int main() {
22 #ifdef ANS
23 freopen("wzoi.in","r",stdin);
24 freopen("wzoi.out","w",stdout);
25 #endif
26 scanf("%s",s);
27 n=strlen(s);
28 For(i,0,n-1) {
29 int c=s[i]-'0';
30 if(i==0||s[i]!=s[i-1]) cc=1;
31 else { ans+=cc*10; cc^=1;}
32 if((i==n-1||s[i+1]!=s[i])&&cc) {
33 if(cnt==0||c!=now) { cnt++; now=c; }
34 else if(c==now) { cnt--; now^=1; ans+=10; }
35 }
36 }
37 ans+=cnt/2*5;
38 printf("%d
",ans);
39 Formylove;
40 }
T2课程
精度误差允许范围让人浮想联翩，随机化的提示不要太明显。然而我并不会随机化。
暴力就是枚举所有可能的顺序看有没有出现讨厌的单词，那么考虑从所有可能的序列中随机出一部分来算。题解说当顺机10000个序列的时候精度就够了ORZ。
当然不能随便随机了，发现每次对于一片森林，每个根作为拓扑序的下一个点的概率跟子树大小成正比（证明感觉和之前雅礼那道期望题有点像）。即使这么告诉我这样我还是不知道怎么随机2333，std告诉我每次随机一个未选择的点如果有父亲就沿着父亲跳就好了，学到了。
//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=107;
typedef long long LL;
typedef double db;
using namespace std;
int n,fa[N],len[N],m;
char s[N],a[N][25],p[N];
db ans;
template<typename T>void read(T &x) {
char ch=getchar(); T f=1; x=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') f=-1,ch=getchar();
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}
int cmp(int x) {
For(i,1,n-len[x]+1) {
For(j,0,len[x]-1) {
if(p[i+j]!=a[x][j]) break;
if(j==len[x]-1) return 1;
}
}
return 0;
}
int vis[N];
void solve() {
For(cs,1,10000) {
For(i,1,n) vis[i]=0;
vis[0]=1;
For(pos,1,n) {
int x=rand()%(n-pos+1)+1,i;
for(i=1;i<=n;i++) if(!vis[i]) {
x--; if(!x) break;
}
while(!vis[fa[i]]) i=fa[i];
vis[i]=1;
p[pos]=s[i];
}
int fl=1;
For(i,1,m) if(cmp(i)) fl=0;
if(fl) ans+=1.0;
}
}
#define ANS
int main() {
#ifdef ANS
freopen("course.in","r",stdin);
freopen("course.out","w",stdout);
#endif
read(n);
For(i,1,n) read(fa[i]);
scanf("%s",s+1);
read(m);
For(i,1,m) {
scanf("%s",a[i]);
len[i]=strlen(a[i]);
}
solve();
printf("%lf
",ans/10000);
Formylove;
}
T3画
这题好神啊，框框画出来跑完dijkstra我就不知道该怎么做了。哪位大佬会做教教我吧QAQ。