标签归档:map

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

 

BZOJ 2761: [JLOI2011]不重复数字(map)

Description

给出N个数,要求把其中重复的去掉,只保留第一次出现的数。
例如,给出的数为1 2 18 3 3 19 2 3 6 5 4,其中2和3有重复,去除后的结果为1 2 18 3 19 6 5 4。

Input

输入第一行为正整数T,表示有T组数据。
接下来每组数据包括两行,第一行为正整数N,表示有N个数。第二行为要去重的N个正整数。

Output

对于每组数据,输出一行,为去重后剩下的数字,数字之间用一个空格隔开。

Sample Input

2
11
1 2 18 3 3 19 2 3 6 5 4
6
1 2 3 4 5 6

Sample Output

1 2 18 3 19 6 5 4
1 2 3 4 5 6
map记一下。

 

uvalive 6959 Judging Troubles(双hash模板题)

题目链接

题意:给出2*n个字符串,前n个为一组,后n个为一组。问在两组中都出现的字符串有几个。

map瞎搞搞也可以做,但是为了学一下字符串的双hash,所以我写了hash。

直接把每个字符串hash一下,map记一下数。