Alice and Recoloring 1
题目描述题目传送门思路好妙好妙的构造题!没想到对矩阵的转化qwq不妨假设 W 为 111,B 为 000。显然操作 2、3 都可以由两次操作 1 容斥得到,而且花费更优。可以不考虑。于是我们只需要考虑操作 1、4 的贡献。矩阵的全部元素翻转相当于子矩阵异或 111。处理矩阵很麻烦,有没有办法将矩阵信
[集训队作业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=maxw>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∑rai≥(r