Codeforces Round #107 (Div. 2)-吐血记~~

地址 http://codeforces.com/contest/151

A：弱水题，分别求出三种食品分别用来提供几次toast，取最小值再除以人数即可，一点弯都不要转。

 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
    int n,k,l,c,d,p,nl,np,a,b,cc;
    while(scanf("%d%d%d%d%d%d%d%d",&n,&k,&l,&c,&d,&p,&nl,&np)!=EOF){
        a=k*l;
        b=c*d;
        cc=p;
        a/=nl;
        cc/=np;
        cout<<min(a,min(b,cc))/n<<endl;
    }
    return 0;
}

 

B，字符串处理有点麻烦，不过不是太大的问题。最后标点符号的处理很蛋疼，需要先统计答案的个数。另外一个，比如当所有人都没有texi的电话号码时，居然是需要输出所有人的名字，因为他们这一项的最大值都等于0！！很多人都栽在这个上面了，我也犹豫了许久。最后侥幸1A。

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include <algorithm>
using namespace std;
const int inf=1<<28;
const int nMax=1005;
const int mMax=40000;

char name[101][101];
int has[101][3];
char phone[20];

int check(){
    if(phone[0]==phone[1]&&phone[1]==phone[3]&&phone[1]==phone[4]&&phone[1]==phone[6]&&phone[1]==phone[7]){   //texi
        return 0;
    }
    if(phone[0]>phone[1]&&phone[1]>phone[3]&&phone[3]>phone[4]&&phone[4]>phone[6]&&phone[6]>phone[7]){   //texi
        return 1;
    }
    return 2;
}

int maxx[3];
char ans[101][101];
int main(){
    int n,i,j,m,a,b,c;
    while(scanf("%d",&n)!=EOF){
        memset(maxx,0,sizeof(maxx));
        memset(has,0,sizeof(has));
        for(i=1;i<=n;i++){
            scanf("%d",&m);
            scanf("%s",name[i]);
            while(m--){
                scanf("%s",phone);
                a=check();
                has[i][a]++;
                maxx[a]=max(has[i][a],maxx[a]);
            }
        }
        int num=0;
        printf("If you want to call a taxi, you should call: ");
        for(i=1;i<=n;i++){
            if(has[i][0]==maxx[0]){
                strcpy(ans[num],name[i]);
                num++;
            }
        }
        for(i=0;i<num-1;i++){
            printf("%s, ",ans[i]);
        }printf("%s.\n",ans[num-1]);

        num=0;
        printf("If you want to order a pizza, you should call: ");
        for(i=1;i<=n;i++){
            if(has[i][1]==maxx[1]){
                strcpy(ans[num],name[i]);
                num++;
            }
        }
        for(i=0;i<num-1;i++){
            printf("%s, ",ans[i]);
        }printf("%s.\n",ans[num-1]);

        num=0;
        printf("If you want to go to a cafe with a wonderful girl, you should call: ");
        for(i=1;i<=n;i++){
            if(has[i][2]==maxx[2]){
                strcpy(ans[num],name[i]);
                num++;
            }
        }
        for(i=0;i<num-1;i++){
            printf("%s, ",ans[i]);
        }printf("%s.\n",ans[num-1]);

    }
    return 0;
}

 

一个小时完成上面两题，没想到的是接下来的一个小时居然爆零了，c题博弈完全没想法。D组合数学感觉能想出来，最后也想出来了，但是是TM的最后十分钟恍然大悟！！然后第二天早上马上交了上去ac。接下来说说D吧

 

给出三个数字n，m，k。求出存在多少中字符串，它的长度是n，字典大小是m(比如全部小写字母的单词的字典大小就是26).且他的每个长度为k的子串都是回文串。

其实这道题关键就在，无论字典的大小有多大，当k小于n时，一个字符串最多只能包含两种字符，否则不可能每个长度为k的子串都回文。其他的，再按照k和n的关系太讨论即可。很不明白为什么k会大于n。那道字符串的子串能大于这个字符串？？wa在这个上面好几次……囧

 

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int main(){
    int n,m,k,i;
    long long ans;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF){
        if(k==n){
            ans=1;
            for(i=0;i<(n+1)/2;i++){
                ans*=m;
                ans%=1000000007;
            }
            cout<<ans<<endl;
            continue;
        }
        if(k==1||k>n){
            ans=1;
            for(i=0;i<n;i++){
                ans*=m;
                ans%=1000000007;
            }
            cout<<ans<<endl;
            continue;
        }
        if(k&1){
            ans=m*(m-1)+m;
            ans%=1000000007;
            cout<<ans<<endl;
            continue;
        }
        cout<<m<<endl;
    }
    return 0;
}

评论

2 楼 暴风雪 2012-02-19  

euyuil 写道

B 题我没有考虑某种电话没有的情况，也 AC 了。C 题其实是数论……欢迎交流：http://euyuil.com/3254/codeforces-round-107-div-2/

那道题，不是需要考虑，而是完全不需要考虑，考虑了就错了~

1 楼 euyuil 2012-02-19  

B 题我没有考虑某种电话没有的情况，也 AC 了。C 题其实是数论……欢迎交流：http://euyuil.com/3254/codeforces-round-107-div-2/