首页 > 代码库 > BUPT2017 springtraining(16) #1 题解

BUPT2017 springtraining(16) #1 题解

https://vjudge.net/contest/162590

<style>p.p1 { margin: 0.0px 0.0px 2.0px 0.0px; text-align: justify; font: 14.0px Helvetica; color: #454545 } p.p2 { margin: 0.0px 0.0px 2.0px 0.0px; text-align: justify; font: 14.0px "PingFang SC"; color: #454545 } p.p3 { margin: 0.0px 0.0px 0.0px 0.0px; text-align: justify; font: 12.0px "PingFang SC"; color: #454545 } p.p4 { margin: 0.0px 0.0px 2.0px 0.0px; text-align: justify; font: 14.0px "PingFang SC Semibold"; color: #454545 } span.s1 { font: 14.0px Helvetica } span.s2 { font: 14.0px "PingFang SC" } span.s3 { font: 12.0px Helvetica }</style>

A:

不难发现,当L=R时输出L,当L<R时输出2

B

贪心得配对。1n 2n-1配,对与对直接只要花1个代价就可以跳到。所以答案是(n-1)/2

C:

先考虑形式于aaaab的串变形。若有na,不难看出次数f[n]=2^n-1。接下来我们对于原串S从左到右扫描,若遇到acnt++,若遇到bans+=f[cnt]

D:

构造aabbaabb..的串即可。

E

Ans=max(s[i]). 通过dfs进行染色,对于节点x,集合x中已经被染过色的ice不管它,未被染色的节点从1开始找没用过的颜色染。

因为对于任何兄弟节点x,y 当他们的父亲fa被染过色之后 x,y中未被染色的ice一定不互相影响。(树上ice分布是连续的,若存在互相影响的ice,则这个ice一定也属于fa,那么就已经被染过色了)

F:

f[n]为欧拉函数,所以g[n]=n.

所以只需要做(k+1)/2phi[n]即可

注意到若n为偶数,phi(n)<=n/2(因为偶数不会与n互质),若n为奇数phi(n)一定为偶数。故在log(n)级别内n就会变为1

n=1时直接跳出即可

G:

因为每扇门只有两个开关,所以这两个开关之间的关系是确定的,要么同正同负要么一正一负。我们以开关为节点,进行黑白图染色。边有两种,一种是颜色相同一种是颜色不同。如果推出矛盾则不存在

H:

字符串简单题

BUPT2017 springtraining(16) #1 题解