Alice and Recoloring 1


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

[CERC2013] Magical GCD


https://www.luogu.com.cn/problem/P7009

[集训队作业2013]城市规划


题目描述题目传送门思路套路题。设 fif_ifi​ 表示由 iii 个点所组成的联通无向图个数,gig_igi​ 表示由 iii 个点组成的无向图个数,不保证联通。由于没有重边与自环, iii 个点最多有 (n2)\binom{n}{2}(2n​) 条边,则有 gi=2(n2)g_i = 2^{\b

[USACO22DEC] Bribing Friends G


题目描述题目传送门思路有显然的三维 dp。设 fi,j,kf_{i,j,k}fi,j,k​ 表示前 iii 个朋友用了 jjj 个哞尼和 kkk 个冰激凌甜筒能得到的最大价值。那么有:fi,j,k=max⁡w>ci,w×xi>k{fi−1,j,k,fi−1,j−ci+w,k−w×xi+p

[PA2021] Od deski do deski


题目描述题目传送门思路计数题,很容易想到 dp。难点在于状态的设计,显然有一维状态是序列长度,有一维表示合法与否,dp 值表示为方案数,记为 fi,0/1f_{i,{0/1}}fi,0/1​。这样是没有办法转移的,因为我们接下来要填什么与之前填的数字有关,考虑加维。发现对于一个合法序列 SSS,假设

CF1616F Tricolor Triangles


题目描述题目传送门思路发现一个边权为 1,2,31,2,31,2,3 的三元环三边全部相同或不相同有一个共同的条件: 三边和为 333 的倍数。注意到这点就可以暴力把所有三元环找出来,然后根据题目要求列出方程,跑模 333 意义下的高斯消元即可。根据经典结论,三元环个数为 O(mm)\mathcal

[ABC289G] Shopping in AtCoder store


题目描述题目传送门思路先将 BBB 和 CCC 从小到大排序。显然的,每一个 PiP_iPi​ 都可以表示为 Bj+CiB_j + C_iBj​+Ci​。称 BjB_jBj​ 为 CiC_iCi​ 的最优决策。然后还可以发现答案具有单调性,如果 BjB_jBj​ 是 CiC_iCi​ 的最优决策,那

CF750E New Year and Old Subsequence


定义一个数字串满足性质$nice$当且仅当:该串包含子序列$2017$,且不包含子序列$2016$。 定义一个数字串的函数$ugliness$为:该串至少删去几个字符,可以使得剩余串满足性质$nice$;如果该串没有满足性质$nice$的子序列,则该串的$ugliness$是$-1$。 给定一个长度为$n$的字符串$t$,和$q$次询问,每次询问用$(l,r)$表示。对于每次询问,回答$ugliness(t[l,r])$。

CF1616D Keep the Average High


题目描述题目传送门给定一个长 nnn 的数列 aaa,再给定一个 xxx。你需要选中其中一些数,使得对于所有连续的被选中的长度至少为 222 的子串 $[l,r] $ 满足:∑i=lrai≥(r−l+1)×x\sum_{i=l}^ra_i\ge (r-l+1)\times xi=l∑r​ai​≥(r

CF1245F Daniel and Spring Cleaning


题目描述题目传送门简意:给定 l,r(0≤l,r≤109)l,r(0 \le l,r \le 10^9)l,r(0≤l,r≤109),求:∑a=lr∑b=lr[a+b=a⊕b]\sum_{a=l}^r \sum_{b=l}^r[a+b = a \oplus b]a=l∑r​b=l∑r​[a+b=a⊕