Summary3

$U\sim Z$

U 国庆-朝日的括号序列

时间限制：1000ms 内存限制：65536kb

通过率：40/91 (43.96%) 正确率：40/298 (13.42%)

题目描述

Asahi 在你的电脑键盘上按了若干次 ( 和 ) ，在屏幕上打出了一段括号序列。

众所周知，按下 ( 和 ) 时，电脑会根据光标 | 的位置生成括号。光标的移动只能通过按 ( 和 ) 实现。具体规则如下：

按下 ( 时，光标 | 的左侧和右侧会各自添加一个 ( 和 ) 。举个例子，屏幕上显示 (|) 时按下 ( ，屏幕会显示 ((|)) 。

按下 ) 时，有两种情况：

  1. 屏幕上光标 | 的右侧是 ) 时，光标向右移动一格。如显示(|) 时按下 ) ，屏幕会显示 ()| 。
  2. 屏幕上光标 | 的右侧是 ( 或空白时，会在光标左侧添加一个 ) 。如显示()| 时按下 ) ，屏幕会显示 ())| 。

Asahi 输入括号序列后，打印下来后交给了你，然后就去河边捡石头了。注意打印后的括号序列是没有光标 | 的。你很好奇 Asahi 是怎么打出来的。请你给出一个程序，找出 Asahi 可能的最短输入序列。

输入

一行，一个仅包含 ( 和 ) 的字符串 $S$ ，表示 Asahi 给你的括号序列。$(1≤|S|≤10^6)$

输出

一行，符合要求的最短输入序列 TT ；若不存在则输出 Asahi?? 。

输入样例（1）

1
((()))

输出样例（1）

1
(((

输入样例（2）

1
(

输出样例（2）

1
Asahi??

输入样例（3）

1
)))()

输出样例（3）

1
)))(

样例解释

样例（1）的输入序列也可以为 ((() 、 ((()) 、((())) 等等，都符合条件，最短的是 ((( 。

author:Layn

这题自己打几个样例来就比较清晰了，主要是理解题意和分析所有可能的情况,需要注意的就是

  • 左括号一定会有有括号匹配
  • 右端若有未能匹配的右括号，左侧的所有括号一定会被敲出来，
  • 光标移动只能通过敲括号

V 查重红线 !

时间限制：1000ms 内存限制：65536kb

通过率：32/88 (36.36%) 正确率：32/936 (3.42%)

题目背景

⌈⌈ 御坂美琴 ⌋⌋ 正在学习 C 语言，她实在想不到这些题应该怎么写，于是她通过意念获取到了 ⌈⌈ 初春饰利 ⌋⌋ 一份已经 $\text{AC}$ 了的代码，但一想到有被查重的风险，她决定修改一下再提交上去。

这份代码一共有 $n$ 个语句，查重红线是 $m$ 个语句，也就是如果她提交的代码与 ⌈⌈ 初春饰利 ⌋⌋ 的代码有 $x$ 个语句不同，当 $x\le m$ 的时候会触发 1 次预警。

  • $x=0$ 的时候一定会触发预警，$x>n$ 的时候一定不会触发预警。
  • 预警次数达到 $3$ 次就算作抄袭，成绩清零！
  • 如果提交次数超过 $[\sqrt{2n}]$，就会被助教注意到并人工查重，同样会被发现抄袭，成绩清零！（其中 $[\ ]$ 表示四舍五入取整）

现在她想要通过多次试探性提交的方式，在成绩不被清零的前提下，猜出 $m$ 的值究竟是多少，你能帮帮她嘛？

题目描述

我们已经帮你实现好了两个函数 submit(x) 和 guess(x)，请你利用这两个函数帮她猜出 $m$ 的值。如果在 成绩不被清零 的前提下猜对了，你就能够 AC 本题，否则不能。

  • submit(x) 表示你提交了一份有 x 个语句不同的代码，可以调用不超过 $[\sqrt{2n}]$ 次。其返回值为本次提交的查重结果。
  • guess(x) 表示你最终猜测 $m$ 的值为 x，只能调用 $1$ 次，调用后我们会立即结束你的程序并判断是否猜测正确。这个函数没有返回值。

这两个函数的参数 $x$ 必须是一个 int 型变量，变量名不必为 $x$。

submit(x) 的返回值是 int 类型，其返回值含义如下：

返回值 含义
1 本次提交触发了预警
0 本次提交未触发预警
-1 成绩被清零（预警次数达到了 3 次，或提交次数超过了$\sqrt{2n}$）

NOT HINT

请务必在你的程序最前面完整地加入以下两行代码

（这是两个函数的实现，但你不必关心具体是如何实现的，更不要试图改动，以免发生意外错误~）

1
2
#define submit(x) (printf("%d\n",x),fflush(stdout),scanf(" "),(int)(getchar()-'0'))
#define guess(x) return (printf("m=%d\n",x),fflush(stdout))

输入

1 个正整数 $n$，保证 $3≤n≤10000$。

输出

无

输入样例

1
100

submit(x) 返回值样例

1
2
3
4
5
0
0
0
0
1

样例解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define submit(x) (printf("%d\n",x),fflush(stdout),scanf(" "),(int)(getchar()-'0'))
#define guess(x) return (printf("m=%d\n",x),fflush(stdout))  

#include<stdio.h>  
int main() 
{
    int n;
    scanf("%d", &n); //第一步先读入 n
    for(int i = n; i >= 0; i--) 
    {
        int jud = submit(i); // jud 中获得了这次提交是否预警的反馈
        if(jud == 1) 
        {
            guess(i); //猜测最终结果为当前的 i
        }
    }
    return 0; //这行可以省略，因为 guess(i) 自带 return
}

返回值样例或许可以来源于这个程序，这里每次 submit(i) 对应的不同语句数（i 的值）分别为 $100,99,98,97,96$，反馈依次为 $0,0,0,0,1$，说明查重红线 $m=96$。

但这是一个只能通过样例的示例，用来演示这个程序的结构。

如果 $n=100,m=1$ 那么这个示例程序显然因为提交次数过多就不能 AC 了！

此题需要格外注意限制条件，预警3次即清0，考虑到最后一定会经过从右往左扫描试出第一个预警值m，所以在此之前的阶段必须限制只能试错一次（现实是人生试错的次数太少了，故三思而后行）。相当于逐步缩小m所在的区间。一个可行的方法是从右往左扫描，但是提交次数是有限制的，如果m比较小，在试出答案前提交次数就已经消耗完了。所以应该采用“线性探测”方法，每次探测一段，逐步缩小范围——需要注意的是每探测一次会消耗一次提交次数，为保证每一个可能的区间能够被检测，因此，第$i$次探测的长度为$k-i,(k=\sqrt{2n})$,求和会发现$\sum_{i=1}^{i=k-1}(k-i)=k(k-1)/2=n-\frac{\sqrt{2n}}{2}$,理论上是不可能将整个区间给探测完的，所以这里 $hack$ 一下，面向结果编程，10个测试点不可能完全覆盖，多试探几次，在中间的空白段直接跳过就能过

这题刚开始没明白，自己计算的时候只是算了个大概的，但是这样没有严谨的证明反而会增加思维的负担，前面有好多次都试错

W 见证奇迹的时刻 ！

时间限制：1000ms 内存限制：65536kb

通过率：2/49 (4.08%) 正确率：2/115 (1.74%)

题目背景

相信大家都看了今年央视春晚的魔术，其本质是一个约瑟夫环问题，魔术流程如下：

  1. 将 $N$ 张牌对半撕开，一半整体放到另一半下面。
  2. 将第一张牌放到最后，重复次数 == 自己名字字数。
  3. 将前 $N−1$ 张牌插到中间，然后将第一张牌藏起来。
  4. 根据南北，将最前 1 或 2 或 3 张牌插到中间。
  5. 男生扔掉第 1 张牌，女生扔掉前 2 张牌。
  6. 将第一张牌放到最后，重复 $Q$ 次。
  7. 将当前第 1 张牌放到最后，再将此后第 1 张牌扔掉…… 重复此过程直到只剩一张牌。

最后剩的牌与藏起来的牌刚好能匹配，魔术成功。

题目描述

原魔术中 $N=4, Q=7$；当 $N>4$ 时，$Q$ 为能保证男女生在操作无误时都成功的最小值。

主持人在 第 4 步 中不小心把一张牌插到了最后，导致原来的最后 1 张牌变为了倒数第 2 张牌。不过或许他自己悄悄将 第 5 步 操作改为一次性扔掉前 $M$ 张，就依然有成功的可能。

现给出一个 $N$，请问是否存在一个满足下列条件的正整数 $M$，使得当 第 6,7 步 不再出错时，最终能成功匹配？

$$
⌊\frac{Q}{2 N−M−1}⌋≤\frac{2^{⌊\log _2Q⌋}}{2^{⌊\log _2(2N−M−1)⌋}}+2
$$

其中，$⌊X⌋$ 表示对 $X$ 向下取整。

输入

不定组输入，不超过 1000 组；每组 1 行，若干个整数。

每行第一个整数为 $t$，后面 $t$ 个整数，依次为 $a_1,a_2,a_3,…,a_t$，用来表示这一组数据的 $N$。$a_i$ 表示 $N$ 在二进制下从低位向高位数第 $i$ 个 1 出现在第 $a_i$ 位（最低位是第 0 位）。

保证 $4≤N≤2^{10^8}，1≤t≤1000$。

输出

每组 1 行。

若存在相应的 $M$，输出 YES。

若不存在相应的 $M$，输出 NO。

输入样例

1
2
2 2 0
4 3 2 1 0

输出样例

1
2
NO
YES

样例解释

第 $1$ 组数据中 $N=5$，此时不存在 $M$。

第 $2$ 组数据中 $N=15$，此时存在 $M=24$。

HINT

不难发现：$Q=2^y−1 , 2^{y−1}<2N−2≤2^y$

这是迷宫密码，本题不必理会：MSJ

这题觉得太长，连题都没有读完。但是经过这次练习，看到题目限制这么大的数据量，说明一定有常数时间的判断方法，否则就不能被解决，只不过是没明白罢了

X 国庆-Xhesica的集合

时间限制：1000ms 内存限制：65536kb

通过率：62/87 (71.26%) 正确率：62/162 (38.27%)

题目描述

Xhesica有一个集合 $S$ 用于存放一些正整数,一开始，$S$ 为空集 ，他首先将所有的位于 $l$ 和 $r$ 之间的整数插入集合 $S$ ,即满足当且仅当整数 $x$ 满足 $l≤x≤r$ 时，整数 $x$ 会被加入于集合中。随后, Xhesica 允许你进行接下来的操作:

选择仍然存在于集合中的三个不同的整数 $a,b,c$，满足 $\gcd(a,b)=\gcd(a,c)=\gcd(b,c)=1$，之后将这三个整数从集合中删去。

理论上最多能进行多少次操作呢?

注意，$\gcd(a,b)$指的是 $a$ 和 $b$ 的最大公因数。

输入

本题目包括多个测试用例，测试用例之间互相独立。

第一行仅有一个正整数 $t$,满足 $1≤t≤500$ ,表示测试用例的数量

接下来有 $t$ 行，每行表示一个测试用例，每行包括两个正整数 $l,r$ 满足 $1≤l≤r≤108$，表示含义同题目描述。

输出

对于每一个测试用例，输出一行，仅包括一个整数，表示本测试用例下你能进行的最多的操作次数。

输入样例

1
2
3
4
5
6
7
8
9
8
1 3
3 7
10 21
2 8
51 60
2 15
10 26
1 1000

输出样例

1
2
3
4
5
6
7
8
1
1
3
1
2
3
4
250

样例解释

对于测试用例 1，可以选择 $a=1，b=2，c=3$，之后集合变为空集，无法进行更多的操作。

对于测试用例 2, 可以选择 $a=3，b=5，c=7$ ,之后集合中仅剩下 $4,6$，无法进行更多的操作。

这题明确目标是使得在区间$[l,r]$中的操作$F(a,b,c)={a,b,c\in [l,r],\and\gcd(a,b)=\gcd(b,c)=\gcd(c,a)}$的次数最大化，$a,b,c$需要满足的条件就是三个数的最大公因数为1，其实简单写一写，就可以知道$\text{if}\ k\mod 2==0,\Rightarrow\ \gcd(k-1,k)=\gcd(k,k+1)=\gcd(k+1,k-1)=1$而且这样使得$a,b,c$三个数尽量的接近，使得能进行的操作次数达到最大化。如果这样连续分组，中间会空出一个偶数来，因此周期是4.需要注意的是考虑区间$[l,r]$的边界条件，合理的情况是按l和r的奇偶性分4种情况讨论

Y 摩卡与数学家水獭

时间限制：1000ms 内存限制：65536kb

通过率：122/176 (69.32%) 正确率：122/501 (24.35%)

题目描述

$\text{Moca}$ 非常喜欢水獭，一天，她遇到了一只被难题困扰着的数学家水獭。

对于一个给定的正整数，显然可以把它分解为若干质数的和。数学家水獭想知道，对一个给定的正整数，把它分解为若干质数（可以重复）需要的质数个数最少是多少。

由于这个问题太难了，数学家水獭希望 Moca 编程帮它得到 $5×106$ 以内的结果。

输入

第一行一个正整数 $n$ ，表示接下来会有 $n$ 组输入，$1≤n≤500000$ 。

接下来 $n$ 行，每行一个正整数 $k$ ，代表数学家水獭每次询问的正整数，有 $2≤k≤5×106$ 。

输出

输出 $n$ 行，每行一个正整数，代表对应输入的正整数被分解的最少的质数个数。

输入样例

1
2
3
4
5
4
3
9
12
27

输出样例

1
2
3
4
1
2
2
3

样例解释

对于 $3$ ，质数个数最少的分解为 $3=3$ ，只需要 $1$ 个质数。

对于 $9$ ，质数个数最少的分解为 $9=2+7$ ，需要 $2$ 个质数。

对于 $12$ ，质数个数最少的分解为 $12=5+7$ ，需要 $2$ 个质数。

对于 $27$ ，质数个数最少的一种分解为 $27=3+7+17$ ，需要 $3$ 个质数。

分解质因数

著名的哥德巴赫猜想，小学生都知道的陈景润证明$1+1$的情况，

果然是大数学家。Goldbach猜想，任何大于2的偶数都可以分解为两个素数相加，二任何大于2的质数则可以表示成3个质数之和

对于是奇数而非质数时，考分解为一个2和质数，其余则是根据定理[^1]

判断即可，对于素数的判断，可以进行素数测试（前面有Miller Rabin测试可以判断$2^{32}$以内的整数

zhu 数学、物理百科之根基。有复变，实变，拓扑等广阔数学分支，而计算机领域也是常常用到，益自学数学，物理，提高自己的理论分析水平

但是本题主要逻辑流是在查询素数上，而且数据范围也不大，所以使用素数表是一个明智选择。打表根据优化情况，一般是根据对称性将区间缩小为$[1, \sqrt{n}]$ 然后使用筛素数的方法来处理，然而筛素数又有多种方法，一般有埃氏筛，但是效率较低，这里选用欧拉筛

Z 摩卡与取石子游戏

时间限制：1000ms 内存限制：65536kb

通过率：91/151 (60.26%) 正确率：91/372 (24.46%)

题目描述

在受到数学家水獭的启发后，Moca 想到了一个好玩的游戏，她决定邀请 Ran 一起玩这个游戏。

游戏规则如下：现在有 $n$ 个石子，Ran 先手，每名玩家每次可拿走质数个石子（拿走的石子不可能比剩下的石子多，也就是说此质数应该小于等于剩下的石子数），轮到一位玩家时不能不拿。将最后一个石子取走的玩家获胜；或者当某位玩家取完石子后，若场上只剩下一个石子，则对方获胜。

Moca 和 Ran 都很聪明，她们每次都会选择最优策略来进行操作。请你编写一个程序，判断出在一个给定的初始局面下两个人谁会赢。

输入

第一行一个正整数 $t$ ，表示输入数据组数，其中 $1≤t≤106$。

接下来 $t$ 行每行一个正整数 $n$ ，表示初始的石子数，其中 $2≤n≤109$。

输出

每组输入对应一行输出，若 Ran 获胜（先手获胜），则输出 Ran ；若 Moca 获胜（后手获胜），则输出 Moca。

输入样例

1
2
3
4
3
3
4
8

输出样例

1
2
3
Ran
Moca
Moca

样例解释

若初始有 3 个石子，则 Ran 拿走 3 颗石子后获胜。

若初始有 4 个石子，如果 Ran 拿走 3 颗石子，则剩下 1 颗石子，根据获胜规则二，Moca 获胜；若 Ran 拿走 2 颗石子，Moca 再拿走 2 颗石子，根据获胜规则一，Moca 获胜。

若初始有 8 个石子，如果 Ran 拿走 3 颗石子，Moca 再拿走 5 颗石子，根据获胜规则一，Moca 获胜；若 Ran 拿走 5 颗石子，Moca 再拿走 3 颗石子，根据获胜规则一，Moca 获胜；若 Ran 拿走 2 颗石子，Moca 再拿走 2 颗石子，此时剩下 4 颗石子，且 Ran 先拿，根据上个样例，Moca 获胜。

Author：Moca

这种博弈问题真的不会做，在经过“猪脚”步步引导后，终于理解一点先后手的博弈状态。

整个过程可以说是行云流水，非常丝滑。首先样例是给了一些提示的，（理所当然），类比同类问题：一次可以取一个或者两个的问题，如何判断这样对局（这种题一般需要找到先手必输的条件，如果当前先手能够将当前局面转化成先手必输，则当前局面就是先手必赢。一个小提示：和余数有关。具体的策略是谁能让最后一个回合场上剩下$m+1$个谁就赢。现在推广一下，如果你能拿超过m个呢？核心策略依旧是维持$m+1$或者$m+1的倍数个$，为了维持这个状态，所以我们需要使每一个回合取得子数为m+1的倍数个（这是中间过程）。

现在考虑开始时，如果开具不是$m+1$的倍数个，先手就会让他剩$m+1$的倍数个，然后自己就可以当后手

那么对于质数来说，这个$m$是多少？也就是说，$m$取多少能保证质数里没有$m+1$的倍数，并且模$m+1$等于1到$m$的均存在

其实只有一个m能满足上述条件，$m+1=4$

总结：这种博弈题一般都是先看后手必胜的条件，其余情况先手只需要能转换成后手必胜的情况即可。有可能会有余数、位运算等思考角度

#I 💖 [PUAA]
Summary3
http://example.com/2024/10/09/Summary3/
作者
独步星尘
发布于
2024年10月9日
许可协议