526互联

AtCoder Grand Contest 025

发布时间 2023-09-27 19:06:23作者: Zhou_JK

A - Digits Sum

按题意模拟即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int INF=1061109567;
int n;
int calc(int x)
{
    int res=0;
    while(x)
        res+=x%10,x/=10;
    return res;
}
int main()
{
    scanf("%d",&n);
    int ans=INF;
    for(int a=1;a<n;a++)
    {
        int b=n-a;
        ans=min(ans,calc(a)+calc(b));
    }
    printf("%d",ans);
    return 0;
}

B - RGB Coloring

可以将 \(A+B\) 的位置看作是既涂了红色也被涂成了蓝色，这样就只有红蓝两种颜色且相互独立了。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=300005;
const int MOD=998244353;
int n,a,b;
long long k;
int ksm(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=1LL*res*a%MOD;
        a=1LL*a*a%MOD,b>>=1;
    }
    return res;
}
int fac[N],inv[N];
void init(int n=300000)
{
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=1LL*fac[i-1]*i%MOD;
    inv[n]=ksm(fac[n],MOD-2);
    for(int i=n;i>=1;i--)
        inv[i-1]=1LL*inv[i]*i%MOD;
    return;
}
int C(int n,int m)
{
    if(m>n) return 0;
    else return 1LL*fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int main()
{
    init();
    scanf("%d%d%d%lld",&n,&a,&b,&k);
    int ans=0;
    for(int i=0;i<=n;i++)
        if((k-1LL*i*a)%b==0&&(k-1LL*i*a)/b>=0&&(k-1LL*i*a)/b<=n)
        {
            int j=(k-1LL*i*a)/b;
            ans=(ans+1LL*C(n,i)*C(n,j))%MOD;
        }
    printf("%d",ans);
    return 0;
}

C - Interval Game

可以发现，Takahashi 只会走到线段的端点。

贪心的考虑，Aoki 有两种选择：

  • 先选择一条 \(l\) 最大的，然后跳到 \(r\) 最小的，再跳到 \(l\) 次大的，依次类推；
  • 先选择一条 \(r\) 最小的，然后跳到 \(l\) 最大的，再跳到 \(r\) 次小的，依次类推；

两种情况里面取个较大值即可。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100005;
const int M=100000;
int n;
int l[N],r[N];
long long solve(int s,bool flag)
{
    vector<int>posl[N+N],posr[N+N];
    for(int i=1;i<=n;i++)
        posl[l[i]].emplace_back(i),posr[r[i]].emplace_back(i);
    static bool vis[N];
    fill(vis+1,vis+n+1,false);
    int i=0,j=M+M;
    int now=s;
    long long ans=0;
    for(int k=1;k<=n;k++)
    {
        if(flag)
        {
            while(j>now)
            {
                while(!posl[j].empty()&&vis[posl[j].back()]) posl[j].pop_back();
                if(posl[j].empty()) j--;
                else break;
            }
            if(j<=now) break;
            ans+=j-now,now=j;
            vis[posl[j].back()]=true;
        }
        else
        {
            while(i<now)
            {
                while(!posr[i].empty()&&vis[posr[i].back()]) posr[i].pop_back();
                if(posr[i].empty()) i++;
                else break;
            }
            if(i>=now) break;
            ans+=now-i,now=i;
            vis[posr[i].back()]=true;
        }
        flag=!flag;
    }
    ans+=abs(now-s);
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&l[i],&r[i]);
        l[i]+=M,r[i]+=M;
    }
    printf("%lld",max(solve(M,false),solve(M,true)));
    return 0;
}

D - Choosing Points

考虑只有一个 \(D\) 的情况。可以发现，如果我们将距离为 \(\sqrt D\) 的点之间连边，这个图一定是一个二分图。

考虑两个 \(D\) 的情况。给两张二分图染色后，每个格子在两张二分图中各有一种颜色。我们可以枚举选中的点第一张图和第二张图中的颜色，共有四种情况，肯定有一种颜色方案的点数至少有 \(n^2\) 个。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<functional>
using namespace std;
const int N=605,M=200005;
const int dir[4][2]={{1,1},{1,-1},{-1,1},{-1,-1}};
int n;
int d1,d2;
int id[N][N];
int fsqrt[M];
void draw(int col[N][N],int d)
{
    vector<int>G[N*N];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int a=0;a*a<=d;a++)
                if(fsqrt[d-a*a]!=-1)
                {
                    int b=fsqrt[d-a*a];
                    for(int k=0;k<4;k++)
                    {
                        int x=i+a*dir[k][0],y=j+b*dir[k][1];
                        if(x<1||x>n||y<1||y>n) continue;
                        G[id[i][j]].emplace_back(id[x][y]);
                    }
                }
    static int c[N*N];
    memset(c,-1,sizeof(c));
    function<void(int,int)>dfs=[&](int u,int col)
    {
        if(c[u]!=-1) return;
        c[u]=col;
        for(int v:G[u])
            dfs(v,col^1);
        return;
    };
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(c[id[i][j]]==-1) dfs(id[i][j],1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            col[i][j]=c[id[i][j]];
    return;
}
int col[2][N][N];
int main()
{
    scanf("%d%d%d",&n,&d1,&d2);
    n=n*2;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            id[i][j]=(i-1)*n+j;
    memset(fsqrt,-1,sizeof(fsqrt));
    for(int i=0;i*i<=max(d1,d2);i++)
        fsqrt[i*i]=i;
    draw(col[0],d1);
    draw(col[1],d2);
    vector<pair<int,int>>pos[2][2];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            pos[col[0][i][j]][col[1][i][j]].emplace_back(i,j);
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            if((int)pos[i][j].size()>=n*n/4)
            {
                for(int k=0;k<n*n/4;k++)
                {
                    auto [x,y]=pos[i][j][k];
                    printf("%d %d\n",x-1,y-1);
                }
                return 0;
            }
    return 0;
}

E - Walking on a Tree

考虑贪心。

对于一条边 \((u,v)\)，\(v\) 为 \(u\) 的父亲：

  • 如果经过 \((u,v)\) 的路径条数等于 \(0\)，可以直接删除 \((u,v)\)，这条边的贡献为 \(0\)。
  • 如果经过 \((u,v)\) 的路径条数等于 \(1\)，可以将那条路径的端点 \(u\) 改为 \(v\)，这条边的贡献为 \(1\)。
  • 如果经过 \((u,v)\) 的路径条数大于等于 \(2\)，我们随便取出两条路径，不妨令其为 \([a,u],[u,b]\)，令 \(u\to a\) 和 \(u\to b\) 的分叉点为 \(c\)，则 \(u\to c\) 上的所有边的贡献都为 \(2\)，分叉后的部分可以看作是一条 \([a,b]\) 的路径，\([a,u],[u,b]\) 的方向取决于 \([a,b]\) 的方向，其他边端点从 \(u\) 改为 \(v\) 就好了。

从下至上不断删掉叶子就好了。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
const int N=2005;
int n,m;
int u[N],v[N];
vector<int>G[N];
int dep[N];
int fa[N][20];
void init(int u,int father)
{
    dep[u]=dep[father]+1;
    fa[u][0]=father;
    for(int i=1;(1<<i)<=n;i++)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int v:G[u])
    {
        if(v==father) continue;
        init(v,u);
    }
    return;
}
int LCA(int u,int v)
{
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=log2(n);i>=0;i--)
        if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    if(u==v) return u;
    for(int i=log2(n);i>=0;i--)
        if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
set<int>pos[N];
vector<pair<int,int>>edge;
int bel[N*N],rev[N*N];
void dfs(int u,int father)
{
    for(int v:G[u])
    {
        if(v==father) continue;
        dfs(v,u);
    }
    if((int)pos[u].size()==1)
    {
        int id=*pos[u].begin();
        if(edge[id].first!=u) swap(edge[id].first,edge[id].second),rev[id]^=1;
        int a=father,b=edge[id].second;
        pos[u].erase(pos[u].begin());
        pos[b].erase(pos[b].find(id));
        if(a!=b)
        {
            edge.emplace_back(a,b);
            int idn=(int)edge.size()-1;
            pos[a].insert(idn);
            pos[b].insert(idn);
            bel[id]=idn;
        }
    }
    else if((int)pos[u].size()>=2)
    {
        int a,b;
        int ida=*pos[u].begin();
        if(edge[ida].second!=u) swap(edge[ida].first,edge[ida].second),rev[ida]^=1;
        a=edge[ida].first;
        pos[u].erase(pos[u].begin());
        pos[a].erase(pos[a].find(ida));
        int idb=*pos[u].begin();
        if(edge[idb].first!=u) swap(edge[idb].first,edge[idb].second),rev[idb]^=1;
        b=edge[idb].second;
        pos[u].erase(pos[u].begin());
        pos[b].erase(pos[b].find(idb));
        if(a!=b)
        {
            edge.emplace_back(a,b);
            int id=(int)edge.size()-1;
            pos[a].insert(id);
            pos[b].insert(id);
            bel[ida]=bel[idb]=id;
        }
        while(!pos[u].empty())
        {
            int id=*pos[u].begin();
            if(edge[id].first!=u) swap(edge[id].first,edge[id].second),rev[id]^=1;
            int a=father,b=edge[id].second;
            pos[u].erase(pos[u].begin());
            pos[b].erase(pos[b].find(id));
            if(a!=b)
            {
                edge.emplace_back(a,b);
                int idn=(int)edge.size()-1;
                pos[a].insert(idn);
                pos[b].insert(idn);
                bel[id]=idn;
            }
        }
    }
    return;
}
int getr(int v)
{
    if(bel[v]==-1) return rev[v];
    if(getr(bel[v])) swap(edge[v].first,edge[v].second),rev[v]^=1;
    bel[v]=-1;
    return rev[v];
}
bool c0[N],c1[N];
void add(int u,int v)
{
    int s=LCA(u,v);
    while(u!=s)
        c0[u]=true,u=fa[u][0];
    while(v!=s)
        c1[v]=true,v=fa[v][0];
    return;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        G[x].emplace_back(y);
        G[y].emplace_back(x);
    }
    init(1,0);
    edge.resize(m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&u[i],&v[i]);
        edge[i]={u[i],v[i]};
        pos[u[i]].insert(i);
        pos[v[i]].insert(i);
    }
    memset(bel,-1,sizeof(bel));
    dfs(1,0);
    for(int i=0;i<m;i++)
        getr(i);
    for(int i=0;i<m;i++)
        add(edge[i].first,edge[i].second);
    int ans=0;
    for(int i=2;i<=n;i++)
        if(c0[i]&&c1[i]) ans+=2;
        else if(c0[i]||c1[i]) ans++;
    printf("%d\n",ans);
    for(int i=0;i<m;i++)
        printf("%d %d\n",edge[i].first,edge[i].second);
    return 0;
}

F - Addition and Andition

对于每次操作，考虑从大到小加上每个位置的贡献，若 \(s_i=t_i=1\)，对其这一位进行操作后有 \(x_i=y_i=0\)。而 \(i\) 以前的进位最多对 \(i\) 加一，不会影响到 \(i\) 后面的位置。

可以发现，每次操作后 \(s_i=t_i=1\) 的相对位置不会改变。那么就有一个结论：

对 \(i\) 进行 \(k\) 次操作，再对 \(j\) 进行 \(k\) 次操作，其中 \(i\gt j\)，和两个位置轮流进行操作 \(k\) 次效果相同。

除了 \(s_i=t_i=1\) 的操作，均会使得 \(1\) 的数量变少，维护不为 \(s_i=t_i=0\) 的位置，每次跳过为 \(s_i=t_i=0\) 的段就好了。

#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
const int N=4000005;
int n,m,k;
int s[N],t[N];
set<int>pos;
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        scanf("%1d",&s[i]);
    reverse(s+1,s+n+1);
    for(int i=1;i<=m;i++)
        scanf("%1d",&t[i]);
    reverse(t+1,t+m+1);
    for(int i=max(n,m);i>=1;i--)
        if(s[i]==1&&t[i]==1)
        {
            pos.insert(i);
            int ret=k;
            set<int>::iterator it=pos.begin();
            while(it!=pos.end())
            {
                int j=*it;
                if(s[j]>=2||t[j]>=2)
                {
                    if(s[j]>=2) s[j+1]+=s[j]/2,s[j]%=2;
                    if(t[j]>=2) t[j+1]+=t[j]/2,t[j]%=2;
                    pos.insert(j+1);
                    if(s[j]==0&&t[j]==0)
                    {
                        set<int>::iterator p=it;
                        p++;
                        pos.erase(it);
                        it=p;
                    }
                    else if(s[j]==1&&t[j]==1)
                    {
                        if(ret==0) break;
                        set<int>::iterator p=it;
                        p++;
                        if(p!=pos.end())
                        {
                            int nxt=*p;
                            pos.erase(it);
                            it=p;
                            if(ret>nxt-j)
                            {
                                s[j]--,t[j]--;
                                s[nxt]++,t[nxt]++;
                                pos.insert(nxt);
                                ret-=nxt-j;
                                it=pos.find(nxt);
                            }
                            else
                            {
                                nxt=j+ret;
                                s[j]--,t[j]--;
                                s[nxt]++,t[nxt]++;
                                pos.insert(nxt);
                                ret=0;
                                it=pos.find(nxt);
                            }
                        }
                        else
                        {
                            pos.erase(it);
                            int nxt=j+ret;
                            s[j]--,t[j]--;
                            s[nxt]++,t[nxt]++;
                            pos.insert(nxt);
                            ret=0;
                            it=pos.find(nxt);
                        }
                    }
                    else it++;
                }
                else if(s[j]==1&&t[j]==1)
                {
                    if(ret==0) break;
                    set<int>::iterator p=it;
                    p++;
                    if(p!=pos.end())
                    {
                        int nxt=*p;
                        pos.erase(it);
                        it=p;
                        if(ret>nxt-j)
                        {
                            s[j]--,t[j]--;
                            s[nxt]++,t[nxt]++;
                            pos.insert(nxt);
                            ret-=nxt-j;
                            it=pos.find(nxt);
                        }
                        else
                        {
                            nxt=j+ret;
                            s[j]--,t[j]--;
                            s[nxt]++,t[nxt]++;
                            pos.insert(nxt);
                            ret=0;
                            it=pos.find(nxt);
                        }
                    }
                    else
                    {
                        pos.erase(it);
                        int nxt=j+ret;
                        s[j]--,t[j]--;
                        s[nxt]++,t[nxt]++;
                        pos.insert(nxt);
                        ret=0;
                        it=pos.find(nxt);
                    }
                }
                else break;
            }
        }
        else if(s[i]==1||t[i]==1) pos.insert(i);
    int lens=n+k;
    while(lens>1&&s[lens]==0) lens--;
    int lent=m+k;
    while(lent>1&&t[lent]==0) lent--;
    reverse(s+1,s+lens+1);
    reverse(t+1,t+lent+1);
    for(int i=1;i<=lens;i++)
        printf("%d",s[i]);
    printf("\n");
    for(int i=1;i<=lent;i++)
        printf("%d",t[i]);
    return 0;
}