当前位置：首页 > article >正文

Codeforces Round 974 (Div. 3)

article 2024/11/14 20:47:47

比赛地址 :

Dashboard - Codeforces Round 974 (Div. 3) - Codeforceshttps://codeforces.com/contest/2014

A

模拟

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

#define endl '\n'
typedef long long LL;
#define pb push_back
#define eb emplace_back
#define PII pair<int,int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define int long long

const int N = 2e5 + 10 ;
const int Mod = 1e9 + 7 ;
// int xx[] = { 1,0,-1,0 };
// int yy[] = { 0,1,0,-1 };

LL qmi(LL m, LL k){LL res = 1 % Mod, t = m;while (k){if (k&1) res = res * t % Mod;t = t * t % Mod;k >>= 1;}return res;}


inline void solve(){
	int n , k  ; cin >> n >> k ;
	vector<int> a(n) ;
	for(int& x : a) cin >> x ;
	int p = 0 , ans = 0 ;
	for(int i=0;i<n;i++){
		if(a[i]>=k) p+=a[i] ;
		else if(p>0&&a[i]==0){
			p--;ans ++ ;
		}
	} 
	cout << ans << endl ;
}
 
signed main(){
    IOS
    int _ = 1;
    cin >> _;
    while(_ --) solve();
    return 0;
}

B

只用分情况(奇偶)讨论即可 ;

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

#define endl '\n'
typedef long long LL;
#define pb push_back
#define eb emplace_back
#define PII pair<int,int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define int long long

const int N = 2e5 + 10 ;
const int Mod = 1e9 + 7 ;
// int xx[] = { 1,0,-1,0 };
// int yy[] = { 0,1,0,-1 };

LL qmi(LL m, LL k){LL res = 1 % Mod, t = m;while (k){if (k&1) res = res * t % Mod;t = t * t % Mod;k >>= 1;}return res;}


inline void solve(){
	int n , k ; cin >> n >> k ;
	// n-k+1,n
	if(n&1){
		if(k==1) cout << "No" << endl ;
		else{
			// 多少个奇数
			int t = 0 ;
			if(k%2==0) t = k/2 ;
			else t=k/2+1;
			if(t&1) cout << "NO" << endl ; 
			else cout << "Yes" << endl ;
		}
	}else{
		if(k==1) cout << "yes" << endl ;
		else{
			int t = 0 ;
			if(k%2==0) t = k/2 ;
			else t=k/2;
			if(t&1) cout << "NO" << endl ; 
			else cout << "Yes" << endl ;
		}
	}
}
 
signed main(){
    IOS
    int _ = 1;
    cin >> _;
    while(_ --) solve();
    return 0;
}

C

也是模拟，找到最小不满足哪一个，求出应满足的最小值+1减去原来的sum即可 ;

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

#define endl '\n'
typedef long long LL;
#define pb push_back
#define eb emplace_back
#define PII pair<int,int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define int long long

const int N = 2e5 + 10 ;
const int Mod = 1e9 + 7 ;
// int xx[] = { 1,0,-1,0 };
// int yy[] = { 0,1,0,-1 };

LL qmi(LL m, LL k){LL res = 1 % Mod, t = m;while (k){if (k&1) res = res * t % Mod;t = t * t % Mod;k >>= 1;}return res;}


inline void solve(){
	int n ; cin >> n ;
	vector<int> a(n) ;
	int sum = 0 ;
	for(int& x : a) cin >> x , sum += x ;
	if(n<=2){cout << -1 << endl ; return ;}
	sort(all(a)) ;
	int p = a[n/2] ;
	// 平均财富>p*2;
	int ans = 2*p*n-sum ;
	if(ans<0) cout << 0 << endl ;
	else cout << ans+1 << endl ; 
	
}
 
signed main(){
    IOS
    int _ = 1;
    cin >> _;
    while(_ --) solve();
    return 0;
}

D

二分 + 差分

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

#define endl '\n'
typedef long long LL;
#define pb push_back
#define eb emplace_back
#define PII pair<int,int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define int long long

const int N = 2e5 + 10 ;
const int Mod = 1e9 + 7 ;
// int xx[] = { 1,0,-1,0 };
// int yy[] = { 0,1,0,-1 };

LL qmi(LL m, LL k){LL res = 1 % Mod, t = m;while (k){if (k&1) res = res * t % Mod;t = t * t % Mod;k >>= 1;}return res;}

int n , d , k;

bool cmp(PII& x, PII& y){
	if(x.fi==y.fi) return x.se<y.se;
	return x.fi<y.fi ;
}

inline void solve(){
	cin >> n >> d >> k ;
	vector<PII> a(k) ;
	vector<int> h(n+2,0) ,t(n+1,0);
	for(int i=0;i<k;i++) {
		cin >> a[i].fi >> a[i].se ;
		t[a[i].fi]++ ;
		h[a[i].fi]++ ;
		h[a[i].se+1]-- ;
	}
	vector<int> p(n+2,0) ;
	for(int i=1;i<=n;i++) p[i] = p[i-1] + h[i] ;
	sort(all(a),cmp) ;
	vector<int> cnt(n+1,0) ;
	int la = n-d+1 ; 
	for(int i=1;i<=la;i++){
		int ed = i+d-1;
		// st>=i的下标
		int l = -1 , r = k ;
		while(l+1<r){
			int mid = l+r>>1 ;
			if(a[mid].fi>=i) r = mid ;
			else l = mid ;
		}
		int L = r ;
		// st<=ed的下标 
		l = L-1  ; r = k ;
		while(l+1<r){
			int mid = l+r>>1 ;
			if(a[mid].fi<=ed) l = mid ;
			else r = mid ;
		}
		int R = l ;
		if(R>=L) cnt[i] += R-L+1 ;
		//上面区间一定满足
		// fi<i but ed>=i
		//l = -1 ; r = L ;//双开区间 
		// 不一定有序 , 所以不能二分 
		cnt[i] += p[i]-t[i] ;
	}
	int ma = -1 , mi = 2e18 ;
	int r1 = -1 , r2 = -1 ;
	for(int i=1;i<=la;i++){
		// cout << cnt[i] << " " ;
		if(cnt[i]>ma) ma = cnt[i],r1=i;
		if(cnt[i]<mi) mi = cnt[i],r2=i;
	}
	// cout << endl ;
	cout << r1 << " " << r2 << endl ;
}
 
signed main(){
    IOS
    int _ = 1;
    cin >> _;
    while(_ --) solve();
    return 0;
}

查看全文

http://www.kler.cn/a/315838.html