2nm 块三明治, 每块是尺寸相同的等腰直角三角形, 拼成了 n*m 的矩形. 一块三明治能被吃掉仅当以下条件中的至少一个被满足:
- 它的斜边不与尚存的其他三明治相邻
- 它的两条直角边均不与尚存的其他三明治相邻
对于 i=1,2,...,n, j=1,2,...,m, 要吃掉 (i,j) 位置的两块三明治, 一共得吃掉多少块? (包括这两块本身)
- 35%: n,m ≤ 50
- 100%: n,m ≤ 400
[雅礼1706 Day 7] 回转寿司
n 个数的序列 x, 依次进行 q 个操作: 给定 s, t, p
for (int i = s; i <= t; ++i)
if (x[i] > p)
swap(x[i], p);对于每次操作, 输出 p 最终变成了多少 (并执行修改). (1 ≤ n ≤ 4*10^5, 1 ≤ q ≤ 25000, 1 ≤ xi, p ≤ 10^9)
[雅礼1706 Day 7] 电报
一座 n 个点的基环外向树森林, 改变第 i 个点的入边, 代价为 ci. 求变成一个环的最小代价. (2 ≤ n ≤ 10^5, 1 ≤ ci ≤ 10^9)
[雅礼1706 Day 5] 仰望星空
平面上 n 个点和一个圆, 圆外 (不包括边界) 为 I 类点, 圆内 (包括边界) 为 II 类点. 每次可以消掉一对点 x,y, 满足: - x 为 I 类点, y 为 II 类点 - x,y 间的欧几里德距离不超过定值 d - 不存在还未消去, 且与 x 的距离不超过 d 的 II 类点 z,w, 使连线 x-y 与 z-w 相交
求最多可以消去多少个点, 并按顺序输出一种方案. (n ≤ 1000, 1 ≤ 坐标 ≤ 10^4, 1 ≤ d,半径R ≤ 2*10^4)
[雅礼1706 Day 5] 学外语
一个长度为 n 的序列 a, 每个元素是不超过 n 的正整数. 一次操作: 选择两个不超过 n 的正整数 x,y, 交换 a[x],a[y], 再把序列中所有 x 改成 y, 所有 y 改成 x. 操作可以进行任意次. 问能生成多少个不同的新序列, 模 10^9+7. (1≤数据组数T≤30, 1≤n≤10^5)
[雅礼1706 Day 5] 吃干饭
q个询问: 区间[L,R]中的整数能异或出多少个不同的数? (1≤q≤100, 0≤L≤R≤10^18)
[雅礼1706 Day 11] jump
编号为 1~n 的 n 个点. 编号为 i 的点可以跳到编号为 [max(i-xi,1), min(i+xi,n)] 的点. 定义 i,j 的距离为 min(i跳到j的最小步数, j跳到i的最小步数). 求两点间的最大距离. (1≤n≤10^5, 1≤xi<n)
[雅礼1706 Day 4] QYH
n 个开区间, 从中选 m (m > 1) 个, 它们的权值为 |交| * |并|. 求最大权值. (1 ≤ n ≤ 10^6, 1 ≤ l < r ≤ 10^6) [bzoj 2687] 交与并
[雅礼1706 Day 2] C
一棵 n 个节点, 采用堆式存储的完全二叉树. ci 为节点 i 最多能容纳的鸟的数量. m 只鸟, 第 i 只鸟的初始位置为 pi. 移动一只鸟的代价为树上的距离. 对于 k=1,2,...,m, 求将前 k 只鸟安排妥当 (节点上鸟的数目不超过其最大容纳量) 的最小代价. (n,m ≤ 3*10^5)
[雅礼1706 Day 2] A
一棵 n 个节点的有标号无根树, 求这样的路径 u-v (u≠v) 的数目: 路径上不存在点对 (a,b) (a≠b) 满足 gcd(a,b) = a. u-v, v-u 算作同一条.
- 10%: n ≤ 500
- 30%: n ≤ 3000
- 50%: n ≤ 30000
- 另 30%: 树是一条链
- 100%: n ≤ 10^5
[雅礼1706 Day 1] 无心行挽
一棵边权均为1的无根树, q个询问: 给出k个关键点, 每个点隶属于与它最近的关键点, 求每个点和它上司的距离的最大值. (1 ≤ n,q,Σm ≤ 10^5)
[bzoj 3572] [Hnoi2014]世界树
一棵边权均为1的无根树, q个询问: 给出m个关键点, 每个点隶属于与它最近的关键点, 距离相同取编号最小的, 求每个关键点管多少点. (n,q,Σm ≤ 3*10^5)
[雅礼1706 Day 11] delight
[雅礼1706 Day1] 看无可看
给出
- 对60%的数据,
- 对100%的数据,
Educational Codeforces Round 24
做着玩一玩...... 10分钟看起来很短......但是每道题多花10分钟......就会GG. TAT 比赛时完成A-E. F需要感性理解想一想. G题算是上上场 Educational Round 某题的扩展版. 当时就看到有神犇用费用流来做. 嘿嘿, 果然把上次的代码粘了一遍...... ^_^ 然而我的建图太过 naive......修改了一下, 以点数多几倍的代价把边数从