Coder-Strike 2014 - Finals (online edition, Div. 1)

CF 420A A. Start Up

题目链接：

http://codeforces.com/problemset/problem/420/A

题目意思：

给一个字符串A，通过镜面反射后得到A‘，推断A和A’是否全然一样。

解题思路：

水题。分析知有些字母通过镜面反射后和原来一样。

代码：

//#include<CSpreadSheet.h>

#include<iostream>

#include<cmath>

#include<cstdio>

#include<sstream>

#include<cstdlib>

#include<string>

#include<string.h>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#include<ctime>

#include<bitset>

#include<cmath>

#define eps 1e-6

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define ll __int64

#define LL long long

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

#define M 1000000007

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

#define Maxn 33

int hav[Maxn];

char save[110000];

void init()

{

    memset(hav,0,sizeof(hav));

    hav[1]=1,hav['H'-'A'+1]=1;

    hav['I'-'A'+1]=1;

    hav['M'-'A'+1]=1;

    hav['O'-'A'+1]=1;

    hav['T'-'A'+1]=1;

    hav['U'-'A'+1]=1;

    hav['V'-'A'+1]=1;

    hav['W'-'A'+1]=1;

    hav['X'-'A'+1]=1;

    hav['Y'-'A'+1]=1;

}

int main()

{

   //freopen("in.txt","r",stdin);

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

   while(~scanf("%s",save+1))

   {

       int len=strlen(save+1);

       int ans=1;

       int p=1;

       init();

       //printf("%d %d\n",p,len);

       while(save[p]==save[len]&&p<=len)

       {

           if(!hav[save[p]-'A'+1])

           {

               ans=0;

               break;

           }

           p++;

           len--;

       }

       if(p<=len)

            ans=0;

       if(ans)

            printf("YES\n");

       else

            printf("NO\n");

   }

   return 0;

}

CF 420B B. Online Meeting

题目链接：

http://codeforces.com/problemset/problem/420/B

题目意思：

有n个人开会，已知按时间顺序的m个进出记录（部分开会），求哪些人可能一直在开会。

解题思路：

抽象模拟。

能够保存一个当前时间的统治者me.

（无）+（有）

（有）-（无）

详解请见代码：

//#include<CSpreadSheet.h>

#include<iostream>

#include<cmath>

#include<cstdio>

#include<sstream>

#include<cstdlib>

#include<string>

#include<string.h>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#include<ctime>

#include<bitset>

#include<cmath>

#define eps 1e-6

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define ll __int64

#define LL long long

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

#define M 1000000007

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

#define Maxn 110000

int ans[Maxn],add[Maxn];

int n,m,a,cnt,me;

char temp[3];

int main()

{

   //freopen("in.txt","r",stdin);

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

   while(~scanf("%d%d",&n,&m))

   {

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

            ans[i]=1,add[i]=0;;

       cnt=0;

       me=0;

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

       {

           scanf("%s%d",temp,&a);

           if(*temp=='+')

           {

                if(!me||(me==a)) //更新统治者 注意要分别 +1 -1 +1的情况。此时统治者还是1

                    me=a;

                else

                    ans[a]=0;   //和前面的通知不一样 不行 比方+1 +2那么2不行

                add[a]=1;  //保存出现

                if(a!=me&&!add[me]) //-1 +2 此时的1不行

                    ans[me]=0;

                cnt++;

           }

           else   //'-'

           {

               if(!me) //更新统治者

                    me=a;

              if(a!=me&&add[a]==0) //+1 +2 -3 此时1为统治者

               {

                   ans[me]=0;

                   me=a;

               }

               if(add[a]) //抵消

               {

                   add[a]=0;

                   cnt--;

               }

               if(cnt) //还有剩余力量 +1 +2 -2 此时的2不行 +1 +2 -1此时的1也不行，仅仅要有+的不一样就不行

                    ans[a]=0;

           }

       }

       int tt=0;

       bool fi=true;

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

            if(ans[i])

                tt++;

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

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

       {

           if(ans[i])

           {

               if(!fi) //第一个出现

                    printf(" ");

               printf("%d",i);

               if(fi)

                   fi=false;

           }

       }

       printf("\n");

   }

   return 0;

}

Codeforces 420C - Bug in Code

题目链接：

http://codeforces.com/problemset/problem/420/C

解题思路：

先预处理出当选中第i个人时，会使num[i]个人惬意。注意当(i,j)是某人同一时候讨厌的时候，假设此时选中(i,j)仅仅会使一个人惬意。所以先出于处理出这样的情况，直接推断出选中(i,j)时是否可行。假设不行提前减掉。

然后再排序，枚举选中的第一个人，直接二分出第二个人的位置。

代码:

//#include<CSpreadSheet.h>

#include<iostream>

#include<cmath>

#include<cstdio>

#include<sstream>

#include<cstdlib>

#include<string>

#include<string.h>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#include<ctime>

#include<bitset>

#include<cmath>

#define eps 1e-6

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define ll __int64

#define LL long long

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

#define M 1000000007

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

#define Maxn 310000

int num[Maxn],n,p;

map<pair<int,int>,int>myp;

int main()

{

   //freopen("in.txt","r",stdin);

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

   while(~scanf("%d%d",&n,&p))

   {

       memset(num,0,sizeof(num));

       myp.clear();

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

       {

           int a,b;

           scanf("%d%d",&a,&b);

           if(a>b)

                swap(a,b);

           myp[make_pair(a,b)]++;

           num[a]++;

           num[b]++;

       }

       map<pair<int,int>,int>::iterator it=myp.begin();

       ll ans=0;

       for(;it!=myp.end();it++)

       {

           int ta=it->first.first,tb=it->first.second;

           if(num[ta]+num[tb]>=p&&num[ta]+num[tb]-it->second<p)

                ans--;  //说明选中ta和tb不可行

       }

       sort(num+1,num+n+1);

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

       {

          /* if(!num[i])

                continue;*/

           if(num[i]>=p)

           {

               ans+=n-i;

               continue;

           }

           int temp=p-num[i];

           if(temp>num[n]) //二分出第二个人的位置

                continue;

           int pos=lower_bound(num+i+1,num+n+1,temp)-num;

           ans+=n-pos+1;

           //printf("i:%d pos:%d\n",i,pos);

       }

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

   }

   return 0;

}

巴特西

Coder-Strike 2014 - Finals (online edition, Div. 1)

最新文章

热门文章