NOI2024省选训练赛 11 解题报告
目录A. 小L的栈
Description
有一个栈和 \(n\) 个元素，这 \(n\) 个元素要依次入栈，并且最终全部出栈，要求第 \(m\) 个元素入栈后，栈内恰好有 \(k\) 个元素。
求方案数，对 \(10^9+7\) 取模。
Constraints
对于 \(30\%\) 的数据，\(n,m,k\le30,T\le 100\)
对于另外 \(30\%\) 的数据，\(n,m,k\le 10^3,T\le 10\)
对于 \(100\%\) 的数据，\(1\le n,m,k \le 10^6,T\le 10000\)
Solution
这题用了一个神秘的公式，扩展卡特兰数：有 \(n\) 个左括号和 \(m\) 个右括号，组成一个串，任何一个前缀的左括号个数都不少于右括号个数，那么不同的串的个数为：\({n+m \choose m}-{n+m \choose m-1} \; (n\ge m)\) 。
当第 \(m\) 个元素入栈后，栈内恰有 \(k\) 个元素，也就是说，前面总共有 \(m\) 次入栈操作，\(m-k\) 次出栈操作。
后面要把所有元素入栈后出栈，所以有 \(n-m\) 次入栈操作，\(n-m+k\) 次出栈操作。
我们分别套用扩展卡特兰数的计算公式即可。对于后面的情况，我们修改扩展卡特兰数的计算公式：有 \(n\) 个左括号和 \(m\) 个右括号（\(n \le m\)） ，组成一个串，使得任何后缀的右括号个数不少于左括号个数，那么共有 \({n+m \choose n}-{n+m \choose n-1}\) 种串。（相当于对反串做这个公式）
Conclusion
赛时除了扩展卡特兰公式以外的东西都想到了，推了半天式子都没推出来，现在也证不出来这个式子，就姑且先当个结论背着。
B. interval
Description
给定一个长度为 \(n\) 的序列。
支持以下两种操作：
- 第一种操作输入 \(l,r,x\) ，问能否在最多修改区间 \([l,r]\) 内一个数字的情况下，使得区间 \([l,r]\) 的 gcd 为 \(x\) 。
- 第二种操作输入 \(x,c\) ，表示将第 \(x\) 个值变为 \(c\)
总共有 \(q\) 次操作。
Constraints
对于 \(100\%\) 的数据，\(n,m \le 50000,a_i \le 10^9\)
Solution
第一种操作相当于问区间里面是否有多于 1 个数不是 \(x\) 的倍数。
用线段树维护区间 gcd，每次问询考虑当前区间：
- 如果区间 gcd 是 \(x\) 的倍数，那么直接返回
- 否则分别递归两个子区间计算。
递归处理问询的时候维护一个全局的计数器 \(cnt\)，表示当前已经有多少个节点所维护的区间的 gcd 不是 \(x\) 的倍数，当 \(cnt\) 的值大于 1 的时候，就可以直接结束递归。
Conclusion
鉴定为，莫队莫傻了，直接往莫队的方向想，写了一个带修莫队，然后发现思路假了。主要是第一步（也就是把问询转化为统计非 \(x\) 的倍数的数的个数）让我往莫队那个方向去想了，这种多个区间统计，而且可以离线的东西太容易让人想到莫队了。
但是，如果只关注区间 gcd 这个点的话，就可以很直接的想到线段树。
C. Digit Sum
Description
对于任意非负整数 \(x\) 和 \(m(2\le m)\) ，定义 \(f_m(x)\) 为 \(x\) 在 \(m\) 进制下的各位数字之和。例如 \(f_{10}(87654)=8+7+6+5+4=30,f_{100}(87654)=8+76+54=138\)。
给定两个整数 \(x\) 和 \(n\)，你需要计算是否存在某个 \(m\ge 2\) 使得 \(f_m(x)=n\) 。如果存在，输出最小的满足条件的 \(m\) ；如果不存在，输出 \(-1\)。
Constraints
对于 \(30\%\) 的数据，\(1\le x,n \le 10^6\)
对于 \(100\%\) 的数据，\(1\le x,n\le 10^{11}\)
Solution
考虑一个根号分治：
如果进制数 \(m\le \sqrt x\) ，那么我们可以枚举 \(m\)，然后计算是否合法。复杂度为 \(O(\sqrt x \log x)\)
否则，\(x\) 在 \(m\) 进制下只有两位，我们枚举高位，然后计算低位，并且以此判断是否存在对应的基数即可。由于在这种情况下，基数是大于 \(\sqrt x\) 的，所以高位最多是 \(\sqrt x\) ，因此复杂度是 \(O(\sqrt x)\)
所以，单次问询的复杂度是 \(O(\sqrt x \log x)\)
Conclusion
这种和进制以及数位和相关联的题目，一般而言是考虑数位 dp 或者同余最短路 ，但是这题并不是。这题用到了这样的一个思考：\(m\) 只能取 \([2,x+1]\) 之间的整数，当 \(m\) 比较大的时候，\(x\) 在 \(m\) 进制下对应的数位数不会很多，可以考虑直接枚举。而在 \(m > \sqrt x\) 的时候，\(x\) 在 \(m\) 进制下就只有两位了，因此对于较大的情况，我们枚举两位数；对于较小的情况，我们直接枚举 \(m\) 。
D. 机器故障探测
Description
有 \(n\) 个机器，其中有 \(m\) 个是坏的。
每次能问询 \(k\) ，返回 \(1,2,\dots,k-1,k\) 的前缀里面是否有坏掉的机器（YES/NO）。
当你能百分百推断出某台机器是坏的时，你可以立即修复它，接下来的回答里就不会再认为它是坏掉的。
问在最优操作下，在最坏情况下最少需要问询几次。
补充说明：这个所谓的“百分百推断出某台机器是坏的”，是指：问询 \(k-1\) 时回答没有坏的，问询 \(k\) 时，回答有坏的，所以推断出 \(k\) 是坏的。
而不是：我有 \(n\) 台机器，其中 \(m=n\) 个是坏的，所以我不需要问询，全部都修好。换而言之，修理人员是不知道实时的损坏机器的数量的。
这点东西题目又不写清楚，又没给满足这个性质的样例，赛时问了又没人回我，就很离谱。
Constraints
本题共十个测试点。
第 \(1\sim 3\) 号测试点，满足 \(n\le 8,m\le 2\)
第 \(6\) 号测试点，满足 \(m=n\)
第 \(1 \sim 7\) 号测试点，满足 \(1\le m \le n \le 50\)
第 \(7,8\) 号测试点，满足 \(m=1\)
对于所有的测试点，满足 \(1\le m \le n \le 500\)
Solution
考虑 dp
\(f(i,j,k)\) 表示 \(i\) 台机器中有 \(j\) 台是坏的，且已知 \([1,k]\) 里至少有一台是坏的最小步数。答案为 \(f(n,m,n)\)
转移：
若 \(k=1\) ，则 \(f(i,j,k)=f(i-1,j-1,k-1)\)
否则，\(f(i,j,k)=\min_{p=1}^{k-1} \{ \max(f(i,j,p)+1,[j\le i-p]?f(i-p,j,k-p)+1) \}\)
注意到 \(k\) 递增时，决策转移点 \(p\) 也递增。
利用决策单调性，复杂度 \(O(n^3)\)
标签：11,10,le,测试点,省选,问询,sqrt,括号,训练赛 From： https://www.cnblogs.com/hsfzbzjr2008/p/NOI2024_11.html