给定一个长度为 的 01 串,求最多可以选出多少互不相交的子串,满足这些子串按照原串中的顺序,字典序严格升序。
。
JOISC2017F 鉄道旅行 (Railway Trip) 做题记录
给定长 n 的序列 ai,满足 a1=an=max{ai}。
构建一个 n 个点的无向图 G 如下:
- ∀1≤i<j≤n,若存在某个正整数 k 满足 ai,aj≥k 且 ∀i<p<j 都有 ap<k,则 G 中存在边 (i,j);
q 次询问,每次询问点 xi 和 yi 之间的最短路长度减一。
1≤n,q≤105,1≤ai≤n。
CF1637F Towers 做题记录
给定一棵 n 个点的树,每个点有一个权值 ai。
一个长度为 n 的序列 b 合法当且仅当 ∀1≤u≤n,都存在两个整数 x,y 满足:
- 1≤x,y≤n;
- x=y;
- u 在 x 到 y 的简单路径上;
- min(bx,by)≥au;
输出所有合法的 b 中最小的 ∑bi。
2≤n≤2×105,1≤ai≤109。
CF1770F Koxia and Sequence 做题记录
给定非负整数 n,x,y,对于所有满足 i=1∑nai=x,所有 ai 按位或和为 y 的序列 a,求出 ⊕i=1nai 的异或和。
1≤n≤240,0≤x<260,0≤x<220。
ABC228G Digits on Grid 做题记录
给定一个 H×W 的矩阵 c 和一个整数 n。
起初在任意格子上放置一个棋子,接下来操作 n 次,第 i 次操作:
- 若 i 是奇数,则把棋子移动到当前所在行中任意一个格子(可以不动);
- 若 i 是偶数,则把棋子移动到当前所在列中任意一个格子(可以不动);
把每次操作完后棋子所在的格子上的数依次写下,形成一个长度为 2n 的序列 b,请你求出有多少种可能的序列 b,对 998244353 取模。
1≤H,W≤10,1≤n≤300,1≤ci,j≤9。
CF1270H Number of Components 做题记录
给定一个长 n 的元素两两不同的序列 a,∀1≤i<j≤n,若 ai<aj,则让 i 向 j 连一条无向边。
q 次修改数组某个位置的值,每次修改后输出图中连通块个数。
1≤n,q≤5×105,1≤ai≤106,保证任意时刻数组中元素两两不同。
CF1368E Ski Accidents 做题记录
给定一张 n 个点 m 条边的 DAG,每个点出度至多为 2。可以删除不超过 74n 个点,使得删点后的图中不存在包含三个点的链。
1≤n≤2×105。
CF1519F Chests and Keys 做题记录
给定 n,m 表示存在 n 个宝箱和 m 把钥匙,第 i 把钥匙需要 bi 元,第 i 个宝箱内部有 ai 元。
现在进行一场游戏,Bob 是本场游戏的玩家,而 Alice 则是场景布置者,Alice 可以给每个宝箱上一些锁(第 j 种锁需要第 j 种钥匙打开)
如果 Bob 可以购买一些钥匙,然后打开一些宝箱,使得 Bob 的收益大于 0,那么 Bob 就赢得了游戏,反之 Alice 获得了胜利。
现在 Alice 打算布置宝箱上的锁,第 i 个宝箱上放置第 j 种锁的花费为 ci,j,请帮助 Alice 找到一种布置锁的方案,使得花费最小,且 Alice 将取得胜利。
注意:一个箱子上可以放置若干把锁,Bob 需打开所有锁才能获得内部的钱。
n,m≤6,ai,bi≤4,ci,j≤107。
CF1446D1&2 Frequency Problem 做题记录
给定长 n 的序列 a[1,n]。
输出最长的满足不同的众数(出现次数最多的数)至少有两个的区间的长度。
D1:1≤n≤2×105,1≤ai≤min(100,n);
D2:1≤n≤2×105,1≤ai≤n;