拿到题

上来先让我看t2,思考一会儿感觉不会

题意:

给你个人,每个人有概率p会选择通过概率1-p选择不通过,求选k个人让平票概率最大(k是偶数)

不会做..

然后翻开t1

2^n个人在玩石头剪刀布循环赛

给你P个人一直出布,R个人出石头,S个人出剪刀

求给个方案使得比赛能打完..

妈呀这又是个不可做题

后来队友提出了个结论,瞬间成了[/tex]H_2O[/tex]题

结论:

max(P,R,S)-min(P,R,S)=1不然无解

然后...发现递归构造下就好

t2不是我做的..他给A掉了

t3不是我做的

t4是个奇怪的题,题意如下:

你有n个工人和n个机子,每个工人来的顺序是随机的

每个人来的时候会随机找个自己会开的而且没人的机子,开始工作

如果某个工人发现自己没机子了,那么他今天就不工作了

为了防止有人偷懒,你决定教某些人开某些机子(不允许让某人忘掉怎么开某机子),教一个人要1$

你需要知道怎么教才能确保让没有人偷懒不工作

[tex]O(2^{n^2}*n!*n^n)[/tex]的大暴力好啊..反正N<=4

过了..

0罚时0WA 果断晋级

俩题代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char ans[100005];
char now_ans[100005];
char next[10005];
void dfs(int x,int y,int z,int n)
{
    if (n==0)
    {
        if (x==1) ans[0]='P';
        if (y==1) ans[0]='R';
        if (z==1) ans[0]='S';
        return;
    }
    int t=min(min(x/2,y/2),z/2);
    int xx=x-t*2;
    int yy=y-t*2;
    int zz=z-t*2;
    if ((xx+yy+zz)==4)
    {
        if (xx==2) dfs(t+1,t,t+1,n-1);
        if (yy==2) dfs(t+1,t+1,t,n-1);
        if (zz==2) dfs(t,t+1,t+1,n-1);
    }
    else
    {
        if (xx==0) dfs(t,t+1,t,n-1);
        if (yy==0) dfs(t,t,t+1,n-1);
        if (zz==0) dfs(t+1,t,t,n-1);
    }
    int i;
    for (i=0;i<(1<<(n-1));i++)
    {
        now_ans[i*2]=ans[i];
        now_ans[i*2+1]=next[ans[i]];
    }
    memcpy(ans,now_ans,sizeof(ans));
}
int main()
{
    freopen("A-small.in","r",stdin);
    freopen("A-small.out","w",stdout);
    int t;
    scanf("%d",&t);
    int zu;
    next['P']='R';
    next['R']='S';
    next['S']='P';
    for (zu=0;zu<t;zu++)
    {
        printf("Case #%d: ",zu+1);
        int a,b,c,n;
        scanf("%d",&n);
        scanf("%d%d%d",&b,&a,&c);   //PRS
        if ((a-b>1)||(b-c>1)||(c-a>1)||(b-a>1)||(c-b>1)||(a-c>1))
        {
            puts("IMPOSSIBLE");
            continue;
        }
        dfs(a,b,c,n);
        int i;
        for (i=1;i<=n;i++)
        {
            int j;
            for (j=0;j<(1<<n);j+=(1<<i))
            {
                int k;
                for (k=0;k<(1<<(i-1));k++)
                {
                    if (ans[j+k]!=ans[j+(1<<(i-1))+k]) break;
                }
                if (ans[j+k]>ans[j+(1<<(i-1))+k])
                {
                    for (k=0;k<(1<<(i-1));k++)
                    {
                        swap(ans[j+k],ans[j+(1<<(i-1))+k]);
                    }
                }
            }
        }
        ans[1<<n]='\0';
        printf("%s\n",ans);
    }
    return 0;
}

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[35][35];
int n;
int b[15];
bool used[15];
bool unok(int x)
{
    if (x==n) return false;
    int i;
    int sum=0;
    for (i=0;i<n;i++)
    {
        if (used[i]) continue;
        if (a[b[x]][i]=='1')
        {
            sum=1;
            used[i]=true;
            if (unok(x+1)) return true;
            used[i]=false;
        }
    }
    if (sum==0) return true;
    return false;
}
bool check()
{
    int i;
    for (i=0;i<n;i++)
    {
        b[i]=i;
        used[i]=false;
    }
    for (;;)
    {
        if (unok(0)) return false;
        if (!next_permutation(b,b+n)) return true;
    }
}
int main()
{
    freopen("D-small.in","r",stdin);
    freopen("D-small.out","w",stdout);
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        printf("Case #%d: ",zu+1);
        int i;
        scanf("%d",&n);
        for (i=0;i<n;i++)
        {
            scanf("%s",a[i]);
        }
        int max_ans=10000;
        for (i=0;i<(1<<(n*n));i++)
        {
            int j;
            int sum=0;
            for (j=0;j<(n*n);j++)
            {
                int t1=j/n;
                int t2=j%n;
                if ((1<<j)&i) continue;
                if (a[t1][t2]=='1') break;
                sum++;
            }
            if (j!=n*n) continue;
            if (sum>=max_ans) continue;
            for (j=0;j<(n*n);j++)
            {
                int t1=j/n;
                int t2=j%n;
                if ((1<<j)&i) continue;
                a[t1][t2]='1';
            }
            if (check()) max_ans=sum;
            for (j=0;j<(n*n);j++)
            {
                int t1=j/n;
                int t2=j%n;
                if ((1<<j)&i) continue;
                a[t1][t2]='0';
            }
        }
        printf("%d\n",max_ans);
    }
    return 0;
}