月度归档:2017年02月

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了。。。

 

Codeforces Round #401 (Div. 2)做题记录

A. Shell Game

发现6次为一个位置的循环节,打表。。。

B. Game of Credit Cards

第一问的贪心就是莫里亚蒂的每个数字要尽量大于等于福尔摩斯的数字。记录下来福尔摩斯的十个数字的出现次数,并对每个人的数字排序。贪心的想法是莫里亚蒂的每个数字i从0到i一次找是否在福尔摩斯的数字中存在过就好了。

第二问贪心的想法是田忌赛马了。。。但是首先如果莫里亚蒂的最小数字大于福尔摩斯的最小数字肯定要选最小的,最大的大于福尔摩斯最大的选最大的。

C. Alyona and Spreadsheet
题意:给出一个n*m的数字矩阵(n*m<=100000),给出k个询问(k<=100000),询问形式是l,r。代表询问从第L行开始到第R行为止,是否存在一列是非单调递减的。是输出YES,否输出NO。
预处理出来每个位置最上可以延伸到哪一个位置,然后做一个n*m的dp就可以了。dp[i][j]代表(i,j)这个位置左边所有列中最上可以延伸到的位置。然后每次就可以O(1)回答了。

D. Cloud of Hashtags

题意:略。

从后往前贪心,如果对于第i个字符串发现第i+1个字符串字典序比它小,这也就意味着他需要把它从哪个字符开始字典序变小的字符全部删去。当然如果出现长度上的问题,多余的也需要删去。。。发现cin实在是太慢了,cin用了1400ms,scanf只需要148ms。。。。。

E. Hanoi Factory

题意:给出N个圆环(N<=100000),每个圆环有三个属性:a,b,h。a是内圆环半径,b是外圆环半径,h是这个圆环的高度。如果两个圆环i可以摆到j上面去,要求i的b要小于等于j的b。而且j的a要小于i的b,求最高高度。

比赛的时候想的dp啊。。。没写出来实在是自己太菜了。。。

对dp[i]代表第i个圆环的最大高度。先按照b降序排序吧,如果b相同就按照a降序排序,因为如果b相同的话肯定a越大的在最下面。然后把所有圆环的a和b离散化一下。然后每次对于第i个圆环,我们需要知道a小于他的b所有的圆环的最大的dp值。这个可以用线段树logn解决。

 

BZOJ 1044: [HAOI2008]木棍分割(二分+dp)

Description

  有n根木棍, 第i根木棍的长度为Li,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连
接处, 砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小, 并且输出有多少种砍的方法使得总长
度最大的一段长度最小. 并将结果mod 10007。。。

Input

  输入文件第一行有2个数n,m.接下来n行每行一个正整数Li,表示第i根木棍的长度.n<=50000,0<=m<=min(n-1,10
00),1<=Li<=1000.

Output

  输出有2个数, 第一个数是总长度最大的一段的长度最小值, 第二个数是有多少种砍的方法使得满足条件.

Sample Input

3 2
1
1
10

Sample Output

10 2

HINT

两种砍的方法: (1)(1)(10)和(1 1)(10)

整个题看上去和某次cf的C很像。。。

第一问的话二分最大长度,贪心的判断是否可以保证在m段内凑完。

第二问肯定dp了。dp[i][j]代表前j个木棒组成了i段的方案数,,其中a[k+1]+….a[i]应该小于等于第一问求出来的答案。但这样的话是O(n^2*m)的时间复杂度,而且空间复杂度是O(n*m)也炸了。

其实空间优化的话,就是因为每次转移其实只和上一段的dp值有关滚动数组就可以了。

时间上的优化,因为发现每次求dp值的时候相当于求取一段区间和,想到之前玲珑杯用前缀和维护一下就可以了。然后其实随着j值的增加,k的最小值也是单调不递减的。。所以我们可以类似像单调队列那样维护这个最小的位置,统计上一轮答案的前缀。如果出现当前位置不符合的情况减去就可以了。

但是还是有些细节的。初始化dp[0][]其实代表的是形成1段的方案数。而且其中有取模中的减法,所以可能出现负数,需要处理好。。。

发现我写的常数特别大。。。。