今天好不容易趕到codeforces比賽的時間剛剛好，九點開始（之前一般是23:30開始，因為時差的原因），今天大概是在比賽開始後半小時才看的題，第一題很簡單的一道題（基本上每次都有一道水題），今天就做了這一道題，還費了很大的勁，大概一個小時左右的時間，就有好幾個人A掉了四題（一共五題），不得不羨慕他們的智商啊，先說一下我做的那道水題吧。
題意：
A. The Child and Homework
time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output
Once upon a time a child got a test consisting of multiple-choice questions as homework. A multiple-choice question consists of four choices:A,B,C andD. Each choice has a description, and the child should find out the only one that is correct.
Fortunately the child knows how to solve such complicated test. The child will follow the algorithm:
- If there is some choice whose description at least twice shorter than all other descriptions, or at least twice longer than all other descriptions, then the child thinks the choice is great.
- If there is exactly one great choice then the child chooses it. Otherwise the child choosesC (the child think it is the luckiest choice).
You are given a multiple-choice questions, can you predict child's choose?
Input
The first line starts with "A." (without quotes), then followed the description of choiceA. The next three lines contains the descriptions of the other choices in the same format. They are given in order:B, C,D. Please note, that the description goes after prefix "X.", so the prefix mustn't be counted in description's length.
Each description is non-empty and consists of at most 100 characters. Each character can be either uppercase English letter or lowercase English letter, or "_".
Output
Print a single line with the child's choice: "A", "B", "C" or "D" (without quotes).
Sample test(s) Input
A.VFleaKing_is_the_author_of_this_problem
B.Picks_is_the_author_of_this_problem
C.Picking_is_the_author_of_this_problem
D.Ftiasch_is_cute
Output
D
Input
A.ab
B.abcde
C.ab
D.abc
Output
C
Input
A.c
B.cc
C.c
D.c
Output
B
Note
In the first sample, the first choice has length 39, the second one has length 35, the third one has length 37, and the last one has length 15. The choiceD (length 15) is twice shorter than all other choices', so it is great choice. There is no other great choices so the child will chooseD.
In the second sample, no choice is great, so the child will choose the luckiest choiceC.
In the third sample, the choice B (length 2) is twice longer than all other choices', so it is great choice. There is no other great choices so the child will chooseB.
題目就是說國小生選選擇題，如果有一個選項的長度小于其他三個選項的二倍，或者大于其他三個選項的二倍，則這個選項是最佳選項，否則選C。
我的代碼比較繁瑣，應該這題是屬于簡單題的，代碼應該不是很長，不過部落客太笨沒有想到，隻能非很大的勁來做了，等有空看看别的大神的代碼，再更新下，下面放我的代碼
(錯誤的貌似忽略掉了隻有下劃線的情況）：
#include <iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
struct home
{
int num;
int length;
} len[4];
int cmp(const void *a,const void *b)
{
home *p1=(home *)a,*p2=(home *)b;
return p1->length-p2->length;
}//排序其實沒有用在這，這是多餘的
int main()
{
char s[4][103];
bool flag;
int i,longer[4],shorter[4],j,k,l,con,coun;
while(cin>>s[0])
{
len[0].length=strlen(s[0])-2;
len[0].num=0;
//l=0;
coun=con=0;
memset(longer,0,sizeof(longer));
memset(shorter,0,sizeof(shorter));
// k=0;
for(i=1; i<4; i++)
{
cin>>s[i];
len[i].length=strlen(s[i])-2;//記錄長度
len[i].num=i;
}
qsort(len,4,sizeof(len[0]),cmp);
for(i=0; i<4; i++)
{
for(j=0; j<4; j++)
{
if(j!=i)
{
if(len[i].length/len[j].length>=2)
{
longer[i]++;//記錄是否大于其他選項的二倍
if(longer[i]==3)
{
k=i;
con++;
}
}
}
}
}
for(i=0; i<4; i++)
{
for(j=0; j<4; j++)
{
if(j!=i)
{
if(len[j].length/len[i].length>=2)//&&(len[i].length/len[j].length!=1))
{
shorter[i]++;
if(shorter[i]==3)//記錄是否少于其他選項的二倍
{
l=i;
coun++;
}
}
}
}
}
flag=false;
for(i=0; i<4; i++)//輸出
{
if((longer[i]==3&&con==1))
{
switch(len[k].num)
{
case 0:
cout<<"A"<<endl;
flag=true;
break;
case 1:
cout<<"B"<<endl;
flag=true;
break;
case 2:
cout<<"C"<<endl;
flag=true;
break;
case 3:
cout<<"D"<<endl;
flag=true;
break;
}
}
else if(shorter[i]==3&&coun==1)
{
switch(len[l].num)
{
case 0:
cout<<"A"<<endl;
flag=true;
break;
case 1:
cout<<"B"<<endl;
flag=true;
break;
case 2:
cout<<"C"<<endl;
flag=true;
break;
case 3:
cout<<"D"<<endl;
flag=true;
break;
}
}
if(flag)
break;
}
if(!flag)
cout<<"C"<<endl;
}
return 0;
}
//哎，太長了， 我都不願看了。
貼上一個大神的代碼，果然精悍：
#include<iostream>
#include<string>
using namespace std;
int main(){
string s;
int i,a[4],j,tmp=0,k;
bool b1,b2;
for(i=0;i<4;++i){
cin>>s;
a[i]=s.length()-2;
}
for(i=0;i<4;++i){
b1=true;b2=true;
for(j=0;j<4;++j)if(j!=i){
if(2*a[i]>a[j])b1=false;
if(a[i]<2*a[j])b2=false;
}
if(b1||b2){tmp++;k=i;}
}
if(tmp==1)cout<<(char)('A'+k)<<'\n';
else cout<<(char)'C'<<'\n';
return 0;
}
這次比賽第一的代碼：
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define dep(i, a, b) for (int i = a; i > b; --i)
using namespace std;
char s[10][1010];
int len[10], rank[10], cnt;
bool rk_cmp(const int &a, const int &b)
{
return len[a] < len[b];
}
int main()
{
rep(i, 0, 4)
{
scanf("%s",s[i]+1);
len[i] = strlen(s[i]+1) - 2;
rank[i] = i;
}
sort(rank, rank+4, rk_cmp);
if (len[rank[0]] * 2 <= len[rank[1]]) cnt += 1;
if (len[rank[2]] * 2 <= len[rank[3]]) cnt += 2;
if (cnt == 1) printf("%c", rank[0]+'A');
else if (cnt == 2) printf("%c", rank[3]+'A');
else printf("C");
}
倍感自己太差啊，加油吧！！！難得cf比賽，還是挂零了。。。。
![Codeforces Round #633 (Div. 2) B. Sorted Adjacent Differences（排序，思維）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)