CodeForces 1426F Numbers of Subsequences

题意简述给你一个字符串,其中有四种字符a b c ?,? 可以任意替换成 a b c 中的一种,求所有可能的替换方案中子序列 abc 的个数之和。 解题思路一个计数 dp。 考虑设 dp[i][...

CodeForces 1349C Orac and Game of Life

题意简述给定一个 n \times m 的网格,每个格子在 0 时刻有黑白两种颜色之一。接下来每个时刻,网格会做一次变换:如果一个格子上下左右至少有一个格子与它颜色...

CodeForces 875F Royal Questions

题意简述有 x 个王子 y 个公主,每一个公主喜欢其中两个王子,还有 一个美丽度。你需要将王子和公主配对,使得配对的每一个公主都和自己喜欢的王子配对,并且配对的公主美丽度之和最大。 注意并不必...

CodeForces 1311E Construct the Binary Tree

题意简述给定一个 n 和 k,构造一棵以 1 为根的二叉树,使得每个点的深度之和恰好为 k。无解输出 Impossible。 解题思路首先来判断一下有没有解。 显然,这个答案的上界是一条...

NOIP2014 联合权值

题意简述给定一棵无根树,每个点有一个点权 w ,定义一个距离为 2 的有序点对的联合权值为两个点的点权之积,求图上的所有联合权值之和。 换句话说,求: \sum_{\mathr...

「国家集训队」 阿狸和桃子的游戏

题意简述给定 n 个点的一棵树,点有点权。有两个人在树上染色,先手后手轮流染黑白两色,最后的得分是自己染的点权和 + 两端均为自己的颜色的边权和。 求先手的得分与后手的得分之差...

差分约束系统学习笔记

0x01 引子解不等式组大家都会解吧形式化地,给定一个不等式组 \left\{ \begin{array}{l} x_1 - x_2 \leq a\\ x_2 - x_3 \leq b\\ ...

差分约束杂题选讲

题面自己找,这里只讲思路。 HDU 3592 World Exhibition线性约束板子题。和 POJ3169 Layout 相同。 12345678910111213141516171819...

POJ3169 Layout

题意简述有 n 头奶牛编号 1 ~ n,要按照 1~n 的顺序站成一排,两头相邻的奶牛之间要有距离(也可以没有,我们可以认为他们坐标相同,同时可以认为奶牛是没有体积的)。但是有几对奶牛互相讨厌,...

12320