时间戳

首页 > 技术文章 > Codeforces Round #429 (Div. 2)

Codeforces Round #429 (Div. 2)

xiaowuga 2017-10-06 16:20 原文

A. Generous Kefa

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

题目意思以及思路：每个人能不能分到均不相同的颜色气球……思路很简单，只要数目最多的颜色不超过人数就好了……

代码：

 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 "\n"
14 char b[30]={0};
15 int main() {
16     ios::sync_with_stdio(false);cin.tie(0);
17     II n,k;
18     cin>>n>>k;
19     char s[1000];
20     if(k>=n){cout<<"YES"<<endl;return 0;}
21     cin>>s;
22     for(II i=0;i<n;i++){
23        b[s[i]-'a'+1]++; 
24     }
25     for(II i=0;i<30;i++){
26         if(b[i]>k){
27             cout<<"NO"<<endl;return 0;
28         }
29     }
30     cout<<"YES"<<endl;
31     return 0;
32 }
View Code

B. Godsend

题目链接：http://codeforces.com/contest/841/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 "\n"
14 int main() {
15     ios::sync_with_stdio(false);cin.tie(0);
16     II n;
17     cin>>n;
18     II flag=0;
19     LL sum=0;
20     for(II i=0;i<n;i++){
21         LL t;
22         cin>>t;
23         sum+=t;
24         if(t%2) flag=1;
25     }
26     if(sum%2) cout<<"First"<<endl;
27     else if(flag&&sum%2==0) cout<<"First"<<endl;
28     else if(flag==0) cout<<"Second"<<endl;
29     return 0;
30 }
View Code

 C. Leha and Function

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

题目意思：输入两个区间长度为m的集合A、B，重新构造集合A成为A’，使得A’集合中所有长度为A’[i]的1....n集合的所有长度为B[i]的子集的最小值的期望之和最大，我们举一个例子：F(4,2)的子集有{1,2}、{1,3}、{1,4}、{2,3}、{2,4}、{3,4}所以答案F(4,2)=(1+1+1+2+2+3)/6。不难发现，F(n,k)中n不变，当k越大的时候，大的数成为最小的几率就变小了，所以直接导致了F(n,k)变小，当k不变，n变小的时候大的数成为最小概率肯定也变小，也会导致F(n,k)变小，所以一种贪心的做法就是让n,k差值尽量大，所以我们只需要让A序列和B序列一个倒序，一个逆序，然后记录B数组中每个数位置，然后输出就好了。

代码：

 1 /* ***********************************************
 2 Author        :xiaowuga
 3 Created Time  :2017年10月06日 星期五 15时50分43秒
 4 File Name     :C.cpp
 5 ************************************************ */
 6 #include <bits/stdc++.h>
 7 typedef long long LL; 
 8 #define endl "\n" 
 9 #define inf 0x3f3f3f3f 
10 const long long N=1000000;
11 const long long mod=1e9+7;
12 using namespace std;
13 int a[N];
14 vector<pair<int,int> >b;
15 int main(){
16     ios::sync_with_stdio(false);cin.tie(0);
17     int n;
18     cin>>n;
19     for(int i=1;i<=n;i++) cin>>a[i];
20     b.resize(n+1);
21     for(int i=1;i<=n;i++){
22         cin>>b[i].first;
23         b[i].second=i;
24     }
25     sort(a+1,a+1+n,greater<int>());
26     sort(b.begin()+1,b.end());
27     int ans[N];
28     for(int i=1;i<=n;i++){
29         ans[b[i].second]=a[i];
30     }
31     for(int i=1;i<=n;i++){
32         cout<<ans[i]<<' ';
33     }
34     cout<<endl;
35     return 0;
36 }
View Code

 

推荐阅读