安利一个叫codeforces better的插件 https://greasyfork.org/zh-CN/scripts/465777-codeforces-better
今天装了后使用cf体验非常舒适
=====
A.Gardener and the Capybaras (easy version)
问字符串s能否切分成3个字符串a、b、c，且满足a<=b&&c<=b或者b>=a&&b>=c
s长度<=100，暴力枚举即可
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+5; void solve(){ string s; cin>>s; int n=s.length(); for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) for(int k=j+1;k<n;k++) { string a,b,c; a="";b="";c=""; for(int h=0;h<=i;h++) a=a+s[h]; for(int h=j;h<=k-1;h++) b=b+s[h]; for(int h=k;h<n;h++) c=c+s[h]; if((!a.length())||(!b.length())||(!c.length())) continue; if(a<=b&&c<=b){ cout<<a<<" "<<b<<" "<<c<<endl; return ; } if(b<=a&&b<=c){ cout<<a<<" "<<b<<" "<<c<<endl; return; } } } int main(){ int t; cin>>t; while(t--){ solve(); } }
A2.A2 - Gardener and the Capybaras (hard version)
题意同上，但是s的长度变成2e5
那肯定有一些特殊的解法
考虑什么情况下字符串最小，s仅由a、b构成，显然如果存在a，那么a肯定最小
但是a可能出现在两端或者中间，讨论一下
- 如果出现在中间，记出现的位置为pos，直接令字符串b="a"即可，字符串a=s[0:pos-1]，字符串c=s[pos+1,|s|-1]
- 如果出现在两端，则中间串必然为bbb...bbb，令字符串a=s[0]，字符串c=s[|s|-1]，字符串b=s[1,|s|-2]，这样做一定是对的，证明：
- 不失一般性地令s[0]="a"，则s[|s|-1]若="a"，中间的串必然大于两边的串
- 若s[|s|-1]="b"，则中间的串必然大于两边的串
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+5; void solve(){ string s; cin>>s; int n=s.length(); int flag=0; for(int i=1;i<n-1;i++) if(s[i]=='a') { flag=i; break; } if(flag){ for(int i=0;i<flag;i++) cout<<s[i]; cout<<" a "; for(int i=flag+1;i<n;i++) cout<<s[i]; cout<<endl; } else { cout<<s[0]<<" "; for(int i=1;i<n-1;i++) cout<<s[i]; cout<<" "<<s[n-1]<<endl; } } int main(){ int t; if("bb">"b") cout<<1<<endl; cin>>t; while(t--){ solve(); } }
给定n和x(n<=1e18)，要求最小的m使得 n&(n+1)&(n+2)..&m=x
一开始直接做差，令del=n-x，则del在二进制表示下有1的位置必是x有1的位置的子集（因为&只会使n的1减少，&运算是单调不增的）
那么考虑del的最高位，显然要把这位的1消掉必须要加到这位会被进位
又因为这个过程是不断累加的，所以最高位之前的1也都会被抹去
所以只要在n中把del出现过的1都抹去，再在最高位+1的地方补1即可
不过这样写要特判一些东西：
显然
- x<=n
- del是n的子集
- 要保证del是x的某个后缀（对应“最高位之前的1也都会被抹去”）
- 补位时不能进位。这点很重要，有点难考虑到。如果补位会进位的话说明n的这位也会变成0，就无法得到x
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+5; vector<int>v[maxn]; int cntx[maxn],cntdel[maxn],k[maxn]; typedef long long ll; void solve(){ ll x,y; cin>>x>>y; if(y>x) { cout<<-1<<endl; return ; } if(x==y) { cout<<x<<endl; return; } ll del=x-y; int flag=1; for(ll i=63;i>=0;i--){ if((del>>i)&1){ if(((x>>i)&1)==0) flag=0; } } ll tmpx=x,tmpdel=del; int cnt_x=0,cnt_del=0; while(tmpx){ cnt_x++;cntx[cnt_x]=tmpx%2; tmpx>>=1; } while(tmpdel){ cnt_del++;cntdel[cnt_del]=tmpdel%2; tmpdel>>=1; } for(int i=1;i<=cnt_del;i++){ if(cntx[i]==1&&cntdel[i]==0){ flag=0; } } if(flag==0) { cout<<-1<<endl; return; } if(del!=x){ ll pos=log2(del),ans; ans=pow(2,pos+1); for(int i=pos+3;i<=cnt_x;i++) { if(cntx[i]==1) ans+=(1ll<<(i-1)); } if(cntx[pos+2]==1) { cout<<-1<<endl; return; } cout<<ans<<endl; } else { cout<<(ll)pow(2,(ll)log2(del)+1)<<endl; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--){ solve(); } }
经典图论，两个数之间gcd!=1即可连边，代价为1。问从s到t的最小代价。
跟gcd有关的话很容易考虑到枚举因数，我最开始考虑的是按照每个质因数去分类，但是这样往下推会遇到无法解决的问题
正解是按照因数去分类（是的，直接枚举因子，略暴力了。。），对于每个点，和自己的因子连一条边权为1的边，这里的因子是新建的虚点
然后bfs，答案为最短路/2+1
#不知道为啥一直wa15，饿了，先去吃个饭，然后再填坑
#include<bits/stdc++.h> using namespace std; const int N=1e6+5; const int inf=1e9+5; vector<int>fac[N],e[N]; int dis[N],vis[N],a[N],pre[N]; void init(){ for(int i=2;i<N;i++){ if(vis[i]) continue; for(int j=i;j<N;j+=i){ vis[j]=true; fac[j].push_back(i); } } } void solve(){ int n;cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; int s,t;cin>>s>>t; for(int i=1;i<=2*n;i++) e[i].clear(),dis[i]=inf,pre[i]=0; for(int i=1;i<=n;i++){ int x=a[i]; for(auto c:fac[x]){ e[n+c].push_back(i); e[i].push_back(n+c); } } queue<int>q; dis[s]=0; q.push(s); while(!q.empty()){ int x=q.front(); q.pop(); for(auto to:e[x]){ if(dis[to]>dis[x]+1){ dis[to]=dis[x]+1; q.push(to); pre[to]=x; } } } if(dis[t]==inf){ cout<<-1<<endl; return; } cout<<dis[t]/2+1<<endl; vector<int>ans; int at=t; while(at){ if(at<=n) ans.push_back(at); at=pre[at]; } for(int i=ans.size()-1;i>=0;i--) cout<<ans[i]<<" "; cout<<endl; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); init(); int t=1; while(t--){ solve(); } }