Problem A: nudun故事集之ATM出的线段树

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 367  Solved: 16

Description

题目背景
ATM的好队友Daota在苦练线段树，于是ATM给Daota出了一道题目，但是Daota表示线段树给做的心态炸裂，你能帮他解决么？
题目描述
已知一个长度为n的数列a[1],a[2]...a[n]，你需要进行m次操作，每次操作为下面两种之一：
1. 1 L R d: 将a[L],a[L+1]...a[R]的每一个数加上d
2. 2 k: 判断

与k的大小关系
其中beautiful(x)为[1,x]中不为x的因数的数的个数
例如:6的因数有[1,2,3,6]，而[4,5]不是6的因数，所以beautiful(6)=2

Input

第一行两个正整数n,m
第二行为n个非负整数，表示a[1],a[2]...a[n] 接下来m行，每行表示上面两种操作之一

Output

对于每个操作2，如果

>=k，输出“YES”，反之输出“NO”

Sample Input

5 3
1 1 1 1 1
2 1
1 2
2 1

Sample Output

NO
YES

HINT

1<=n,m,d,a[i],k<=1e5

1<=L<=R<=n

Problem B: nudun故事集之ATM发现了”st”

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1559  Solved: 257

Description

题目背景
一天，群友说到:“st!”。ATM很疑惑，“到底啥是st呢?”。于是ATM找到了万能的nudun。由于懂得都懂的原因，nudun不能直接告诉ATM什么是“st”，但是nudun在1秒钟之内产生了13个st，并用了一种神奇的加密方式表示。
题目描述
首先nudun产生了一个数组长度为n的a，并给了m次操作，每次操作给出一个区间[l,r]，并将区间内的所有数与运算上w。最后的数组a就是解压的密码。
与运算规则：对于二进制下第i位的a与b进行与操作。
例如，3&2=1,(11)2&(10)2=1 请帮在1秒钟内帮助ATM解决这个问题，作为答谢他会给你一份“st！”。

Input

第一行输入n,m，表示长度为n的数组，和m次操作（1<=n,m<=1e5）
第二行有n个数，第i个数表示a[i]（a[i]<=1e18）
接下来的m行每行三个整数，l,r,w（1<=l<=r<=n,w<=1e18）

Output

输出n个数，表示最后的数组a

Sample Input

2 4
3 0 
1 1 5
2 2 2
1 2 2
1 2 5

Sample Output

0 0

HINT

样例解释： 3&5=1，0&2=0，1&2=0,而之后0无论如何操作结果都是0，所以答案是0 0

这是破解样例后产生的“st”。
 

 

 

Problem C: nudun故事集之ATM开路

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1057  Solved: 81

Description

题目背景
单身富豪widow想要走过这条路，经nudun的介绍找来了ATM来帮忙开路，ATM*成为了苦力工，途中有好多障碍，而ATM体力有限，最多只能推倒一个障碍，请问ATM能为widow提供的最短距离是多少
题目描述
有一个n*m的01矩阵，其中0表示空地，1表示障碍，求从起点s走到终点t最多经过1次障碍的最短距离。

Input

第一行输入6个正整数n，m，x1，y1，x2，y2（1<=x1,x2<=n<=50，1<=y1,y2<=m<=50），代表矩阵的大小为n*m，起点s的位置为（x1,y1），终点t的位置为（x2,y2），题目保证s和t一定是一个空地
接下来n行，第i行输入一个长度为m的01串代表矩阵的第i行

Output

第一行输出最短距离，如果无法从s到达t，输出-1

Sample Input

3 3 1 1 3 3
000
111
000

Sample Output

4

 

Problem D: nudun故事集之edgnb

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 869  Solved: 56

Description

EDG夺冠了，nudun也想庆祝。
nudun有一个长度为n的字符串，仅由小写字母排列而成。他想依次执行以下操作把他的字符串整理成“edgnb”的形状：
1. 从前向后找到第一个长度恰好为5的子串，包含'e','d','g','n','b'五个字符各一次，且此子串不等于"edgnb"。如果不存在，跳到第3步。
2. 重新排列这五个字符，使它们变成"edgnb"（其他字符的位置都没有变化）。然后回到第1步。
3. 结束。
nudun觉得排列字符串太麻烦了，他想请你来帮忙。

Input

一个字符串s，仅由小写字母组成。

Output

输出执行完所有操作后的字符串。

Sample Input

【样例输入1】
gnbnbedg

【样例输入2】
edgnbedgnb

Sample Output

【样例输出1】
edgnbgnb

【样例输出2】
eedgnbdgnb

HINT

【数据规模与提示】

1 <= |s| <= 10000

|s|表示字符串s的长度

 

Problem E: nudun故事集之touch the fish (hard version)

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 625  Solved: 576

Description

题目背景
在zstu里有一个池塘，里面有很多fish，雨停了后nudun与ATM到池塘边touch the fish， 假设池塘中有n条鱼，两人轮流touch the fish，当有人没法touch the fish时便输掉了游戏， 每个人一次最多touch k条鱼，最少touch 一条鱼，而后一次操作touch the fish的数量要不超过前一次操作touch the fish 的数量，请问最终谁能赢得游戏？
题目描述
有n个数，一次最多能取k个，并且下一次取数不超过上一次取数个数，若nudun赢输出“YES”，否则输出“N0”

Input

第一行输入n,k（1<=n,k<=1e18）

Output

若nudun赢输出“YES”，否则输出“N0”

Sample Input

【输入1】
1 1
【输入2】
2 1

Sample Output

【输出1】
YES
【输出2】
N0

 

Problem F: nudun故事集之Ulirs的宝具

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 115  Solved: 4

Description

Ulire有n件对字符串宝具，从1到n编号。
Ulire即将退役。
Ulire想把宝具送给nudun。
但宝具不能直接改变归属，Ulire发现有m条咒语可以改变宝具的归属，吟唱第i条咒语将获得以下一个效果：
1. 如果没有第a[i]件宝具，施法者将获得这件宝具。
2. 如果施法者已经持有第a[i]件宝具，但没有第b[i]件宝具，他将获得第b[i]件宝具。
3. 如果施法者已经持有第a[i]件和第b[i]件宝具，则此次吟唱无任何效果。
如果相同的咒语被吟唱了多次，或者有一条咒语没有被吟唱，Ulire就会觉得无趣。在每条咒语被nudun以任意顺序吟唱恰好一次的情况下，Ulire想知道nudun最多可以获得几件宝具？
注意：有些咒语可能会产生相同的效果，但它们仍被视为不同的。

Input

第一行两个整数n，m (1<=n<=2e5, 0<=m<=2e5)
第二行为m个整数，表示a[1],a[2]...a[m] (1<=a[i]<=n)
第三行为m个整数，表示b[1],b[2]...b[m] (1<=b[i]<=n)

Output

一行一个整数，表示nudun可以获得宝具的最大个数。

Sample Input

【输入样例1】
3 3
2 1 1
2 3 3
【输入样例2】
6 5
1 4 4 4 5
4 2 3 5 1

Sample Output

【输出样例1】
3
【输出样例2】
5

 

Problem G: nudun故事集之XD

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 351  Solved: 3

Description

nudun和ATM在玩一个小游戏。他们面前的桌子上放有n种卡片，每种卡片有一个“XD值”，且每种卡片都有无限张。
nudun和ATM每个人都需要选择恰好k张卡片组成一套卡组，一套卡组的“XD值”为这套卡片内所有卡片“XD值”的总和，他们的选择需要满足以下条件：
1. 对于每个人，每种卡片最多只能取1张
2. 两个人允许拥有同一种卡片
3. 两个人组成的卡组的“XD值”不能相等
4. nudun选完所需的k张卡片后，ATM才能进行选择
nudun和ATM想知道，在这种规则下，两个人能取得的卡组的“XD值”的最大值分别为多少？

Input

第一行一个整数T，表示数据的组数。接下来是T组数据：
每组数据的第一行包含两个空格分隔的正整数n，k——表示卡片的种数以及两人需要选择的卡片数量。
每组数据的第二行是n个整数，第i个整数a_i表示第i种卡片的“XD值”。

Output

对于每组数据，输出一行两个整数，用一个空格分隔。
第一个数表示nudun能取得的卡组的“XD值”的最大值。
第二个数表示ATM能取得的卡组的“XD值”的最大值。
如果没有合法的方案，输出“huaiqilai<=”（不包含引号）。

Sample Input

3
2 1
1145 14
2 2
-114 514
6 3
1 1 4 5 1 4

Sample Output

1145 14
huaiqilai
13 10

HINT

【数据规模与提示】

1 <= T, n <= 100000

1 <= k <= n

|a_i| <= 100000, |x|表示x的绝对值

所有数据中n的和 <= 100000

 

Problem H: nudun故事集之杰哥不要A

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2349  Solved: 634

Description

今天杰哥把nudun，ATM带到家里玩…………
(你在期待什么)
给你两个整数n，k(1<=n<=1000， 0<=k<=9)，求1~n的n个数中，十进制表达下含有数字k的数的个数

Input

一行两个整数n,k(1<=n<=1000， 0<=k<=9)

Output

一行一个数表示答案

Sample Input

【输入样例1】
1 1
【输入样例2】
10 1

Sample Output

【输出样例1】
1
【输出样例2】
2

HINT

(你猜猜谁比较逊？)

 

Problem I: nudun故事集之你真的会数数么

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1837  Solved: 554

Description

今天天才nudun又给傻瓜ATM出了道数数题，傻瓜ATM不会做，需要你的帮助。
对于两个正整数a和b，如果a是b的因数，且a是一个完全平方数，我们称a是b的“平方因数”。
求出1~n中每个数的“平方因数”的个数之和。

Input

输入一个数n（1<=n<=100000）

Output

输出一个数表示答案

Sample Input

【输入样例1】
1
【输入样例2】
2
【输入样例3】
6

Sample Output

【输出样例1】
1
【输出样例2】
2
【输出样例3】
7

HINT

对于第三组数据

1有平方因子1

2有平方因子1

3有平方因子1

4有平方因子1，4

5有平方因子1

6有平方因子1

因此总个数为7

【完全平方数】完全平方指用一个整数乘以自己例如1 * 1,2 * 2,3 * 3等,依此类推。若一个数能表示成某个整数的平方的形式,则称这个数为完全平方数。

 

Problem J: nudun故事集之下雨天

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 198  Solved: 17

Description

题目背景
今天外面又下起了大雨，nudun和ATM被困在实验室出不来了，nudun非常讨厌下雨，因此他想早点回到宿舍，而ATM很享受下雨的感觉，因此他想慢慢走。
题目描述
宿舍的钥匙被分成了n份碎片，他们必须恰好拿到其中的k份才能打开宿舍的门。你可以想象一条x轴，ATM和nudun此时站在x=0的位置；而n份钥匙碎片，第i片放在x=a[i]的位置。x轴上x1、x2两点间的距离为|x1-x2|。
现在，他们需要选择n份碎片中的k份，从起点开始依次到达这k个点，以取得回宿舍需要的钥匙碎片，nudun想要走最短的路，而ATM想要走最长的路，你能帮他们解决么？

Input

第一行给出n,k（1<=n<=2e5, 1<=k<=n） 接下来的一行输入n个数，表示a[i] (|a[i]|<=1e9) （数组a非递减）

Output

输出一行两个数： 第一个为nudun所走路径长度，即最小值； 第二个为ATM所走路径的长度，即最大值； 两个数用一个空格隔开。

Sample Input

4 2
-4 -1 1 4

Sample Output

3 12

HINT

【样例解释】
 

可能存在多条最优路径，只需选择其中一条计算即可。

 

 

Problem K: nudun故事集之约会

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 332  Solved: 117

Description

题目背景
时隔多年，赚了不少达不溜的zmw想要来一场甜甜的恋爱，于是乎他找到了万能的nudun。在情场高手mk23ez66的介绍下,挑选出了n个具有一定魅力值的小姐姐。虽然zmw都非常喜欢，但是并不是所有的小姐姐都想要与zmw进行约会。简而言之，对于第i个小姐姐，她同意与zmw进行约会的条件是从1到i-1中存在任意三个小姐姐的魅力值异或起来为第i个姐姐的魅力值。(可重复选择)，现在，满脑子都是小姐姐的zmw想要你帮他计算他到底能和多少个小姐姐共度良宵。
QwQ
QwQ
QwQ
题目描述
已知一个长为n的序列，序列的第i个数是a[i]。 如果a[i] (i>1)可以表示成a[1],a[2],...,a[i-1]中的任意三个数（同一个数可重复选择）的异或和，则称第i个数为“QwQ数”。现在让你求这个序列中有多少个数是“QwQ数”。
异或（xor）运算规则：在二进制下按位异或，对于每一位 0 xor 0 = 1 xor 1 = 0，1 xor 0 = 0 xor 1 = 1
例如：2 xor 3 xor 5 = (010) xor (011) xor (101) = (100) =4

Input

第一行输入两个正整数n(1<=n<=5000)
第二行输入n个正整数a[i] (0<=a[i]<2^20)

Output

第一行输出“QwQ数”的个数

Sample Input

5
1 2 3 0 3

Sample Output

2

HINT

说明/提示

对于第一组样例：

2不能表示成三个1的异或和，所以a[2]不是“QwQ数”

3不能表示成三个1或2的异或和，所以a[3]不是“QwQ数”

0 = 1 xor 2 xor 3，所以a[4]是“QwQ数”

3 = 1 xor 1 xor 3 ， 2 xor 2 xor 3 ， 1 xor 2 xor 0 ， 3 xor 3 xor 3 ， 3 xor 0 xor 0，所以a[5]是“QwQ数