一棵有根树, 每个点有权值Hi. m个操作, 每个可以选择子树Di中权值在[Li,Ri]中的任意不超过Ti个点. 问所有操作后最多能选择多少个点. (1≤n,m≤10^4, 1≤Hi,Ti≤n, 1≤Li≤Ri≤n)
[bzoj 3218] a + b Problem
n个方格从左到右排成一列, 给它们黑白染色. 如果方格i染成黑色, 获得bi收益; 染成白色, 获得wi收益. 如果一个黑色方格i的左边存在白色方格j, 使得li≤aj≤ri, 则称i为奇怪的方格, 收益减少pi. 求所有染色方案中最大的收益. (n≤5000, a,l,r≤10^9, b,w≤2*10^5, p≤3*10^5, 每个测试点时限2s, 内存限制48MB)
[bzoj 4561] [JLoi2016]圆的异或并
给出两两没有交点的n个圆(x,y,r), 求被圆面覆盖奇数次的区域的总面积. 输出面积除以pi的结果. (|x|,|y|≤10^8, r>0, n≤2*10^5)
Codeforces Round #418 (Div. 2)
Chinese Round. 是说时间怎么这么友善...... 不是很难. 比赛的时候完成了前4道. 离比赛结束还有40s的时候交了一发D, 然而...... CE了...... 一开始以为是C++11的锅, 结果发现M_PI这个常量不是标准库里的. GG...... 比赛结束后又交了一发, A掉了......TAT 本场比赛很多题目都是多解的 (我做出的也不是最优解法 TAT), 兹磁一个......D的贪心很妙. E是个不错的DP题. 题解: 5/5
[bzoj 4025] 二分图
n个节点的无向图, 总时间为T. m条在一个时间段内存在的边, 求每一时刻该图是否是二分图. (n≤10^5, m≤2*10^5, T≤10^5)
Educational Codeforces Round 22
昨天早上打的. 做出ABCE四道题. 以前看到过F题, 但是不知道具体做法......原来对时间分治是这样的. D题......看到过的人比较少, 可能就没有认真想吧......其实并不困难. 题解: 5/5
[bzoj 3694] 最短路
给出一个n个点m条边的无向图 (边带权) 和该图的一棵最短路树, 对于除源点1外的每个点i, 求1到i的最短路, 要求不经过i在最短路树上的父边. (n≤4000, m≤10^5, 1≤边权≤10^5)
[bzoj 3309] DZY Loves Math
定义
[bzoj 2693] jzptab
求
[bzoj 3702] 二叉树
给一棵所有非叶子节点都有两个儿子的二叉树. 每个叶子节点上有一个权值, 它们是1..n的一个排列. 可以任意交换每个非叶子节点的左右孩子. 求所有叶子节点的权值按中序遍历写出来, 逆序数的最小值. (2≤n≤2*10^5)
[bzoj 1021] [SHOI2008]Debt 循环的债务
A, B, C之间相互欠钱. 每个人有一些面额100,50,20,10,5,1元的钞票. 求三人还清债务需要交换钞票的最少张数, 或报告不能还清. (每人拥有的10,5,1元钞票张数不超过30, 三人总共拥有的钞票面值总额不超过1000, 任何一个人欠另一个人的钱数的绝对值不超过1000)
[usaco2013 Open] Yin and Yang
n个点的无根树, 每个边权为0或1. 一条路径阴阳平衡当且仅当它至少有两条边, 且路径上0,1数目相等. 统计有多少条简单路径上可以选一个点作休息站, 休息站的两侧是阴阳平衡的路径. 两条路径相等当且仅当它们包含的边集相等. (1≤n≤10^5) (bzoj 3127 & 3697)
[bzoj 1019] [SHOI2008]汉诺塔
n个盘子摞在柱子A上, 按照下述策略移动: - 给六种操作 (AB、AC、BA、BC、CA和CB) 赋予不同的优先级. - 每次选择符合以下两个条件的操作来移动盘子, 直到所有盘子都从A移到另一根柱子: 1. 它是所有合法操作中优先级最高的. 2. 所要移动的盘子不是上一次操作所移动的.
现在给定n和每种盘子的优先级, 求游戏终止所需要的步骤数. (1≤n≤30)
Codeforces Round #417 (Div. 2)
今天早上打了一下, 只做出了前三道简单题......TAT 还以为自己想到了E题的正解, 没过样例, 我把题目看错了......真是太不冷静了. QAQ (不过在一个没有空调的小房间里呆上一个半小时确实让人很难冷静) 度娘告诉我这是个经典问题, 然而我孤陋寡闻......涨知识了. D题也不难, 然而我读不懂题啊......QAQ 题解: 5/5