题意:从两个关系任意的区间取两个不同的数。(q≤500,1≤l,r≤109)
思路:取两个不同的端点即可。
#include <bits/stdc++.h> using namespace std; void solve(){ int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2; for(int i:{l1,r1}) for(int j:{l2,r2}) if(i!=j){ cout<<i<<‘ ‘<<j<<"\n"; return; } } int main() { int t;cin>>t; while(t--) solve(); return 0; }
题意:给出含有两个数因子(包含1和该数本身)的数组,找出这两个数。(2≤n≤128,1≤di≤104)
思路:记录每个因子出现的次数,最大因子即为第一个数,消去该数因子,余下最大因子即为第二个数。
#include <bits/stdc++.h> using namespace std; const int M=11000; int cnt[M]; int main() { int n;cin>>n; int mx=0; for(int i=0;i<n;i++){ int t;cin>>t; ++cnt[t]; mx=max(mx,t); } for(int i=1;i<=mx;i++) if(mx%i==0) --cnt[i]; for(int i=mx;i>=1;i--) if(cnt[i]){ cout<<i<<‘ ‘<<mx<<"\n"; break; } return 0; }
题意:一条长为n的灯带,可能有Red,Green,Blue三种颜色,找出使相同颜色间距可被3整除的最小替换次数。(1≤n≤2x105)
思路:枚举哪种排列替换次数最小即可。
#include <bits/stdc++.h> using namespace std; int main() { int n;string s;cin>>n>>s; char p[3]={‘R‘,‘G‘,‘B‘};sort(p,p+3); int mi=INT_MAX;string ans; do{ int cnt=0;string t=s; for(int i=0;i<n;i++) if(t[i]!=p[i%3]) t[i]=p[i%3],++cnt; if(cnt<mi) mi=cnt,ans=t; }while(next_permutation(p,p+3)); cout<<mi<<"\n"<<ans<<"\n"; return 0; }
题意:找出使相邻两个颜色不同的最小替换次数。
思路:贪心,如果si和si+1颜色相同,根据si和si+2的颜色改变si+1的颜色即可,因为改变后者带来的收益不会低于改变前者。
#include <bits/stdc++.h> using namespace std; int main() { int n;cin>>n; string s;cin>>s;s+=" "; int ans=0; for(int i=0;i<n;i++) if(s[i]==s[i+1]) for(char c:{‘R‘,‘G‘,‘B‘}) if(s[i]!=c&&s[i+2]!=c){ ++ans,s[i+1]=c; break; } cout<<ans<<"\n"<<s<<"\n"; return 0; }
Codeforces Round #535 (Div. 3)
原文:https://www.cnblogs.com/Kanoon/p/12548478.html