做题记录
1.17
[TJOI2007]足彩投注
From
tag
概率DP
[SHOI2007]冠军调查
From
tag
网络流 最小割
Solution
建图：
对于每个点，若为 \(1\) 则与 \(S\) 连边，若为 \(0\) 则与 \(T\) 连边，为好友的相互连边，边权均为 \(1\)；
转化：
考虑将一张图分为两部分，表示：与 \(S\) 在同一连通块内的点最后被标为 \(1\)，与 \(T\) 在同一连通块内的点最后被标为 \(0\)，
则对于每种分割方式：
- 割边为 \(S\) 或 \(T\) 与 \(1-n\) 的边，则说明该点状态改变，代价 \(+1\)；
- 割边为 \(1-n\) 之间的边，则说明这对好友站在了对立面，代价 \(+1\)；
代价为割边的权值和，故答案为所建的图的最小割。
[JLOI2011]小A的烦恼
From
tag
模拟
股神小L
From
tag
贪心
做任务
From
tag
网络流 最小割
Solution
考虑一个任务的奖励很像k位数,所以将其转化成10进制数,然后权值有正有负,考虑对于限制关系建图,方式就是如果做任务i之前需要做任务j,那就从i向j连一条边,然后对于这个图求最大权闭合子图.选出的子图就是答案.
正确性证明如下：
首先最大权闭合子图是用所有正权值之和减去原图的最小割,然后我们相对于限制反向建边,就是要求如果要选一个点,则它之前的所有点必须要选.这样就满足了限制.
1.18
CF1288A Deadline
From
Educational Codeforces Round 80 A
tag
数学
CF1288B Yet Another Meme Problem
From
Educational Codeforces Round 80 B
tag
数学
CF1288C Two Arrays
From
Educational Codeforces Round 80 C
tag
DP
CF1288D Minimax Problem
From
Educational Codeforces Round 80 D
tag
二分答案 二进制
CF1288E Messenger Simulator
From
Educational Codeforces Round 80 E
tag
思维 树状数组
BZOJ 1396 识别子串
From
tag
后缀自动机 线段树
update 1.19 8:00
更多精彩
