[ARC127E] Priority Queue 发表于 2023-07-13 | 分类于 默认分类 | 0 | 阅读次数 559 题目描述题目传送门思路正着做比较困难,反着来。假设 {a}\{a\}{a} 是我们最后剩下来的集合。可以发现一个结论:aaa 是一个单调上升序列肯定不劣。这样我们可以从头开始加入数字。每一此 2 操作实际上可以与其之前的 1 操作抵消。所以我们无需考虑二操作。由于我们可以证明 aaa 单调升。可以设 阅读全文 »
[CCC2021 S3] Lunch Concert 发表于 2023-07-08 | 分类于 默认分类 | 0 | 阅读次数 524 https://www.luogu.com.cn/problem/P9025 阅读全文 »
Alice and Recoloring 1 发表于 2023-07-03 | 分类于 默认分类 | 0 | 阅读次数 446 题目描述题目传送门思路好妙好妙的构造题!没想到对矩阵的转化qwq不妨假设 W 为 111,B 为 000。显然操作 2、3 都可以由两次操作 1 容斥得到,而且花费更优。可以不考虑。于是我们只需要考虑操作 1、4 的贡献。矩阵的全部元素翻转相当于子矩阵异或 111。处理矩阵很麻烦,有没有办法将矩阵信 阅读全文 »
[CERC2013] Magical GCD 发表于 2023-06-30 | 分类于 默认分类 | 0 | 阅读次数 481 https://www.luogu.com.cn/problem/P7009 阅读全文 »
[集训队作业2013]城市规划 发表于 2023-05-25 | 分类于 默认分类 | 0 | 阅读次数 513 题目描述题目传送门思路套路题。设 fif_ifi 表示由 iii 个点所组成的联通无向图个数,gig_igi 表示由 iii 个点组成的无向图个数,不保证联通。由于没有重边与自环, iii 个点最多有 (n2)\binom{n}{2}(2n) 条边,则有 gi=2(n2)g_i = 2^{\b 阅读全文 »
[USACO22DEC] Bribing Friends G 发表于 2023-05-19 | 分类于 默认分类 | 0 | 阅读次数 529 题目描述题目传送门思路有显然的三维 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 发表于 2023-05-17 | 分类于 默认分类 | 0 | 阅读次数 569 题目描述题目传送门思路计数题,很容易想到 dp。难点在于状态的设计,显然有一维状态是序列长度,有一维表示合法与否,dp 值表示为方案数,记为 fi,0/1f_{i,{0/1}}fi,0/1。这样是没有办法转移的,因为我们接下来要填什么与之前填的数字有关,考虑加维。发现对于一个合法序列 SSS,假设 阅读全文 »
CF1616F Tricolor Triangles 发表于 2023-05-14 | 分类于 默认分类 | 0 | 阅读次数 520 题目描述题目传送门思路发现一个边权为 1,2,31,2,31,2,3 的三元环三边全部相同或不相同有一个共同的条件: 三边和为 333 的倍数。注意到这点就可以暴力把所有三元环找出来,然后根据题目要求列出方程,跑模 333 意义下的高斯消元即可。根据经典结论,三元环个数为 O(mm)\mathcal 阅读全文 »
[ABC289G] Shopping in AtCoder store 发表于 2023-02-25 | 分类于 默认分类 | 0 | 阅读次数 980 题目描述题目传送门思路先将 BBB 和 CCC 从小到大排序。显然的,每一个 PiP_iPi 都可以表示为 Bj+CiB_j + C_iBj+Ci。称 BjB_jBj 为 CiC_iCi 的最优决策。然后还可以发现答案具有单调性,如果 BjB_jBj 是 CiC_iCi 的最优决策,那 阅读全文 »
CF750E New Year and Old Subsequence 发表于 2023-01-13 | 分类于 默认分类 | 0 | 阅读次数 519 定义一个数字串满足性质$nice$当且仅当:该串包含子序列$2017$,且不包含子序列$2016$。 定义一个数字串的函数$ugliness$为:该串至少删去几个字符,可以使得剩余串满足性质$nice$;如果该串没有满足性质$nice$的子序列,则该串的$ugliness$是$-1$。 给定一个长度为$n$的字符串$t$,和$q$次询问,每次询问用$(l,r)$表示。对于每次询问,回答$ugliness(t[l,r])$。 阅读全文 »