思维+启发式合并

活动地址：CSDN21天学习挑战赛

D - Magical Array

昨天确实没想到这个思路，操作1的话需要看一下i-1,i,j,j+1的前缀和，进行完1操作之后，i-1减少了1，i没变，j减少了1，j+1没变，总的前缀和的总和是没变的，而操作2的话多了一个j+2，也就是说j+1减少了1，j+2没变，但前缀和的总和是减少了1的，所以可以用这个发现去得出答案

CodeTON Round 2 (Div. 1 + Div. 2) D(前缀和) E(DP) - 知乎 (zhihu.com)

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=998244353;
ll t,n,m,sum[100005];
int main(){ 
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=n;i++) sum[i]=0;
        for(int i=1;i<=n;i++){
            ll pre=0;
            for(int j=1;j<=m;j++){
                ll x;scanf("%lld",&x);
                pre+=x;
                sum[i]+=pre;
            }
        }
        ll mx=*max_element(sum+1,sum+n+1),mi=*min_element(sum+1,sum+n+1);
        ll id=min_element(sum+1,sum+n+1)-sum;
        printf("%lld %lld\n",id,mx-mi);
    }
    system("pause");
    return 0;
}

1256D - Binary String Minimizing

可以发现只要将0尽可能地向前挪动即可，直接计算出距离然后看看剩下的步数是否足够，不够就前进剩下的步数，然后退出

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=998244353;
ll t,n,k;
string s;
int main(){ 
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&k);
        cin>>s;
        ll ze=0;
        for(int i=0;i<n;i++){
            if(s[i]=='0'){
                if(i-ze<=k){k-=i-ze;swap(s[ze],s[i]);ze++;}
                else {swap(s[i],s[i-k]);break;}
            }
        }
        cout<<s<<endl;
    }
    system("pause");
    return 0;
}

1327C - Game with Chips

一道挺有意思的题，乍一看像是多个点的搜索，但是最多可以走2nm步，这个数字的含义是可以绕整个地图两圈，所以我们可以先把所有点聚集到1,1上，这个步骤花费n-m-2步，然后再绕地图走一圈即可，实践证明都可以这样走，所以其实没有-1这玩意(我一开始还傻傻的写了个搜索，，）

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=998244353;
ll n,m,k,flag,vis[205][205],vs[205][205];
ll dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
string op[4]={"R","L","D","U"};
struct node{
    ll x,y;
}f[205],ss[205];
string ans;
void dfs(ll x,ll y,ll cnt,string s){
    if(s.size()>2*n*m-n-m+2) return;
    if(cnt>=k){
        ans+=s;
        flag=1;return;
    }
    if(flag) return;
    for(int i=0;i<4;i++){
        ll tx=x+dx[i],ty=y+dy[i],val,vss;
        if(!vis[tx][ty]&&tx>=1&&tx<=n&&ty>=1&&ty<=m){
            vis[tx][ty]=1;vss=vs[tx][ty];
            if(vs[tx][ty]) val=1,vs[tx][ty]=0;
            else val=0;
            dfs(tx,ty,cnt+val,s+op[i]);
            vis[tx][ty]=0;vs[tx][ty]=vss;
        }
    }
}
int main(){ 
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=k;i++) scanf("%lld%lld",&ss[i].x,&ss[i].y);
    for(int i=1;i<=k;i++) scanf("%lld%lld",&f[i].x,&f[i].y),vs[f[i].x][f[i].y]=1;
    ll kk=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    if(vs[i][j]) kk++;
    k=kk;
    ans="";
    for(int i=1;i<m;i++) ans+="L";
    for(int i=1;i<n;i++) ans+="U";
    if(n*m-1>=n+m-2){
        for(int i=1;i<=n;i++){
            for(int j=1;j<m;j++){
                if(i&1) ans+="R";
                else ans+="L";
            }
            if(i!=n) ans+="D";
        }
        cout<<ans.size()<<"\n"<<ans<<"\n";
        return 0;
    }
    // ll cnt=0;
    // if(vs[1][1]) vs[1][1]=0,cnt++;
    // vis[1][1]=1;
    // dfs(1,1,cnt,"");
    // if(!flag) printf("-1\n");
    // else{
    //     cout<<ans.size()<<"\n"<<ans<<"\n";
    // }
    system("pause");
    return 0;
}

741D - Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths启发式合并

这个很搞的题目需要的知识：异或在树上的应用，非常熟练的启发式合并；

字母都转换为2进制的形式(1<<(s[0]-'a'),Xor[u]存的是u到1的异或和，u，v这条路径的异或和就是Xor[u]^Xor[v],f[xor[u]]表示的是Xor[u]这个异或值的最大深度，三种更新答案的方式：1.子树的最大路径；2.子树根与子树中某一点的最大路径；3.子树中某两点的路径。

丫的，改了一晚上也没改出来，题解讲的挺不错的，代码真是不大好看，当然也有自己弱鸡的原因在，但是在这么难的题目中，一篇好题解都没有，我也是没想到

我是伞兵！！！

我是伞兵！！！

我是伞兵！！！

题解 CF741D 【Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths】 - Arextre 的博客 - 洛谷博客

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll MAXSIZE=1<<22;
const ll mod=998244353;
ll n,c[500005],f[MAXSIZE+5],ans[500005],son[500005],siz[500005],Xor[500005],fson;
ll cnt,head[1000006];
struct Edge{
    ll from,to,next,w;
}edge[1000006];
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 dfs1(ll u){
    siz[u]=1,son[u]=0;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        Xor[v]=Xor[u]^edge[i].w;
        dfs1(v);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void cal(ll u,ll d,ll keep){
    if(keep==1) f[Xor[u]]=max(f[Xor[u]],d);
    else f[Xor[u]]=0;
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        cal(j,d+1,keep);
    }
}
//rtd为一开始的子树根节点的深度
ll dfs3(ll u,ll d,ll rtd){
    ll res=0;
    if(f[Xor[u]]) res=max(res,f[Xor[u]]+d-(rtd<<1));
    for(int i=0;i<22;i++)
        if(f[Xor[u]^(1<<i)]) res=max(res,f[Xor[u]^(1<<i)]+d-(rtd<<1));
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        res=max(res,dfs3(j,d+1,rtd));
    }
    return res;
}
void dfs2(ll u,ll d){
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
       if(v!=son[u]){
        dfs2(v,d+1);
        ans[u]=max(ans[u],ans[v]);
        cal(v,d+1,-1);
    }
    }
    if(son[u]) dfs2(son[u],d+1),ans[u]=max(ans[u],ans[son[u]]);
    if(f[Xor[u]]) ans[u]=max(ans[u],f[Xor[u]]-d);
    for(int i=0;i<22;i++) 
        if(f[Xor[u]^(1<<i)]) ans[u]=max(ans[u],f[Xor[u]^(1<<i)]-d);
    f[Xor[u]]=max(d,f[Xor[u]]);
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j!=son[u]){
            ans[u]=max(dfs3(j,d+1,d),ans[u]);cal(j,d+1,1);
           
        }
    }
}
int main(){ 
    scanf("%lld",&n);
    for(int i=2;i<=n;i++){
        char s[3];
        ll x;
        scanf("%lld %s",&x,s);
        addedge(x,i,1<<(s[0]-'a'));
    }
    dfs1(1);
    dfs2(1,0); 
    for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
    system("pause");
    return 0;
}