526互联

师大 2023 月赛题解

发布时间 2023-06-11 21:10:13作者: xiehanrui0817

A 德军坦克数量

Background

第二次世界大战中，由于战况的激烈与残酷，双方的人员和军备都有惊人的损失。盟军方面发现一个有趣的事实：可能是出于严谨，德国人每月生产的坦克都是从1开始依次往后编号。假设某个月一共生产了\(N\)辆坦克，则这批坦克的编号就是从\(1\)到\(N\)。这使得通过观察坦克编号从而推断坦克产量成为了可能。事实上，盟军每次打扫战场的时候，随机抽查了被击毁的德国坦克编号，并请数学家进行了估计。战后证明，数学家的估计结果比根据情报人员获取的情报进行推断的结果更加准确。正因为此，目前凡是有需要的地方，其产品均不会采用连续编号。

Description

给定\(N\)个被击毁的德军坦克编号，合理的推断当月德军坦克的产量。为简便起见，不考虑其他月份，即保证这\(N\)个编号全部都是当月的。另外，这是一个统计学里的点估计问题。采用不同的假设，显然可能导致不同的估计结果。因此，本题的答案不唯一，只要你能输出有道理的输出即可。当然考虑到情报人员获取到的最大数目是\(1400\)，因此请你的推断不要超过\(1000\)。

Format

Input

第一行是一个int，记作\(N\)，满足\(1\le{N}\le{5}\)。第二行是\(N\)个不超过\(1000\)且互异的正整数。

Output

输出一行，为一个正整数，表示你推断的结果。

Samples

5
215 90 256 248 60

306

Limitation

1s, 1024KiB for each test case.

Note

样例为采用不放回抽样估计离散型均匀分布的最大值的结果。

B 中国炮兵的射程

Background

根据百度百科，中国是世界上少数还保留有炮兵师的国家之一。由于历史原因，我们深知陆军火力的重要性，所以一直以来炮兵都是我军的重点发展对象。中国的炮兵不仅仅是编制人数最多，无论装备型号还是火力覆盖面等，在世界上都是最猛的。但是大炮原则上不是一种精确制导武器，炮弹发射之后只能在重力和空气阻力的作用下行进。因此为了扩大射程，需要增加装填量、延长炮身、加固炮管。为了方便起见，忽略空气阻力，且认为地面是水平无限大的。重力加速度认为是10，国际标准单位制。假定大炮为原点，且看做是一个质点（这个词很熟悉啊，有没有？）。大炮可以以任意仰角、任意初速度发射炮弹。假定炮管长度忽略不计，即炮弹直接从原点出发。距离原点右方L处，有一高度为H的山（山认为是一条竖直的线段，没有宽度）。问，为了使炮弹越过山峰，炮弹的最小发射速度是多少。

Description

给定\(L\)和\(H\)，求炮弹越过山峰的最小初速度。精度控制在\(10^{-3}\)即可。即你的答案与标准答案误差小于\(10^{-3}\)即认为正确。

Format

Input

首先输入一个不超过100的正整数\(N\)，表示测试样例的数量。接下来\(N\)行，每行是一个样例，分别是\(L\)和\(H\)。均为不超过100的正整数，涵义如上。均为国际标准单位制。

Output

对每一个样例输出一行，为一个实数，当然整数也可以，表示答案，为炮弹的最小初速度。

Samples

1
100 1

31.7812837807

Limitation

1s, 1024KiB for each test case.

C 植树节的日期

Background

根据2023年3月12日发布的《2022年中国国土绿化状况公报》：2022年全年完成造林383万公顷，种草该量321.4万公顷，治理沙化石漠化土地184.73万公顷。该报告于3月12日发布时很显然的，因为这一天是植树节。不过植树节并非中国独有，根据百度百科，

国家 国家缩写 植树节日期
中国 Z 3月12日
朝鲜 C 4月6日
泰国 T 9月24日
菲律宾 F 9月的第二个星期六
巴基斯坦 B 8月4日
叙利亚 X 12月的最后一个星期四
约旦 Y 1月15日

特别提示，2023年5月27日是星期六。

Description

给定一个日期，问距离该日期最近的植树节是哪个国家的。已经过去的和即将到来的均可。国家仅限于上述列表中的。

Format

Input

首先输入一个不超过400的正整数\(T\)，表示一共有\(T\)个测试用例。其后还有\(T\)行。每一行是一个形如\(yyyy-MM-dd\)的字符串，分别表示年月日。中间用一个减号作为分隔。其中年份必然在\(2000\)到\(2023\)之间。月、日必然合法。

Output

对每一个日期，输出一行，为距离最近的植树节的国家缩写。如果有多个答案，输出字典序最小的那个。注意，要输出大写字母。

Samples

3
2020-3-11
2020-3-12
2020-3-13

Z
Z
Z

Limitation

1s, 1024KiB for each test case.

D 树上前驱后继关系

Background

这是一个简单的数据结构题，相信出题人。

Description

给定一个\(N\)节点的树，有如下2种操作：

  • 1 u v: 查询u和v的关系，如果u是v的祖先，输出Ancestor，如果v是u的祖先，输出Descendent，如果都是不是输出None；
  • 2 u: 将一个新节点作为u的子节点连接到u，新节点将顺次编号。

树根编号始终是1。

Format

Input

输入首先是一个正整数\(N\)，满足\(1\le{N}\le{10^5}\)。
然后还有\(N-1\)行，每一行为2个正整数\(u,v\)，满足\(1\le{u,v}\le{N}\)，表示\(u,v\)之间有一条边。
再接下来一行是一个正整数\(Q\)，满足\(1\le{Q}\le{10^5}\)。
再接下来是\(Q\)行，每行表示一个询问，格式为如上。
将当前节点总数记作\(M\)，\(M\)显然等于\(N\)加上迄今为止操作2的数量。
对每一个操作1，保证\(1\le{u,v}\le{M}\)，且保证\(u,v\)至多只有一个大于\(N\)，且\(u\ne{v}\)。
对每一个操作2，保证\(u\)要么是初始树中的叶子节点，要么\(u\gt{N}\)。

Output

对每一个操作1输出一行，为查询结果。

Samples

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

Ancestor
Descendent

Note

初始时树只有3个节点，经过2个操作2以后变成了5个节点。深色节点是后加上去的节点，根据执行的顺序依次编号为\(4,5\)。

Limitation

1s, 1024KiB for each test case.

E 哥德巴赫猜想与西班牙电影

Background

最近看了一部西班牙电影（如果在B站上看也算看的话），其讲述了一个研究了一辈子哥德巴赫猜想的老数学家被另外一个宣称证明了哥德巴赫猜想但其实并没有的年轻的数学家误导从而以为自己的证明哥德巴赫猜想的论文发表将晚于那个年轻人的事实上并不存在的论文所以试图谋害这个年轻人的故事。

所以这个电影跟这个题目有一毛钱关系吗？有的，如果你也看了电影的话。

Description

有3个盒子，为了方便起见，就命名为\(1,2,3\)。

有2种糖，为了方便起见，就命名为\(1,2\)。

规则是：只装糖1的盒子应该是盒1，只装糖2的盒子应该是盒2，两种糖混合装的盒子应该是盒3（如果你会位运算的话，你会觉得这样标号很合理）。

但是，这个老数学家非常的阴险，他故意将所有盒子都装错了。也就是说盒1有可能只装糖2，或者糖1、糖2混合，绝不会只装糖1；盒2同理；盒3要么只装糖1，要么只装糖2，绝不会混合装。

现在给你一个机会，来辨别三个盒子中到底装的什么。

你最多可以执行2次查询操作。每一次操作，可以指定1个盒子，从中拿出一个糖。当然拿出来的这颗糖，其种类就被知晓了。

最多2次查询操作之后，请回答每个盒子中到底装的什么糖。

注意：

  1. 2次查询操作可以选同一个盒子；
  2. 如果选装混合糖的盒子，则等概率的得到\(1,2\)中的任意一种；且多次选择的概率独立同分布。

本题是交互题。请详细阅读输入输出要求。

Input and Output

本题是交互题。你有两种合法的输出格式：

  1. ? x: 其中\(1\le{x}\le{3}\)，表示查询操作，即从指定盒子中取出一颗糖，此时会返回该糖的类型，必然是\(1\)或者\(2\)。
  2. ! x y z: 其中\(x,y,z\)是\(\{1,2,3\}\)的一个排列，分别表示盒1、2、3所装糖的种类，其中糖1和糖2分别就用\(1,2\)表示，混合糖用数字\(3\)表示。

请务必保证每次输出一个操作之后，进行换行！！！

任何不按规定的输出，都会导致莫名的错误。不按规定的输出包括但不限于：操作1多于2次，没有操作2，操作1中的\(x\)范围不对，操作2输出不是\(3\)的排列……

另外请阅读以下几点：

  1. 如果你用的是Python，使用print和input输入输出即可；
  2. 如果你使用的是Java，使用System.out.println与Scanner输入输出即可；
  3. 如果你用的C++，使用cin和cout即可，换行使用endl最佳，'\n'也行；
  4. 如果你使用的是C或者在C++中使用了printf，请务必按照第6条的做，否则会有奇怪的错误；
  5. 如果你使用的是其他语言，祝你好运；
  6. 你提交的代码每执行完一次输出操作之后，最好刷新IO流，不同语言刷新IO流的方法如下。
语言 方法
C fflush(stdout);
C++ cout.flush();
Java System.out.flush();
Python stdout.flush()
Pascal flush(output)

以C语言为例，每调用一个printf语句，紧接其后调用一次fflush(stdout);语句。

Samples

input output
? 1
1
! 3 1 2

Note

样例说明：第一次操作查询盒1里的一颗糖，发现是糖1，根据题意，盒1必然装的是混合糖，则盒2必然装的是糖1，盒3装的必然是糖2。

虽然本关没有输入，但是一共有7个样例。也就是说你的提交会拿去测7次，每次测试均是独立的。

Limitation

1s, 1024KiB for each test case.

F 扫雷

这是一道交互题

Background

Hex正在玩扫雷，但是他不太聪明玩不下去了，需要你来帮他找到所有的雷的位置。

Description

在一副扫雷地图上包含三种类型的字符。

  • . 表示地图上还未打开的格子
  • * 表示地图上被标记为地雷的格子
  • 0-8 表示地图上这个被打开的非雷的格子周围的雷的数量。

例如，这是一个合法的地图。

00001..100
00012..210
0001*..*10
0001111.10
0000001.21
0000002...
0001123...
0001*.*...
0001122...
0000001...

为了防止奇怪的致命二选一出现，保证最初的地图已经将四个角和所有的 0 格子揭示，并且最初的地图也不会有 *，需要你自己添加。

经过Hex的脑动筛选，应该不会出现致命二选一的情况。

虽然在描述中地图里可以出现 0-8 ，但是数据保证不会出现包含 4-8 的字符，在实际上地图里只会包含 0-3。

数据保证有唯一解，意思是保证你能够通过已有的信息来得到新的信息，又通过新的信息进一步更新地图，以此往复直到整个地图都被揭示或标记。

例如，下面这个地图就是非法的，因为中间四个未揭示的格子绝对无法确定结果。

111111
1*22*1
12..21
12..21
1*22*1
111111

下面这种情况是合法的，左边第一张地图是最初的地图，之后是一步一步逐渐揭示地图的过程，数据保证每次都能进行下去，并且答案是唯一的。

01..1     01..1     01..1     01*.1     01*21
12...     12...     1222.     1222*     1222*
..111  →  .*111  →  1*111  →  1*111  →  1*111
11100     11100     11100     11100     11100
00000     00000     00000     00000     00000

Interaction

最初，第一行Hex会告诉你 \(n,m,num(3\leq n,m \leq 10, 1\leq num \leq \lceil \frac{n*m}{10} \rceil )\) 表示地图的大小为 \(n*m\)，并且地图里包含 \(num\) 个地雷。
接下来的 \(n\) 行每行 \(m\) 个字符，表示最初的地图，保证四个角落已经被揭示。

接下来你的可以进行四种操作

  • ? 1 x y 表示将 \((x,y)\) 这个点标记为地雷，如果这个点不是地雷，那么程序会直接结束并判 Wrong Answer；否则在之后的地图中这个位置会被 '*' 代替。
  • ? 2 x y 表示揭示 \((x,y)\) 这个位置，如果这个位置是地雷，那么程序会直接结束并判 Wrong Answer；否则在之后的地图中这个位置会被揭示，并且显示出周围地雷的数量（包括被标记的和未揭示的地雷）。
  • ? 3 交互程序会返回整张地图。
  • end 表示扫雷结束，确保地图上每个位置都被揭示或标记为地雷，之后Hex会检查是否正确，并且一定会结束程序，如果正确那么会判 Accepted，否则会判 Wrong Answer。

需要注意的是，你一共只有 \(n*m\) 次操作的机会，最初被揭示格子不算在操作数里，被揭示的格子重复揭示会算作操作数，被标记为地雷的格子重复标记也会被计入操作次数。
Hex 在 ? 3 次这个操作之后，会告诉你更新后的地图，具体来说是一个包含 \(n\) 行 \(m\) 列满足题意的字符串。

为了避免奇怪的错误请：

尽量使用 cin 和 cout 进行输入和输出!

尽量使用 cin 和 cout 进行输入和输出!

尽量使用 cin 和 cout 进行输入和输出!

  1. 如果你用的是Python，使用print和input输入输出即可；
  2. 如果你使用的是Java，使用System.out.println与Scanner输入输出即可；
  3. 如果你用的C++，使用cin和cout即可，换行使用endl最佳，'\n'也行；
  4. 如果你使用的是C或者在C++中使用了printf，请务必按照第6条的做，否则会有奇怪的错误；
  5. 如果你使用的是其他语言，祝你好运；
  6. 你提交的代码每执行完一次输出操作之后，最好刷新IO流，不同语言刷新IO流的方法如下。
语言 方法
C fflush(stdout);
C++ cout.flush();
Java System.out.flush();
Python stdout.flush()
Pascal flush(output)

以C语言为例，每调用一个printf语句，紧接其后调用一次fflush(stdout);语句。

Example

input output
5 5 2
01.10
01110
00111
001..
001.1
? 1 1 3
? 1 4 4
? 2 4 5
? 2 5 4
? 3
01*10
01110
00111
001*1
00111
end

G 混乱的组队

Background

作为湖南省著名高校，我校的xCPC运动一向开展的非常热烈，各级领导也大力支持。由于组队的策略太复杂，集训队决定采用一种简单粗暴的组队方法。

（1）有一张排名表，排在第1/4/7/10……名次的队员称为A类队员，排在第2/5/8……名次的队员称为B类队员，排在第3/6/9……名次的队员称为C类队员。排名表中，没有并列排名，即每个队员的排名都是唯一的。

（2）每支队伍有且只有一名A类队员作为队长，当然，队长什么的其实无所谓。B类和C类队员上限均为1个，可以没有。也就是说队伍结构类型必然为以下4种之一：A、AB、AC、ABC。

（3）第1/2/3名组成HUNNU1队，第4/5/6名组成HUNNU2队，第7/8/9名组成HUNNU3队，……，最后剩下的人组成最后一个队。

但是这样一来，参赛的各兄弟院校就非常清楚我校的虚实。俗话说，知己知彼，百战不殆。现在被知己知彼了，是极不好的。我们决定将上面的第3条规则修改一下，来一种混乱组队方式：所有的队伍，都不应包含按原规则应该包含的队员。即，HUNNU1队不应包含第1/2/3名中的任何一个队员，HUNNU2队不应包含第4/5/6名中的任何一个队员，……。

当然，头两条规则还是要遵守的。且队伍编号必须从1开始递增。且不能有队员没有参与组队。

Description

众所周知，教练是只会做签到题的。这样一样，教练完全弄不清楚自己的队员是如何组队的。因此给定集训队总人数\(N\)，请你告诉教练一共有多少种不同的混乱组队方式。

两个组队方法是不同的：只需存在某个HUNNUn队，在两个组队方法下所包含的队员不完全相同。注意：我们不考虑队员出现的顺序。即由1/5/9组成的队伍与由9/5/1组成的队伍是相同的。当然，人数不同的组队方案肯定也是不同的。

由于结果可能巨大，只需要输出对\(998244353\)取模后的结果即可。

Format

Input

首先是一行不超过\(1000\)的正整数\(T\)，表示一共有\(T\)个测试样例。

接下来\(T\)行，每行是一个不超过\(10^4\)的正整数，表示队伍的总人数。

Output

输出\(T\)行，对每一个输入，输出胡乱组队方案总数取模以后的结果。

Samples

2
3
6

0
1

Note

第一个测试样例表明一共有\(3\)个人，则只能组成HUNNU1队，因此混乱组队方案为\(0\)个。

第二个测试样例一共有6个人，混乱组队方案只有\(1\)个。即456组成HUNNU1队，123组成HUNNU2队。

Limitation

1s, 1024KiB for each test case.

H 快跑，这是一道模拟题

Background

不知道你有没有听说过JavaBean，或者POJO类。不知道你有没有听说过JSON。没听说过，没有关系。

所谓JSON，指的是这一种以键值对传递信息的轻量级文本格式。典型的JSON格式如下：

{
    "person":{
        "name":"zhangsan",
        "age": 18,
        "height": 1.83,
        "star": true
    }
}

如上表示了一个嵌套JSON的结构。其中person是键，其值又是一个JSON。

该JSON包含4个键值对，其值的类型分别是字符串、整型、实型和bool类型。

JSON的键永远是字符串类型。

所谓JavaBean或者POJO类就是把一个JSON键的格式转换为一个Java class的对象，一个具体的JSON信息则会对应该对象的一个实例。

如上述JSON，对应的JavaBean为

public class Person{
    private String name;
    private int age;
    private double height;
    private bool star;
    public String getName() {return name;}
    public void setName(String name) {this.name = name;}
    public int getAge() {return age;}
    public void setAge(int age) {this.age = age;}
    public double getHeight() {return height;}
    public void setHeight(double height) {this.height=height;}
    public bool getStar() {return star;}
    public void setStar(bool star) {this.star = star;}
}

可以观察到上述Java类与JSON格式是具有高度对应关系的。首先类名是外层JSON的键名，其次该类的4个成员分别对应内层JSON的4个键。

因此这是一个非常机械的代码片段，我们可以使用自动构造工具来生成。

现在这个任务交给你了。

Description

给定一个JSON字符串，生成对应的JavaBean类的代码。保证输入是正确的JSON格式，且符合本题的限制。

本题的JSON只会是一个两层的嵌套JSON，其中最外层JSON必然由一个键值对组成，其键应作为JavaBean类的类名使用，其值又是一个JSON，即内层JSON。

内层JSON由若干个键值对构成。每个键值对之间用一个逗号进行分隔。最后一个键值对之后不会再有逗号。

键和值之间用一个冒号进行分隔。

键必然是双引号包裹的字符串格式，只包含小写英文字母，且长度不超过10。内层键名保证各不相同，且必不等于任意关键字。

值有以下5种类型：

  1. 双引号包裹的字符串类型，字符串可能包含任意可打印字符，保证值字符串的长度不超过10，且大于0；
  2. 普通整型，符合现有C/C++/Java的int类型的整数数字，即数值需要在\([-2147483648, 2147483647]\)之间的整数。注意，只支持十进制写法，不支持八进制、十六进制等；保证没有前导零；但可能有正负号；
  3. 长整型，数值范围超过普通整型的一律定义为长整型；保证没有前导零；
  4. 实数类型，只支持定点数的写法，注意.1和1.之类都是合法的写法；
  5. 布尔类型，只有2种，true和false。

在Java中，这5种类型对应的关键字分别是

  1. String，注意大小写；
  2. int；
  3. long；
  4. double；
  5. bool。

对照样例代码，对代码格式固定如下：

  • 类名和成员函数之前需要加public关键字；
  • 成员前需要加private关键字；
  • 类名首字母大写；
  • 成员名全小写；
  • 成员函数命名以驼峰规则，一律以setXxx或者getXxx命名；
  • 缩进为4个空格；
  • 每个成员或者成员函数写一行；
  • 每个单词之间空1格；
  • 字母与符号之间无需空格，除非另有规定；
  • 函数签名的右圆括号与函数体的左花括号需要空一格；
  • 赋值符号两端需要各空一格；
  • get函数与set函数的写法参照样例；
  • 类中先写成员，成员顺序按照JSON给出的顺序排列；后写成员函数，也按照JSON顺序，同一对get和set，get在前，set在后。

其他未尽事宜，可以在比赛中提问，如果确实为题目描述不清，可能会给予回答。

Format

Input

输入是一行符合JSON格式字符串。

Output

输出有若干行，根据输入内容决定。是具有JavaBean格式的源代码。

Samples

{"person":{"name":"zhangsan"}}

public class Person{
    private String name;
    public String getName() {return name;}
    public void setName(String name) {this.name = name;}
}

Note

本关要求逐字符相同。该空格的地方要空格，该换行的地方要换行。注意最后一个右括号之后需要换行。

另外，大胆的做，评测可能有惊喜。

Limitation

1s, 1024KiB for each test case.

I 部长的时光机

Background

最近我们派出了老、中、青三代选手参加了CCPCFinal。部长作为老年选手，保住了晚节。但是部长不想做老年选手，请教过\(Hex\)爷爷后，部长决定使用时光机来度过师大时光。

时光机可以加速时间的流逝，或者缩短时间的间隔，随你怎么说，主要看你站在哪个参考系上。所以你最好看看下面的例子。

譬如说：部长在4月22日参加了天梯赛，又在5月14日参加了CCPCFinal，这中间隔了23天。所以部长就老了23天。这属于原本的时间流速。

部长使用时光机以后，就可以加快未来的到来。在上面的例子中，部长对这段时间间隔使用最大功率，于是别人需要23天才能从4月22日到达5月14日，但是部长只需要1天即可。这样，部长老的就没有那么快了。当然根据需要，部长也可以调整时光机，使得这段间隔变为2天、3天、4天、……。显然最多是23天，其实就是没有加速。

考虑到时光机显然是利用了某种量子效应的设备，因此不可能把某段时间间隔加速到0.5天、1.5天之类。即时间间隔必须是整数天数。当然，0天也是禁止的，至少1天。

另外，时光机的作用是有后效的，即每次操作之后，如果没有后续别的操作，则会一直以当前时间流速进行。

最后，时光机只能加速，不能减速。难道有人会想多老一点吗？

假设部长进了学校以后除了打比赛就没有干过别的有意义的事情，因此给定所有比赛的时间节点，问部长最少需要多少天完成整个大学时光。

Description

为了方便起见，我们并不给出实际的日期，只是用一根坐标轴来表示时间。时间起点为0，表示入学时刻，且必然没有比赛。坐标\(x\)即代表第\(x\)天有一场比赛。

Format

Input

共有\(2\)行，第一行是一个不超过\(10^5\)的正整数\(N\)。第二行是\(N\)个不超过\(10^9\)的正整数（尽管理论上肯定不会超过1500天，不过随意啦），分别记作\(A_1,A_2,...,A_N\)。其中\(A_i\)表示第\(A_i\)天有一场比赛。保证\(A_i\)各不相同。

Output

对每一组测试数据，输出一个整数，表示经过时光机加速，最少能用多少天完成这些比赛。

Samples

2
6 16

2

2
6 9

3

Note

在第一组数据中，首先将时光机加速到6，则1天即可完成第1场比赛；然后将时光机加速到10，又用1天完成第二场比赛，所以一共2天。

在第二组数据中，如果首先就加速到6，因为不能降速，所以第二场比赛变成了0.5天，是不允许的。因此只能加速到3，则刚好用3天完成所有比赛。可以证明，3是此种情况下最小的。

友情提示：

  1. 时间间隔必须是整数；
  2. 此外还有一个小坑。

Limitation

3s, 1024KiB for each test case.

J CYH的奖学金

Background

2020年以后，学校加大了对学科竞赛的奖励力度。各级别奖项奖金对应表如下。

获奖等级 奖金(元) 缩写
国家特等奖 6000 GT
国家一等奖 5000 GY
国家二等奖 4000 GE
国家三等奖 3000 GS
省特等奖 3000 ST
省一等奖 2000 SY
省二等奖 1000 SE
省三等奖 800 SS

现在还有一个问题，这个奖项可能是组队获得的。因此队员之间需要平分奖金。不太清楚别的竞赛是怎么做的，但是程序设计竞赛都是平分。

例如：ICPC比赛是三个人一个队，假设拿到了国三，那就每个人1000元。

不过\(CYH\)作为校运会\(400m,800m\)双冠王，对奖金有着不同的理解。ICPC比赛一般是三个人一个队，但\(CYH\)一般都是2个人就组队参赛了。于是奖金就能多分一点。

\(CYH\)做了周密的策划，对不同等级的奖项计划了参赛人数。但是她有时间跑步，没时间算术。因此想问问你，照她的计划参赛拿奖，每个人能分多少奖金。

Description

给定奖项等级与组队人数，求每个人的奖金数量。如果奖金不能整除人数，则前面的人应该多分1元钱，直到没有多余的为止。看样例。

Format

Input

首先是一个不超过100的正整数\(T\)，表示一共有\(T\)个奖项。

其后还有\(T\)行，每一行有2个内容，分别是获奖等级缩写与组队人数。其中缩写必然是列表中的字符串，人数是不超过100的正整数。中间用一个空格分隔。

Output

每个奖项输出二行。

对第\(k\)个奖项，\(k\in{[1,T]}\)，首先输出一行为：
Case ## k:

然后再输出一行，为每个队员的奖金数目，每两个数之间用一个空格分隔。

两个相邻的奖项之间要空一行。

Samples

3
GS 3
GS 2
GY 3

Case ## 1:
1000 1000 1000

Case ## 2:
1500 1500

Case ## 3:
1667 1667 1666

Note

本题要求逐字符相同。请仔细观看样例。明确空格、换行等要求。

Limitation

1s, 1024KiB for each test case.

K 没活了

Description

Hex老了，已经整不出新活了，只能改改题目出给大家。

\[S(n) = \sum_{i=1}^n\sum_{j=1}^igcd(i^5-j^5,i^3-j^3)\mu(gcd(i,j)^2) \]

Input

第一行一个正整数 \(T(1\leq T \leq 10^4)\) 表示数据组数。

对于每组数据，一行一个正整数 \(n(1\leq n \leq 10^7)\) 。

Output

对于每组数据，输出 \(S(n)\)，答案可能很大，请对 1e9+7 取模。

Samples

1
5

18

Note

友情提示：如果不懂\(\mu\)的含义，本题不要做，也不要问。

2023HUNNUCPC题解

德军坦克的数量

本题来源于某音频网站上的一期节目，泄露天机的1379号监听员和德国坦克问题。简单的说，就是不同的假设会导致不同的估计结果。因此反过来，你给出不同的结果，必然基于某种未知的假设。因此，输入最大值到1000的任意整数均可。

#include <iostream>
int main(){
    std::cout << 1000 << std::endl;
    return 0;
}

中国炮兵的射程

本题来源于一道物理竞赛题。如果你的物理与数学足够的好的话，有

\[v_{min}=L\sqrt{\frac{g}{\sqrt{H^2+L^2}-H}}=\sqrt{g\sqrt{H^2+L^2}+gH} \]

如果你的物理不行的话，注意到这是一个求最值的问题，且与实际问题有关，一般这种函数曲线必然是光滑且单峰的，因此可以使用三分法。

\(magic\_cat\)的公式法

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t --) {
        int l, h;
        cin >> l >> h;
        cout << sqrt(10 * sqrt(l * l + h * h) + 10 * h) << endl;
    }
}

出题人的三分法

#include <bits/stdc++.h>
using namespace std;

using Real = double;
Real const EPS = 1E-6;
Real const PI = acos(-1.0);

inline int sgn(Real x){return x>EPS?1:(x<-EPS?-1:0);}

int L, H;

inline Real f(Real x){
    return L / cos(x) * sqrt(5.0 / (L*tan(x) - H));
}

Real proc(){
    Real left = atan((Real)H/L);
    Real right = PI * 0.5;
    Real m1, m2, t;
    do{
        t = right + left;
        m1 = (t + left) / 3.0;
        m2 = (t + right) / 3.0;
        if(f(m1) < f(m2)) right = m2;
        else left = m1;
    }while(sgn(right - left));
    return f(right);
}

int main(){  
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int nofkase; cin >> nofkase;
    while(nofkase--){
        cin >> L >> H;
        printf("%.8f\n", proc());
    }
    return 0;
}

\(HPY\)的三分法

#include <bits/stdc++.h>
using namespace std;

const double EPS = 1E-4;

int L, H;

double check(double v1) {
    double t = L / v1;
    double v2 = H / t + 5 * t;
    return v1 * v1 + v2 * v2;
}

void solve() {
    cin >> L >> H;
    double l = 0, r = 1e9;
    for(int i = 1; i <= 60; i ++) {
        double mid1 = (l + r) / 2, mid2 = mid1 + EPS;
        if(check(mid1) < check(mid2)) r = mid2;
        else l = mid1;
    }
    printf("%.10lf\n", sqrt(check(l)));
}

int main() {
    int T;
    cin >> T;
    while(T --)
        solve();
}

植树节的日期

这个题目来源于出题人有感于国家在环保中为全人类做出的一点贡献，于是想出一道题让选手们模拟处理一下日期。验题人均不想验这道题，因此本题小概率会有\(bug\)不可能，完全不可能。

暴力法就行。对每一个给定的日期，分别向前和向后检查经过多少天才第一次到达题目给定的植树节日期。对每一个日期，显然最好情况是循环\(0\)次，而最差情况远低于\(365\)次，一共最多有\(400\)个日期要询问，因此循环次数远低于\(O(400\times{365})\)，完全可以接受。

比较麻烦的在于星期的检查，有多种实现方法和表现手法（实现不行，也可以拿着计算机上的日历人工比对）。

出题人提供一种预处理的方法，即预先处理并保存1999年到2024年所有的植树节，然后再做暴力法（注意：2024年其实无需处理，但1999年的是必须的）。预处理的时间基本上是\(O(26\times{365})\)。

#include <bits/stdc++.h>
using namespace std;

struct _t{
    int year;
    int month;
    int day;
    bool isLeap()const{
        return 0 == year % 400 or (0 == year % 4 and year % 100);
    }
    _t & operator ++ (){
        ++day;
        switch(month){
            case 1: case 3: case 5: case 7: case 8: case 10:{
                if(32 == day){
                    day = 1;
                    month += 1;
                }
            }break;
            case 4: case 6: case 9: case 11:{
                if(31 == day){
                    day = 1;
                    month += 1;
                }
            }break;
            case 2:{
                if(isLeap()){
                    if(30 == day){
                        day = 1;
                        month += 1;
                    }
                }else{
                    if(29 == day){
                        day = 1;
                        month += 1;
                    }
                }
            }break;
            case 12:{
                if(32 == day){
                    day = 1;
                    month = 1;
                    year += 1;
                }
            }break;
            default: assert(0);
        }     
        return *this;   
    }
    bool operator < (const _t & b) const {
        if(year != b.year) return year < b.year;
        if(month != b.month) return month < b.month;
        return day < b.day;
    }
    bool operator == (const _t & b) const {
        return year == b.year and month == b.month and day == b.day;
    }
};

map<_t, char> Map;

void init(){
    int w = 5;
    for(int year=1999;year<=2024;++year){
        _t t = {year, 1, 1};
        int n = 365;
        if(t.isLeap()) n = 366;

        int c9 = 0;
        _t last_12_4;
        for(int i=0;i<n;++i){
            char ch = '\0';
            if(3 == t.month and 12 == t.day) ch = 'Z';
            if(4 == t.month and 6 == t.day) ch = 'C';
            if(9 == t.month){
                if(24 == t.day) ch = 'T';
                if(6 == w){
                    if(2 == ++c9){
                        assert(!ch);
                        ch = 'F';
                    }
                }    
            } 
            if(8 == t.month and 4 == t.day) ch = 'B';
            if(1 == t.month and 15 == t.day) ch = 'Y';
            if(12 == t.month){
                if(4 == w) last_12_4 = t;
            }
            auto p = Map.insert({t, ch});
            assert(p.second);
            ++t;
            if(7 == ++w) w = 0;
        }
        auto it = Map.find(last_12_4);
        if(it == Map.end()){
            throw runtime_error(to_string(last_12_4.year) + "-" + to_string(last_12_4.month) + "-" + to_string(last_12_4.day) + " no 12 4");
        }
        if(it->second){
            throw runtime_error("12 4 is " + to_string(it->second));
        }
        it->second = 'X';        
    }
}

int main(){
    init();
    int nofkase; scanf("%d", &nofkase);
    while(nofkase--){
        int year, month, day;
        scanf("%d-%d-%d", &year, &month, &day);
        assert(2000 <= year and year <= 2023);
        assert(1 <= month and month <= 12);
        if(1 == month or 3 == month or 5 == month or 7 == month or 8 == month or 10 == month or 12 == month) assert(1 <= day and day <= 31);
        else if(4 == month or 6 == month or 9 == month or 11 == month) assert(1 <= day and day <= 30);
        else if(2 == month) assert(1 <= day and day <= 28 + (0 == year % 400 or (0 == year % 4 and year % 100) ? 1 : 0));
        else assert(0);

        _t today = {year, month, day};
        auto it = Map.find(today);
        assert(it != Map.end());
        if(it->second){
            printf("%c\n", it->second);
            continue;
        }

        auto at = it;
        auto bt = it;
        while(1){
            assert(at != Map.end() and bt != Map.begin());
            ++at; --bt;
            char ch = '\0';
            if(at->second){
                if(bt->second) ch = min(at->second, bt->second);
                else ch = at->second;
            }else{
                if(bt->second) ch = bt->second;
            }
            if(ch){
                printf("%c\n", ch);
                break;
            }
        }
    }
    return 0;
}

树上前驱后继关系

这道题就是想出个数据结构，主体考查树、附带来个并查集，后来发现出题人想多了，只能考查树。

基本知识点在于：对树做一个深搜，对每个节点记录进入与离开的时间戳，则树上两个节点\(u\)和\(v\)，\(u\)是\(v\)的祖先当前仅当\(In_u<In_v \&\& Out_v>Out_u\)。因此，预处理后可以在\(O(1)\)时间完成原有节点的查询。

操作2有关的新节点怎么办？注意到题目的限制，操作2添加的节点之间其实是无需维护层次关系的，都接在对应的原叶子节点之上即可。由此有了几种做法。

\(magic\_cat\)的类离线方法：首先将操作完全读入，对操作1保存，对操作2连边；然后深搜；然后对刚才保存的操作1依次回答即可。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 2e5 + 10;

int n;
vector<int> g[N];
vector<int> pos[N];

int tmp = 0;
void dfs(int u,int fa) {
    pos[u].push_back(++ tmp);

    for(auto v : g[u]) {
        if(v == fa) continue;
        dfs(v, u);
    }
    pos[u].push_back(++ tmp);
}

int main() {
    cin >> n;
    for(int i = 1; i < n; i ++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<pii> ques;

    int q;
    cin >> q;
    while(q --) {
        int op, u, v;
        cin >> op;
        if(op == 1) {
            cin >> u >> v;
            ques.push_back({u, v});
        } else {
            cin >> u;
            n ++;
            g[u].push_back(n);
            g[n].push_back(u);
        }
    }
    dfs(1, 0);
    for(auto [u, v]: ques) {
        int lu = pos[u][0], ru = pos[u][1];
        int lv = pos[v][0], rv = pos[v][1];

        if(lu > lv && ru < rv) {
            cout << "Descendent\n";
        } else if(lu < lv && ru > rv) {
            cout << "Ancestor\n";
        } else {
            cout << "None\n";
        }
    }
}

出题人的并查集做法：操作2添加的节点之间其实是无需维护层次关系的，都接在对应的原叶子节点之上即可，这句话本身就描述了一个并查集的性质。对操作2，做合并操作即可，对操作1分情况讨论，并最终落在时间戳的判断上。

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> Edges;


struct uf_t{

vector<int> father;
void init(int n){father.assign(n + 1, 0);for(int i=1;i<=n;++i)father[i] = i;}
int find(int x){return x == father[x] ? x : father[x] = find(father[x]);}
void unite(int x, int y){x = find(x); y = find(y); if(x > y) swap(x, y); father[y] = x;}

}UF;

vector<pair<int, int>> Dfn;
int TimeStamp = 0;

int N, Q;

void dfs(int u, int p){
    Dfn[u].first = ++TimeStamp;
    for(int v : Edges[u]){
        if(v == p) continue;
        dfs(v, u);
    }
    Dfn[u].second = ++TimeStamp;
}

inline bool isAn(int a, int b){
    return Dfn[a].first <= Dfn[b].first and Dfn[b].second <= Dfn[a].second;
}

string ask(int u, int v){
    if(u <= N and v <= N) goto L;

    if(u > N){
        u = UF.find(u);
        if(v == u) return "Descendent";
        goto L;
    }

    if(v > N){
        v = UF.find(v);
        if(v == u) return "Ancestor";
        goto L;
    }

L:
    if(isAn(u, v)) return "Ancestor";
    if(isAn(v, u)) return "Descendent";
    return "None";
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> N;
    Edges.assign(N + 1, vector<int>());
    Dfn.assign(N + 1, {});
    for(int a,b,i=1;i<N;++i){
        cin >> a >> b;
        Edges[a].emplace_back(b);
        Edges[b].emplace_back(a);
    }
    dfs(1, 0);

    cin >> Q;
    UF.init(Q + N);
    int m = N;
    for(int c,u,v,qi=1;qi<=Q;++qi){
        cin >> c >> u;
        if(1 == c){
            cin >> v;
            cout << ask(u, v) << endl;
        }else{
            ++m;
            UF.unite(u, m);
        }
    }
    return 0;
}

\(HPY\)的时间戳改进方法：上两种方法的时间戳都是一个整数，该方法使用一个\(pair\)两个整数来表示时间戳，对于原树上的点，\(first\)表示正常的时间戳，\(second\)表示一种标记，入口处是负无穷，出口处是正无穷。对于操作2只需将入口与出口的\(second\)分别加减一即可。这样对于操作1，如果均是原树上的点，比较\(first\)即可；如果存在新加的点，比较\(second\)即可。

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
const int N = 1e5 + 10;

int n, m;
vector<int> g[N];

pii l[N * 2], r[N * 2];

int cnt;

void dfs(int u, int f) {
    l[u] = {cnt++, N * -10000};
    for(int v : g[u]) {
        if(v != f)
            dfs(v, u);
    }
    r[u] = {cnt++, N * 10000};
}

int main() {
    cin >> n;
    for(int i = 1, u, v; i < n; i ++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    int q;
    cin >> q;
    m = n;
    for(int i = 1, op, u, v; i <= q; i ++) {
        cin >> op;
        if(op == 1) {
            cin >> u >> v;
            assert(u <= n || v <= n);
            if(l[u] < l[v] && r[u] > r[v]) puts("Ancestor");
            else if(l[v] < l[u] && r[v] > r[u]) puts("Descendent");
            else puts("None");
        }else{
            cin >> u;
            m ++;
            l[m] = {l[u].first, l[u].second + 1};
            r[m] = {r[u].first, r[u].second - 1};
        }
    }
}

哥德巴赫猜想与西班牙电影

题目来源题目里说的非常清楚，这个电影的中文名应该是《费马的房间》，不过感觉也不是十分想看的样子。

这道题主要是为了练习交互，为扫雷做准备。

考虑样例就知道应该如何做。假设盒1里查询出来是糖2，咋办？可以继续查询盒1，如果还是糖2，就回答2 3 1。此时有\(\frac{1}{8}\)的几率出错。一共有7个样例，因此全对通过本题的概率约为\(0.39\)。因此重复提交3次，期望就能超过1。也就是概率意义下，提交3~4次就能通过本题。

当然其实问3就行了，问1次就能确定答案。

#include <bits/stdc++.h>
using namespace std;

int main() {
    cout << "? 3" << endl;
    int x;
    cin >> x;
    if(x == 1) {
        cout << "! 2 3 1" << endl;
    } else {
        cout << "! 3 1 2" << endl;
    }
}

扫雷

不知道是因为题面限制的原因，还是\(Hex\)想象力的原因，总之这道题数据比较弱。

\(Hex\)的解法，看起来像个深搜。

#include <bits/stdc++.h>

#define ed end()
#define bg begin()
#define mp make_pair 
#define pb push_back
#define all(x) x.bg,x.ed
#define newline puts("")
#define si(x) ((int)x.size())
#define rep(i,n) for(int i=1;i<=n;++i)
#define rrep(i,n) for(int i=0;i<n;++i)
#define srep(i,s,t) for(int i=s;i<=t;++i)
#define drep(i,s,t) for(int i=t;i>=s;--i)

#define DEBUG
#define d1(x) std::cout << #x " = " << (x) << std::endl
#define d2(x, y) std::cout << #x " = " << (x) << " ," #y " = " << (y) << std::endl
#define disp(arry, fr, to) \
    { \
        std::cout << #arry " : "; \
        for(int _i = fr; _i <= to; _i++) std::cout << arry[_i] << " "; \
        std::cout << std::endl; \
    }


using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int Maxn = 1e5+10;
const int Inf = 0x7f7f7f7f;
const ll Inf_ll = 1ll*Inf*Inf;
const int Mod = 1e9+7;
const double eps = 1e-7;

int nx[] = { 1,  0, -1,  1, -1,  1,  0, -1};
int ny[] = {-1, -1, -1,  0,  0,  1,  1,  1};

int n, m, num;
bool vis[12][12];
string s[12];

void In(){
    for(int i=0;i<n;i++)  
        cin>>s[i];
}
void Out(int op, int x, int y){
    cout << "? " << op << " " << x+1 << " " << y+1 << endl;
}

vector<pii> vp;
int Sivp;

bool CheckPos(int x, int y){
    if( s[x][y] == '*' )  return true;
    int num = 0;
    for(int k=0;k<8;k++)
    {
        int xx = x + nx[k], yy = y + ny[k];
        if( xx < 0 || xx >= n || yy < 0 || yy >= m )  continue;
        if( s[xx][yy] == '*' )  num++;
    }
    if( s[x][y] == '.' )
    {
        if( num > 3 )  return false;
        else return true;
    }
    if( s[x][y]-'0' < num )  return false;
    return true;
}

bool Check(){
    for(int i=0;i<n;i++)  for(int j=0;j<m;j++)
    {
        if( s[i][j] == '*' || s[i][j] == '.' )  continue;
        int num = 0;
        for(int k=0;k<8;k++)
        {
            int x = i + nx[k], y = j + ny[k];
            if( x < 0 || x >= n || y < 0 || y >= m )  continue;
            if( s[x][y] == '*' )  num++;
        }
        if( s[i][j]-'0' != num )  return false;
    }
    return true;
}


bool book[110];
int Ans = 0;
queue<pair<int,pii>> q;
void dfs(int i, int num){
    if( i == Sivp )
    {
        if( Check() )
        {
            Ans++;

            // cout<<endl;
            // for(int i=0;i<n;i++)  cout<<s[i]<<endl;
            // cout<<endl;
            for(int i=0;i<Sivp;i++)
            {   
                if( book[i] )   Out(1, vp[i].first, vp[i].second);
                else            Out(2, vp[i].first, vp[i].second);
            }
            // In();
            cout<<"end"<<endl;
            exit(0);
        }
        return ;
    }
    if( num != 0 )
    {
        bool add_flag = true;
        for(int k=0;k<8;k++)
        {
            int x = vp[i].first + nx[k], y = vp[i].second + ny[k];
            if( x < 0 || x >= n || y < 0 || y >= m || s[x][y] == '*' || s[x][y] == '.' )  continue;
            if( !CheckPos(x, y) )  add_flag = false;
        }
        if( add_flag )
        {
            s[vp[i].first][vp[i].second] = '*';
            book[i] = true;
            dfs(i+1, num-1);
        }
    }
    s[vp[i].first][vp[i].second] = '.';
    book[i] = false;
    dfs(i+1, num);
}

void solve(){
    cin >> n >> m >> num;
    In();
    for(int i=0;i<n;i++)  for(int j=0;j<m;j++)
    {
        if( s[i][j] == '*' )  throw(-1);
    }
    bool flag = false;
    while( !flag )
    {
        while( !q.empty() )
        {
            pair<int,pii> p = q.front();  q.pop();
            Out(p.first, p.second.first, p.second.second);
            // In();
        }
        cout<<"? 3"<<endl;
        In();
        flag = true;
        for(int i=0;i<n&&flag;i++)  for(int j=0;j<m;j++)
        {
            if( s[i][j] == '*' || s[i][j] == '.' || s[i][j] == '0' || vis[i][j] )  continue;
            int around = 0, around_mark = 0;
            for(int k=0;k<8;k++)
            {
                int x = i + nx[k], y = j + ny[k];
                if( x < 0 || x >= n || y < 0 || y >= m )  continue;
                if( s[x][y] == '.' || s[x][y] == '*' )  around++;
                if( s[x][y] == '*' )  around_mark++;
            }
            if( around == s[i][j]-'0' )
            {
                vis[i][j] = true;
                for(int k=0;k<8;k++)
                {
                    int x = i + nx[k], y = j + ny[k];
                    if( x < 0 || x >= n || y < 0 || y >= m )  continue;
                    if( s[x][y] == '.' )
                    {
                        q.push(mp(1, mp(x, y)));
                    }
                }
                flag = false;
                break;
            }
            if( around_mark == s[i][j]-'0' )
            {
                vis[i][j] = true;
                for(int k=0;k<8;k++)    
                {
                    int x = i + nx[k], y = j + ny[k];
                    if( x < 0 || x >= n || y < 0 || y >= m )  continue;
                    if( s[x][y] == '.' )
                    {
                        q.push(mp(2, mp(x, y)));
                    }
                }
                flag = false;
                break;
            }
        }
    }
    vp.clear();
    int mark = 0;
    for(int i=0;i<n;i++)  for(int j=0;j<m;j++)
    {
        if( s[i][j] == '.' )  vp.pb(mp(i, j));
        else if( s[i][j] == '*' )  mark++;
    }  
    Sivp = si(vp);
    if( Sivp == 0 )
    {
        cout<<"end"<<endl;
        return ;
    }
    dfs(0, num-mark);
}

int main(){
    solve();
    return 0;
}

验题人的解法，简单描述一下，基于数据较弱的实现。
首先统计所有已知数量的格子，记录其邻域雷的数量与.的数量，分几种情况：

  1. 格子数等于雷数加点数，说明点全是雷，标记；
  2. 找如下模式：
  • \(2\times{3}\)，其中一行未开，另一行为121且无其他相邻的空格，则中间一格非雷，两边各有一个雷；
  • \(2\times{3}\)，其中一行未开，另一行为111且无其他相邻的空格，则中间一格是雷，两边非雷；
  • \(2\times{4}\)，假设为1221，则中间两个是雷；
  • \(2\times{4}\)，假设为1111，则两边是是雷；
  • 列主序的照此办理，但本题数据只需验证前两个模式即可；
  1. 对于不同的两个数字格，其相邻未开的位置集合分别记作\(A\)和\(B\)，且\(A\subset{B}\)，则一定条件下可以断定\(B-A\)中的所有格子均非雷。

每次更新地图，反复处理即可。

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
using spii = set<pii>;

int const DR[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int const DC[] = {-1, 0, 1, 1, 1, 0, -1, -1};

int N, M, K;
char A[12][12];

vector<pair<int, int>> ToDo;
spii Empty;
spii Can[12][12];
spii Bomb[12][12];

void read(){
    for(int i=0;i<N;++i) cin >> A[i];

    Empty.clear();
    ToDo.clear();
    for(int i=0;i<N;++i)for(int j=0;j<M;++j){
        Can[i][j].clear();
        Bomb[i][j].clear();
        if(A[i][j] == '.'){
            Empty.insert({i, j});
        }else if(isdigit(A[i][j])){
            int c = A[i][j] - '0';
            for(int k=0;k<8;++k){
                auto nr = i + DR[k];
                auto nc = j + DC[k];
                if(0 <= nr and nr < N and 0 <= nc and nc < M){
                    if('.' == A[nr][nc]) {Can[i][j].insert({nr, nc}); ToDo.emplace_back(i, j);}
                    else if('*' == A[nr][nc]) Bomb[i][j].insert({nr, nc});
                }
            }
        }else if('*' == A[i][j]){
            
        }else{
            throw runtime_error("wrong character.");
        }
    }
}

inline void ask(int cmd, int r, int c){
    cout << "? " << cmd << " " << r + 1 << " " << c + 1 << endl;
    cout.flush();
}

bool procBrute(){
    bool ret = false;
    int flag[12][12] = {0};
    for(const auto & p : ToDo){
        const auto r = p.first, c = p.second;
        const auto shouldcnt = A[r][c] - '0';
        const auto bcnt = Bomb[r][c].size();
        if(shouldcnt == bcnt){
            for(const auto & pp : Can[r][c]){
                if(0 == flag[pp.first][pp.second]){
                    flag[pp.first][pp.second] = 1;
                    ask(2, pp.first, pp.second);
                    ret = true;  
                    // return true;                  
                }
            }
        }else if(shouldcnt - bcnt == Can[r][c].size()){
            for(const auto & pp : Can[r][c]){
                if(0 == flag[pp.first][pp.second]){
                    flag[pp.first][pp.second] = 1;
                    ask(1, pp.first, pp.second);
                    ret = true;
                    // return true;
                }
            }
        }
    }  
    return ret;
}

bool checkAndProcRow121(int originr, int r, int c){
    if('1' == A[r][c] and '2' == A[r][c + 1] and '1' == A[r][c + 2] and Can[r][c+1].size() == 3){
        ask(1, originr, c);
        // return true;
        ask(1, originr, c + 2);
        ask(2, originr, c + 1);
        return true;
    }
    return false;
}

bool checkAndProcRow111(int originr, int r, int c){
    if(
        '1' == A[r][c] and '1' == A[r][c + 1] and '1' == A[r][c + 2]
        and Can[r][c].size() == 2 
        and Can[r][c + 1].size() == 3
        and Can[r][c + 2].size() == 2
    ){
        ask(1, originr, c + 1);
        // return true;
        ask(2, originr, c);
        ask(2, originr, c + 2);
        return true;
    }
    return false;
}

bool checkAndProcRow3(int r, int c){
    if(r > 0){
        if(checkAndProcRow121(r, r - 1, c)){
            return true;
        }
        if(checkAndProcRow111(r, r - 1, c)){
            return true;
        }
    }
    if(r + 1 < N){
        if(checkAndProcRow121(r, r + 1, c)){
            return true;
        }
        if(checkAndProcRow111(r, r + 1, c)){
            return true;
        }
    }
    return false;
}

bool checkAndProcCol121(int originc, int r, int c){
    if('1' == A[r][c] and '2' == A[r + 1][c] and '1' == A[r + 2][c] and Can[r+1][c].size() == 3){
        ask(1, r, originc);
        // return true;
        ask(1, r + 2, originc);
        ask(2, r + 1, originc);
        return true;
    }
    return false;
}

bool checkAndProcCol111(int originc, int r, int c){
    if(
        '1' == A[r][c] and '1' == A[r + 1][c] and '1' == A[r + 2][c]
        and Can[r][c].size() == 2
        and Can[r + 1][c].size() == 3
        and Can[r + 2][c].size() == 2
    ){
        ask(1, r + 1, originc);
        // return true;
        ask(2, r, originc);
        ask(2, r + 2, originc);
        return true;
    }
    return false;
}

bool checkAndProcCol3(int r, int c){
    if(c > 0){
        if(checkAndProcCol121(c, r, c - 1)){
            return true;
        }
        if(checkAndProcCol111(c, r, c - 1)){
            return true;
        }
    }
    if(c + 1 < M){
        if(checkAndProcCol121(c, r, c + 1)){
            return true;
        }
        if(checkAndProcCol111(c, r, c + 1)){
            return true;
        }
    }
    return false;
}

bool checkAndProcRow1221(int originr, int r, int c){
    if('1' == A[r][c] and '2' == A[r][c + 1] and '2' == A[r][c + 2] and '1' == A[r][c + 3] and Can[r][c+1].size() == 3 and Can[r][c+2].size() == 3){
        ask(1, originr, c + 1);
        // return true;
        ask(1, originr, c + 2);
        ask(2, originr, c);
        ask(2, originr, c + 3);
        return true;
    }
    return false;
}

bool checkAndProcRow1111(int originr, int r, int c){
    if(
        '1' == A[r][c] and '1' == A[r][c + 1] and '1' == A[r][c + 2] and '1' == A[r][c + 3]
        and Can[r][c].size() == 2
        and Can[r][c + 1].size() == 3
        and Can[r][c + 2].size() == 3
        and Can[r][c + 3].size() == 2
    ){
        ask(1, originr, c);
        // return true;
        ask(1, originr, c + 3);
        ask(2, originr, c + 1);
        ask(2, originr, c + 2);
        return true;
    }
    return false;    
}

bool checkAndProcRow4(int r, int c){
    if(r > 0){
        if(checkAndProcRow1221(r, r - 1, c)){
            return true;
        }
        if(checkAndProcRow1111(r, r - 1, c)){
            return true;
        }
    }
    if(r + 1 < N){
        if(checkAndProcRow1221(r, r + 1, c)){
            return true;
        }
        if(checkAndProcRow1111(r, r + 1, c)){
            return true;
        }
    }
    return false;
}

bool checkAndProcCol1221(int originc, int r, int c){
    if('1' == A[r][c] and '2' == A[r + 1][c] and '2' == A[r + 2][c] and '1' == A[r + 3][c] and Can[r+1][c].size() == 3 and Can[r+2][c].size() == 3){
        ask(1, r + 1, originc);
        // return true;
        ask(1, r + 2, originc);
        ask(2, r, originc);
        ask(2, r + 3, originc);
        return true;
    }
    return false;    
}

bool checkAndProcCol1111(int originc, int r, int c){
    if(
        '1' == A[r][c] and '1' == A[r + 1][c] and '1' == A[r + 2][c] and '1' == A[r + 3][c]
        and Can[r][c].size() == 2
        and Can[r + 1][c].size() == 3
        and Can[r + 2][c].size() == 3
        and Can[r + 3][c].size() == 2
    ){
        ask(1, r, originc);
        // return true;
        ask(1, r + 3, originc);
        ask(2, r + 1, originc);
        ask(2, r + 2, originc);
        return true;
    }
    return false;        
}

bool checkAndProcCol4(int r, int c){
    if(c > 0){
        if(checkAndProcCol1221(c, r, c - 1)){
            return true;
        }
        if(checkAndProcCol1111(c, r, c - 1)){
            return true;
        }
    }
    if(c + 1 < M){
        if(checkAndProcCol1221(c, r, c + 1)){
            return true;
        }
        if(checkAndProcCol1111(c, r, c + 1)){
            return true;
        }
    }
    return false;    
}

bool proc34(){
    vector<vector<int>> rows(N), cols(M);
    for(const auto & p : Empty){
        rows[p.first].emplace_back(p.second);
        cols[p.second].emplace_back(p.first);
    }
    for(auto & i : rows) sort(i.begin(), i.end());
    for(auto & i : cols) sort(i.begin(), i.end());

    for(int i=0;i<N;++i){
        const auto r = rows[i];
        for(int j=0,n=r.size();j<n-2;++j){
            if(r[j] + 1 == r[j + 1] and r[j] + 2 == r[j + 2]){
                if(checkAndProcRow3(i, r[j])){
                    return true;
                }
                if(j + 3 < n and r[j] + 3 == r[j + 3]){
                    if(checkAndProcRow4(i, r[j])){
                        return true;
                    }                    
                }
            }
        }
    }

    for(int i=0;i<M;++i){
        const auto r = cols[i];
        for(int j=0,n=r.size();j<n-2;++j){
            if(r[j] + 1 == r[j + 1] and r[j] + 2 == r[j + 2]){
                if(checkAndProcCol3(r[j], i)){
                    return true;
                }
                if(j + 3 < n and r[j] + 3 == r[j + 3]){
                    if(checkAndProcCol4(r[j], i)){
                        return true;
                    }
                }
            } 
        }        
    }

    return false;
}

bool contains(const spii & big, const spii & small){
    for(const auto & p : small){
        if(0 == big.count(p)){
            return false;
        }
    }
    return true;
}

bool checkAndProcFinally(pii a, pii b){
    int ac = (A[a.first][a.second] - '0') - Bomb[a.first][a.second].size();
    int bc = (A[b.first][b.second] - '0') - Bomb[b.first][b.second].size();
    if(ac != bc) return false;
    

    const auto as = Can[a.first][a.second];
    const auto bs = Can[b.first][b.second];
    if(!contains(bs, as)) return false;

    bool ret = false;
    for(const auto & p : bs){
        if(as.count(p)) continue;

        ask(2, p.first, p.second);
        ret = true;
        return ret;
    }
    return ret;
}

bool proc(){
    if(procBrute()) return true;  
    if(proc34()) return true;
    
    sort(ToDo.begin(), ToDo.end(), [](pii a, pii b){
        return Can[a.first][a.second].size() < Can[b.first][b.second].size();
    });

    for(int i=0,n=ToDo.size();i<n;++i){
        const auto & a = ToDo[i];
        const auto & az = Can[a.first][a.second].size();
        for(int j=i+1;j<n;++j){
            const auto & b = ToDo[j];
            if(az < Can[b.first][b.second].size() and checkAndProcFinally(a, b)){
                return true;
            }
        }
    }

    return false;
}

int main(){
    // freopen("z.txt", "r", stdin);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> N >> M >> K;
    read();

    while(1){        
        if(Empty.empty()){
            cout << "end" << endl;
            cout.flush();
            break;
        }
        if(!proc()){
             throw runtime_error("not good strategy.");
        }
        cout << "? 3" << endl;
        cout.flush();
        read();
    }
    return 0;
}

混乱的组队

这是2017年校赛某题的改版，原题保证\(N\)是3的倍数。这样的话，首先显然A/B/C三类是分开各不干扰的，然后如果保证\(N\)是3的倍数，则三类均是\(\frac{N}{3}\)的一个错排。错排及其公式可以自行上网学习，不再赘述。再乘起来即可，其实就是错排的立方。

本题由于B、C可能不满，因此相当于将\(n-1\)个球放入\(n\)个格子中，且球、格不能同号，记此数量为\(V_n\)，且\(U_n\)为错排数量，则

\[V_n=U_{n-1}+U_{n} \]

如果第\(n\)格为空，则就是\(U_{n-1}\)；如果第\(n\)个不为空，将“空”视为一个特殊的小球，此时的数量其实就是\(U_n\)。

求出\(U,V\)后，给定\(N\)，再取合适的数量乘起来即可。

出题人的做法：

#include <bits/stdc++.h>
using namespace std;

using llt = long long;
llt const MOD = 998244353LL;

// int const SZ = 13;
int const SZ = 3400;

array<llt, SZ * 3> D;
array<llt, SZ> U, V;

void init(){
    U[1] = 0, U[2] = 1; 
    V[1] = 1, V[2] = 1;
    for(int i=3;i<SZ;++i){
        U[i] = (i - 1) * (U[i - 1] + U[i - 2]) % MOD;
        V[i] = (U[i - 1] + U[i]) % MOD;
    } 
    D[1] = D[2] = D[3] = 0;
    D[4] = D[5] = D[6] = 1;
    for(int i=7;i<SZ*3;++i){
        auto k = i / 3;
        switch(i % 3){
            case 0:{
                D[i] = U[k] * U[k] % MOD * U[k] % MOD;
            }break;
            case 1:{
                k += 1;
                D[i] = U[k] * V[k] % MOD * V[k] % MOD;
            }break;
            case 2:{
                k += 1;
                D[i] = U[k] * U[k] % MOD * V[k] % MOD;
            }break;
            default: assert(0);
        }
    }
    return;
}

int main(){
    init();
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int nofkase; cin >> nofkase;
    for(int kase=1;kase<=nofkase;++kase){
        int n; cin >> n;
        cout << D[n] << endl;
    }
    return 0;
}

\(Hex\)的做法，出题人没有看懂，但本质上应该差不多。

#include <bits/stdc++.h>

#define ed end()
#define bg begin()
#define mp make_pair
#define pb push_back
#define all(x) x.bg,x.ed
#define newline puts("")
#define si(x) ((int)x.size())
#define rep(i,n) for(int i=1;i<=n;++i)
#define rrep(i,n) for(int i=0;i<n;++i)
#define srep(i,s,t) for(int i=s;i<=t;++i)
#define drep(i,s,t) for(int i=t;i>=s;--i)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int Maxn = 1e5+10;
const int Inf = 0x7f7f7f7f;
const ll Inf_ll = 1ll*Inf*Inf;
const int Mod = 998244353;
const double eps = 1e-7;

#define DEBUG
#define d1(x) std::cout << #x " = " << (x) << std::endl
#define d2(x, y) std::cout << #x " = " << (x) << " ," #y " = " << (y) << std::endl
#define disp(arry, fr, to) \
    { \
        std::cout << #arry " : "; \
        for(int _i = fr; _i <= to; _i++) std::cout << arry[_i] << " "; \
        std::cout << std::endl; \
    }

ll inv[Maxn],fac[Maxn],finv[Maxn];
void Init(int n){
    inv[0] = inv[1] = fac[0] = finv[0] = 1;
    for(int i=2;i<=n;i++)
        inv[i] = 1ll*(Mod - Mod/i)*inv[Mod%i]%Mod;
    for(int i=1;i<=n;i++)
        fac[i] = fac[i-1]*i%Mod,
        finv[i] = finv[i-1]*inv[i]%Mod;
}

int C(int n, int m){
    return fac[n]*finv[m]%Mod*finv[n-m]%Mod;
}

int calc(int x, int f){
    int ans = 0;
    for(int i=0;i<=x;i++)
    {
        int tmp = 1ll*C(x, i)*fac[x-i+f]%Mod;
        if( i&1 )  ans = (ans - tmp + Mod)%Mod;
        else ans = (ans + tmp)%Mod;
    }
    // d2(x, ans);
    return ans;
}

void solve(){
    int n;
    scanf("%d",&n);
    int a = 0, b = 0, c = 0;
    for(int i=1;i<=n;i++)
    {
        if( i%3 == 1 )  a++;
        else if( i%3 == 2 )  b++;
        else c++;
    }
    int A = calc(a, 0), B, C;
    if( a != b )  B = calc(b, 1);
    else          B = calc(b, 0);
    if( a != c )  C = calc(c, 1);
    else          C = calc(c, 0);
    int ans = 1ll*A*B%Mod*C%Mod;
    printf("%d\n", ans);
}

int main(){
    Init(Maxn-10);
    int T;
    scanf("%d",&T);
    for(int _=1;_<=T;_++)
    {
        solve();
    }
    return 0;
}

\(HPY\)的做法：与出题人一样。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10, P = 998244353;

int D[N], Z[N];

int main() {
    D[0] = 1;
    D[1] = 0;
    for(int i = 2; i < N; i ++)
        D[i] = (i - 1ll) * (D[i - 2] + D[i - 1]) % P;

    Z[0] = 1;
    Z[1] = 1;
    for(int i = 2; i < N; i ++)
        Z[i] = (Z[i - 1] + (i - 1ll) * (Z[i - 1] + Z[i - 2])) % P;
    
    int T;
    cin >> T;
    while(T --) {
        int n;
        cin >> n;
        int base = (n + 2) / 3;
        int ans = 1;
        for(int i = 0; i < 3; i ++) {
            if(i >= base * 3 - n) ans = ans * 1ll * D[base] % P;
            else ans = ans * 1ll * Z[base - 1] % P;
        }
        cout << ans << "\n";
    }
}

快跑，这是一道模拟题

本题来源于出题人当年用过的小工具。显然没有人验题。数据是手搓的，有几个比较阴险的点。不过如果\(wa\)的话，OJ会显示你的输出与标准答案的第一个不同字符的ASCII码，应该对编码很有帮助。

#include <bits/stdc++.h>
using namespace std;

string getType(const string & s){
    if(-1 != s.find('\"')) return "String";
    if(-1 != s.find('.')) return "double";
    
    for(auto ch : s){
        if(isalpha(ch)) return "bool";
    }

    stringstream ss(s);
    int x;
    if(ss >> x) return "int";
    return "long";
}

vector<pair<string, string>> parse(const string & s){
    vector<pair<string, string>> vec;
    int k = 0;
    while(1){
        while(s[k] != '\"') ++k;
        ++k;
        int t = k;
        while(s[t] != '\"') ++t;
        string name = s.substr(k, t - k);
        
        k = t + 1;
        while(s[k] != ':') ++k;
        ++k;

        t = k;
        while(s[t] != ',' and s[t] != '}') ++t;
        string type = getType(s.substr(k, t - k));
        vec.emplace_back(type, name);

        if(s[t] == '}') break;
        k = t + 1;
    }
    return vec;
}

string proc(const string & s){
    string ans;
    int k = 0, n = s.length();
    while(s[k] != '{') ++k;
    while(s[k] != '\"') ++k;

    ++k;
    int t = k;
    while(s[t] != '\"') ++t;

    string classname = s.substr(k, t - k);
    classname[0] = toupper(classname[0]);
    ans += "public class ";
    ans += classname;
    ans += "{\n";
    
    k = t + 1;
    while(s[k] != ':') ++k;
    ++k;
    while(s[k] != '{') ++k;
    ++k;

    auto vec = parse(s.substr(k));
    for(const auto & p : vec){
        ans += "    private ";
        ans += p.first;
        ans += " ";
        ans += p.second;
        ans += ";\n";
    }
    
    for(auto & p : vec){
        ans += "    public ";
        ans += p.first;
        ans += " get";
        p.second[0] = toupper(p.second[0]);
        ans += p.second;
        ans += "() {return ";
        p.second[0] = tolower(p.second[0]);
        ans += p.second;
        ans += ";}\n";
        
        ans += "    public void set";
        p.second[0] = toupper(p.second[0]);
        ans += p.second;
        ans += "(";
        ans += p.first;
        ans += " ";
        p.second[0] = tolower(p.second[0]);
        ans += p.second;
        ans += ") {this.";
        ans += p.second;
        ans += " = ";
        ans += p.second;
        ans += ";}\n";
    }

    ans += "}";
    return ans;
}

int main(){
    string s;
    getline(cin, s);
    cout << proc(s) << endl;
    return 0;
}

部长的时光机

本题来源于2016年CCPC杭州站的某题，套了个部长放上来，题解一模一样。第一遍看题可能有点懵，不过本题已经配合样例尽量清晰描述了，原题更难懂。

很明显最后一段时间要加速成1天过完，然后往前倒推即可。其实是一个基于贪心的简单题。

一个小坑是指输入并未保证升序，需要先排个序。

不记得为啥要用\(Python\)了。

from math import fabs


EPS = 1E-3


def is_zero(x):
    return fabs(x) < EPS

def proc(a):
    n = len(a)
    ans = 1
    speed = a[n - 1] - a[n - 2]
    for i in range(n - 2, 0, -1):
        now = a[i] - a[i - 1]
        if is_zero(now - speed):
            ans += 1
        elif speed > now:
            ans += 1
            speed = now
        else:
            t = int((now - EPS) / speed) + 1
            ans += t
            speed = now / t
    return ans


if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    a.append(0)
    a.sort()
    print(proc(a))

CYH的奖学金

本题来源于这样一个理论：无论什么档次的比赛，当出完题以后，整体再调简单一点，这样题目难易度与选手水平就能匹配的更好。

因此最后加了一个签到题。

\(magic\_cat\)的代码：

#include <bits/stdc++.h>
using namespace std;
string s[] = {"GT", "GY", "GE", "GS", "ST", "SY", "SE", "SS"};
int v[] = {6000, 5000, 4000, 3000, 3000, 2000, 1000, 800};

int main() {
    int t;
    cin >> t;
    for(int kase = 1; kase <= t; kase ++) {
        string op;
        int x;
        cin >> op >> x;
        int val = 0;
        for(int i = 0; i < 8; i ++) {
            if(s[i] == op) val = v[i];
        }
        int lef = val % x;
        int ans[110];

        for(int i = 0; i < x; i ++) ans[i] = val / x;
        for(int i = 0; i < lef; i ++) ans[i] ++;

        cout << "Case # " << kase << ":\n";
        for(int i = 0; i < x; i ++) {
            cout << ans[i];
            if(i != x - 1) cout << ' ';
            else if(kase != t) cout << '\n';
        } 
        if(kase != t)
            cout << "\n"; 
    }
}

没活了

考虑到学妹的存在，以及后面来了一群小朋友踢馆，最后专门请\(Hex\)出了一道题。反正管理员不会做。以下是\(Hex\)的题解及标程。

首先给定的 \(\mu(gcd(i,j)^2)\) 易得为，\([gcd(i,j)==1]\) 这个条件。

在 \(gcd(i^a-j^a,i^b-j^b)[gcd(i,j)==1\&\&gcd(a,b)==1]\) 情况下为 \(i-j\) 可以打表得到。

\[gcd(i^a-j^a,i^b-j^b) = i^{gcd(a,b)}-j^{gcd(a,b)} = i - j \ [gcd(i,j)==1] \]

证明：

假设 \(a \ge b, r = a\%b\)

\(i^a-j^a = (i^b-j^b)(i^{a-b}+i^{a-2b}j^b+...+i^rj^{a-b-r})+i^rj^{a-r}-j^b\)

\(gcd(i^a-j^a,i^b-j^b) = gcd(i^rj^{a-r}-j^b,i^b-j^b)=gcd(j^{(a-r)}(i^r-j^r), i^b-j^b)\)

设 \(j^{a-r} = j^{b\lfloor a/b \rfloor } = j^{bk}\)

考虑 \(gcd(j^{bk}, i^b-j^b)\)

有 \(j^{bk} = (i^b-j^b)(-j^{b(k-1)}-i^bj^{b(k-2)}-...-i^{b(k-1)}+i^{bk}\)

\(gcd(j^{bk}, i^b-j^b) = gcd(i^{bk}, i^b-j^b) = d\)

所以 \(d|j^{bk}, d|i^{bk},d|gcd(i,j)=1\)

即 \(gcd(j^{bk}, i^b-j^b)=1\)

得到 \(gcd(i^a-j^a,i^b-j^b) = gcd(i^{a\%b}-j^{a\%b}, i^b-j^b) = i^{gcd(a,b)}-j^{gcd(a,b)}\)

证毕。

问题转化为:

\[\sum_{i=1}^n \sum_{j=1}^i (i-j)[gcd(i,j)==1] \]

\[\sum_{i=1}^n(i\phi(i)-\sum_{j=1}^ij)[gcd(i,j)==1] \]

\[\sum_{i=1}^{n}i\phi(i)-\frac{i\phi(i)}{2} \]

\[\frac12(\sum_{i=1}^ni\phi(i)-1) \]

当 \(n=1e9\) 时，还可以用杜教筛解决。

#include <bits/stdc++.h>

#define ed end()
#define bg begin()
#define mp make_pair
#define pb push_back
#define all(x) x.bg,x.ed
#define newline puts("")
#define si(x) ((int)x.size())
#define rep(i,n) for(int i=1;i<=n;++i)
#define rrep(i,n) for(int i=0;i<n;++i)
#define srep(i,s,t) for(int i=s;i<=t;++i)
#define drep(i,s,t) for(int i=t;i>=s;--i)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int Maxn = 1e7+10;
const int Inf = 0x7f7f7f7f;
const ll Inf_ll = 1ll*Inf*Inf;
const int Mod = 1e9+7;
const double eps = 1e-7;

int prim[Maxn],tol,mu[Maxn],phi[Maxn],sum[Maxn];
bool vis[Maxn];
void Get(int n){
    mu[1] = phi[1] = 1;
    for(int i=2;i<=n;i++)
    {
        if( !vis[i] )  prim[++tol] = i,mu[i] = -1,phi[i] = i-1;
        for(int j=1;j<=tol&&i*prim[j]<=n;j++)
        {
            vis[i*prim[j]] = true;
            if( i%prim[j] == 0 )
            {
                phi[i*prim[j]] = phi[i]*prim[j];
                break;
            }
            mu[i*prim[j]] = -mu[i];
            phi[i*prim[j]] = phi[i]*(prim[j]-1);
        }
    }
    for(int i=1;i<=n;i++)
        sum[i] = (sum[i-1] + 1ll*i*phi[i]%Mod)%Mod;
}

int n;
void solve(){
    scanf("%d",&n);
    int inv2 = (Mod+1)/2;
    printf("%lld\n", 1ll*(sum[n]+Mod-1)%Mod*inv2%Mod);
}

int main(){
    int T;
    Get(Maxn-10);
    scanf("%d",&T);
    for(int _=1;_<=T;_++)
    {
        solve();
    }
    return 0;
}