题意简述 有一个含有 nnn 个数字的数组 aaa（n≤1000n\le1000n≤1000），有 kkk 个不重合的集合 S1,S2,⋯ ,SkS_1,S_2,\cdots,S_kS1​,S2​,⋯,Sk​，集合元素为 111 到 nnn 的整数，由此生成一个长度为 kkk 的密码 ppp，定义 pi=max⁡j∉Siajp_i=\displaystyle\max_{j\notin S_i}a_

我的方法使用了动态规划和树状数组，可能并不简洁，但题解太简略了，我暂时也不清楚怎么简单地维护题解里的 uuu 和 vvv，其他部分是原题解的详细版本。 首先分析一下操作（方便描述，标了个号）： 将 aaa 循环左移一位。若在进行操作前 a1≠0a_1\neq 0a1​=0，则消耗 xxx 点代价。 将 aaa 循环右移一位。若在进行操作前 a1≠0a_1\neq 0a1​=0，则消耗 yy

本次比赛难度为入门至提高+/省选。 但是没有入门。 首先考虑最小值，如果只有一只羊感染，那么它传染边上任何一个位置，然后两只羊互相传染就行了，最小值是 222 只。如果有更多的羊感染，它们只要紧挨着排列，每一只都传染给边上已经感染的，最小值是 xxx 只。于是有： ansmin⁡=max⁡{2,x}ans_{\min}=\max\{2,x\} ansmin​=max{2,x} 然后是最大值，先

正难则反，考虑后涂色的不会被先涂色的覆盖，因此可以到序求解。 具体的，先找出输入矩阵中字典序最大的字母，从这个字母开始倒序枚举。 对于每一个字母，有出现过和没有出现过两种情况，如果没有出现过，直接在一个比它大的位置涂色一格就可以了（这一格将被覆盖，等于没涂），实现时可以直接填充为最后一个字母的第一格。如果出现过，判断它是否合法：首先判断出这个字母出现的所有位置是否都在同一行或同一列，再判断出现顺序

快捷键表 编译与查看：\ll 编译，:copen看日志 快捷编辑 Key = Key = bd \begin{document} ed \end{document} be \begin{enumerate} ee \end{enumerate} bc \begin{cneter} ec \end{center} c \chapter{ s \section{ p \p

贪心地，依次扫描每一行（列），如果当前格子有球，将它打上标记，如果没有球且之前没有打过标记，直接进入下一行（列），最终统计有没有有球而没有标记的格子，如果有，说明不合法，否则合法。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include<

分类讨论。 【111】当 mmm 是奇数时，构造 $ \text{abababab} \cdots$ 的串即可满足题意，于是直接交替输出 111 和 222 凑足 m+1m+1m+1 个即可。 【222】当 mmm 是偶数时： 【2.12.12.1】存在一个点对，来回字母一样，如下图： 这时显然和【111】相同处理即可。 【2.22.22.2】存在三个点，路径上字母相同，如下图： 这时构造一个

提供一种简单的线段树写法。 首先，给出朴素的 DP，令 dpi,jdp_{i,j}dpi,j​ 表示前 iii 种食物，第 iii 种选择了 jjj 的最小花费，显然得出转移： dpi,j=min⁡(j,k) is OKdpi−1,k+ci,jdp_{i,j}=\min\limits_{\text{(j,k)\ is\ OK}}dp_{i-1,k}+c_{i,j} dpi,j​=(j,k) is

正难则反，倒序操作，操作的一定是四个同色格子（或者其中有已经完成操作的点，其他同色），可以从此入手进行 DFS。 遍历每一个点，对其进行 DFS，首先检查是否已经完成处理（被标记为 000）、越界或者不符合条件（有杂颜色），如果没有问题，标记这四个格子（改为 000），对其四周的格子进行搜索，具体的，分别是以下 888 个点： 1234dfs(x-1,y);dfs(x-1,y+1);dfs(x+2

如果存在 uuu 不在 vvv 的子树内且 wu>wvw_u>w_vwu​>wv​，则最大的 vvv 一定是可行的点。 此时，选择了这个点后，对方将无法选出一个点使得消除后剩下的点大于选择的点，因此可行。如果选择不出这样一个点，则无解。 首先想到枚举 vvv，并要求在 O(log⁡n)O(\log n)O(logn) 时间内完成判断。看到这个时间复杂度以及最大值，我想到的是线段树