首页 > > 程序设计 > C/C++ >

二进制枚举之被RE完虐的我的一天

2020-01-03 16:00:38来源：博客园阅读 ()

记录一道学长们说有点难度的题目

好好玩啊这道题

ACM程序设计大赛是大学级别最高的脑力竞赛，素来被冠以"程序设计的奥林匹克"的尊称。大赛至今已有近40年的历史，是世界范围内历史最悠久、规模最大的程序设计竞赛。比赛形式是：从各大洲区域预赛出线的参赛队伍，于指定的时间、地点参加世界级的决赛，由1个教练、3个成员组成的小组应用一台计算机解决7到13个生活中的实际问题。
  现在假设你正在参加ACM程序设计大赛，这场比赛有 n 个题目，对于第 i 个题目你有 a_i 的概率AC掉它，如果你不会呢，那么这时候队友的作用就体现出来啦，队友甲有 b_i 的概率AC掉它， 队友乙有 c_i 的概率AC掉它，那么现在教练想知道你们队伍做出 x 个题目的概率。

Input

输入一个正整数T(T<=100)，表示有T组数据，对于每组数据首先输入一个 n (7<=n<=13)，表示有 n 个题目，接下来输入三行，
第一行输入 n 个数a_i,第二行输入 n 个数b_i,第三行输入 n 个数c_i, 其中 a_i, b_i, c_i 的意义如题，最后输入一个 x 表示教练想要知道你们队伍做出的题目数(x>=0)。

Output

输出一行表示结果，保留4位小数

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int i,j;
double gl[4][15];
double ac[15][15];
double eror[15];
int main()
{
int zu;
while(scanf("%d",&zu)!=EOF)
{
while(zu>0)
{
int n;
scanf("%d",&n);
for(i=1;i<=3;i++)
{
for(j=1;j<=n;j++)
{
scanf("%lf",&gl[i][j]);
}
}
int x;
scanf("%d",&x);
ac[0][0]=1;
for(i=1;i<=n;i++)
{
eror[i]=(1-gl[1][i])*(1-gl[2][i])*(1-gl[3][i]);//这里是每道题错的概率
}
for(i=1;i<=n;i++)//这里i表示的是题数
{
for(j=0;j<=i;j++)//这里j表示的是ac数
{
if(j==0)
ac[i][j]=ac[i-1][j]*(eror[i]);//第一道错题总是要一直错的 =^=
else
ac[i][j]=ac[i-1][j-1]*(1-eror[i])+ac[i-1][j]*eror[i];//可能是错了也可能是对了，很有意思
}
}
if(x>n)
printf("0.0000\n");
else
printf("%.4f\n",ac[n][x]);
zu--;
}

}
//cout << "Hello world!" << endl;
return 0;
}

然后在记录一些不懂怎么解决这个RE时我错了好多遍的题

Give an odd number n, (1<=n<=10000001)

Given you an array which have n numbers : a[1], a[2] a[3] ... a[n].They are positive num.
There are n/2 numbers which appear twice and only one number appears once.
Now you should tell me the number which appears only once.

Input

There are several test cases end with EOF. 
The first line there is a integer n.
Then the 2nd line there are n integer a[1],a[2]..a[n].

Output

For each case, output the number which appears only once.（英文出题觉得有点搞笑

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int g,ans;
int main()
{
    while(~scanf("%d",&g))
    {
        scanf("%d",&ans);
        int x;
       for(int i=0;i<g-1;i++)
       {
           scanf("%d",&x);
           ans=ans^x;
       }
       printf("%d\n",ans);
       /*这个故事告诉我们RE了就不要再弄大数组了
       直接输入的时候就把它干掉= =
       都是泪千行啊*/

    }
    //cout << "Hello world!" << endl;
    return 0;
}

这道题也要记录一下
上午做的思路是差不多的，电脑睡眠的时候忽然重启
丢失了之后再写就没有输出了//发现了，好乌龙的错误啊，要不我能多ac一道题= = 把循环中的j误写成了i；看来用太多循环的时候要避免i,j这两个长得相似的--

在选举问题中，总共有n个小团体，每个小团体拥有一定数量的选票数。如果其中m个小团体的票数和超过总票数的一半，则此组合为“获胜联盟”。n个团体可形成若干个获胜联盟。一个小团体要成为一个“关键加入者”的条件是：在其所在的获胜联盟中，如果缺少了这个小团体的加入，则此联盟不能成为获胜联盟。一个小团体的权利指数是指：一个小团体在所有获胜联盟中成为“关键加入者”的次数。请你计算每个小团体的权利指数。

Input

输入数据的第一行为一个正整数T，表示有T组测试数据。每一组测试数据的第一行为一个正整数n（0<n<=20）。第二行有n个正整数，分别表示1到n号小团体的票数。

Output

对每组测试数据，在同一个行按顺序输出1到n号小团体的权利指数。

 这是学长的代码~=……=~

#include <bits/stdc++.h>
using namespace std;
int n,t,i,j,s,tmp,a[21],ans[21],flag[21];
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        s=0;
        for(i=0;i<n;i++)
        {cin>>a[i];s=s+a[i];}
        memset(ans,0,sizeof(ans));
        for(i=0;i<(1<<n);i++)
        {
            tmp=0;
            memset(flag,0,sizeof(flag));
            for(j=0;j<n;j++)
            {
                if(i&(1<<j))
                {tmp=tmp+a[j];flag[j]=1;}
            }
            if(tmp<=s/2)
            {
                for(j=0;j<n;j++)
                {
                    if(tmp+a[j]>s/2&&flag[j]==0)
                    ans[j]++;
                }
            }
        }
        for(i=0;i<=n-2;i++)
        printf("%d ",ans[i]);
        printf("%d\n",ans[n-1]);
    }
    return 0;
}

我还要学好多东西呢，写得太垃圾了

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

struct hs
{
    int qz;
    int piao;
    int flag;
};
struct hs man[1000];
int n,i,j,temp,sum;
int main()
{
    int zu;
   while(cin>>zu)
   {
       while(zu>0)
       {
           sum=0;
           cin>>n;
           for(i=0;i<n;i++)
            cin>>man[i].piao;
           for(i=0;i<n;i++)
            {sum=sum+man[i].piao;
            man[i].qz=0;}
           for(i=0;i<(1<<n);i++)
           {
               temp=0;
               for(j=0;j<n;j++)
                man[j].flag=0;
               for(j=0;j<n;j++)
               {
                   if(i&(1<<j))
                {temp+=man[j].piao;
                man[j].flag++;}

               }
               if(temp>sum/2)
               {
                   for(j=0;j<n;j++)
                   {
                       if(man[j].flag!=0&&temp-man[j].piao<=sum/2)
                        man[j].qz++;
                   }
               }
           }
           for(int ki=0;ki<n-1;ki++)
            printf("%d ",man[ki].qz);
           printf("%d\n",man[n-1].qz);
           zu--;
       }
   }

    //cout << "Hello world!" << endl;
    return 0;
}

这一题也RE了= =
我和RE不得不说有仇
贴个标准答案

This time,suddenly,teacher Li wants to find out who have missed interesting DP lesson to have fun.The students who are found out will get strictly punishment.Because,teacher Li wants all the students master the DP algorithm.
    However,Li doesn't want to waste the class time to call over the names of students.So he let the students to write down their names in one paper.To his satisfaction,this time, only one student has not come.
    He can get the name who has not come to class,but,it is troublesome,and,teacher always have many things to think about,so,teacher Li wants you, who is in the ACM team, to pick out the name.

Input

There are several test cases.The first line of each case have one positive integer N.N is the  number of the students,and N will not greater than 500,000.
   Then,following N lines,each line contains one name of students who have attended class.The N-1 lines are presented after N lines.These N-1 lines indicates the names of students who have come to class this time,one name in one line.
   The length of student's name is not greater than 30.
   Process to the end of file.

Output

 For each test case, first print a line saying "Scenario #k", where k is the number of the test case.Then output the name of the student who have not come to class.One case per line.Print a blank line after each test case, even after the last one.

（英文出题弄得我漏掉好多细节

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long int n,i;
char name[40],tmp[40];
int main(){
    int cas=1;
    while(~scanf("%ld",&n))
    {

        memset(name,0,sizeof(name));
        for(i=1;i<=2*n-1;i++)
        {
            scanf("%s",tmp);
            for(int j=0;j<40;j++)
                name[j]=name[j]^tmp[j];
        }
        printf("Scenario #%d\n",cas++);
        cout<<name<<endl<<endl;//这里特别注意，题中说每组输出之后要有一行blank，所以多输出一个换行:-）
    }
    return 0;
}