昨天考完月考，明天初赛，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
      
        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
       
        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]
       
      

 

T1投票

如果知道了哪些人参与了投票，n^2dp随便做。

其实结论应该很套路了，但是我还是太蠢没有想到，如果是llj应该可以秒这题的。

结论就是参与投票的一定是pi最小的一部分加pi最大的一部分人。

反证，如果一个人i参与了投票，一个p比他大的人和一个p比它小的人都没参加投票，在其他投票人确定的情况下，最后答案是关于pi的一个一次函数，那么pi变小或者变大一定有一个能使函数值变大，即这种情况不合法。

1 //Achen 2 #include
      
        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
       
        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 ANS21 int main() {22 #ifdef ANS23     freopen("vote.in","r",stdin);24     freopen("vote.out","w",stdout);25 #endif26     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
       
      

 

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
      
        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
       
        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<
        
         y) x=y; }27 28 //#define ANS29 int main() {30 #ifdef ANS31     freopen("1.in","r",stdin);32     //freopen("1.out","w",stdout);33 #endif34     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<
         
          =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\n",ans);58     }59     Formylove;60 }
         
        
       
      

1 //Achen 2 #include
      
        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
       
        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
       
      

1 //Achen 2 #include
      
        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
       
        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
        
         21 #define MP make_pair22 #define fi first23 #define se second24 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 ANS35 int main() {36 #ifdef ANS37     freopen("factory.in","r",stdin);38     freopen("factory.out","w",stdout);39 #endif40     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]
        
       
      

 

DAY2

T1wzoi

好久没做过贪心题了。。。

连续的00，11就消掉价值为10，那么每一坨1和0如果是奇数个就有剩的，剩下这样的00101011001010

把其中相邻的00,11再消掉价值还是10，剩下的01或者10价值就是5。

1 //Achen 2 #include
      
        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
       
        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 ANS21 int main() {22 #ifdef ANS23     freopen("wzoi.in","r",stdin);24     freopen("wzoi.out","w",stdout);25 #endif26     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\n",ans);39     Formylove;40 }
       
      

 

T2课程

精度误差允许范围让人浮想联翩，随机化的提示不要太明显。然而我并不会随机化。

暴力就是枚举所有可能的顺序看有没有出现讨厌的单词，那么考虑从所有可能的序列中随机出一部分来算。题解说当顺机10000个序列的时候精度就够了ORZ。

当然不能随便随机了，发现每次对于一片森林，每个根作为拓扑序的下一个点的概率跟子树大小成正比（证明感觉和之前雅礼那道期望题有点像）。即使这么告诉我这样我还是不知道怎么随机2333，std告诉我每次随机一个未选择的点如果有父亲就沿着父亲跳就好了，学到了。

//Achen#include
      
       #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 0const 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
       
        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 ANSint 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\n",ans/10000);    Formylove;}
       
      

 

T3画

这题好神啊，框框画出来跑完dijkstra我就不知道该怎么做了。哪位大佬会做教教我吧QAQ。