2022/7/21

I finished the yellow question today , It could have been a green question , But I have to fight cf Just drive tomorrow  

1497C2 - k-LCM (hard version)

This inscription took an hour and a half , Or to see the solution ,,, The idea is just three numbers , The back is full of 1 Just go , But how to get and write these three numbers took a lot of effort, and it has always been wrong , Finally, it should be divided into three cases in the code , A simple version should be made first , The simple version is k Constant for the 3, In this way, you can always think about how to take three numbers , Instead of thinking in the direction of structure

Codeforces #708 Div2_C2. k-LCM (hard version)_ Ouyang little Lily's blog -CSDN Blog

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
ll t,n,k;
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&k);
        n=n-(k-3);
        for(int i=1;i<=k-3;i++) printf("1 ");
        k=3;
        if(n%3==0){
            printf("%lld %lld %lld\n",n/3,n/3,n/3);
        }
        else if((n/2)%2==1&&n%2==0){
            printf("%lld %lld %lld\n",2,n/2-1,n/2-1);
        }
        else if(n%4==0&&n%2==0){
            printf("%lld %lld %lld\n",n/2,n/4,n/4);
        }
        else{
            printf("%lld %lld %lld\n",1,(n-1)/2,(n-1)/2);
        }
        
    }
    system("pause");
    return 0;
} 

1396A - Multiples of Length

You can find that (a[i]+(n-1)x)%n==0(x Is an integer ) Is established , So I thought of it for the first time l=n,r=n, The second time l=1,r=n-1, third time l=1,r=n or r=n-1, The first is output -a[n], The second value needs to be enumerated , But when I was testing the sample, I suddenly found that it could o1 Find out , Test a few more groups and you will find that the formula is (a[i]%n)*(n-1), The third time outputs the value of the second time plus a[i] Take another opposite number

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
ll n,b[100005],a[100005];
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),b[i]=0;
    if(n==1){
        printf("1 1\n%lld\n1 1\n0\n1 1\n0\n",-a[1]);
        system("pause");
        return 0;
    }
    for(int i=1;i<n;i++){
        b[i]=(a[i]%n)*(n-1);
    }
    printf("%lld %lld\n%lld\n",n,n,-a[n]);a[n]=0;
    printf("1 %lld\n",n-1);
    for(int i=1;i<n;i++) printf("%lld ",b[i]);
    printf("\n1 %lld\n",n);
    for(int i=1;i<=n;i++) printf("%lld ",-(b[i]+a[i]));
    system("pause");
    return 0;
} 

Robot Cleaner Revisit expect

It can be seen that the grid the robot walks is circularly fixed ,k Is the number of grids that can be cleaned ,z Is the number of grids that can walk , The probability of working is p, The probability of not working is q=1-p, The expected number of times is

pt[1]+q(pt[2]+q(pt[3]+...+q(pt[k]+q(z+pt[1]+...), It means that if the first cleaned grid is successful, it is pt[1], Otherwise, keep looking down at the second cleaned grid , The judgment method is the same as the first one, assuming that the answer to a circular section is T, The answer to each cycle section is the same , Then you can deduce the answer

CF1623D Answer key - GaryH The blog of - Luogu blog (luogu.com.cn)

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=1e9+7;
ll T,n,m,rb,cb,rd,cd,P,t[100005];
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll getinv(ll a){return qpow(a,mod-2);}
int main(){
    cin>>T;
    while(T--){
        cin>>n>>m>>rb>>cb>>rd>>cd>>P;
        ll p=P*getinv(100)%mod;
        //ll q=(100-P)*getinv(100)%mod;
        ll q=(mod+1-p)%mod;
        map<pair<pair<ll,ll>,pair<ll,ll>>,ll>mp;
        ll dr=1,dc=1;
        if(rb+dr>n||rb+dr<1) dr=-dr;
        if(cb+dc>m||cb+dc<1) dc=-dc;
        ll z=0,k=0;
        while(1){
            mp[{
   {rb,cb},{dr,dc}}]++;z++;
            if(rb==rd||cb==cd) t[++k]=z-1;
            rb+=dr;cb+=dc;
            if(rb+dr>n||rb+dr<1) dr=-dr;
            if(cb+dc>m||cb+dc<1) dc=-dc;
            if(mp.count({
   {rb,cb},{dr,dc}})) break;
        }
       // for(int i=1;i<=k;i++)cout<<t[i]<<endl;
        ll inv=getinv((mod+1-qpow(q,k))%mod);
        ll ans=qpow(q,k)*z%mod*inv%mod;
        for(int i=1;i<=k;i++){
            ans=(ans+qpow(q,i-1)*p%mod*t[i]%mod*inv%mod)%mod;
        }
        printf("%lld\n",ans);
    }
    system("pause");
    return 0;
} 

 P2420 Let's XOR - Luogu | New ecology of computer science education (luogu.com.cn)

This problem only requires the XOR and sum of each point to the root node 了 , The answer is xo[u]^xo[v], Because the same path of two points is XOR gone .

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=1e9+7;
ll n,m,xo[100005];
ll head[200005],cnt;
struct node{
    ll from,to,next,w;
}edge[200005];
void addedge(ll from,ll to,ll w){
    edge[++cnt].from = from;
    edge[cnt].to = to;
    edge[cnt].w=w;
    edge[cnt].next=head[from];
    head[from] = cnt;
}
void dfs(ll u,ll fa){
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j!=fa){xo[j]=xo[u]^edge[i].w;dfs(j,u);}
    }
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<n;i++){
        ll u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,w);
    }
    dfs(1,0);
    scanf("%lld",&m);
    while(m--){
        ll u,v;
        scanf("%lld%lld",&u,&v);
        printf("%lld\n",xo[u]^xo[v]);
    }
    system("pause");
    return 0;
} 

P4826 [USACO15FEB]Superbull S - Luogu | New ecology of computer science education (luogu.com.cn)

In fact, the XOR of two numbers is the distance between two points , After processing the distance of each point, run the minimum spanning tree once

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=1e9+7;
ll n,m,s[5000005],c[5000005];
struct node{
    ll u,v,w;
    bool operator<(const node& a) const { return w>a.w; }
}ed[5000006];
ll findd(ll x){return x==s[x]?x:s[x]=findd(s[x]);}
ll kruscal(){
    ll ans=0,ct=0;
    for(int i=1;i<=n;i++) s[i]=i;
    sort(ed+1,ed+m+1);
    for(int i=1;i<=m;i++){
        ll xx=findd(ed[i].u),yy=findd(ed[i].v);
        if(xx==yy) continue;
        s[xx]=yy;
        ct++; ans+=ed[i].w;
        if(ct>=n-1) return ans;
    }
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++){
            ed[++m].u=i;ed[m].v=j;ed[m].w=c[i]^c[j];
        }
    printf("%lld\n",kruscal());
    system("pause");
    return 0;
} 

P5836 [USACO19DEC]Milk Visits S - Luogu | lca

Process the path from each node to the root node H The number of and G The number of , use lca After finding the nearest ancestor , Find the ancestor to two points H,G And see if it meets the conditions

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=1e9+7;
ll n,m,sum0[100005],sum1[100005];
string s;
ll f[100005],son[100005],siz[100005],top[100005],d[100005];
ll head[500005],cnt;
struct Edge{
    ll from,to,next;
}edge[500005];
void addedge(ll from, ll to){
    edge[++cnt].from = from;
    edge[cnt].to = to;
    edge[cnt].next = head[from];
    head[from] = cnt;
}
void dfs1(ll u,ll fa){
    siz[u]=1;son[u]=0;d[u]=d[fa]+1;f[u]=fa;
    sum0[u]=sum0[fa]+(s[u]=='G');// It's better to put in parentheses , Otherwise, there is a high probability of error 
    sum1[u]=sum1[fa]+(s[u]=='H');
   // cout<<"u: "<<u<<" fa: "<<fa<<" s[u]: "<<s[u]<<" sum0[u]: "<<sum0[u]<<" sum0[fa]: "<<sum0[fa]<<" sum1[u]: "<<sum1[u]<<" sum1[fa]: "<<sum1[fa]<<endl;
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j==fa) continue;
        dfs1(j,u);
        siz[u]+=siz[j];
        if(siz[son[u]]<siz[j]) son[u]=j;
    }
}
void dfs2(ll u,ll topx){
    top[u]=topx;
    if(son[u]) dfs2(son[u],topx);
    for(int i=head[u];i;i=edge[i].next){
        if(edge[i].to!=f[u]&&edge[i].to!=son[u])
        dfs2(edge[i].to,edge[i].to);
    }
}
ll lca(ll x,ll y){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]]) swap(x,y);
        x=f[top[x]];
    }
    return d[x]<d[y]?x:y;
}
int main(){
    scanf("%lld%lld",&n,&m);
    cin>>s;s=" "+s;
    for(int i=1;i<=n-1;i++){
        ll u,v;
        scanf("%lld%lld",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    dfs1(1,0);dfs2(1,1);
    //for(int i=1;i<=n;i++) cout<<i<<" "<<sum0[i]<<" "<<sum1[i]<<endl;
    while(m--){
        ll u,v;char c;
        cin>>u>>v>>c;
        ll x=lca(u,v);
        ll H=sum1[u]+sum1[v]-2*sum1[f[x]];
        ll G=sum0[u]+sum0[v]-2*sum0[f[x]];
        if(c=='H'&&H) printf("1");
        else if(c=='G'&&G) printf("1");
        else printf("0");
    }
    system("pause");
    return 0;
}