codeforces #304 DIV2

先送上一篇题解（虽然全英文的）:http://codeforces.com/blog/entry/18034

A题：http://codeforces.com/problemset/problem/546/A

没什么好说的，SB题

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<cctype>
 8 #include<vector>
 9 #include<stack>
10 #include<map>
11 using namespace std;
12 int n,k,w;
13 int main()
14 {
15     while(cin>>k>>n>>w)
16     {
17         int sum;
18         sum=(1+w)*w*k/2;
19         int num;
20         num=sum-n;
21         if(num<=0)
22             cout<<"0"<<endl;
23         else
24             cout<<num<<endl;
25     }
26     return 0;
27 }

View Code

B题：http://codeforces.com/problemset/problem/546/B

这题也没啥好说的，赛场上完全应该搞出来的，但是自己作死，不看后来官方给的题目修改的提示，然后一直WA在第六组，后来改了以后又是因为细节问题，一直WA在第21组，经最终修改，终于A了。就是将其排序一下，然后记录每个数最少加多少，才能让数列里面的数各不相同，暴力即可，不过注意的就是记录数组的范围应该是6000，因为后来题目改了，a[i]可以大于n，所以最大就是3000+3000=6000

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<vector>
 7 #include<algorithm>
 8 #include<map>
 9 #include<stack>
10 using namespace std;
11 const int maxn=6000+10;
12 int a[maxn],n;
13 int vis[maxn];
14 int main()
15 {
16     while(cin>>n)
17     {
18         memset(vis,0,sizeof(vis));
19         for(int i=0;i<n;i++)
20         {
21             scanf("%d",&a[i]);
22             vis[a[i]]++;
23         }
24         sort(a,a+n);
25         long long  sum=0;
26         for(int i=0;i<n;i++)
27             if(a[i]==a[i+1])
28         {
29             int j;
30             for(j=1;;j++)
31             {
32                 if(vis[a[i]+j]==0)
33                 {
34                     a[i]=a[i]+j;
35                     ++vis[a[i]];
36                     break;
37                 }
38             }
39             sum+=j;
40         }
41         cout<<sum<<endl;
42     }
43     return 0;
44 }

View Code

C题：http://codeforces.com/problemset/problem/546/C

其实是个水题，赛场上完全可以搞出来的，但是我也不知道为什么用栈模拟不行，后来改用了vector就可以了，纯粹的模拟题，很水，最后结束那个地方处理一下就行

附上一篇vector的用法介绍：http://codeforces.com/problemset/problem/546/C

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<string>
 6 #include<cmath>
 7 #include<cctype>
 8 #include<vector>
 9 #include<stack>
10 #include<map>
11 using namespace std;
12 vector <long long> s1,s2;
13 int main()
14 {
15     long long n,k1,k2;
16     cin>>n;
17     cin>>k1;
18     vector <long long> s1(k1),s2(n-k1);
19     for(long long i=0;i<s1.size();i++)
20         cin>>s1[i];
21         vector<long long> temps1=s1;
22     cin>>k2;
23     for(long long i=0;i<s2.size();i++)
24         cin>>s2[i];
25         vector<long long> temps2=s2;
26     long long cnt=0;
27     for(int i=0;i<100000;i++)
28     {
29         cnt++;
30         if(s1.front()>s2.front())
31         {
32             long long temp1,temp2;
33             temp1=s1.front(); temp2=s2.front();
34             s1.erase(s1.begin()); s2.erase(s2.begin());
35             s1.push_back(temp2);  s1.push_back(temp1);
36         }
37         else
38         {
39             long long temp1,temp2;
40             temp1=s1.front(); temp2=s2.front();
41             s1.erase(s1.begin());  s2.erase(s2.begin());
42             s2.push_back(temp1); s2.push_back(temp2);
43         }
44         if(s1.size()==0)
45         {
46             cout<<cnt<<" 2"<<endl;;
47             return 0;
48         }
49         else if(s2.size()==0)
50         {
51             cout<<cnt<<" 1"<<endl;
52             return 0;
53         }
54     }
55     cout<<"-1"<<endl;;
56     return 0;
57 }

View Code