ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined)做题记录

雪崩啊。。。FST了两题数组下标打错。。

A. A Serial Killer

B. Sherlock and his girlfriend

随便构造一下,合数为2,质数为1就好了。

C. Molly’s Chemicals

题意:给出n个数字a[]和一个k,求区间和为k的次幂的区间有多少个。N<=1e5,1<=|k|<=10,-1e9<a[i]<1e9。

因为区间和最大为1e14,最小为-1e14,所以这个k的次幂的指数大概不会超过50.把所有的在范围内的K次幂全部算出来。然后维护一个前缀和,把搞过的前缀和放到map里面去。对于每个前缀和都减去一个k次幂的数看是否在Map里能找到就可以了。

D. The Door Problem

题意:有n个门,m个开关,每个门被两个开关控制。给出n个门的初始状态,然后给出每个开关可以控制哪些门。让你判断能否通过操作,可以让所有的门打开。n,m<=1e5

因为每个门都是被两个开关控制,那么把钥匙看成点,门看成边,如果某个门的状态为1,那么也就意味着它所连的两个钥匙必须都选或者都不选。也就是这条边两端的颜色要一样。如果某个门的状态为0,那么他连的两个钥匙必须要只选择一个。也就是这条边两端的颜色不一样。这样建完图后会有一个个连通块,如果每个连通块二染色不会出现矛盾,那么就是可行。否则无解。。。

 

E. The Holmes Children

题意:略。。太长了。。

首先(x,y)满足x+y=n和gcd(x,y)=1的话,那么gcd(x+y,y)=1,所以gcd(n,y)=1.所以满足的y就是。这个反证法证一证就好了。。。f(n)=

然后g()那个函数就是g(n)=n。

然后我们就需要求一个这样的东西,大概是(k+1)/2左右。而这个暴力算logn次就变成1了。。。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注