Atcoder NOMURA Programming Competition 2020简要题解

A

int main()
{
    int h1=read(),m1=read(),h2=read(),m2=read();
    if (m2<m1) {m2+=60;h2--;}
    int x=60*(h2-h1)+(m2-m1),k=read();
    printf("%d\n",x-k);
    return 0;
}

B

全部填D即可

int n;
char s[N];

int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    int ans=0;
    rep(i,1,n) 
    {
        if (s[i]=='P') putchar('P');
        else putchar('D');
    }
    return 0;
}

C

记\(B_i\)为第\(i\)层的非叶子节点数,那么显然有\(B_i\in[\lceil\frac{A_{i+1}}{2}\rceil,A_{i+1}]\), 倒推求出每层节点数的范围后,再顺序确定每层节点的最大值。

int n,a[200200];
ll L[200200],R[200200];

int main()
{
    n=read();
    rep(i,0,n) a[i]=read();
    if (a[0])
    {
        if ((n==0) && (a[0]==1)) puts("1");
        else puts("-1");
        return 0;
    }
    per(i,n,0)
    {
        L[i]=a[i]+(L[i+1]+1)/2;
        R[i]=a[i]+R[i+1];
    }
    if (L[0]>1) {puts("-1");return 0;}
    ll ans=1,now=1;
    rep(i,1,n)
    {
        now=min(now*2,R[i]);
        ans+=now;
        now-=a[i];
    }
    printf("%lld",ans);
    return 0;
}

D

连边\((i,P_i)\),注意到每个联通块都是基环内向树的形式,考虑通过数环的个数来确定联通块数,进而确定所需边数,具体的,对最终所需的边数\(E\)有\(E=N-C\),其中\(C\)为形成的环数,等价于联通块的个数。

考虑每个环的形成过程,环是由若干个内向树连接而成,具体的,我们假设\(m\)个大小分别为\(a_1,a_2,\cdots,a_m\)的内向树连接形成了一个环,那么方案数有:

[ \begin{cases} a_1-1 & m=1\ (m-1)!\prod a_i & m>1 \end{cases} ]

\(m=1\)的情况需要特判是因为在自己成环的时候不能有自己连向自己的情况,最后还要乘上其它节点任意连边的贡献,即\((N-1)^{K-m}\)(其中\(K\)为\(P=-1\)的节点数)

考虑用dp求出\(\prod a_i\),记\(f_{i,j}\)为考虑了前i棵树,所有大小为\(j\)的环的\(\prod a\),转移显然。之后乘上系数,再用所有情况的总边数和\(N\times(N-1)^K\)减去即可。

注意不要忘记减去一开始就成环的贡献,每个环都是\((N-1)^K\).

实现时使用的变量名和上述过程会有略微的差异。

int n,fa[N],siz[N],m=0,p[N],f[N];

int find(int x)
{
    if (fa[x]==x) return x;
    fa[x]=find(fa[x]);
    return fa[x];
}

int main()
{
    n=read();
    rep(i,1,n) {fa[i]=i;siz[i]=1;}
    rep(i,1,n)
    {
        p[i]=read();
        if (p[i]==-1) m++;
        else
        {
            int x=i,y=p[i];
            int fx=find(i),fy=find(p[i]);
            if (fx!=fy) {siz[fy]+=siz[fx];fa[fx]=fy;}
        }
    }
    f[0]=1;
    int ans=mul(n,qpow(n-1,m));
    rep(i,1,n)
    {
        if (find(i)!=i) continue;
        if (p[i]==-1)
        {
            per(j,n,1)
                f[j]=add(f[j],mul(f[j-1],siz[i]));
        }
        else ans=dec(ans,qpow(n-1,m));
    }
    f[1]=dec(f[1],m);
    int prod=1;
    for (int i=1;i<=m;prod=mul(prod,i),i++)
    {
        ans=dec(ans,mul(f[i],mul(prod,qpow(n-1,m-i))));
    }
    printf("%d",ans);
    return 0;
}

E

找一堆性质的妙妙题。

我们首先可以把所有操作倒过来,对给定序列先算贡献再删去一个数。

接下来会给出一些重要性质:

  • 当这个序列同时存在\(0\)和\(1\)时,会优先删去\(0\).

如果这时删去的是\(1\),那么可以将这个位置向相邻的位置移动,由于除了受影响的两个位置外其他数的位置的奇偶性不变,所以这么做的答案一定不会更劣。

这样的话我们只需要考虑前半部分删\(0\)的方案,对于全是\(1\)的序列很容易计算贡献。

  • 对于两个相邻的\(1\),假设当前序列的长度为\(N\),则这两个数会产生\(N\)的贡献。

这两个数一定是一奇一偶,所以每次操作后都会恰好有\(1\)的贡献。

这样的话这个序列可以看成是\(0\cdots 010\cdots 01\cdots\)

对于每个\(1\),记其前面的\(0\)的个数为\(p\),后面的\(0\)的个数为\(q\),如果这个\(1\)在奇数位上,那么它的贡献的上界是\(\lfloor \frac{p}{2}\rfloor+q\);若在偶数位上,那么贡献上界是\(\lceil \frac{p}{2}\rceil+q\)(注意这里都没有计算未开始删数时的贡献),现在的问题是是否存在一种方案使得所有\(1\)都能取到上界。

答案是存在的,首先删去前缀的\(0\),之后对于每一段\(0\)从左往右删至留下一个(这样能保证删\(1\)之后的\(0\)时这个\(1\)一定是奇数位),在每一段都只有\(1\)个\(1\)时,从右往左删\(0\)即可。

int n;
char s[N];

int main()
{
    scanf("%s",s+1);n=strlen(s+1);
    ll ans=0;
    int c0=0,c1=0;
    rep(i,1,n) 
    {
        if (s[i]=='0') c0++;else c1++;
    }
    int pre=0;
    rep(i,1,n)
    {
        if (s[i]=='0') pre++;
        else
        {
            if (s[i+1]=='1')
            {
                ans+=(c0+1);i++;
            }
            else
            {
                ans+=((i&1)+(c0-pre));
                if (i&1) ans+=(pre>>1);
                else ans+=((pre+1)>>1);
            }
        }
    }
    per(i,c1-1,1) ans+=((i+1)>>1);
    printf("%lld",ans);
    return 0;
}

F

首先考虑什么样的序列可以通过交换操作得到排序。

对于交换相邻元素的操作,显然要去考察所有的逆序对,也就是\(\forall i<j,a_i>a_j,a_i\)和\(a_j\)在二进制意义下只能有\(1\)位不同。

接下来考虑dp,记\(f_{i,j}\)为有\(i\)个二进制位还未确定,序列有\(j\)个数的方案数。考虑枚举最高位是什么,当最高位形如\(00\cdots011\cdots 1\)时,由于已经排好了序,所以对更低的二进制位没有影响。而如果最高位形如\(00\cdots 0|1xxx0|11\cdots 1\)时,注意到中间的段已经形成了逆序对,也就是它们在剩下的二进制位上必须完全一致,那么在转移中可以将其合并成一个二进制数,这种情况可以枚举合并后的序列长度\(k\)进行转移。最后的转移方程如下。

[f{i,j}=(j+1)f{i-1,j}+\sum{k=1}^{j-1}k2^{j-k-1}f{i-1,k} ]

注意到后面的sigma可以通过沿途维护前缀和做到\(O(1)\)转移。所以总时间复杂度是\(O(nm)\)的。

int n,m,f[N][N];

int main()
{
    n=read();m=read();
    rep(i,1,m) f[0][i]=1;
    rep(i,1,n)
    {
        int sum=0;
        rep(j,1,m)
        {
            f[i][j]=add(sum,mul(j+1,f[i-1][j]));
            sum=add(mul(sum,2),mul(f[i-1][j],j));
        }
    }
    printf(&quot;%d&quot;,f[n][m]);
    return 0;
}

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

本周热议
python每日一练之单元测试
zookeeper 实现一个简单的服务注册与发现(C++) 三:服务发现
zookeeper 实现一个简单的服务注册与发现(C++) 二:注册
zookeeper 实现一个简单的服务注册与发现(C++) 一:与zk保持连接
Java+MySQL笔记
一些零散笔记
TCP/IP协议栈相关知识点总结
Dart学习手册
9.ubuntu文件文本编码的查看与转换,乱码问题
C++输入输出流
扩展2
69-django-forms组件源码刨析、cookie与session
67-django-前后端传数据编码格式、ajax传json格式数据、ajax传文件数据、ajax与sweetalert结合二次确认、django自带的序列化组件、批量插入、分页器
66-django-模型层之choices参数、多对多三种创建方式、数据库三大设计范式、Ajax
64-django-模型层(ORM语法)单表查询、常见十几种查询方法、双下划线查询、多表操作、外键字段增删改查、跨表查询
62-django-无名有名分组反向解析、路由分发、名称空间、伪静态、pycharm虚拟环境、django版本区别、视图层之三板斧、JsonResponse、form表单上传文件、FBV与CBV
61-django-数据增删改、orm创建表关系、django请求生命周期流程图、路由层之路由匹配、无名分组、有名分组
60-django-静态文件配置、request对象方法初识、pycharm链接数据库(MySQL)、django链接数据库(MySQL)、orm简介、orm数据增删改查
巴基斯坦 4400 万移动用户信息泄露,黑客欲以 210 万美元比特币价格出售
支付宝杭州健康码出现异常 地铁大厅人满为患
HaowuliaoA

微信扫码关注 HaowuliaoA 订阅号

友情链接

支付猫
链才网-区块链英才
phpEnv集成环境
广州翻译公司
Lion技术博客
花香诱人醉
LyApi框架
凉风有信
快斗博客
佩晨的博客
蛙导
layui
WebIM
layer
layDate
申请友链
QQ联系