NOIp2018集训test-10-6/test-10-7 (联考五day1/day2)

昨天考完月考，明天初赛，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就可以写个递归函数直接输出答案了。

 //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

 typedef long long LL;

 typedef double db;

 using namespace std;

 int f[][][],g[][],rak[][];

 int a,b,c,n,l;

 template<typename T>void read(T &x) {

     char ch=getchar(); T f=; x=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 int calc(int i,int j) {

     if(i>j) swap(i,j);

     if(i==&&j==) return ;

     if(i==&&j==) return ;

     if(i==&&j==) return ;

 }

 void print(int h,int top) {

     if(!h) {

         if(top==) printf("R");

         if(top==) printf("P");

         if(top==) printf("S");

         return;

     }

     if(top==) {

         if(rak[h-][]<rak[h-][]) { print(h-,); print(h-,); }

         else { print(h-,); print(h-,); }

     }

     else if(top==) {

         if(rak[h-][]<rak[h-][]) { print(h-,); print(h-,); }

         else { print(h-,); print(h-,); }

     }

     else if(top==) {

         if(rak[h-][]<rak[h-][]) { print(h-,); print(h-,); }

         else { print(h-,); print(h-,); }

     }

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("rps.in","r",stdin);

     freopen("rps.out","w",stdout);

 #endif

     read(a); read(b); read(c);

     f[][][]=;

     f[][][]=;

     f[][][]=;

     For(i,,) {

         For(j,,) {

             f[i][][j]=f[i-][][j]+f[i-][][j];

             f[i][][j]=f[i-][][j]+f[i-][][j];

             f[i][][j]=f[i-][][j]+f[i-][][j];

         }

     }

     g[][]=; rak[][]=;

     g[][]=; rak[][]=;

     g[][]=; rak[][]=;

     For(h,,) {

         g[h][]=calc(g[h-][],g[h-][]);

         g[h][]=calc(g[h-][],g[h-][]);

         g[h][]=calc(g[h-][],g[h-][]);

         rak[h][g[h][]]=;

         rak[h][g[h][]]=;

         rak[h][g[h][]]=;

     }

     n=; l=;

     while(n<a+b+c) {

         n<<=; l++;

     }

     int ok=;

     For(i,,) if(f[l][i][]==a&&f[l][i][]==b&&f[l][i][]==c) {

         ok=;

         print(l,i); puts("");

     }

     if(!ok) puts("IMPOSSIBLE");

     Formylove;

 }

T1投票

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

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

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

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

 //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=;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n,k,sta[N];

 db f[N][N],g[N][N],p[N],ans;

 template<typename T>void read(T &x) {

     char ch=getchar(); T f=; x=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("vote.in","r",stdin);

     freopen("vote.out","w",stdout);

 #endif

     read(n); read(k);

     For(i,,n) scanf("%lf",&p[i]);

     sort(p+,p+n+);

     f[][]=1.0;

     For(i,,n) {

         f[i][]=f[i-][]*(1.0-p[i]);

         For(j,,min(i,k/))

             f[i][j]=f[i-][j-]*p[i]+f[i-][j]*(1.0-p[i]);

     }

     For(i,,n) if(i<n-i+) swap(p[i],p[n-i+]);

     g[][]=1.0;

     For(i,,n) {

         g[i][]=g[i-][]*(1.0-p[i]);

         For(j,,min(i,k/))

             g[i][j]=g[i-][j-]*p[i]+g[i-][j]*(1.0-p[i]);

     }

     For(i,,k) {

         db tp=0.0;

         For(j,,k/)

             tp+=f[i][j]*g[k-i][k/-j];

         ans=max(ans,tp);

     }

     printf("%lf\n",ans);

     Formylove;

 }

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说这个叫我自己转移到我自己。这题让我想起了之前做的两道题，按理说其实会了那两道也就该会这道题了，但是当时对状压的理解比现在还肤浅，于是我很开心地又去做了一下。

一道是这个兴奋剂检查，和这道题的状态压缩方式是一样的，当时我还不懂为什么可以这样压，抄的题解，而且都写得好蠢。。用这道题的写法就优美多了。

另一道是这个学校食堂，是我做的第一道我自己转移到我自己的状压。不知道我当时的近百行丑陋转移是怎么写出来了。。。看来我还是进步了那么一丢丢的。

 //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=,up=;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int T,n,f[N][up][],t[N],b[N],ans;

 template<typename T>void read(T &x) {

     char ch=getchar(); T f=; x=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 int ck(int st,int s,int p) {

     if(st+p>n||(s&(<<p))) return ;

     For(i,,p-) if(!(s&(<<i))&&b[st+i]<p-i)

         return ;

     return ;

 }

 void GM(int &x,int y) { if(x>y) x=y; }

 //#define ANS

 int main() {

 #ifdef ANS

     freopen("1.in","r",stdin);

     //freopen("1.out","w",stdout);

 #endif

     read(T);

     while(T--) {

         read(n);

         For(i,,n) {

             read(t[i]); read(b[i]);

         }

         memset(f,/,sizeof(f));

         int inf=f[][][];

         ans=inf;

         For(i,,) if(ck(,,i)) f[][<<i][i]=;

         For(i,,n) For(s,,up-) For(j,,) if(f[i][s][j]!=inf) {

             For(p,,) if(ck(i,s,p)) {

                 int pr=j<=?i+j:i-(j-);

                 int cost=(t[pr]|t[i+p])-(t[pr]&t[i+p]);

                 GM(f[i][s|(<<p)][p],f[i][s][j]+cost);

             }

             For(p,,) if(!(s&(<<p))) {

                 int pp=(j>=p?j-p:+(p-j));

                 GM(f[i+p][s>>p][pp],f[i][s][j]);

                 break;

             }

         }

         For(i,,) GM(ans,f[n+][][i]);

         printf("%d\n",ans);

     }

     Formylove;

 }

学校食堂

 //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=;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n,m,f[N],up[],b[],a[][],w[],ans;

 template<typename T>void read(T &x) {

     char ch=getchar(); T f=; x=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 void GM(int &a,int b) { if(a<b) a=b; }

 //#define ANS

 int main() {

 #ifdef ANS

     freopen("1.in","r",stdin);

     //freopen("1.out","w",stdout);

 #endif

     read(n); read(m);

     For(i,,m) read(up[i]);

     w[]=;

     For(i,,m) w[i]=w[i-]*(up[i]+);

     For(i,,n) {

         read(b[i]);

         For(j,,m) read(a[i][j]);

     }

     For(i,,n) {

         Rep(s,w[m]-,) {

             int ss=s,fl=;

             For(j,,m) {

                 if(s%w[j]/w[j-]+a[i][j]<=up[j]) ss+=a[i][j]*w[j-];

                 else fl=;

             }

             if(fl) GM(f[ss],f[s]+b[i]);

         }

     }

     For(s,,w[m]-) GM(ans,f[s]);

     printf("%d\n",ans);

     Formylove;

 }

兴奋剂检查

 //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=,M=2e5;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n,w[M],f[M][N],tpans;

 char s[N];

 template<typename T>void read(T &x) {

     char ch=getchar(); T f=; x=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 #define pr pair<int,int>

 #define MP make_pair

 #define fi first

 #define se second

 pr operator + (const pr &A,const pr &B) { return MP(A.fi+B.fi,A.se+B.se); }

 pr operator *(const pr &A,const int &B) { return MP(A.fi*B,A.se*B); }

 pr sz[N*],S[M];

 int fa[N*],cnt[M],m;

 int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); }

 int pf(int x) { return x*x; }

 void GM(int &x,int y) { if(x>y) x=y; }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("factory.in","r",stdin);

     freopen("factory.out","w",stdout);

 #endif

     read(n);

     For(i,,n+n) fa[i]=i;

     For(i,,n) sz[i]=MP(,);

     For(i,n+,n+n) sz[i]=MP(,);

     For(i,,n) {

         scanf("%s",s+);

         For(j,,n) if(s[j]=='') {

             tpans++;

             int x=find(i),y=find(n+j);

             if(x!=y) {

                 sz[x]=sz[x]+sz[y];

                 fa[y]=x;

             }

         }

     }

     For(i,,n+n) if(find(i)==i)

         S[++m]=sz[i];

     sort(S+,S+m+);

     int tpm=m; m=;

     For(i,,tpm) {

         if(!m||S[m]!=S[i]) { S[++m]=S[i]; cnt[m]=; }

         else cnt[m]++;

     }

     w[]=;

     For(i,,m) w[i]=w[i-]*(cnt[i]+);

     For(s,,w[m]-) For(i,,n) f[s][i]=(i==?:n*n);

     For(s,,w[m]-) {

         pr now=MP(,);

         For(i,,m) now=now+S[i]*(s%w[i]/w[i-]);

         if(now.fi==now.se) {

             For(i,,now.fi-)

                 GM(f[s][now.fi],f[s][i]+pf(now.fi-i));

         }

         For(i,,m) if(s%w[i]/w[i-]<cnt[i]) {

             For(j,,n)

                 GM(f[s+w[i-]][j],f[s][j]);

             }

     }

     int ans=f[w[m]-][n]-tpans;

     printf("%d\n",ans);

     Formylove;

 }

工厂

DAY2

T1wzoi

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

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

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

 //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=1e6+;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n,now,cnt,cc,ans;

 char s[N];

 template<typename T>void read(T &x) {

     char ch=getchar(); T f=; x=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("wzoi.in","r",stdin);

     freopen("wzoi.out","w",stdout);

 #endif

     scanf("%s",s);

     n=strlen(s);

     For(i,,n-) {

         int c=s[i]-'';

         if(i==||s[i]!=s[i-]) cc=;

         else { ans+=cc*; cc^=;}

         if((i==n-||s[i+]!=s[i])&&cc) {

             if(cnt==||c!=now) { cnt++; now=c; }

             else if(c==now) { cnt--; now^=; ans+=; }

         }

     }

     ans+=cnt/*;

     printf("%d\n",ans);

     Formylove;

 }

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=;

typedef long long LL;

typedef double db;

using namespace std;

int n,fa[N],len[N],m;

char s[N],a[N][],p[N];

db ans;

template<typename T>void read(T &x) {

    char ch=getchar(); T f=; x=;

    while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

    if(ch=='-') f=-,ch=getchar();

    for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

}

int cmp(int x) {

    For(i,,n-len[x]+) {

        For(j,,len[x]-) {

            if(p[i+j]!=a[x][j]) break;

            if(j==len[x]-) return ;

        }

    }

    return ;

}

int vis[N];

void solve() {

    For(cs,,) {

        For(i,,n) vis[i]=;

        vis[]=;

        For(pos,,n) {

            int x=rand()%(n-pos+)+,i;

            for(i=;i<=n;i++) if(!vis[i]) {

                x--; if(!x) break;

            }

            while(!vis[fa[i]]) i=fa[i];

            vis[i]=;

            p[pos]=s[i];

        }

        int fl=;

        For(i,,m) if(cmp(i)) fl=;

        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,,n) read(fa[i]);

    scanf("%s",s+);

    read(m);

    For(i,,m) {

        scanf("%s",a[i]);

        len[i]=strlen(a[i]);

    }

    solve();

    printf("%lf\n",ans/);

    Formylove;

}

T3画

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

巴特西

NOIp2018集训test-10-6/test-10-7 (联考五day1/day2)

最新文章

热门文章