Codeforces Round #436 (Div. 2)

A. Fair Game

题目链接：http://codeforces.com/contest/864/problem/A

题目意思：Petya和Vasya 要分别从选择两种不同的数字，然后把给出数列中的这两种数字的卡片分别都取走，要求取完后卡片全部被取完，而且双方取走卡片的数量是相同的。

题目思路：很简单，排个序，判断前n个是不是同一个数字，后n个是不是另外的n个相同的数字。

代码：

 1 //Author: xiaowuga
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 #define inf 0x3f3f3f3f
 5 #define MAX INT_MAX
 6 #define mem(s,ch) memset(s,ch,sizeof(s))
 7 const long long N=100000; 
 8 const long long mod=1e9+7; 
 9 typedef long long LL;
10 typedef int II;
11 typedef unsigned long long ull;
12 #define nc cout<<"nc"<<endl
13 #define endl "
"
14 int main() {
15     ios::sync_with_stdio(false);cin.tie(0);
16     II a[120]={0};
17     II n;
18     cin>>n;
19     for(II i=1;i<=n;i++){
20         cin>>a[i];
21     }
22     sort(a+1,a+n+1);
23     if(a[n/2]!=a[n/2+1]&&a[n/2]==a[1]&&a[n/2+1]==a[n]){
24         cout<<"YES"<<endl;
25         cout<<a[1]<<" "<<a[n]<<endl;
26     } 
27     else cout<<"NO"<<endl;
28     return 0;
29 }

View Code

B. Polycarp and Letters

题目链接：http://codeforces.com/contest/864/problem/B

题目意思：判断两个大写字母之间小写字母种类的的数量的最大值，注意开始和结尾和第一个大写字母和最后一个大写字母之间的也算。

题目思路：暴力扫一遍。

代码：

 1 //Author: xiaowuga
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 #define inf 0x3f3f3f3f
 5 #define MAX INT_MAX
 6 #define mem(s,ch) memset(s,ch,sizeof(s))
 7 const long long N=100000; 
 8 const long long mod=1e9+7; 
 9 typedef long long LL;
10 typedef int II;
11 typedef unsigned long long ull;
12 #define nc cout<<"nc"<<endl
13 #define endl "
"
14 int main() {
15     ios::sync_with_stdio(false);cin.tie(0);
16     II n;
17     cin>>n;
18     char s[500];
19     cin>>(s+1);
20     II h[30];
21     mem(h,0);
22     II ct=0;
23     II ans=0;
24     for(II i=1;i<=n;i++){
25         if(s[i]>='A'&&s[i]<='Z'){
26             ans=max(ans,ct);
27             mem(h,0);
28             ct=0;
29         }
30         else{
31             II v=s[i]-'a';
32             if(h[v]==0) {h[v]=1,ct++;}
33         }
34     }
35     ans=max(ans,ct);
36     cout<<ans<<endl;
37     return 0;
38 }

View Code

C. Bus

题目链接：http://codeforces.com/contest/864/problem/C

题目意思：在一个一维直线上有一个起点为0，终点为a，距离为a，车有b单位的燃料，现在记录0-a或者a-0算是完成一次旅程，现在要完成k次旅程，在f处有一个加油站，现在问完成旅程最少需要多少加多少次油。

题目思路：首先我们需要假想把起点移到加油站，然后把初始油量变成b-f，然后每次从f出发到a再回到f需要2*（a-f）的汽油，从f出发到0再回到f需要2*f的汽油，要进行k次旅程就需要经过f这个加油站k次，由于我们把起点移到了加油站，所以只需要途径k-1次了，然后最后在回到0或者a就好了（根据k的值），所以然后直接看代码吧！

代码：

 1 //Author: xiaowuga
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 #define inf 0x3f3f3f3f
 5 #define MAX INT_MAX
 6 #define mem(s,ch) memset(s,ch,sizeof(s))
 7 const long long N=100000; 
 8 const long long mod=1e9+7; 
 9 typedef long long LL;
10 typedef int II;
11 typedef unsigned long long ull;
12 #define nc cout<<"nc"<<endl
13 #define endl "
"
14 int main() {
15     ios::sync_with_stdio(false);cin.tie(0);
16     II a,b,f,k;
17     cin>>a>>b>>f>>k;
18     II c=b-f;
19     II ans=0;
20     if(c<0) {cout<<-1<<endl; return 0;}
21     for(II i=1;i<k;i++){
22         II d=(i&1)?a-f:f;
23         if(c<2*d){
24             c=b;
25             ans++;
26         } 
27         if(c<2*d){
28             cout<<-1<<endl; return 0;
29         }
30         c-=2*d;
31     }
32     II x;
33     if(k&1) x=a-f;else x=f;
34     if(c<x){
35         ans++;
36         c=b;
37     } 
38     if(c<x) {cout<<-1<<endl; return 0;}
39     cout<<ans<<endl;
40     return 0;
41 }

View Code

D. Make a Permutation!

题目链接：http://codeforces.com/contest/864/problem/D

题目链接：给出一个数列，其中的一些数可能是会重复，然后要用最少的步数使其变成一个1-n的排列，而且字典序还要是最小的。

题目思路：首先需要改变的数的数量要最少，必定是不存在的数的数量，然后我们要找出这些数都有哪些，然后把他们从小到大，依次，填进去。具体看代码吧！

代码：

 1 //Author: xiaowuga
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 #define inf 0x3f3f3f3f
 5 #define MAX INT_MAX
 6 #define mem(s,ch) memset(s,ch,sizeof(s))
 7 const long long N=100000; 
 8 const long long mod=1e9+7; 
 9 typedef long long LL;
10 typedef int II;
11 typedef unsigned long long ull;
12 #define nc cout<<"nc"<<endl
13 #define endl "
"
14 II a[200000+10];
15 II b[200000+10];
16 II c[200000+10];
17 int main() {
18     ios::sync_with_stdio(false);cin.tie(0);
19     II n;
20     cin>>n;
21     mem(b,0);
22     mem(c,0);
23     for(II i=1;i<=n;i++){
24         II t;
25         cin>>t;
26         a[i]=t;
27         b[t]++;
28     }
29     vector<int>q;
30     for(II i=1;i<=n;i++){
31         if(b[i]==0) q.push_back(i);
32     }
33     II k=0;
34     LL ans=0;
35     for(II i=1;i<=n;i++){
36         II v=a[i];
37         if(b[v]>1){
38             if(c[v]==0&&a[i]<q[k]){
39                 c[v]=1;
40             }
41             else{
42                 ans++;
43                 b[v]--;
44                 a[i]=q[k];
45                 k++; 
46             }
47         }
48     }
49     cout<<ans<<endl;
50     for(II i=1;i<=n;i++) cout<<a[i]<<' ';cout<<endl;
51     return 0;
52 }

View Code