竞赛题目解析

A.谁是主角

将读入的所有数异或起来即可。由于异或运算满足交换律与结合律，并且异或的逆运算是其本身，因此出现两次的数会自然被“抵消”掉。

参考程序(C语言)

#include <stdio.h>

#include <stdlib.h>

int main()

{

       int n, x;

       int i;

       int s = 0;

       scanf("%d" , &n);

       for (i = 0 ; i < n ; ++i)

       {

              scanf("%d" , &x);

              s ^= x;

       }

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

       return 0;

}

B.投票统计

题目实际上是求众数。不过需要特别注意的一点是，票数并列第一则输出“nobody”。

C.分享巧克力

每掰开一次巧克力都会使总块数加1，初始为1整块，最终为m*n个1*1的小块。所有总共需要掰n*m-1次。

D.弹幕过滤器

读入数据后在内存中建立过滤列表，建议使用索引（例如哈希表或查找树），然而校内赛放水，线性查找也是能够通过的。

参考程序(C++)

#include <iostream>

#include <set>

#include <algorithm>

#include <vector>

using namespace std;

struct record

{

       int time;

       string sender;

       string content;

       bool operator< (const record &rhs) const

       {

              return this->time < rhs.time;

       }

};

vector<record> a;

set<string> filter;

int n,m;

int main()

{

       cin >> n >> m;

       for (int i = 0 ; i < n ; ++i)

       {

              record r;

              cin >> r.time >> r.sender >> r.content;

              a.push_back(r);

       }

       for (int i = 0 ; i < m ; ++i)

       {

              string s;

              cin >> s;

              filter.insert(s);

       }

       vector<record> out;

       for (int i = 0 ; i < n ; ++i)

       {

              if (!filter.count(a[i].sender))

                     out.push_back(a[i]);

       }

       sort(out.begin() , out.end());

       for (vector<record>::iterator it = out.begin() ; it != out.end() ; ++it)

              cout << it->time << ' ' << it->sender << ' ' << it->content << endl;

       return 0;

}

E.春假

分析：

       显然,春假能放几天假和5.1这一天是周几是有直接关系的,若是周一则是九天,周二和周日则是六天.否则就是五天.

       然后只要我们能够推出每年的5.1是周几就好了.假设我们知道N年5.1是周几,而第N+1年有多少天可以直接通过是否是闰年判断出来.然后根据天数对七的余数就能算出N+1年的5.1是周几.

       并不难得到1928年5.1是  周二.那么随后递推即可

代码：

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

int ans[18] = {6,9,6,5,5,5,5};

int T,n;

int pd(int x){

    if(x%400==0 || (x%4==0&&x0!=0))

        return 366;

    return 365;

}

int main(int argc,char* argv[]){

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

   //  freopen(argv[1],"r",stdin);

   // freopen(argv[2],"w",stdout);

    cin>>T;

    while(T--){       

        cin>>n;

        int d = 2,y = 1928;

        if(n==y) cout<<ans[d]<<endl;

        else{

            while(n!=y){

                y++;

                d = (d+pd(y))%7;

            }

            cout<<ans[d]<<endl;

        }

    }

    return 0;

}

F.红豆的故事

首先判断是否存在四个相同的数字，如果不存在则为章鱼老师。

接下来考察剩下的两个数，如果相等则为羊驼；如果不等，则为猴子。

G.立迪的n维数组

对坐标各维数字总和进行奇偶分析即可。

因为相邻两个位置的坐标，一个各维数字总和是奇数，另一个是偶数。

所以对相邻位置的两个数同时加上或同时减去一个数，奇数位置数字的总和与偶数位置数字的总和的差是不会改变的。

所以若想最后全变成零，就需要奇数位置数字总和与偶数位置数字总和相等。

H.ACM组队须知

分析

       (以下讨论位数均为二进制位)

       对于两个数x和y,如果x⊕y>max(x,y),那么x,y的二进制最高位一定不相同.

假设x的最高位是第i位,y最高位是第j位(i>j).那么一定存在 x的第j位是0 ,如果不是那么   x⊕y<x(请读者自己证明).

       反过来,如果x的最高位是第i位,y最高位是第j位(i>j),而且x第j位是0,那么 x⊕y>max(x,y)(请自己证明)

       所以,所有的数可以分按最高位是第几位计数,然后再按第i位是否为0计数.

       设sum[i][j]代表最高位是第i位,且第j位是0的数字的个数.num[i]是最高位是第i位的数的个数.

       那么对于所有最高位是i且第j位是0的数字,满足x⊕y>max(x,y)且y<x的组合数是sum[i][j]*num[j].答案即为sigma(sum[i][j])

代码

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

int len,n,a[35],x;

long long ans,num[35],sum[35][35];

int cf(){

       len=-1;

       while(x>0){

              len++;

              a[len]=x%2;

              x/=2;

       }

       num[len]++;

       for(int i=0;i<len;i++) if(a[i]==0) sum[len][i]++;

}

int main(int argc, char const *argv[])

{

       int T;

       cin>>T;

       while (T--){

              ans=0;

              for(int i=0;i<35;i++)

                     for(int j=0;j<35;j++)

                            sum[i][j]=0;

              for(int i=0;i<35;i++) num[i]=0;

              cin>>n;

              for(int i=0;i<n;i++){

                     cin>>x;

                     cf();

              }

              for(int i=0;i<35;i++)

                     for(int j=0;j<i;j++){

                            ans=ans+sum[i][j]*num[j];

                            //if(sum[i][j]*num[j]>0) printf("%d  %d    %lld   %lld  \n",i,j,sum[i][j],num[j]);

                     }

              cout<<ans<<endl;         

       }

       return 0;               

}

I.立迪的信号覆盖

当一个基站被主站覆盖的时候，突变的面积就是基站所在圆减去与主站圆相交部分，剩下的月牙形的面积。

但需要注意的是，主站的服务半径增大时，可能同时覆盖到若干个圆，这时的突变面积为其总和。所以参考解法为，首先枚举主站的选址。对于一个确定的主站，按基站到主站的距离对所有的基站排序，这样便可以算出每次突变的面积。

J.立迪的2048

  这道题目只要按照规则进行模拟即可，需要仔细分析清楚游戏的规则，考察选手的细心程度。