两个n颗珠子的手镯, 每颗珠子有亮度 ([1,m]上的整数). 手镯可以旋转, 不能翻转. 可以将其中一个手镯的所有珠子的亮度同时增加一个自然数. 求对应位置亮度的最小方差. (n≤5*10^4, m≤100)
[bzoj 4825] [Hnoi2017]单旋
一棵Spaly, m个操作, 分为5种, 每种有代价: - 插入 (插入之后不用单旋), 插入后的深度 - 单旋最小值, 单旋前的深度 - 单旋最大值, 单旋前的深度 - 单旋删除最小值, 单旋前的深度 - 单旋删除最大值, 单旋前的深度
深度从1开始标号. 执行这些操作, 并报告每个操作的代价, 保证操作合法, 所有关键字互不相同. (1≤m≤10^5, 1≤key≤10^9)
Codeforces Round #409 (Div. 2)
比赛时只完成了A-C, C题FST, 于是掉回两场前的rating...... 题解: 5/5
[bzoj 2329] [HNOI2011]括号修复
维护一个长度为N的由(和)组成的字符串, 支持四类操作: - Replace a b c: 将[a,b]之间的所有字符改为c. (c=( / )) - Swap a b: 将[a,b]之间的字符串翻转. - Invert a b: 将[a,b]之间的左右括号互换. - Query a b: 询问[a,b]之间的字符串至少要改变多少位才能变成合法 (可以匹配) 的括号序列, 保证有解.
(N,M≤10^5)
[bzoj 1030] 文本生成器
字符集为全体大写英文字母. 给N个串, 问存在多少个长度为M的文本包含其中至少一个串. 答案模10007. (N≤60, M和所有串的长度≤100)
[NOI2013] 矩阵游戏
求
[bzoj 2843] 极地旅行社
维护一个n个点的初始没有边的无向图, m个操作, 支持: - 查询a,b连通性并连一条边 (已连通则忽略) - 修改某点点权 - 查询a,b路径上点权之和, 或报告不连通
(1≤n≤3*10^4, 1≤m≤10^5, 点权是[0,1000]内的整数)
[bzoj 1023] [SHOI2008]cactus仙人掌图
求n个点的边不带权的仙人掌的直径. 仙人掌上两点间距离定义为两点间最短路. (1≤n≤50000)
[hdu 2196] Computer
一棵n个结点的树, 求每个点到其他点的最远距离. 多组数据. (n≤10^4)
[51nod 1766] 树上最远点对
给一棵n个结点边带权的无根树, m个询问, 求标号分别在[a,b], [c,d]中的两点间的最远距离. (n≤10^5, m≤10^5, 1≤权值≤10^4)
[bzoj 3438] 小M的作物
两块无限大的耕地A,B, n种作物的种子. 第i种作物种到A中获得ai的收益, 种到B中获得bi的收益 (不能同时种到A,B). 另有m个组合, 第i个组合中的ki种作物同时种到A中获得c1i的额外收益, 同时种到B中获得c2i的额外收益. 求最大总收益. (1≤k<n≤1000, 0<m≤1000, 保证所有数据及结果不超过2*10^9)
[CQOI2009]dance跳舞
n个男孩n个女孩, 每个男孩和每个女孩之间相互喜欢或不喜欢 (无 "单向喜欢" ). 每个男孩最多和每个女孩跳一次舞, 且只愿意和不超过k个不喜欢的女孩跳舞, 女孩亦然. 每支曲子开始时, 男女恰配成n对. 问舞会最多能有几首舞曲. (n≤50, k≤30)