比赛链接:https://codeforc.es/contest/1712
这次比赛做了ABC,A题有些失误,大概十二分钟才AC,中途WA了一次。
B题做的很快6分钟一次过
C题WA了三次,改完一个bug后,手贱多加了一条语句,导致后面WA了两次。
A题:大意是给出一个长度为N的数组,给出数字k。求前k项的和最小。每次可以交换任意 i j 元素。元素互不相同为1-n的排列
很简单,排一下序,然后查看原序列和 排序后的序列,前k项有多少元素不存在。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) 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; } bool sign[110]; void solve() { memset(sign,false,sizeof sign); int n,k,x; cin>>n>>k; vector<int> a; for(int i=1;i<=n;i++) { cin>>x; a.push_back(x); } vector<int> b = a; sort(b.begin(),b.end()); for(int i=0;i<k;i++) { sign[a[i]] = true; } int sum = 0; for(int i=0;i<k;i++) { if(sign[b[i]]==false) sum++; } cout<<sum<<endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
B题:大意是给出一个n,构造一个序列 for 1-n,使得LCM(i,a[i])最小公倍数的和最大。
很简单的构造题,对于偶数,互换相邻两个数,对于奇数,除了1之外其他互换。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) 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; } void solve() { int n; cin>>n; if(n%2==0) { int kt = 1; for(int i=1;i<=n;i++) { cout<<i+kt<<' '; kt*=-1; } cout<<endl; }else{ cout<<1<<' '; int kt = 1; for(int i=2;i<=n;i++) { cout<<i+kt<<' '; kt*=-1; } cout<<endl; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
C题:给出一个序列,通过操作使得这个序列为非递减序列。
可以的操作:对于一个数x,使得所有等于x的a[i] i for 1-n 变为 0 。
方法:模拟一遍,每次遇到不符合的数对,更新其之前的所有数使其为0,作为标记更新后序。直到当前标记之前的全部为标记过的。寻找标记从后往前。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) 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; bool sign[nn]; vector<int>ve; set<int> se; void solve() { ve.clear(); se.clear(); memset(sign,false,sizeof sign); int n,x; cin>>n; for(int i=0;i<n;i++) { cin>>x; ve.push_back(x); } int cur = -1; while(1) { for(int i=ve.size()-1;i>=1;i--) { if(ve[i]<ve[i-1]||sign[ve[i-1]]==true) { cur = i-1; // sign[ve[i-1]] = true; break; } } bool flag = true; for(int i=0;i<=cur;i++) { if(sign[ve[i]]==false) flag = false; sign[ve[i]] = true; } if(flag) break; } if(sign[ve[n-1]]==true) cur = n-1; for(int i=0;i<=cur;i++) se.insert(ve[i]); cout<<se.size()<<endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }