WQIANG & kennyS 的模拟赛

T1T1 T2T2 T3T3 T4T4
题目名称 魔法化肥 kennyS 的命运 偷税 天降横祸
英文文件名 raftraft farcryfarcry taxestaxes destinydestiny
时空限制 1s/256MB1s/256 MB 1s/256MB1s/256 MB 1s/256MB1s/256MB 2s/512MB2s/512MB
评测方式 打包评测 按点评测 按点评测 打包测评
  • 部分题目使用打包评测。
  • Wqiang\sf\textcolor{black}{W} \textcolor{red}{qiang} 认为本次模拟赛非常简单。
  • 请根据自身常数情况使用快读快输
  • 有问题请问出题人,赛后请锕掉写在标题第一个的出题人。

魔法化肥(raft.cpp)

题目背景

6.267.106.26-7.10 这段日子里,是黑心游戏平台 SteamSteam 夏季促销的日子。

Wqiang\sf\textcolor{black}{W} \textcolor{red}{qiang}kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 买了许多游戏。

RaftRaft 这一款游戏中,Wqiang\sf\textcolor{black}{W} \textcolor{red}{qiang} 是一个从名字中都流露出强大的高手。

RaftRaft 里,神 Wqiang\sf\textcolor{black}{W} \textcolor{red}{qiang} 有一块菜园,他把菜园分成了 nn 块菜地并在这些菜地中种上了水稻。由于种水稻的时间不同,整个菜园中每一块菜地的生长周期都错开了,水稻长得参差不齐。神 Wqiang\sf\textcolor{black}{W} \textcolor{red}{qiang} 看到菜园中的水稻参差不齐,十分难受,想让所有水稻长成同一个高度。

每天在水稻进行自然生长之后,Wqiang\sf\textcolor{black}{W} \textcolor{red}{qiang} 可以施展他神奇的魔法(肥料掺了金坷垃,一袋能顶两袋撒,肥料掺了金坷垃,小麦亩产一千八!),这个魔法可以让任意一块菜地中的水稻长高一个单位,或者让任意一块菜地中的水稻缩短一个单位,当然啦,他也可以不进行任何操作。

Wqiang\sf\textcolor{black}{W} \textcolor{red}{qiang} 觉得这道题过水而懒得写,于是这个任务便交给了你来解决,否则你将会收到神 Wqiang\sf\textcolor{black}{W} \textcolor{red}{qiang} 的鄙视。

题目描述

Wqiang\sf\textcolor{black}{W} \textcolor{red}{qiang} 有片编号从 11nn 的菜地,他往每块菜地中都种下了一些水稻,一开始,第 ii 块菜地中的水稻高度均为 aia_i 个单位。水稻的生长周期都是 nn 天,也就是说每逢 nn 天水稻就会长高一个单位。

由于种水稻的时间不同,整个菜园中每一块菜地的生长周期都错开了。具体来说,第 11 天的时候第 11 块菜地中的水稻长高一个单位,第 22 天的时候第 22 块菜地中的水稻长高一个单位....第 nn 天的时候第 nn 块菜地中的水稻长高一个单位,接下来第 n+1n+1 天,又轮到轮到第 11 块菜地中的水稻长高一个单位,以此类推。

Wqiang\sf\textcolor{black}{W} \textcolor{red}{qiang} 每天都能使用一次魔法,请问他最早能在第几天使所有水稻长成同一个高度。

输入格式

第一行是一个正整数 nn,表示有菜园有 nn 块菜地。
接下来一行输入 nn 个正整数,表示每块菜地上水稻的高度。水稻的高度。
数据保证一开始输入时水稻的高度不全都相同且答案至少为 11

输出格式

一个整数,表示最早能在第几天使使所有水稻长成同一个高度。

样例输入

3
1 2 3

样例输出

1

提示说明

对于 $ 50 %$ 的数据,1n100,1ai101\le n\le 100,1\le a_i\le 10

对于 100%100\% 的数据,1n5105,1ai1091\le n \le 5\cdot 10^5,1 \le a_i \le 10^9

kennyS 的命运(farcry.cpp)

题目背景

无事可做的 kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 最近正在玩一款名叫 FarCryFarCry 的游戏

游戏中的 NPCNPC Joseph Seed\sf Joseph\ Seed 向他提出了一个问题,如果在 1s1s 内回答不出,那么这位圣父将会让他的子民们把 kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 关进暗无天日的小黑屋。kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 还想快乐地见到明天的太阳,所以他赶紧找到了你来帮他解决这个问题。

题目描述

有一个长度为 nn 的整数序列,kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS}Joseph Seed\sf Joseph\ Seed 轮流取数,kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 先取。每次他们只能从左端或者右端取任意数量的数,但不能两边都取。所有数都被取走视为游戏结束,然后统计每个人取走的数之和,作为各自的得分。两个人采取的策略都是让自己得分尽可能高,求 kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 的得分减去 Joseph Seed\sf Joseph\ Seed 的得分后的结果。

输入格式

输入包含多组数据。

每组数据第一行为正整数 nn ,第二行为给定的整数序列,

当输入的 n=0n=0 时,输入结束。

输出格式

对于每组数据,输出 kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS}Joseph\sf Joseph Seed\sf Seed 都采取最优策略下,kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 的得分减去 Joseph\sf Joseph Seed\sf Seed 的得分。

样例输入

4
4 -10 -20 7
4
1 2 3 4
0

样例输出

7
10

提示说明

对于 $ 50%$ 的数据点,1n401 \leq n \leq 40

对于 $ 100%$ 的数据点,1n1001 \leq n \leq 100

偷税(taxes.cpp)

题目背景

kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 投资成功,钱包鼓鼓囊囊。

Wqiang\sf\textcolor{black}{W} \textcolor{red}{qiang} 听到了这个令人激动的好消息,决定向 kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 要些零花钱。

当然,神 Wqiang\sf\textcolor{black}{W} \textcolor{red}{qiang} 可不会全都拿走,他告诉 kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} ,只需要将每次收入 nn 的最大因子(不等于 nn)交给他,就可以健健康康的过着快乐生活。

kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 不想损失那么多钱,他决定将钱分成几份,使得要交出的钱最少。由于他太蠢了,所以只能找到你来帮他解决这个问题。

题目描述

给出 kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 的收入,求出他最少要上交的钱是多少。

输入格式

输入包含多组测试数据。

第一行一个正整数 tt 标书数据组数。

接下来 tt 行,每行一个正整数 nn 表示 kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 的收入。

输出格式

输出共 tt 行。

表示对于每一组的 nnkennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 至少要交出多少钱。

样例输入

2
4
27

样例输出

2
3

数据范围与约定

对于 $ 30%$ 的数据点,n20n \leq 20

对于 $ 70%$ 的数据点,n106n \leq 10^6

对于 $ 100%$ 的数据点,1t1041\leq t \leq 10^42n10122\leq n\leq 10^{12}

天降横祸(destiny.cpp)

题目背景

kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 正在游玩 destinydestiny 22

kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 正在遭到许多敌人的围攻,他需要找到神 Wqiang\sf\textcolor{black}{W} \textcolor{red}{qiang} 来帮他解决困难。

kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 并不知道 Wqiang\sf\textcolor{black}{W} \textcolor{red}{qiang} 在哪儿,但是好心的 Limit\sf\textcolor{black}{L} \textcolor{red}{imit} 将要通知他 Wqiang\sf\textcolor{black}{W} \textcolor{red}{qiang} 的具体位置,并且他想要赶快找到通往所有星球的道路各一条并立刻出发。因此对于每一个星球(包括地球本身)他想要知道从地球到那个星球所需的最小钱数。由于 kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 正在逃命,所以这个问题只能由你来解决。

题目描述

kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 有一个传送枪,他用这把枪可以制造出一个从他所在的星球通往其他星球(也包括自己所在的星球)的单行道路。但是由于他还在用免费版,因此这把枪的使用是有限制的。

默认情况下他不能用这把枪开启任何传送门。在网络上有 qq 个售卖这些传送枪的使用方案。每一次你想要实施这个方案时你都可以购买它,但是每次购买后只能使用一次。每个方案的购买次数都是无限的。

网络上一共有三种方案可供购买:

  • 开启一扇从星球 vv 到星球 uu 的传送门;
  • 开启一扇从星球 vv 到标号在 [l,r][l,r] 区间范围内任何一个星球的传送门。(即这扇传送门可以从一个星球出发通往多个星球)
  • 开启一扇从标号在 [l,r][l,r] 区间范围内任何一个星球到星球 vv 的传送门。(即这扇传送门可以从多个星球出发到达同一个星球)

输入格式

输入数据的第一行包括三个整数 nnqqss 分别表示星球的数目,可供购买的方案数目以及地球的标号。

接下来的 qq 行表示 qq 种方案。

  • 输入 1 v u w 表示第一种方案,其中 v,uv,u 如题目描述 ww 表示此方案价格。
  • 输入 2 v l r w 表示第二种方案,其中 v,l,rv,l,r 如题目描述,ww 表示此方案价格。
  • 输入 3 v l r w 表示第三种方案,其中 v,l,rv,l,r 意思同上,ww 表示此方案价格。

输出格式

输出一行用空格隔开的 nn 个整数分别表示从地球到第 ii 个星球所需的最小钱数。

样例输入1

3 5 1
2 3 2 3 17
2 3 2 2 16
2 2 2 3 3
3 3 1 1 12
1 3 3 17

样例输出1

0 28 12 

样例输入2

4 3 1
3 4 1 3 12
2 2 3 4 10
1 2 4 16

样例输出2

0 -1 -1 12 

提示说明

在第一组测试样例里, kennyS\sf \textcolor{black}{k} \textcolor{red}{ennyS} 可以先购买第 44 个方案再购买第 22 个方案从而到达标号为 22 的星球.

对于 $ 20%$ 的数据点,n,m1000n,m \leq 1000

对于另外 20%20\% 的数据点,只有 11 方案。

对于另外 15%15\% 的数据点,没有 22 方案。

对于另外 15%15\% 的数据点,没有 33 方案。

对于 100%100\% 的数据点,1lrn1051\leq l\leq r\leq n\leq 10^51vn1\leq v\leq n1m1051\leq m\leq 10^51w1071\leq w\leq 10^7