当前位置：首页 > news >正文

20260224 模拟测总结

news 2026/3/27 3:14:33

Preface

AK J 的感觉就是这么爽 /oh

~~我要是能 AK S 就好了呜呜。~~

T1

估分	得分	挂分
\(100\)	\(100\)	\(0\)

白白送你的 \(100\) 分 /tiao
你只需要读入字符串然后判断一下第一位是 \(0\) 还是 \(1\)，是 \(0\) 就直接原样输出，是 \(1\) 则翻转后面的每一位然后输出即可。

T2

估分	得分	挂分
\(100\)	\(100\)	\(0\)

不开 long long 会见祖宗，嗯对。

考虑将这个数组首尾相接形成一个环，求出这个环的价值（也就是任意两个相邻数字的异或值之和），令其为 \(sum\)。数组形态的价值则一定是 \(sum\) 减去该数组形态下首尾异或的值。

于是我们只需要先算出 \(sum\) 然后实时维护当前数组的最后一位（或者第一位）在原数组中的下标即可解决该题啦。

T3

估分	得分	挂分
\(100\)	\(100\)	\(0\)

有一点诈骗题的意思诶。

不难发现，想判断一个 \(\gcd g\) 是否合法，只需求出最小的满足 \(xg \ge l\) 的 \(x\)，以及最大的满足 \(yg \le r\) 的 \(y\)，判断是否 \(xg < yg\) 即可。

由于在区间 \([l,r]\) 内取两数求出的 \(\gcd\) 最大也只有 \(r-l\)，所以我们直接从 \(r-l\) 开始倒序枚举 \(\gcd\) 然后按上面所述方式判断，若满足条件则直接输出并 break 循环。

然后就做完啦。

T4

估分	得分	挂分
\(?\)	\(100\)	\(?\)

~~别问我为什么估分是问号，问就是赛时我觉得我的做法假完了。~~

哇哦，大家写的都是大炮，正解也是大炮，我这个 fw 贪心怎么过了呀！/jy

我们不难发现，如需将原数组修改为波浪数组，只需确定前两个数的值及其大小关系，就可以顺势推导出后续所有 \(a'\)。具体地，对于 \(3 \le i \le n\)：若 \(a'_{i-2} > a'_{i-1}\) 且 \(a_i \ge a'_{i-1}\) 有 \(a'_i = \min(a'_{i-2},a_{i+1})-1\)，若 \(a'_{i-2} > a'_{i-1}\) 且 \(a_i \le a'_{i-1}\) 有 \(a'_i = \max(a'_{i-2},a_{i+1})+1\)，其他情况均 \(a'_i = a_i\)。

于是现在只需要考虑前两个数了。只有两种大小关系，要么 \(a_1 < a_2\) 要么 \(a_1 > a_2\)，于是至少有两种方案。针对这两种大小关系，还分别有修改 \(a_1\) 和修改 \(a_2\) 两种情况（若原来就是满足大小关系的则无需修改），于是总共可理解为 \(4\) 种方案。分别跑上述贪心最后将修改次数取 \(\min\) 即为答案。

我感觉不写正解不太好诶 /kel，那我再写一篇关于正解的。

考虑 DP。首先肯定有大小关系的定义，以及需确定每个位置的数值是否被修改过，于是不难定义 \(dp_{i,0/1,0/1}\) 表示当前考虑到数组中第 \(i\) 个数，且该数比上一个数小还是大，及该数是否被修改过，的状态下最少的修改次数。

显然有初值 \(dp_{1,0,0} = dp_{1,1,0} = 0\) 及 \(dp_{1,0,1} = dp_{1,1,1} = 1\)。

接下来考虑转移。

\(dp_{i,0,0}\)：第 \(i\) 个数无修改，且 \(a'_i < a'_{i-1}\)。
- 显然可以继承，\(dp_{i,0,0} = dp_{i-1,1,1}\)。
- 若 \(a_i < a_{i-1}\) 则也可从 \(dp_{i-1,1,0}\) 转移。
\(dp_{i,1,0}\)：第 \(i\) 个数无修改，且 \(a'_i > a'_{i-1}\)。
- 也可以继承，\(dp_{i,1,0} = dp_{i-1,0,1}\)。
- 若 \(a_i > a_{i-1}\) 则也可从 \(dp_{i-1,0,0}\) 转移。
\(dp_{i,0,1}\)：第 \(i\) 个数修改过，且 \(a'_i < a'_{i-1}\)。
- 由于该数被修改过，因此只要大小关系确定即可转移，故从 \(dp_{i-1,1,0}\) 或 \(dp_{i-1,1,1}\) 取较小转移。
- 可得转移式 \(dp_{i,0,1} = \min(dp_{i-1,1,0} , dp_{i-1,1,1}) +1\)。
\(dp_{i,1,1}\)：第 \(i\) 个数修改过，且 \(a'_i > a'_{i-1}\)。
- 该数同样被改过，因此只要大小关系确定即可转移，故从 \(dp_{i-1,0,0}\) 或 \(dp_{i-1,0,1}\) 取较小转移。
- 可得转移式 \(dp_{i,1,1} = \min(dp_{i-1,0,0} , dp_{i-1,0,1}) +1\)。