Codeforces Round 942 (Div. 2) （A-D2）C++题解

链接 :

Dashboard - Codeforces Round 942 (Div. 2) - Codeforces

A. Contest Proposal

数据范围小，模拟就好了;

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;
using namespace std;inline void solve(){int n ; cin >> n ;vector<int> a(n) , b(n) ;for(int i=0;i<n;i++) cin >> a[i] ;for(int j=0;j<n;j++) cin >> b[j] ;int ans = 0 ;sort(a.begin(),a.end()) ;sort(b.begin(),b.end()) ;for(int i=0;i<n;i++){if(a[i]<=b[i]){continue ;}else{ans ++ ;a.push_back(1) ;sort(a.begin(),a.end()) ;a.pop_back() ;sort(a.begin(),a.end()) ;}}cout << ans << endl ;
}signed main()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}

B. Coin Games

猜一下，当U出现次数是奇数，Alice能赢，否则Bob能赢；

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'#define int long long
typedef long long LL;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
using namespace std;inline void solve() {int n ; cin >> n ;vector<int> a(n+1) ;int t = 0 ;for(int i=1;i<=n;i++) {char c ; cin >> c ;if(c=='U') a[i] = 1 , t ++;else a[i] = 0 ;}if(t&1) cout << "YES" << endl ;else cout << "NO" << endl ;
}signed main()
{IOSint _ = 1;cin >> _;while (_--) solve();return 0;
}

C. Permutation Counting

贪心，先对数据进行排序，因为要求[1,n]排列，那么一定优先用k买原本数量少的卡片，使每种卡片的最少数量尽可能大；

这里可以用二分进行查找这个数量，假设为l；

那么最少组成k组[1,n]排列 : 为了得到最大ans,一定是交错排列 : 1,2,3..n,1,2,3...,n,1,2,3...n

如图 :

那么至少可以得到(l-1)*n+1个全排列；

那么对于多出来的卡片，每种可以拿出一个贴在现有排列的两边，使ans++,，如果有多余的k,也是这个贪心的套路，详情请看代码 :

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;
using namespace std;LL a[N] ,b[N] ;
LL n , k ;bool pd(int x){LL z = 0 ;for(int i=1;i<=n;i++){if(a[i]<x) z += x - a[i] ;else break ;if(z>k) return false;}if(z>k) return false;return true ;
}inline void solve(){cin >> n >> k ;LL sum = 0 ;for(int i=1;i<=n;i++) cin >> a[i] , sum += a[i] ;sort(a+1,a+1+n) ;LL mi = a[1] , ma = a[n] ;LL l = mi-1 , r = 2e12 + 8 ;while(l+1<r){LL mid = l + (r-l) / 2 ;if(pd(mid)) l = mid ;else r = mid ;}// cout << l << endl ;LL ys = sum + k - 1LL * l * n ;LL ans = n * l - n + 1 ;if(ys==0) {cout << ans << endl ; return ;}for(int i=1;i<=n;i++)if(a[i]<l)k -= l - a[i] ;for(int i=n;i>=1;i--){if(a[i]>l) ans ++ ;else if(k) ans ++ ,k -- ;else break ;}cout << ans << endl ;//	int idx = -1 ; 
//	for(int i=n;i>=1;i--){
//		// l 个
//		if(a[i]<=l) break ;
//		idx = i ; 
//	}
//	int t = n - idx + 1 ;
//	LL yy = min(n-1,a[idx]-l);
//	if(ys==1 || t==1) ans ++ ;
//	else if(ys>=2) ans += 2 * yy  ;
//	cout << ans << endl ;
}signed main()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}

D1. Reverse Card (Easy Version)

要满足(a+b) % (b*gcd(a,b)) == 0;

首先可以得到(a+b) % b == 0,那么a = kb一定成立，那么gcd(a,b) =b;

==> (kb+b) % (b*b) == 0

==> k = xb-1

那么暴力枚举每一个b就好了 :

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;
using namespace std;LL get(LL a , LL b){return a/b ;
}inline void solve(){int n , m ; cin >> n >> m ;LL ans = 0 ;// 求 (a+b) % b方 == 0的数量// a = kb2-bfor(int i=1;i<=m;i++){if(i==1) ans += n ;else{LL b = i*i ; // b ^ 2// 每次加b : kb-i <= n // k<=(n+1)/bans += get(n+i,b) ; }} cout << ans << endl ;
}signed main()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}

D2. Reverse Card (Hard Version)

解析 :

 1 . b * gcd(a , b) % (a + b) == 02 . 设 g =  gcd(a,b) , 则 a=xg , b=yg ;   3 . ==> gy * g = k * (gx + gy)4 . ==> gy = k * (x + y);5 . 由2可得 : x,y互质。那么y,x+y也互质6 . ==> g = k * (x+y);7 . ==> a=k*(x+y)*x,b=k*(x+y)*y ，满足a%x==0,b%y==0,gcd(x,y)==1

代码 :

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;
using namespace std;int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}// 1 . b * gcd(a , b) % (a + b) == 0
// 2 . 设 g =  gcd(a,b) , 则 a=xg , b=yg ;   
// 3 . ==> gy * g = k * (gx + gy)
// 4 . ==> gy = k * (x + y);
// 5 . 由2可得 : x,y互质。那么y,x+y也互质
// 6 . ==> g = k * (x+y);
// 7 . ==> a=k*(x+y)*x,b=k*(x+y)*y ，满足a%x==0,b%y==0,gcd(x,y)==1  inline void solve(){int a , b ; cin >> a >> b ;int ans = 0 ;for(int x=1;x<=a/x;x++){for(int y=1;y<=b/y;y++){if(gcd(x,y)==1){int cnt = min(a/((x+y)*x),b/((x+y)*y));if(cnt>=1) ans += cnt ;}}}	cout << ans << endl ;
}signed main()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}