NCEPU-2013-周练一基本输入输出+排序题解

训练链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=38178#overview

A LightOJ 1000

 1 #include <cstdio>
 2 
 3 int main ()
 4 {
 5     int T;
 6     scanf("%d",&T);
 7     for (int Cas=1;Cas<=T;Cas++)
 8     {
 9         int a,b;
10         scanf("%d%d",&a,&b);
11         printf("Case %d: %d
",Cas,a+b);
12     }
13     return 0;
14 }

A LightOJ 1000

B LightOJ 1001

题意：将一个不超过20的数拆成任意两个不超过10的数。

 1 #include <cstdio>
 2 
 3 int main ()
 4 {
 5     int T;
 6     scanf("%d",&T);
 7     while (T--)
 8     {
 9         int n;
10         scanf("%d",&n);
11         if (n<=10)
12             printf("0 %d
",n);
13         else
14             printf("%d %d
",n-10,10);
15     }
16     return 0;
17 }

B LightOJ 1001

C LightOJ 1008

找规律，我写的比较挫。。。。

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstring>
 4 
 5 int main ()
 6 {
 7     int T;
 8     scanf("%d",&T);
 9     for (int Cas=1;Cas<=T;Cas++)
10     {
11         long long s;
12         scanf("%lld",&s);
13         printf("Case %d: ",Cas);
14         long long a=(long long)sqrt(s);
15         if (a*a==s)
16         {
17             if (a%2==0)  //偶数的平方
18                 printf("%lld 1
",a);
19             else
20                 printf("1 %lld
",a);
21             continue;
22         }
23         s-=a*a;
24         if (a%2==0)  //偶数的平方
25         {
26             if (s>a+1)
27                 printf("%lld %lld
",2*a+1-s+1,a+1);
28             else
29                 printf("%lld %lld
",a+1,s);
30         }
31         else
32         {
33             if (s>a+1)
34                 printf("%lld %lld
",a+1,2*a+1-s+1);
35             else
36                 printf("%lld %lld
",s,a+1);
37         }
38     }
39     return 0;
40 }

View Code

D Hdu 1029

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int N=1000005;
 5 
 6 int hash[N];
 7 
 8 int main ()
 9 {
10     int n;
11     while (~scanf("%d",&n))
12     {
13         int tmp,target=(n+1)/2,ans;
14         memset(hash,0,sizeof(hash));
15         for (int i=0;i<n;i++)
16         {
17             scanf("%d",&tmp);
18             hash[tmp]++;
19             if (hash[tmp]>=target)
20                 ans=tmp;
21         }
22         printf("%d
",ans);
23     }
24     return 0;
25 }

View Code

E Hdu 1040

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int data[1005];
 6 int main ()
 7 {
 8     int T,n,i;
 9     scanf("%d",&T);
10     while (T--)
11     {
12         scanf("%d",&n);
13         for (i=0;i<n;i++)
14             scanf("%d",&data[i]);
15         sort(data,data+n);
16         for (i=0;i<n;i++)
17             printf(i==n-1?"%d
":"%d ",data[i]);
18     }
19     return 0;
20 }

View Code

F Hdu 1391

这题我的代码依旧很挫，这个写法比较简练，我参照他的重写了一下。

该题参考：http://hi.baidu.com/nicker2010/item/8ed121dbf0f66c32e2108fed

我们从图中可以观察到以下信息：1.数字是盘旋上升的2.盘旋是有周期的，周期为4，因为我们将每4个数分为一组的话，{0,1,2,3},{4,5,6,7}....我们可以发现每一组的开始一个数分别是：0,4,8,12,16...,他们的坐标分别是：(0,0),(2,2),(4,4),(6,6),(8,8)...,因此我们首先可以根据坐标找出该坐标的数是属于哪一个组的，方法是：min(x,y)/2。再求该坐标的数在该组内的index,这个我们可以枚举！

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 #define min(a,b) ((a)<(b)?(a):(b))
 5 
 6 const int POS[][2]={{0,0},{1,1},{2,0},{3,1}};
 7 
 8 int main ()
 9 {
10     int T,posX,posY,index;
11     scanf("%d",&T);
12     while (T--)
13     {
14         scanf("%d%d",&posX,&posY);
15         int group = min(posX,posY)/2;  //每4个数一组，属于哪一组
16         posX -= 2*group;
17         posY -= 2*group;
18         bool ok = false;
19         for (int i=0;i<4;++i)  //该组内的第几个数
20             if (POS[i][0]==posX && POS[i][1]==posY)
21             {
22                 index=i;
23                 ok=true;
24                 break;
25             }
26         if (ok==false)
27             printf("No Number
");
28         else
29             printf("%d
",4*group+index);
30     }
31     return 0;
32 }

View Code

G Hdu 1236

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int N=1005;
 7 int n,m,g;
 8 
 9 int data[15];
10 
11 struct Node
12 {
13     char name[25];
14     int num,score;
15     void Get ()
16     {
17         score=0;
18         scanf("%s%d",name,&num);
19         while (num--)
20         {
21             int tmp;
22             scanf("%d",&tmp);
23             score+=data[tmp];
24         }
25     }
26     bool operator < (const Node b) const
27     {
28         if (score==b.score)
29             return strcmp(name,b.name)<0;
30         return score>b.score;
31     }
32 }a[N];
33 
34 int main ()
35 {
36 #ifdef ONLINE_JUDGE
37 #else
38     freopen("read.txt","r",stdin);
39 #endif
40     while (scanf("%d",&n),n)
41     {
42         scanf("%d%d",&m,&g);
43         int i;
44         for (i=1;i<=m;i++)
45             scanf("%d",&data[i]);
46         for (i=0;i<n;i++)
47             a[i].Get();
48         sort(a,a+n);
49         int cnt=0;
50         for (i=0;i<n;i++)
51             if (a[i].score>=g)
52                 cnt++;
53             else
54                 break;
55         printf("%d
",cnt);
56         for (i=0;i<cnt;i++)
57             printf("%s %d
",a[i].name,a[i].score);
58     }
59     return 0;
60 }

View Code

H Hdu 1872

排错的优先级比不稳定排序优先级高，即需要先判断是否排错

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int N=305;
 7 int n;
 8 
 9 struct Node
10 {
11     char name[55];
12     int score;
13     void Get ()
14     {
15         scanf("%s%d",name,&score);
16     }
17     bool operator < (const Node b) const
18     {
19         return score>b.score;
20     }
21 }data[N],after[N];
22 
23 bool Judge ()
24 {
25     for (int i=0;i<n-1;i++)
26         if (after[i].score<after[i+1].score)
27             return false;
28     return true;
29 }
30 
31 bool Same ()
32 {
33     bool flag=true;
34     for (int i=0;i<n;i++)
35         if (strcmp(data[i].name,after[i].name))
36         {
37             flag=false;
38             break;
39         }
40     return flag;
41 }
42 
43 void Output ()
44 {
45     for (int i=0;i<n;i++)
46         printf("%s %d
",data[i].name,data[i].score);
47 }
48 
49 int main ()
50 {
51 #ifdef ONLINE_JUDGE
52 #else
53     freopen("read.txt","r",stdin);
54 #endif
55     while (~scanf("%d",&n))
56     {
57         int i;
58         for (i=0;i<n;i++)
59             data[i].Get();
60         stable_sort(data,data+n);
61         for (i=0;i<n;i++)
62             after[i].Get();
63         if (Judge()==false)
64         {
65             printf("Error
");
66             Output();
67             continue;
68         }
69         if (Same())
70             printf("Right
");
71         else
72         {
73             printf("Not Stable
");
74             Output();
75         }
76     }
77     return 0;
78 }

View Code

I Hdu 2608

坑爹找规律+数论，思路可以参考：http://www.cnblogs.com/Lyush/archive/2011/07/31/2123163.html

 1 #include <cstdio>
 2 #include <cmath>
 3 
 4 int main ()
 5 {
 6     int T,n;
 7     scanf("%d",&T);
 8     while (T--)
 9     {
10         scanf("%d",&n);
11         int m=(int)sqrt(n)+(int)sqrt(n/2);
12         printf("%d
",m%2);
13     }
14     return 0;
15 }

View Code

J UVa 10420

题意：给出人数n，接下来n行，第一个单词是该人的国家，剩下的是他的名字。按照字典序输出每个国家有多少人。

这个题练习了一下STL中map自定义排列顺序……不用map也可以实现。

 1 #pragma warning(disable:4786)
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <string>
 6 #include <map>
 7 #include <algorithm>
 8 using namespace std;
 9 
10 const int N=2005;
11 
12 struct cmp
13 {
14     bool operator () (const string a,const string b)
15     {
16         return a<b;
17     }
18 };
19 
20 map<string,int,cmp> m;
21 
22 int main ()
23 {
24     int n;
25     scanf("%d",&n);
26     string str;
27     char ch[100];
28     for (int i=0;i<n;i++)
29     {
30         cin>>str;
31         gets(ch);
32         m[str]++;
33     }
34     map<string,int,cmp>::iterator it;
35     for (it=m.begin();it!=m.end();it++)
36         cout<<(*it).first<<" "<<(*it).second<<endl;
37     return 0;
38 }

View Code

K UVA 152

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstring>
 4 
 5 const int N=5005;
 6 int ans[10];
 7 
 8 struct Node
 9 {
10     int x,y,z;
11     bool Get ()
12     {
13         scanf("%d%d%d",&x,&y,&z);
14         if (x||y||z) return true;
15         return false;
16     }
17     double Dis (Node b)
18     {
19         return sqrt(1.0*(x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z));
20     }
21 }data[N];
22 
23 int main ()
24 {
25     int n=0,i=0;
26     while (data[i].Get()) n++,i++;
27     memset(ans,0,sizeof(ans));
28     for (i=0;i<=n;i++)
29     {
30         double tmp=255*255;
31         for (int j=0;j<=n;j++)
32         if (i!=j)
33         {
34             double dis=data[i].Dis(data[j]);
35             if (dis<tmp)
36             {
37                 tmp=dis;
38             }
39         }
40         ans[(int)tmp]++;
41     }
42     for (i=0;i<10;i++)
43         printf("%4d",ans[i]);
44     printf("
");
45     return 0;
46 }

View Code

L UVA 156

STL多重映照容器multimap+set实现简单些，不用这个也可以

 1 #pragma warning(disable:4786)
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <string>
 6 #include <map>
 7 #include <set>
 8 #include <algorithm>
 9 using namespace std;
10 
11 multimap<string,string> mm;
12 set<string> s;
13 string origin;
14 char str[25];
15 
16 int main ()
17 {
18     while (scanf("%s",str),str[0]!='#')
19     {
20         origin=str;
21         for (int i=0;str[i];i++)
22             if (isupper(str[i]))
23                 str[i]=tolower(str[i]);
24         sort(str,str+strlen(str));
25         mm.insert(pair<string,string>(str,origin));
26     }
27     multimap<string,string>::iterator it;
28     for (it=mm.begin();it!=mm.end();it++)
29         if (mm.count(it->first)==1)
30             s.insert(it->second);
31     set<string,string>::iterator p;
32     for (p=s.begin();p!=s.end();p++)
33         cout<<*p<<endl;
34     return 0;
35 }

View Code

M Poj 3627

题意：最少多少头牛叠罗汉可以不低于指定高度

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int data[20005];
 6 
 7 bool cmp (int a,int b)
 8 {
 9     return a>b;
10 }
11 
12 int main ()
13 {
14     int n,b;
15     while (~scanf("%d%d",&n,&b))
16     {
17         int i,sum=0;
18         for (i=0;i<n;i++)
19             scanf("%d",&data[i]);
20         sort(data,data+n,cmp);
21         for (i=0;i<n;i++)
22         {
23             sum+=data[i];
24             if (sum>=b) break;  //>=
25         }
26         printf("%d
",i+1);
27     }
28     return 0;
29 }

View Code

N Poj 3646

题意：一个骑士可以击杀一只实力比他低的龙，同时消耗他实力这么多的钱，问最少花费

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int N=20005;
 6 
 7 int dragon[N],knight[N];
 8 
 9 int main ()
10 {
11     int n,m;
12     while (scanf("%d%d",&n,&m),n||m)
13     {
14         int i,j,sum=0;
15         for (i=0;i<n;i++)
16             scanf("%d",&dragon[i]);
17         for (i=0;i<m;i++)
18             scanf("%d",&knight[i]);
19         if (m<n)
20         {
21             printf("Loowater is doomed!
");
22             continue;
23         }
24         sort(dragon,dragon+n);
25         sort(knight,knight+m);
26         for (i=0,j=0;i<n;)
27         {
28             if (knight[j]>=dragon[i])
29             {
30                 sum+=knight[j];
31                 i++,j++;
32             }
33             else
34                 j++;
35             if (j==m) break;
36         }
37         if (i==n)
38             printf("%d
",sum);
39         else
40             printf("Loowater is doomed!
");
41     }
42     return 0;
43 }

View Code

O Hdu 2379

基础DP，dp[i][j]表示用i个单词构成长度为j的密码的方法数，这题同一个单词可以反复用

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 __int64 dp[6][55],hash[15];
 5 char str[15];
 6 
 7 int main ()
 8 {
 9     int T;
10     scanf("%d",&T);
11     while (T--)
12     {
13         int m,n,q,i;
14         scanf("%d%d%d",&m,&n,&q);
15         memset(dp,0,sizeof(dp));
16         memset(hash,0,sizeof(hash));
17         for (i=0;i<m;i++)
18         {
19             scanf("%s",str);
20             int len=strlen(str);
21             hash[len]++;
22         }
23         for (i=1;i<=10;i++)
24             dp[1][i]=hash[i];
25         for (i=2;i<=n;i++) for (int j=1;j<=50;j++)
26             for (int k=1;k<=10;k++)
27                 if (j-k>0)
28                     dp[i][j]+=dp[i-1][j-k]*hash[k];
29         for (i=1;i<=q;i++)
30         {
31             int tmp;
32             scanf("%d",&tmp);
33             printf("%I64d
",dp[n][tmp]);
34         }
35     }
36     return 0;
37 }

View Code

P Poj 3663

直接找也能过，用upper_bound找快一些。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int data[20005];
 6 
 7 int main ()
 8 {
 9     int n,s;
10     while (~scanf("%d%d",&n,&s))
11     {
12         int i;
13         for (i=0;i<n;i++)
14             scanf("%d",&data[i]);
15         sort(data,data+n);
16         int ans=0;
17         for (i=0;i<n;i++)
18         {
19             int k=upper_bound(data+i,data+n,s-data[i])-data;
20             k--;
21             if (k>i) ans+=k-i;
22             else break;
23         }
24         printf("%d
",ans);
25     }
26     return 0;
27 }

View Code

Q Poj 3664

开会时的例题就是这道。

两次排序即可。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int N=50005;
 7 
 8 class Node
 9 {
10 public:
11     int id,f,s;
12     void Get (int a)
13     {
14         id=a+1;
15         scanf("%d%d",&f,&s);
16     }
17     bool operator < (const Node b) const
18     {
19         return f>b.f;
20     }
21 }data[N];
22 
23 bool cmp (const Node a,const Node b)
24 {
25     return a.s>b.s;
26 }
27 
28 int main ()
29 {
30     int n,k;
31     while (~scanf("%d%d",&n,&k))
32     {
33         int i;
34         for (i=0;i<n;i++)
35             data[i].Get(i);
36         sort(data,data+n);
37         sort(data,data+k,cmp);
38         printf("%d
",data[0].id);
39     }
40     return 0;
41 }

View Code

NCEPU-2013-周练一 基本输入输出+排序 题解

NCEPU-2013-周练一基本输入输出+排序题解