CodeForces Good Bye 2020 A-D
A. Bovine Dilemma
题目分析
题意：给你一组数,看他们两两组合的差有多少种情况 。
那么直接求出两两组合的差，然后去重即可得出答案。去重既可以选择开一个数组标记，也可以选择用STL的unique实现
AC代码
#include<iostream>#include<cstring>using namespace std;const int N = 1e6 100;int q[N], T, n, ans;bool s[N];//数组标记int main(){ ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> T; while(T--){ memset(s, 0, sizeof(s)); cin >> n; ans = 0; for(int i = 0; i < n; i ) cin >> q[i]; for(int i = 1; i < n; i ){ for(int j = 0; j < i; j ) if(!s[q[i] - q[j]]) s[q[i] - q[j]] = 1, ans ; } cout << ans << endl; } return 0;}#include<bits/stdc .h> using namespace std;const int N = 1e6 1000; int q[N];vector<int> arr;//vector储存，然后unqiue去重int T, n, m;int main(){ ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> T; while(T--){ cin >> n; for(int i = 0; i < n; i ) cin >> q[i]; for(int i = 1; i < n; i ) for(int j = 0; j < i; j ) arr.push_back(q[i] - q[j]); sort(arr.begin(), arr.end()); arr.erase(unique(arr.begin(), arr.end()), arr.end()); cout << arr.size() << endl;//最后输出去重后剩下的元素的数量 arr.clear(); } return 0;}
B. Last minute enhancements
题目分析
题意：给你一组数字，你能给每一个数字加上1，问你进行多次操作后最多能让这组数字有几个不同的数字
我们只需要遍历数组，如果数字未出现过，那么给它标记一下，然后ans ；如果数字出现过，再看看它加上1之后有没有出现过，如果加上1之后没有出现过，那么标记一下，ans ， 最终输出答案。
注意
注意x的数据范围
本题的解题思路有一个前提：所给的数据是有序的。虽然给的样例是有序的数组，但是题目并没有保证测试数据会给有序的数组
每一次询问结束之后清空标记的数组，同时也要选择适当的数组，防止TLE
AC代码
#include<bits/stdc .h>using namespace std;const int N = 1e6 1000;int q[N];bool s[N];int T, n;int main(){ ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> T; while(T--){ memset(s, 0, sizeof(s)); ans = 0; cin >> n; for(int i = 0; i < n; i ) cin >> q[i]; sort(q, q n); for(int i = 0; i < n; i ){ if(!s[q[i]]) s[q[i]] = 1, ans ;//不改变值的情况 else if(!s[q[i] 1]) s[q[i] 1] = 1, ans ;//加上1的情况 } cout << ans << endl; } return 0;}
C. Canine poetry
题目分析
题意：给几个字符串，问操作几次能让字符串所有的字串不构成回文
这道题是一道贪心题目，我们只需考虑aa 和 aba 这两种情况，用一个非小写字母破坏掉就可以达成目的了
AC代码
#include<bits/stdc .h>using namespace std;int T, ans;int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin >> T; while(T--){ ans = 0; string str; cin >> str; for(int i = 1; i < str.length(); i ){ if(str[i] == str[i - 1]){ str[i] = '?', ans ; } else if(str[i] == str[i - 2] && i > 1){//小细节要处理好 str[i] = '?', ans ; } } cout << ans << endl; } return 0;}
D. 13th Labour of Heracles
题目分析
本题应对点考虑贡献度，点权越大的点计算次数越多，对于答案的贡献度也就越多（答案的值也就越大），所以应该采用贪心策略，从最大的权值开始，同时记录一下点出现的情况。详情请见代码
AC代码
//qwq#include<bits/stdc .h>using namespace std;const int N = 100000 50;int T,n,m;long long ans;struct node{ int d,a;}tree[N];bool cmp(node x,node y){ return x.a>y.a;}int main(){ scanf("%d",&T); while(T--){ scanf("%d",&n); ans=0; memset(tree,0,sizeof(tree)); for (int i=1; i<=n; i){ scanf("%d",&tree[i].a); ans =tree[i].a; } for (int i=1,q1,q2; i<n; i){ scanf("%d%d",&q1,&q2); tree[q1].d ; tree[q2].d ; } sort(tree 1,tree n 1,cmp); printf("%lld",ans); for (int i=1; i<=n; i){ while (tree[i].d>1){ ans =tree[i].a; tree[i].d--; printf(" %lld",ans); } } cout << endl; } return 0;}
赞 (0)