Codeforces Round #843 (Div. 2)

安利一个叫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();
    }
}

C.C - Interesting Sequence

给定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即可

不过这样写要特判一些东西：

显然

1. x<=n
2. del是n的子集
3. 要保证del是x的某个后缀（对应“最高位之前的1也都会被抹去”）
4. 补位时不能进位。这点很重要，有点难考虑到。如果补位会进位的话说明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();
    }
}

D.D - Friendly Spiders

经典图论，两个数之间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();
    }
}