定义集合 合法当且仅当满足以下条件:
;
, ;
给定 ,求最大的 。
,。
CF1784F Minimums or Medians 做题记录
你有一个包含 1∼2n 共 2n 个整数的集合 S。你必须执行恰好 k(1≤k≤n≤106)次操作,每个操作都是以下两种其中之一:
将 S 中第 1,2 个元素删去。
将 S 中第 2∣S∣,2∣S∣+1 个元素删去。(显然 ∣S∣ 一直是偶数,所以 2∣S∣ 也一定是整数)
请你统计,通过这些操作可以获得多少个本质不同的最终集合 S?答案对 998244353 取模。
CF1648E Air Reform 做题记录
一张 n 个点 m 条边的无向带权简单连通图,其上一条路径的权值为其中所有边权的 max。
考虑这张图的补图,补图中一条边的权值为原图中该边两端点间的最短路(路径长度的定义同上)。保证补图亦是连通图。
对于原图中每条边,求出其两端点在补图中的最短路(定义仍同上)。
1≤n,m≤2×105,边权范围 [0,109]。
CF1172F Nauuo and Bug & P5609 做题记录
给定一个如图所示的计算方法:
现在给定长 n 的数组 a 和 p,要求 q 次询问 sum(a,li,ri,p) 的值。
1≤n≤106,1≤m≤2×105,1≤p≤109,∣ai∣≤109。
AGC040E Prefix Suffix Addition 做题记录
你有一个长为 n 的序列 x1,x2,…,xn,一开始全部为 0,你现在可以以任意顺序进行任意次以下两种操作:
- 选定整数 1≤k≤n 与不下降非负整数序列 c1,c2,…,ck,对所有 1≤i≤k,令 xi 加上 ci。
- 选定整数 1≤k≤n 与不上升非负整数序列 c1,c2,…,ck,对所有 1≤i≤k,令 xn−k+i 加上 ci。
问最少进行多少次操作使得 xi=ai。
1≤n≤2×105,1≤ai≤109。
CF1456E XOR-ranges 做题记录
给定 n 和 k,有 n 个 <2k 的非负整数变量 x1,x2,…,xn,其中 xi 的取值范围是 [li,ri]。
给出数列 c0,c1,…,cK−1,并由此定义一个代价函数 f(x):
f(x)=i=0∑k−1(⌊2ix⌋mod2)⋅ci
确定每个变量的取值,使得 ∑i=2nf(xi⊕xi−1) 最小,输出该最小值。
2≤n≤50,1≤k≤50,0≤li≤ri<2k,0≤ci≤1012。
0%