「CF353E」 Antichain-乱搞
· ✏️ 650 words · ☕ 2 mins read

给定一个长度为 n01 序列,第 i 位是 0 代表 节点 i 到节点 imodn+1 有一条有向边,第 i 位是 1 代表 节点 imodn+1 到节点 i 有一条有向边。

我们称一个节点对 (u,v) 是妙的当且仅当不存在 uvvu 的路径任何两者之一。

现在你要从这个图里面挑出一个集合,使得集合中任意两个不同的节点 uv 之间构成的节点对 (u,v) 都是妙的。

请你输出这个集合的大小的最大值。


「CF581F」 Zublicanes and Mumocrates - 树形dp
· ✏️ 580 words · ☕ 2 mins read

一棵树上有 n 个节点,把每个节点染成黑色或白色,要求叶子节点一半是黑色,一半是白色(保证叶子节点的个数是偶数)。

求在满足要求的情况下,最小的两端颜色不同的边的数量。


朋友们
· ✏️ 3 words · ☕ 1 mins read
cqqqwq的朋友们。

「CF804D」Expected diameter of a tree-树的直径+乱搞
· ✏️ 1006 words · ☕ 3 mins read

给定一个含有 n 个点, m 条边的森林。有 q 个询问,每次给出两个点 ui,vi ,如果 ui 在联通块 A 内,vi 在联通块 B 内,我们随机选择两个点 aA,bB ,我们在 (a,b) 之间连一条边,如果这个连接成后新联通块不构成一个树,输出 1 ,否则输出新联通块树的直径的期望。所有边权均为 1


「CF543C」Remembering Strings-状态压缩dp
· ✏️ 658 words · ☕ 2 mins read

给定 n 个长度均为 m 的字符串,再给出一个 nm 列的矩阵 anm
矩阵元素 aij 代表把第 i 个字符串第 j 个字符改成其它任意字符所需要的代价。

现在要求对于任意一个字符串,总存在某一位置 j 使得该位置上的字符在任意其他字符串该位置的字符不同。

即为对于第 x 个字符串 ,有 j[1,m],i[1,n],sxjsij

求把所有字符串修改成满足上述要求的字符串的最小代价是多少?

数据范围: 1n,m20,1aij106


「CF321E」Ciel and Gondolas-wqs二分+决策单调性
· ✏️ 739 words · ☕ 2 mins read

Ciel 狐狸在游乐园里排队等待上摩天轮。现在有 n 个人按编号顺次在队列里,有 m 条船,第 i 条船到时,前 qi 个人可以上船。保证 qi=n。 人总是不愿意和陌生人上同一条船的,当第 i 个人与第 j 个人处于同一条船上时,会产生 ui,j 的沮丧值。请你求出最小的沮丧值和。一条船上的人两两都会产生沮丧值,不会计算这个沮丧值两次。


「CF877F」Ann and Books-莫队
· ✏️ 628 words · ☕ 2 mins read

n 本书,第 i 本书中有 ai 个问题,均属于第 ti 类问题。

q 次询问,每次询问给出一个区间 [li,ri] ,询问有多少个原序列的连续子区间是给出区间的子区间,且该子区间中所有书中问题的和满足第 1 类的问题恰好比第 2 类的问题恰好多 k 个。


「CF476E」Dreamoon and Strings-动态规划
· ✏️ 774 words · ☕ 2 mins read

Dreamoon 有一个字符串 s 和一个模式串 p ,他会先从 s 中删除恰好 x 个字符来产生一个新的字符串 s 。然后他会计算 occ(s,p),即从 s 中能找到的等于 pp 的不相交的子串数量的最大值。他想让 occ(s,p) 的值尽可能大。

更形式地说,让我们用 ans(x) 表示所有可以从 s 中删去恰好 x 个字符得到的 socc(s,p) 的最大值。Dreamoon 想要知道对于所有的 x (0x|s|)ans(x) 的值。


「CF232D」Fence-后缀数组+主席树
· ✏️ 973 words · ☕ 2 mins read

给定长度为 n 的整数序列 h[n] ,有 Q 个询问,每次给出 l1,r1 ,​询问有多少对 l2,r2 ,满足以下条件:

  1. r2l2=r1l1
  2. 区间 [l1,r1] 与区间 [l2,r2] 没有交集
  3. 对于任意 i[0,r1l1] ,满足 h[l1+i]+h[l2+i]=h[l1]+h[l2]

「CF103E」Buying Sets-霍尔定理-网络流-最小权闭合子图
· ✏️ 975 words · ☕ 2 mins read

我们有 n 个集合,第 i 个集合有 mi 个数(1n 中的整数),权值为 wi

现在请你从中选出 kk 为任意 0n 中的整数)个集合,满足这 k 个集合的并集的大小为 k ,询问这 k 个集合的权值和最小值。

保证从这 n 选出任意 x 个集合,他们的并集大小不小于 k


「CF813D」Two Melodies-简单dp
· ✏️ 650 words · ☕ 2 mins read

给定一个长度为 n 的数组,我们要从中找出两个不相交(不含邮相同元素的)的子序列,要求每个子序列的任意两个相邻元素的差的绝对值为 1 或 在模 7 意义下相同。请你求出这两个子序列长度和的最大值。


「NOI2006」最大获利-网络流-最大权闭合子图
· ✏️ 1103 words · ☕ 3 mins read

新的技术正冲击着手机通讯市场,对于各大运营商来说,这既是机遇,更是挑战。THU 集团旗下的 CS&T 通讯公司在新一代通讯技术血战的前夜,需要做太多的准备工作,仅就站址选择一项,就需要完成前期市场研究、站址勘测、最优化等项目。

在前期市场调查和站址勘测之后,公司得到了一共 N 个可以作为通讯信号中转站的地址,而由于这些地址的地理位置差异,在不同的地方建造通讯中转站需要投入的成本也是不一样的,所幸在前期调查之后这些都是已知数据:建立第 i 个通讯中转站需要的成本为 Pi

另外公司调查得出了所有期望中的用户群,一共 M 个。关于第 i 个用户群的信息概括为 Ai , BiCi :这些用户会使用中转站 Ai 和中转站 Bi 进行通讯,公司可以获益 Ci

THU 集团的 CS&T 公司可以有选择的建立一些中转站(投入成本),为一些用户提供服务并获得收益(获益之和)。那么如何选择最终建立的中转站才能让公司的净获利最大呢?(净获利 = 获益之和 – 投入成本之和)


广州旅游记
· ✏️ 1776 words · ☕ 4 mins read

本游记是真的游玩过程记录。


「CTSC2012」熟悉的文章-广义后缀自动机
· ✏️ 1139 words · ☕ 3 mins read

为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得“眼熟”,小强想出了一个评定作文 “熟悉程度”的量化指标:L0 .小强首先将作文转化成一个 01 串。之后,小强搜集了各路名家的文章,同样分别转化成 01 串后,整理出一个包含了 M01 串的“ 标准作文库 ”。

小强认为:如果一个 01 串长度不少于 L 且在 标准作文库 中的某个串里出现过(即,它是 标准作文库 的 某个串 的一个 连续子串 ),那么它是“ 熟悉 ”的。对于一篇作文(一个 01 串)A,如果能够把 A 分割成若干段子串,其中“ 熟悉 ” 的子串的 长度总和 不少于 A 总长度的 90,那么称 A 是 “ 熟悉的文章 ”。 L0 是能够让 A 成为 “ 熟悉的文章 ” 的 所有 L 的最大值 (如果不存在这样的 L ,那么规定 L0=0 )。