2022/7/26

1299A - Anu Has a Function

对于二进制中的某一位，若x和y都有，减去y后就没了，若x没有，y有，减去y后也没了，所以对于二进制的每一位来说只要出现多余1次就会被消掉，出现了1次也不行，除非是第一个位置，所以找出出现了1次最高位数的那个数，把他放在首位就可以了

A. Anu Has a Function(规律、思维)_issue是fw的博客-CSDN博客

#include 
#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<
    }
    for(int i=31;i>=0;i--){
        if(b[i]!=1) continue;
        for(int j=1;j<=n;j++){
            if(a[j]&(1<
                swap(a[1],a[j]);
                for(int k=1;k<=n;k++) cout<" ";
                system("pause");
                return 0;
            }
        }
    }
    for(int i=1;i<=n;i++) cout<" ";
    system("pause");
    return 0;
} 
 

1379A - Acacius and String

我以为会有什么巧的方法，没想到就是暴力，暴力枚举"abacaba"在字符串中的位置，如果匹配就检查一下还有没有别的可以匹配的

#include 
#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<
        res++;
    }
    //cout< "<
    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
            string ss=s;
            ll flag=1;
            for(int j=0;jsize();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;jsize();j++) 
                if(ss[j]=='?') ss[j]='z';
                if(check(ss)){fg=1;ans=ss;break;}
            }
        }
        if(fg) cout<<"YES\n"<"\n";
        else cout<<"NO\n";
    }
    system("pause");
    return 0;
} 
 

600E - Lomsat gelral启发式合并

看了好久才明白点，有个视频感觉讲的很好，感觉这个算法是一个优化的算法，比如在这个题中，普通的做法就是dfs将子树里所有的点的颜色统计出来算出答案然后清空数组再去处理别的子树，但这个算法是n方的，所以需要优化复杂度，我们可以发现在处理该点的儿子节点时最后一个儿子是不需要清空数组的，因为它不会再去影响别的兄弟了，所以我们可以选择子节点个数最多的那个当成最后一个儿子，也就是树链剖分中的重儿子，一开始先去跑所有的轻儿子算出轻儿子的答案，算完之后要清除记录的数组，然后再去跑重儿子，最后再去跑一边所有的轻儿子，最后将该点和该点的轻儿子的 答案合并到重儿子上，合并完就是该点的答案了，所以复杂度省了清空重儿子所需的时间，并且重儿子子节点个数最多，所以复杂度还是很可观的

树上启发式合并总结_p_b_p_b的博客-CSDN博客 这个博客讲的挺好的

代码瞎讲_哔哩哔哩_bilibili这个视频讲的也不错

#include 
#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]]
    }
}
void oper(ll u,ll fa,ll val){
    cnt[c[u]]+=val;
    if(cnt[c[u]]>maxx){//更新最大值
        maxx=cnt[c[u]];
        sum=c[u];
    }
    else if(cnt[c[u]]==maxx) sum+=c[u];//累加最大值
    for(int i=head[u];i;i=edge[i].next){//对儿子继续操作
        ll j=edge[i].to;
        if(j==fa||j==fson) continue;
        oper(j,u,val);
    }
}
void dfs(ll u,ll fa,ll keep){
    //算轻儿子的答案，算完之后删除cnt计数
    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);
    }
    //计算重儿子的答案，记录重儿子的节点，算完之后不清除cnt计数
    if(son[u]) dfs(son[u],u,1),fson=son[u];
    //将u和u的轻儿子的答案合并到重儿子上
    oper(u,fa,1);
    fson=0;
    ans[u]=sum;//oper之后的sum就是u的答案了
    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
        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] 梦幻布丁 - 洛谷 | 启发式合并

x颜色换成y颜色就相当于将x集合合并到y集合呀，如果x颜色左边是y颜色的话，ans--,如果左边是y的话也要--，并且暴力合并可能过不去，所以每次应该将小集合合并到大集合中去，用set做真是非常方便

题解 P3201 【[HNOI2009]梦幻布丁】 - 疑问 的博客 - 洛谷博客

#include 
#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;
setq[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]树 - 洛谷 | dfs 

其实很简单的一道题，光用dfs就可以了，自己还去想如何记忆化，如何去用dp，没大明白为什么要放上dp的标签，，，

#include 
#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];
vectorv[100005];
void dfs(ll u,ll sum){
    if(sum>s) return;
    if(sum==s){ans++;return;}
    for(int i=0;isize();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
        ll x,y;
        cin>>x>>y;
        v[x].push_back(y);
    }
    for(int i=1;i<=n;i++){
        dfs(i,a[i]);
    }
    cout<
    system("pause");
    return 0;
}