CF 1108A Two distinct points
题目意思:给你两个线段的起点和终点,让你给出两个不同的点,这两点分别处于两个不同的线段之中。
解题思路:题目说如果存在多种可能的点,随意一组答案即可,这样其实我们只需要取最特殊的起点即可。但要注意如果起点相同,那我们需要找一个起点一个终点。
#include<cstdio> #include<cmath> #include<cstring> #define ll long long int using namespace std; int main() { int t,l1,l2,r1,r2; scanf("%d",&t); while(t--) { scanf("%d%d%d%d",&l1,&r1,&l2,&r2); if(l1==l2) { printf("%d %d ",l1,r2); } else { printf("%d %d ",l1,l2); } } return 0; }
CF 1180B Divisors(因子) of Two Integers
题目意思:给你n个数,让你从n个数中找两个数,使得剩余的n-2个数皆是这两个数的因子。
解题思路:我们知道最大的那个数必然是其中的一个解,这样我们便已经确定了一个答案了,再利用这个最大数对剩余的数取模运算,不能够整除的必然是另外的一个解了。同时如果因为因子具有唯一性,如果出现了两个相同的数,那么必然有一个是因子,一个是原解。
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define ll long long int using namespace std; int my_cmp(int a,int b) { return a>b; } int main() { int n,i; int a[1010]; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&a[i]); } sort(a,a+n,my_cmp); for(i=0;i<n;i++) { if(a[0]%a[i]!=0||a[i]==a[i+1]) { printf("%d %d ",a[0],a[i]); break; } } return 0; }
CF 1108C Nice Garland
题目意思:给了一个长度为n的字符串,且字符串只包含'R','B','G'三种字符,可以改变任何一个字符,使得任意两个相同的字符的距离是3的倍数,输出改动最少的操作且输出改动后的字符串。
解题思路:任意两个相同的字符的距离是3的倍数,换种说法其实就是RGBRGB这样的三个一循环,所以我们就把RGB的所有排列方式列出来然后暴力枚举找到改动最小的操作就好了。这里学到的知识是对3位一循环的处理,使用求余的方法限定范围。
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define maxs 1000010 using namespace std; int main() { char a[6][4]= {"RGB","RBG","BGR","BRG","GBR","GRB"};///'RGB'的排列组合 char s[maxs]; int i,j,n,counts,ans,flag; ans=0x3f3f3f3f; flag=-1; scanf("%d",&n); getchar(); scanf("%s",s); for(i=0; i<6; i++) { counts=0; for(j=0; j<n; j++) { if(a[i][j%3]!=s[j]) { counts++; } } if(counts<ans) { ans=counts; flag=i; } } printf("%d ",ans); for(i=0; i<n; i++)///注意这里输出的写法 { printf("%c",a[flag][i%3]); } printf(" "); return 0; }
CF 1108D Diverse Garland
题目意思:给了一个长度为n的字符串,且字符串中只包含'G','B','R'这三种字符,可以改变字符,现在要求两个相同的字符不能相连,问最小的改动次数以及改动后的字符串。
解题思路:枚举每一位字符,如果出现了前后字符相同的情况就去判断一下该字符的前一个字符和后一个字符,之后去确定将该字符修改为何种字符。
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define maxs 1000010 using namespace std; char s[maxs]; int main() { int n,i,counts; scanf("%d",&n); getchar(); scanf("%s",s); counts=0; for(i=0;i<n-1;i++) { if(s[i]==s[i+1]) { counts++; if(s[i]!='R'&&s[i+2]!='R') { s[i+1]='R'; } else if(s[i]!='G'&&s[i+2]!='G') { s[i+1]='G'; } else if(s[i]!='B'&&s[i+2]!='B') { s[i+1]='B'; } } } printf("%d ",counts); printf("%s ",s); return 0; }