原題鏈接：B：Godsend

大意：
一串數列。A，B 輪流取一些數字。 A 先走，每次從中抽取和為奇數的串，（抽完后自動縮為一個新串）。B 每次從中取和為偶數的串。最后一個無法操作的人輸。

思路：
博弈論水題。若和為奇數，那么 A 贏，若和為偶數， A 一開始若能從中抽走奇數，那么 B 輸，否則 A 輸。
比賽時hack看到的代碼寫法實在太多了。

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define mem(s,t) memset(s,t,sizeof(s)) //#define D(v) cout<<#v<<" "<<v<<endl #define inf 0x3f3f3f3f #define pb push_back //#define LOCAL inline void read(int &x){x=0;char p=getchar();while(!(p<='9'&&p>='0'))p=getchar();while(p<='9'&&p>='0')x*=10,x+=p-48,p=getchar(); } int a[1000]; const int mod=1e9+7; int main() {int ans=0,f=0;int n;cin>>n;for(int i=0;i<n;i++){int x;cin>>x;if(x&1) f=1;ans+=(x%2);}if(ans&1) puts("First");else if(ans%2==0 && f) puts("First");else puts("Second");return 0; }

C.Leha and Function

大意：
題目包裝得很多。對于一個數列，F(n,k) 表示數列中的第 {1,2,3,…n} 個數中選取 k 個數，k 個數中最小數的數學期望。
現在給出兩個數列，A，B ，即為上述數列，B 為 k 的集合。
現在求 最大。
看了一下樣例是倒序匹配，實際上貪心地想想也是對的。
逆序和大于等于亂序和大于等于順序和

寫法一：

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define mem(s,t) memset(s,t,sizeof(s)) #define D(v) cout<<#v<<" "<<v<<endl #define inf 0x3f3f3f3f #define pb push_back //#define LOCAL inline void read(int &x){x=0;char p=getchar();while(!(p<='9'&&p>='0'))p=getchar();while(p<='9'&&p>='0')x*=10,x+=p-48,p=getchar(); } int a[200005],b[200005],c[200005]; int main() {int m;read(m);for(int i=0;i<m;i++) read(a[i]);for(int i=0;i<m;i++){read(b[i]);c[i]=b[i];}sort(a,a+m,[&](int x,int y){return x>y;});sort(b,b+m);for(int i=0;i<m;i++) printf("%d%c",a[lower_bound(b,b+m,c[i])-b]," \n"[i==m-1]),b[lower_bound(b,b+m,c[i])-b]--;//找到位置，然后這個位置的bi--，防止影響下次查找return 0; }

寫法二：pair

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define mem(s,t) memset(s,t,sizeof(s)) #define D(v) cout<<#v<<" "<<v<<endl #define inf 0x3f3f3f3f #define pb push_back //#define LOCAL inline void read(int &x){x=0;char p=getchar();while(!(p<='9'&&p>='0'))p=getchar();while(p<='9'&&p>='0')x*=10,x+=p-48,p=getchar(); } int a[200005],b[200005],c[200005]; pair<int,int> ans[200005]; int main() {int m;read(m);mem(ans,0);for(int i=0;i<m;i++) read(a[i]);for(int i=0;i<m;i++){read(b[i]);ans[i]={b[i],i};}sort(a,a+m,greater<int>());sort(ans,ans+m);for(int i=0;i<m;i++){int to=ans[i].second;c[to]=a[i];}for(int i=0;i<m;i++) printf("%d%c",c[i]," \n"[i==m-1]);return 0; }

順便復習下pair，二維偏序，排序時先排一維，一維相同時再比較二維。

ps.最近學到了一些c++11的技巧，編譯需要編譯器支持。

總結

以上是生活随笔為你收集整理的codeforces Div.2 #429 B.Godsend C. Leha and Function的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。