2022/7/21

今天把黄题做完了，本来还可以开绿题，但是要打cf就明天开吧 

1497C2 - k-LCM (hard version)

这道题花了一个半小时，还是看的题解，，，思路是只管三个数，后面的全是1就行，但是这三个数该如何取写的时候费了老大劲一直不对，最后应该是要分成代码中的三个情况，应该先做简单版本的，简单版本是k恒为3，这样就可以一直想三个数该咋取，而不是朝着构造的方向胡思乱想了

Codeforces #708 Div2_C2. k-LCM (hard version)_欧阳小百合的博客-CSDN博客

#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

自己首推一下可以发现(a[i]+(n-1)x)%n==0(x是某个整数)是成立的，于是就想出第一次l=n,r=n,第二次l=1,r=n-1,第三次l=1,r=n或r=n-1,第一次就是输出-a[n],第二次的值需要枚举出来，但是在测试样例的时候突然发现可以o1的求出来，多测几组就会发现公式是(a[i]%n)*(n-1),第三次输出第二次的值加上a[i]再取个相反数即可

#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期望

可以看出机器人走的格子是循环固定的，k是可以清扫的格子数，z是能走的格子数，工作的概率是p，不工作概率是q=1-p,期望的次数是

pt[1]+q(pt[2]+q(pt[3]+...+q(pt[k]+q(z+pt[1]+...)，表示如果第一个清扫的格子就成功的话就是pt[1],否则就要继续往下看第二个清扫的格子，判断方法和第一个一样假设一个循环节的答案为T，每个循环节的答案一样，则就可以推出答案

CF1623D 题解 - GaryH 的博客 - 洛谷博客 (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 让我们异或吧 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这题只要求出每个点到根节点的异或和就可以 了，答案就是xo[u]^xo[v],因为两个点的相同的路径都异或没了。

#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.com.cn)

其实两个数的异或也就是两个点的距离，处理出每个点的距离后跑一遍最小生成树就可以了

#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 - 洛谷 | lca

处理出每个节点到根节点路径上H的个数和G的个数，用lca求出最近的祖先后，求出祖先到两个点的H，G的前缀和看看是否符合条件即可

#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');//最好加上括号，不然有很大概率出错
    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;
}