hanabi组队训练1

201706 （ACM）hanabi组队训练 （ACM）构造 （ACM）思维 （ACM）动态规划

题目链接

训练总结

• 题目应该尽量让学弟看，因为我看不懂...
• 比赛一开始应该多看题，看到水题直接打，如果有其他队伍过题，就跟榜。不要一开始死磕一道题。
• 想法想清楚再分享，不要浪费时间。

补题

B. Beer Pressure（dp/滚动数组）

题意

题解

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
double dp1[55][55][55][55];
double dp2[55][55][55][55];
double ans[5];
int _[5];
int main() {
    int n,k;
    while(~scanf("%d%d",&n,&k)) {
        ///init
        memset(dp1,0,sizeof(dp1));
        memset(dp2,0,sizeof(dp2));
        memset(ans,0,sizeof(ans));
        memset(_,0,sizeof(_));
        ///read
        int s=0;
        for(int i=0;i<n;++i) {
            scanf("%d",_+i); 
            s=s+_[i];
        }
        ///solve
        dp1[_[0]][_[1]][_[2]][_[3]]=1;
        for(int i=s;i<k;++i) {//更新i+1 
            for(int a=_[0];a+_[4]<=i;++a) {
            for(int b=_[1];a+b+_[4]<=i;++b) {
            for(int c=_[2];a+b+c+_[4]<=i;++c) {
            for(int d=_[3];a+b+c+d+_[4]<=i;++d) {
                dp2[a+1][b][c][d]+=dp1[a][b][c][d]*a/i;
                dp2[a][b+1][c][d]+=dp1[a][b][c][d]*b/i;
                dp2[a][b][c+1][d]+=dp1[a][b][c][d]*c/i;
                dp2[a][b][c][d+1]+=dp1[a][b][c][d]*d/i;
                dp2[a][b][c][d]+=dp1[a][b][c][d]*(i-a-b-c-d)/i;
            } } } }
            for(int a=_[0];a+_[4]<=i+1;++a) {
            for(int b=_[1];a+b+_[4]<=i+1;++b) {
            for(int c=_[2];a+b+c+_[4]<=i+1;++c) {
            for(int d=_[3];a+b+c+d+_[4]<=i+1;++d) {
                dp1[a][b][c][d]=dp2[a][b][c][d];
                dp2[a][b][c][d]=0;
            } } } }
        }
        for(int a=_[0];a+_[4]<=k;++a) {
        for(int b=_[1];a+b+_[4]<=k;++b) {
        for(int c=_[2];a+b+c+_[4]<=k;++c) {
        for(int d=_[3];a+b+c+d+_[4]<=k;++d) {
            int e=k-a-b-c-d;
            int Max=max(a,max(b,max(c,max(d,e))));
            int cnt=0;
            if(Max==a) ++cnt;
            if(Max==b) ++cnt;
            if(Max==c) ++cnt;
            if(Max==d) ++cnt;
            if(Max==e) ++cnt;
            if(Max==a) ans[0]=ans[0]+dp1[a][b][c][d]/cnt;
            if(Max==b) ans[1]=ans[1]+dp1[a][b][c][d]/cnt;
            if(Max==c) ans[2]=ans[2]+dp1[a][b][c][d]/cnt;
            if(Max==d) ans[3]=ans[3]+dp1[a][b][c][d]/cnt;
            if(Max==e) ans[4]=ans[4]+dp1[a][b][c][d]/cnt;
        } } } }
        for(int i=0;i<n;++i) printf("pub %d: %.2f %\n",i+1,ans[i]*100);
    }
    return 0;
}

F. Foul Play（构造/思维）

题意

• 给出01矩阵表示n个队之间对决谁胜谁负。
• n是2的幂次，并且小等于1024。
• 求出一种对决方式，使得1是最后的冠军。
• 给出的矩阵满足：
  
  • 1至少能打败一半的队伍。
  • 如果1不能打败a，那么b能打败a，并且1能打败b。

题解

• 构造。
• a：1不能打败a。
• b：b能打败a，并且1能打败b。
  
  • 配对ab。
  • 配对aa。
  • 配对1x。（x表示任意数）
  • 配对xx。
• 这样构造能保证进入下一轮依然满足：
  
  • 1至少能打败一半的队伍。
  • 如果1不能打败a，那么b能打败a，并且1能打败b。

代码

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#define de(x) cout<<#x<<" = "<<x<<endl;
const int N=1100;
char s[N][N];
bool del[N],vis[N];
vector<int> tt;
int n;
void print(int x,int y) {
    printf("%d %d\n",x+1,y+1);
    vis[x]=vis[y]=0;
    if(s[x][y]=='1') del[y]=1;
    else del[x]=1;
}
void dfs(int x) {
    if(x==1) return ;
    ///init
    tt.clear();
    memset(vis,0,sizeof(vis));
    ///set vis
    for(int i=0;i<n;++i) {
        if(!del[i]) vis[i]=1;
    }
    ///t1 & t0
    for(int i=0;i<n;++i) {
        if(!vis[i]||s[i][0]=='0') continue;
        bool f=1;
        for(int j=0;j<n;++j) {
            if(!vis[j]||s[j][i]=='0'||s[j][0]=='1') continue;
            print(i,j);
            f=0;
            break;
        }
        if(f) tt.push_back(i);
    }
    ///t0 & t0
    int sz=tt.size();
    for(int i=0;i+1<sz;i+=2) print(tt[i],tt[i+1]); 
    ///1 & X
    for(int i=1;i<n;++i) {
        if(vis[i]&&s[0][i]=='1') {
            print(0,i);
            break;
        }
    }
    ///X & X
    int cnt=1,pre=0;
    for(int i=0;i<n;++i) {
        if(vis[i]) {
            ++cnt;
            if(cnt&1) print(pre,i);
            pre=i;
        }
    } 
    ///
    dfs(x/2);
}
int main() {
    while(~scanf("%d",&n)) {
        ///init
        memset(del,0,sizeof(del));
        ///read
        for(int i=0;i<n;++i) scanf("%s",s[i]);
        ///solve
        dfs(n);
    }
    return 0;
}