Alice and Recoloring 1


题目描述题目传送门思路好妙好妙的构造题!没想到对矩阵的转化qwq不妨假设 W 为 111,B 为 000。显然操作 2、3 都可以由两次操作 1 容斥得到,而且花费更优。可以不考虑。于是我们只需要考虑操作 1、4 的贡献。矩阵的全部元素翻转相当于子矩阵异或 111。处理矩阵很麻烦,有没有办法将矩阵信

[CERC2014]The Imp


题目传送门题目传送门思路Lemma. 按照 viv_ivi​ 升序购买一定最优。Proof. 设先后购买的为 (v1,c1),(v2,c2)(v_1,c_1),(v_2,c_2)(v1​,c1​),(v2​,c2​) 其中 v1≤v2v_1 \le v2v1​≤v2。此时的答案为 min⁡(v1−c

选举预测


题目描述题目传送门思路看到 $n \le 10^6$,显然会有一些结论。结论1能打败人最多的人可能胜利。证明:假设打败人最多的人(称其为 Cms)不可能胜利,那必定有人(下文称其为石老板)可以打败他和他所有能打败的人,否则可能出现 Cms 打败的人干掉了石老板,然后 Cms 干掉了他,取得胜利。为了

[ARC093A] Traveling Plan


题意简述数轴上有 $N$ 个点,一开始在 $0$ 位置上,需要去 $N$ 个点(顺序从 $0$ 号点按顺序走完 $N$ 个点),最后回到 $0$ 位置。对于 $i=1, 2, \ldots, N$ 分别输出不需要去 i 号点的最小路程。思路又是一道水题。。。首先,我们考虑不走 $i$ 原路径会发生什

CF1638C Inversion Graph


题面简述现在有一个序列 $p_1,p_2,\dots,p_n$,你需要构建一个无向图,规则是:当 $i < j$ 且 $p_i > p_j$ 时在 $i$ 和 $j$ 之间连一条无向边。问最后图中会有几个连通块。题目传送门思路我们考虑什么时候会形成一块。很显然,当 $\max\limit

CF1638A Reverse


题意简述给你一个序列 $p_1,p_2,\dots,p_n$ ,保证序列中的数字不重复且为 $1$ ~ $n$ 。你可以选择反转序列中的一个区间(当然也可以不反转),求操作后字典序最小的序列。题目传送门思路首先我们可以检查该序列是否有序,有序(即 $p_i=i$)时则已经为字典序最小,则不用反转。在

CF1203E Boxers


思路用一个类似桶的结构,存储每个体重存在的数量然后进行贪心即可每个体重有用的人数最多为三人并且能够加入 $Ans$ 与且仅与上一个体重的人和下一个体重的人有关那我们只需从小到大进行贪心,注意有个细节:要先判断当前位置的上一个(使其+1),然后再是当前体重(不变),最后是下一个体重(使其-1)【与贪心

CF1566A Median Maximization


题面描述给定 $n$ 和 $s$ , 找到 $n$ 个和为 $s$ 的数,使得他们的中位数最大分析看到题面直接选择贪心,中位数前均为 $0$ (即前 $\frac{2} - 1$ 个数字) , 中位数以及中位数以后的数相等 , 即为 $\frac{n - (\frac{2})}$贪心入门标程#inc

AT197 簡易オセロ


题解 AT197 簡易オセロ题意描述两个人玩一种神奇的游戏,求两人玩了一局后哪方所在棋盘上的棋子多思路由于每次放置棋子后会影响直线上的点,易知:只要棋盘两端点都是一方的棋子,那么就绝杀对方但是,如果棋盘两边棋子不同呢?仔细分析题目, $o$ 只需从一段往另一端放置就必胜,所以 $o$ 胜利时只需占领

AT5158 [AGC037A] Dividing a String


题目描述给定一个字符串 $S$;将该字符串划定为 $k$ 段,保证每一段不同试求 $k$ 是多少思路本题适合我这样的萌新练习贪心大法只需从头扫到尾,记录现在选择的字符串,再用一个变量记录上一个选择的字符串,如果现在选择的字符串与上一个选择的不同,直接 Ans++, 并将上一个选择的字符串改为现在选择