2022/7/26

1299A - Anu Has a Function

For a bit in binary , if x and y There are , subtract y And then it's gone , if x No, ,y Yes , subtract y And then it's gone , So for every bit of binary, as long as there is redundancy 1 Times will be eliminated , There is 1 Not once , Unless it is the first position , So find out what happened 1 The number of the next highest digit , Just put him in the first place

A. Anu Has a Function( law 、 thinking )_issue yes fw The blog of -CSDN Blog

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=10007;
ll n,a[100005],b[100005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        for(int j=0;j<32;j++)
        if(a[i]&(1<<j)) b[j]++;
    }
    for(int i=31;i>=0;i--){
        if(b[i]!=1) continue;
        for(int j=1;j<=n;j++){
            if(a[j]&(1<<i)){
                swap(a[1],a[j]);
                for(int k=1;k<=n;k++) cout<<a[k]<<" ";
                system("pause");
                return 0;
            }
        }
    }
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    system("pause");
    return 0;
} 

1379A - Acacius and String

I thought there would be some clever way , I didn't expect it to be violence , Violence enumeration "abacaba" Position in string , If it matches, check whether there is anything else to match

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=10007;
ll t,n;
string s;
bool check(string ss){
        ll res=0,x=0;
    while(ss.find("abacaba",x)!=string::npos){
        x=ss.find("abacaba",x)+1;
        //cout<<x<<"--------"<<endl;
        res++;
    }
    //cout<<res<<" ------> "<<s<<endl;
    return res==1;
}
int main(){
    cin>>t;
    string ta="abacaba";
    while(t--){
        cin>>n>>s;
        ll fg=0;
        string ans;
        for(int i=0;i+6<n;i++){
            string ss=s;
            ll flag=1;
            for(int j=0;j<ta.size();j++){
                if(ss[i+j]=='?') ss[i+j]=ta[j];
                else if(ss[i+j]!=ta[j]){flag=0;break;}
            }
            if(flag){
                for(int j=0;j<ss.size();j++) 
                if(ss[j]=='?') ss[j]='z';
                if(check(ss)){fg=1;ans=ss;break;}
            }
        }
        if(fg) cout<<"YES\n"<<ans<<"\n";
        else cout<<"NO\n";
    }
    system("pause");
    return 0;
} 

600E - Lomsat gelral Heuristic merging

It took me a long time to understand , There is a video that feels very good , I feel that this algorithm is an optimized algorithm , For example, in this question , The common practice is dfs Count the colors of all points in the subtree, calculate the answer, and then empty the array to deal with other subtrees , But this algorithm is n Fang , So we need to optimize the complexity , We can find that the last son does not need to empty the array when processing the son node of this point , Because it won't affect other brothers anymore , So we can choose the one with the largest number of child nodes as the last son , That is, the heavy son in tree chain dissection , At the beginning, run all the light sons and figure out the answer of the light son , Clear the array of records after calculation , Then run to the heavy son , Finally, go and run aside all the light sons , Finally, the point and the light son of the point   The answer is merged into the heavy son , The answer to this point is to merge , So the complexity saves the time needed to empty the heavy son , And the number of child nodes of the heavy son is the most , So the complexity is still considerable

Tree heuristic merge summary _p_b_p_b The blog of -CSDN Blog   This blog is very good

Code nonsense _ Bili, Bili _bilibili This video is also good

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=10007;
ll n,c[100005];
ll head[200005],tot;
ll son[200005],siz[200005],cnt[200005],ans[200005],fson,sum,maxx;
struct Edge{
    ll from,to,next;
}edge[200005];
void addedge(ll from, ll to){
    edge[++tot].from = from;
    edge[tot].to = to;
    edge[tot].next = head[from];
    head[from] = tot;
}
void dfs_son(ll u,ll fa){
    siz[u]=1;
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j==fa) continue;
        dfs_son(j,u);
        siz[u]+=siz[j];
        if(siz[son[u]]<siz[j]) son[u]=j;
    }
}
void oper(ll u,ll fa,ll val){
    cnt[c[u]]+=val;
    if(cnt[c[u]]>maxx){// Update Max 
        maxx=cnt[c[u]];
        sum=c[u];
    }
    else if(cnt[c[u]]==maxx) sum+=c[u];// Cumulative maximum 
    for(int i=head[u];i;i=edge[i].next){// Continue to operate on your son 
        ll j=edge[i].to;
        if(j==fa||j==fson) continue;
        oper(j,u,val);
    }
}
void dfs(ll u,ll fa,ll keep){
    // Calculate the answer of the light son , Delete after calculation cnt Count 
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j==fa||j==son[u]) continue;
        dfs(j,u,0);
    }
    // Calculate the answer of the heavy son , Record the node of the heavy son , Do not clear after the calculation cnt Count 
    if(son[u]) dfs(son[u],u,1),fson=son[u];
    // take u and u The answer of the light son is merged into the heavy son 
    oper(u,fa,1);
    fson=0;
    ans[u]=sum;//oper After that sum Namely u The answer 
    if(!keep){
        oper(u,fa,-1);
        sum=maxx=0;
    }
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
    for(int i=1;i<n;i++){
        ll u,v;
        scanf("%lld%lld",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    dfs_son(1,0);
    dfs(1,0,1);
    for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
    system("pause");
    return 0;
} 

P3201 [HNOI2009] Dream pudding - Luogu | Heuristic merging

x Change the color to y Color is equivalent to x Merge sets into y Assemble , If x The color on the left is y Color words ,ans--, If on the left is y If so --, And violent mergers may not pass , So you should merge small sets into large sets every time , use set It's really convenient

Answer key P3201 【[HNOI2009] Dream pudding 】 - doubt The blog of - Luogu blog

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=10007;
ll n,m,a[1000005],res;
set<ll>q[1000005];
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        q[a[i]].insert(i);
        res+=(a[i]!=a[i-1]);
    }
    while(m--){
        ll op,x,y;
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld%lld",&x,&y);
            if(x==y) continue;
            if(q[x].size()>q[y].size()) swap(q[x],q[y]);
            for(auto i:q[x]) res-=q[y].count(i-1)+q[y].count(i+1);
            for(auto i:q[x]) q[y].insert(i);
            q[x].clear();
        }
        else printf("%lld\n",res);
    }
    system("pause");
    return 0;
} 

P3252 [JLOI2012] Trees - Luogu | dfs 

In fact, a very simple question , Light use dfs That's all right. , I also think about how to memorize , How to use dp, I don't understand why I put it dp The label of ,,,

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=10007;
ll n,ans,s,a[100005],val[100005];
vector<ll>v[100005];
void dfs(ll u,ll sum){
    if(sum>s) return;
    if(sum==s){ans++;return;}
    for(int i=0;i<v[u].size();i++){
        dfs(v[u][i],sum+a[v[u][i]]);
    }
}
int main(){
    cin>>n>>s;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        ll x,y;
        cin>>x>>y;
        v[x].push_back(y);
    }
    for(int i=1;i<=n;i++){
        dfs(i,a[i]);
    }
    cout<<ans<<endl;
    system("pause");
    return 0;
}