A. Doggo Recoloring
题目意思是给一个字符串（都是小写字母），如果有两个字符相同，我们可以将这两个字符变成其他字符，问能不能使字符串字母都一样
思路 有两个相同字符时就能； 字符串长度为1时也可以。
#include<bits/stdc++.h> #define int long long #define MAX(a,b,c) max(a,max(b,c)) #define MIN(a,b,c) min(a,min(b,c)) #define pb push_back #define fi first #define se second typedef long long ll; typedef long long LL; typedef unsigned long long ull; typedef unsigned long long uLL; using namespace std; const int maxn=3e6+10; const int INF=0x3f3f3f3f; map<char,int> mp; int32_t main() { int n; cin>>n; if(n==1) {cout<<"YES"<<endl; return 0;} string ss; cin>>ss; int t=0; for(int i=0;i<n;i++) { mp[ss[i]]++; if(mp[ss[i]]==2) { t=1; break; } }if(t) cout<<"YES"<<endl; else cout<<"NO"<<endl; }
B. Weakened Common Divisor
给你n对数字，让你求一个数 是每一对数中两个中任意一个数的非1因子；
有的话直接输出那个数，没有输出-1；
给出n<=1e5+5e4; ai,bi<=2e9；
直接找ai, bi 的因子 再看是不是 其他对数的因子，分析一下 n为1e5；
1e9 只有99个； 但是有一组很强的数据 735134400 1396755360 有2456 个因子（没有重复的） 直接超时了； cf 测评机太强了 改了一下 1.4s过了这个第45点。
最后还是超时在第84个点了
#pragma once #include<iostream> #include<cstdio> using namespace std; const int maxn=2e5+10; int vs[maxn]; int main() { int n; scanf("%d",&n); int a,b; int t=0; for(int i=1;i<=n;i++) { scanf("%d %d",&a,&b); if(i==1) { int j; for(j=1;j*j<=a||j*j<=b;j++) { if(a%j==0&&a/j!=1) vs[++t]=a/j; if(b%j==0&&b/j!=1) vs[++t]=b/j; if( (b%j==0||a%j==0)&&j!=1) vs[++t]=j; } } else { int x=0; for(int j=1;j<=t;j++) { if( (a>=vs[j]&&a%vs[j]==0)||(b>=vs[j]&&b%vs[j]==0) ) { vs[++x]=vs[j]; } } t=x; } if(t==0) { printf("%d ",-1); return 0;} }printf("%d ",vs[1]); }
再来考虑 2456 个因子 如果有 2 3 再来个 6 这样的数就不用放了，所以我们只要把质因数放进去就行了。
求2456个数的素因子； 应该是可以的；
#pragma once #include<iostream> #include<cstdio> using namespace std; const int maxn=2e5+10; int vs[maxn]; int main() { int n; scanf("%d",&n); int a,b; int t=0; for(int i=1;i<=n;i++) { scanf("%d %d",&a,&b); if(i==1) { int j; for(j=1;j*j<=a||j*j<=b;j++) { if(a%j==0&&a/j!=1) vs[++t]=a/j; if(b%j==0&&b/j!=1) vs[++t]=b/j; if( (b%j==0||a%j==0)&&j!=1) vs[++t]=j; } sort(vs+1,vs+t+1); int x=0; for(int j=1;j<=t;j++) { int w=0; for(int c=2;c*c<=t;c++) { } } } else { int x=0; for(int j=1;j<=t;j++) { if( (a>=vs[j]&&a%vs[j]==0)||(b>=vs[j]&&b%vs[j]==0) ) { vs[++x]=vs[j]; } } t=x; } cout<<t<<endl; if(t==0) { printf("%d ",-1); return 0;} }printf("%d ",vs[1]); }
这个思路做不到的话 还有一个思路；
拿 17 18 为例子 他们的因数 2 3 6 9 18 1 17； 都是17*18的因数；
15 24来说 2 3 4 5 6 8 12 15 24 是 15*24的因数 或者说 15*24/gcd（15，24）；
这两个例子的 最大公约数 gcd（17*18，15*24）=18； 即 17*18 与 25*24 不互质 存在一个约数；
所以n组 gcd的值不为1，为x>1; 就有约束 ； 还是x的因数；
是不是我们输出 x 就行了 答案是否；例如 2 17 2 17 ；答案是 2 或 14， 不是34；
我们就从2-sqrt(x)找因数 找不到才是gcd的值； 尽管这样 2-sqrt（x）的值还是很大；
要进一步缩小 g=max(gcd(g,a[1]),gcd(g,b[1])) 就有了和第一组数比较 ；
#include<bits/stdc++.h> #define int long long #define MAX(a,b,c) max(a,max(b,c)) #define MIN(a,b,c) min(a,min(b,c)) #define pb push_back #define fi first #define se second typedef long long ll; typedef long long LL; typedef unsigned long long ull; typedef unsigned long long uLL; using namespace std; const int maxn=2e5+10; const int INF=0x3f3f3f3f; int a[maxn]; int b[maxn]; int gcd(int a,int b){return b ? gcd(b, a%b): a; } int32_t main() { int n; scanf("%lld",&n); int g=0; for(int i=1;i<=n;i++) { scanf("%lld %lld",&a[i],&b[i]); if(i==1) g=a[i]*b[i]; else g=gcd(g,a[i]*b[i]); } if(g==1) { cout<<-1<<endl; return 0; } g=max(gcd(g,a[1]),gcd(g,b[1]));//cout<<g<<endl; for(int i=2;i*i<=g;i++) { if(g%i==0) {cout<<i<<endl; return 0;} } cout<<g<<endl; return 0; }
C. Plasticine zebra
给你一个字符串 每一个点 我们可以执行 左边分别 第一个和最后一个。第二个和倒数第二个，第三.....。互换。右边也一样；然后把左边移到右边， 问你wb这样连续的字母最大有多少；
其实每次操作都是头尾相连 中间断开 ； 没看出来的可以倒看；
最后就是一个环 上找一点断开；找那个点断开 wb这样连续字母最大之
几个hack数据 bbbb 1 wbwb 4
#include<bits/stdc++.h> #define int long long #define MAX(a,b,c) max(a,max(b,c)) #define MIN(a,b,c) min(a,min(b,c)) #define pb push_back #define fi first #define se second typedef long long ll; typedef long long LL; typedef unsigned long long ull; typedef unsigned long long uLL; using namespace std; const int maxn=3e6+10; const int INF=0x3f3f3f3f; int32_t main() { string ss; cin>>ss; int k=ss.size(); ss=ss+ss; int ans=0; int num=1; for(int i=0;i<ss.size()-1;i++) { if(ss[i]!=ss[i+1]) num++; else num=1; ans=max(ans,num); } cout<<min(k,ans)<<endl; }