首页 > 其他分享 >AtCoder Grand Contest 025

AtCoder Grand Contest 025

时间：2023-09-27 19:16:17浏览次数：45  
标签：AtCoder nxt int Contest pos 025 edge include id

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;
}

标签：AtCoder,nxt,int,Contest,pos,025,edge,include,id
From： https://www.cnblogs.com/zhou-jk/p/17733473.html

相关文章

  • AtCoder Grand Contest 026
    A-ColorfulSlimes2可以发现，对于连续的一段长度为\(m\)的相同的字符，我们可以花费\(\lfloor\frac{m}{2}\rfloor\)的代价将它改为符合要求的。#include<iostream>#include<cstdio>usingnamespacestd;constintN=105;intn;inta[N];intmain(){scanf("%d"......
  • AtCoder Grand Contest 022
    A-DiverseWord如果至少有一个字符没有出现过，只要在原字符串后面加入一个没有出现过的字符中最小的那个字符就好了。如果所有字符都出现过，找到一个尽量靠后的位置\(i\in[1,n)\)，使得\(s_i\lts_{i+1}\)，最优字符串将\(s_i\)换成\([i+1,n]\)里面比\(s_i\)大的最小的那个......
  • AtCoder Grand Contest 023
    A-Zero-SumRanges令\(s_n=\sum\limits_{i=1}^na_i\)，相当于找满足\(l\ler,s_r-s_{l-1}\)的点对\((l,r)\)的个数，直接搞就完事了。#include<iostream>#include<cstdio>#include<unordered_map>usingnamespacestd;constintN=200005;intn;inta[N]......
  • AtCoder Grand Contest 024
    A-Fairness每次操作后\(a_i-b_i=b_{i-1}-a_{i-1}\)，对\(k\)的奇偶性讨论一下即可。#include<iostream>#include<cstdio>usingnamespacestd;inta,b,c;longlongk;intmain(){scanf("%d%d%d%lld",&a,&b,&c,&k);if(k%2==0)......
  • AtCoder Grand Contest 021
    A-DigitSum2要么是\(n\)要么是\(n\)的第一位后面加上若干个\(9\)。#include<iostream>#include<cstdio>#include<cmath>usingnamespacestd;longlongn;intcalc(longlongx){if(x==0)return0;intsum=0;while(x)sum+=x......
  • AtCoder Regular Contest 102
    C-TriangularRelationship枚举\(a\bmodk\)的值，\(b\bmodk,c\bmodk\)的值也就确定了，算下贡献就好了。#include<iostream>#include<cstdio>usingnamespacestd;intn,k;intmain(){ scanf("%d%d",&n,&k); longlongans=0; for(inta=0;......
  • ACL Contest 1
    A-ReachableTowns现把城市按照\(x_i\)排序将第一维去掉。对于每个联通块，将单调栈将每个联通块中\(y_i\)最小的那个存下来。每次新加入一个点\(i\)相当于前面的\(\lty_i\)的位置合并成一个联通块。具体地，将单调栈中所有\(\lty_i\)的点弹出，并查集合并一下，加入弹出......
  • AtCoder Regular Contest 103
    C-////如果奇数和偶数出现的颜色的最大值相同一边取最大值和一边取次大值，否则两边都选最大值即可。#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintN=100005;intn,m;intv[N];intc[N];intmain(){ scanf("%d",&n); for(in......
  • DISCO Presents Discovery Channel Code Contest 2020 Qual
    A-DDCCFinals直接模拟即可。#include<iostream>#include<cstdio>usingnamespacestd;intx,y;intmain(){ scanf("%d%d",&x,&y); intans=0; if(x==1)ans+=30; elseif(x==2)ans+=20; elseif(x==3)ans+=10; if(y==1)ans+=30; ......
  • diverta 2019 Programming Contest
    A-ConsecutiveIntegers答案为\(n-k+1\)。#include<iostream>#include<cstdio>usingnamespacestd;intn,k;intmain(){ scanf("%d%d",&n,&k); printf("%d",n-k+1); return0;}B-RGBBoxes枚举\(r,g\)，判断一下对应的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99