这次做题可以说比之前进步很大吧。
十分钟做完A题，然后B题想了将近两小时，楞是少考虑了某种情况 ，结束后看了别人提交的代码，他们没分类讨论，代码又短又巧妙 ， 看来有时候不能盲目分类讨论。
大佬还是大佬，还得继续加油！
上题！
A. Replacing Elements
题目链接：https://codeforces.com/contest/1473/problem/A
思路：
分类讨论，只要最小的两个数之和 <= d 或者 最大的数 <= d ， 则输出 YES ， 反之 NO
AC代码：
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std ;
const int N = 110;
int q[N];
int n , t , d;
int main(){
cin >> t;
while(t --){
scanf("%d%d",&n,&d);
for(int i = 1 ; i <= n ; i ++) scanf("%d",&q[i]);
sort(q + 1, q + n + 1);
if(q[1] + q[2] <= d) puts("YES");
else if(q[n] <= d) puts("YES");
else puts("NO");
}
return 0;
}
B. String LCM
题目链接：https://codeforces.com/contest/1473/problem/B
思路：
自己做的时候是分类讨论，结果楞是有一种情况没考虑到，赛后看了错误数据发现，我那种做法实现不了这种错误情况。。
之后又去看了大佬的代码，又短又巧妙，并没有分类讨论，看来有时候不能盲目分类讨论。
这道题就是求出两个字符串的长度的最小公倍数，然后用最小公倍数分别除各自的长度，求出各自需要重复拼接的次数，然后比较拼接后的字符串是否相等，若相等则输出拼接后的字符串，否则，输出-1 。
AC代码：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std ;
int gcd(int x , int y){
return !y ? x : gcd(y , x % y);
}
int main(){
int t ;
cin >> t ;
string a , b;
while(t --){
cin >> a >> b;
int lena = a.length();
int lenb = b.length();
int num = lena * lenb / gcd(lena , lenb);
int lenaa = num / lena , lenbb = num / lenb;
string c = "" , d = "" ;
while(lenaa --) c += a;
while(lenbb --) d += b;
if(c == d) cout << c << endl;
else puts("-1");
}
return 0;
}
在这附上分类讨论的错误代码：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std ;
int flag , flag1 , flag2 ;
int gcd(int x , int y){
return !y ? x : gcd(y , x % y);
}
int main(){
string s , t;
int q;
cin >> q;
while(q -- ){
flag1 = 1;
flag2 = 1; //全相等
cin >> s >> t ;
int lens = s.length();
int lent = t.length();
for(int i = 1 ; i < lens ; i ++){
if(s[i - 1] != s[i]){
flag1 = 0;
break;
}
}
for(int i = 1 ; i < lent ; i ++){
if(t[i - 1] != t[i]){
flag2 = 0;
break;
}
}
int flagg = flag1 && flag2 ;
if(flagg){
if(s[0] != t[0]) puts("-1");
else{
int sum = gcd(lens , lent);
sum = lens * lent / sum ;
for(int i = 0 ; i < sum ; i ++) cout << s[0];
cout << endl ;
}
}
else if((lens >= lent) && flagg == 0){
flag = 0 ;
for(int i = 0 ; i < lens ; i += lent){
for(int j = 0 ; j < lent ; j ++){
if(s[j + i] != t[j]){
puts("-1");
flag = 1;
break;
}
}
if(flag) break ;
}
if(!flag) cout << s << endl;
}
else if((lens < lent) && flagg == 0){
flag = 0 ;
for(int i = 0 ; i < lent ; i += lens){
for(int j = 0 ; j < lens ; j ++){
if(t[j + i] != s[j]){
puts("-1");
flag = 1;
break;
}
}
if(flag) break ;
}
if(!flag) cout << t << endl;
}
}
return 0;
}
C. No More Inversions
题目链接：https://codeforces.com/contest/1473/problem/C
思路:
给你一个 a 序列，然后求出一个 p 序列，使得经过 b[i] = p[a[i]] 计算后的 b 序列的逆序对数量( i < j but b[i] > b[j] ) 不超过 a序列的逆序对数量 ， 并且 b 序列在字典序上最大。
分析题意可以发现，若 a , b 序列都有逆序对，则 p 序列也应有逆序对的存在 ， 并且和 b 中的存在情况相同。
而最大的数是 k ， 所以 p 序列的数的特征是 1 ~ k 递增 以及 k ~ 2k - n 递减 ， (1 <= 2k - n <= k).
AC代码：
#include<iostream>
#include<stdio.h>
using namespace std ;
int t , n , k;
int main(){
cin >>t;
while(t --){
scanf("%d%d",&n,&k) ; //长度 ， 最大值
for(int i = 1 ; i < 2 * k - n ; i ++) printf("%d ",i);
for(int i = k ; i >= 2 * k - n ; i --) printf("%d ",i);
puts("");
}
return 0;
}
每次做cf都在进步，希望自己越来越熟练，越来越强！
追梦不断，继续加油！