Codeforces Round 974 (Div. 3)

比赛地址 :  

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;
}

原文地址：https://blog.csdn.net/ros275229/article/details/142441387

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！