比赛链接:https://codeforces.ml/contest/1691
夜深人静写博客~
c题做不出来555~
A题:大意是给出一个n的数组,求删除一些数后,使得每两个数相加的和为偶数。求最少删除量。
剩下的数都需要是一致的奇偶性,所以删除奇数数量和偶数数量最小的那一个。
code:
#include<bits/stdc++.h> using namespace std; const int maxt = 1e5+10; int a[maxt]; int main() { int t; scanf("%d",&t); while(t--) { memset(a,0,sizeof a); int n,ji=0,ou=0; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(a[i]%2) { ji++; }else ou++; } printf("%d\n",ji>ou?ou:ji); } }
B题:大意是给出n个学生的鞋子鞋码,以非递减次序排。他们需要洗鞋,洗的鞋需要是不是自己的且鞋码大于等于自己的。求一个满足的序列,没有则-1.
把每个段数都记录起来,如果存在某个鞋码只有一双鞋则不满足条件。然后再段内交题输出 n 1~ (n-1)
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } const int nn = 1e5+10; int a[nn]; vector<int>ve; void solve() { ve.clear(); memset(a,0,sizeof a); int n; cin>>n; bool flag = true; int cnt=0; for(int i=1;i<=n;i++) { cin>>a[i]; if(a[i]!=a[i-1]) { ve.push_back(i); if(cnt==1) flag = false; else cnt = 1; } else cnt++; }// 1 1 2 2 2 3 3 if(a[n]!=a[n-1]||n==1) flag = false; if(flag){ ve.push_back(n+1); for(int i=0;i<ve.size()-1;i++) { cout<<ve[i+1]-1<<' '; for(int j=ve[i];j<ve[i+1]-1;j++) cout<<j<<' '; } cout<<endl; } else cout<<"-1"<<endl; } int main() { // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
C题:大意是给出一个长度为n的01序列,你可以拥有k次交换相邻两个元素的计划。f(x)定义为每相邻两个元素的十进制相加的sum,求最小数量的f(x)
要想使得最小值,那么我们需要尽可能的消除10或1,最靠左一定消1靠右消10。
我们可以很容易的计算出当前的sum,然后尽可能的先去消除10再去消除1
code:
#include<bits/stdc++.h> using namespace std; main(){ int t; cin >> t; for(int _ = 0; _ < t; _++){ int n, k; string s; cin >> n >> k >> s; int l = -1, r = -1, ans = 0; for(int i = 0; i < n; i++){ if(s[i] == '1'){ r = i; ans += 11; if(l == -1)l = i; } } if(r != -1 && n-1-r <= k){ k -= n-1-r; ans -= 10; if(l == r)l = k+1; } if(l != -1 && l <= k){ k -= l; ans -= 1; } cout << ans << '\n'; } }