Codeforce 963

本文主要是介绍Codeforce 963，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

B 模拟加贪心 偶数个数

考点：贪心

思路：除了全是偶数的情况，其他的情况都需要将偶数转换为奇数。最少的操作步数是偶数个数，如果有一步操作执行之前最小的偶数都比最大的奇数大，则操作步数要加1，即最后结果是偶数个数+1.

代码1：

t = int(input())
for _ in range(t):n = int(input())a = list(map(int, input().split()))s = -1v = []for x in a:if x%2 == 0:v.append(x)elif x > s:s = xv.sort()if s == -1 or v == []:print(0)continueans = len(v)for t in v:if t < s:s += telse:ans += 1breakprint(ans)

代码2：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define int long long 
#define x first
#define y secondtypedef long long ll;void solve(){int n;cin>>n;vector<int> odd,even;for(int i=0;i<n;i++){int x;cin>>x;if(x%2==0) even.push_back(x);else odd.push_back(x);}sort(even.begin(),even.end());sort(odd.begin(),odd.end());if(even.size()==n||odd.size()==n){cout<<0<<endl;return;}int mx=*max_element(odd.begin(),odd.end());int ans=0,f=0;for(int i=0;i<even.size();i++){if(even[i]<mx){mx+=even[i];ans++;}else{f=(even.size()-1-i+2);break;}}if(f) ans+=f;cout<<ans<<endl;
}signed main(){int T=1;cin>>T;while(T--){solve();}return 0;
}

C 模拟+前缀和 灯能否全亮

考点：模拟，前缀和

思路：将每盏灯的每个打开时刻标记为1，关闭时刻标记为-1。当前时刻的前缀和为1即表示有一盏灯打开，为0则表示没有灯打开。最后判断是否有时刻打开灯的数量为n。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define int long long 
#define x first
#define y secondtypedef long long ll;void solve(){int n,k;cin>>n>>k;vector<int> a(n+1),s(8*k+2),c(8*k+1);int mx=0;for(int i=0;i<n;i++){cin>>a[i];mx=max(mx,a[i]);} int m=2*k;for(int i=0;i<n;i++){int t=a[i]%m,f=1;while(t<=8*k){if(f) c[t]++;else c[t]--;t+=k;f=1-f;}}for(int i=0;i<8*k;i++){s[i+1]=s[i]+c[i];}for(int i=mx%m+m+1;i<=8*k;i++){if(s[i]==n){int t=i-1-(mx%m+m);cout<<mx+t<<endl;return;}}cout<<-1<<endl;
}signed main(){int T=1;cin>>T;while(T--){solve();}return 0;
}

D 二分+DP 中位数尽可能大

考点：二分+序列DP

思路：对于中位数，大多数情况可以考虑二分。本题的trick是删除k个连续数的技巧。

代码1：本质思路

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;#define int long long
#define x first
#define y secondtypedef long long ll;
const int inf=1e9+10;
int u,v;void solve() {int n,k;cin>>n>>k;vector<int> a(n);for(int i=0; i<n; i++) cin>>a[i];if(k==1) {cout<<*max_element(a.begin(),a.end())<<endl;return;}if(n<=k) {sort(a.begin(),a.end());cout<<a[(n-1)/2]<<endl;return;}u=(n-1)/k+1,v=(n-1)%k+1;//这里要注意 vector<vector<int>> b(u+1,vector<int>(v+1));
//	vector<vector<int>> f(u+1,vector<int>(v+1,-inf));//不能在这里定义，不然f数组不能每次执行check函数就初始化一次 for(int i=0; i<u; i++) {for(int j=0; j<v; j++) {b[i][j]=a[i*k+j];}}auto check=[&] (int x) {vector<vector<int>> f(u+1,vector<int>(v+1,-inf));//不能全部初始为-1，要尽量初始化更小一点 for(int i=0; i<u; i++) {for(int j=0; j<v; j++) {if(i>0) f[i][j]=max(f[i][j],f[i-1][j]);if(j==0) {int t=(b[i][j]>=x?1:-1);f[i][j]=max(f[i][j],t);} else {if(j>0) f[i][j]=max(f[i][j],f[i][j-1]+(b[i][j]>=x?1:-1));if(i>0&&j>0) f[i][j]=max(f[i][j],f[i-1][j-1]+(b[i][j]>=x?1:-1));}
//				cout<<"----- "<<i<<" "<<j<<' '<<f[i][j]<<endl;}}int ans=-1e9;for(int i=0;i<u;i++){ans=max(ans,f[i][v-1]);}
//		return ans>=(v+2)/2;return ans>0;};//逗号 int l=1,r=1e9+10;while(l+1<r) {int mid=l+r>>1;if(check(mid)) l=mid;else r=mid;}cout<<l<<endl;}signed main() {int T=1;cin>>T;while(T--) {solve();}return 0;
}

代码2：优化

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define x first
#define y secondtypedef long long ll;
const int N=5e5+10,inf=1e9+10;
int a[N],b[N],f[N];
int n,k;bool check(int x){
//	memset(f,-0x3f,sizeof f);//一定要注意超时 for(int i=0;i<n;i++){if(a[i]>=x) b[i]=1;else b[i]=-1;}f[0]=b[0];for(int i=1;i<n;i++){if(i%k==0){f[i]=max(f[i-k],b[i]);}else{f[i]=f[i-1]+b[i];if(i>k){f[i]=max(f[i],f[i-k]);}}}return f[n-1]>0;
}void solve(){cin>>n>>k;for(int i=0;i<n;i++) cin>>a[i];int l=1,r=inf;while(l+1<r){int mid=l+r>>1;if(check(mid)) l=mid;else r=mid;} cout<<l<<endl;
}signed main(){int T=1;cin>>T;while(T--){solve();}return 0;
}

F1 模拟+镜像

考点：模拟+镜像

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+10;
#define int long long 
string s;
int n,k,w,h;
int tx[2*N],ty[2*N];
map<pair<int,int>,int> cnt;void solve(){cin>>n>>k>>w>>h>>s;cnt.clear();int x=0,y=0;for(int i=0;i<n;i++){if(s[i]=='L') x--;if(s[i]=='R') x++;if(s[i]=='U') y++;if(s[i]=='D') y--;x=(x+2*w)%(2*w);y=(y+2*h)%(2*h);cnt[{x,y}]++;}int ans=0;for(int i=0;i<k;i++){int vx=(-i*x%(2*w)+2*w)%(2*w);int vy=(-i*y%(2*h)+2*h)%(2*h);ans+=cnt[{vx,vy}];}cout<<ans<<endl;
}signed main(){int T=1;cin>>T;while(T--){solve();}return 0;
}

这篇关于Codeforce 963的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---