DDOSvoid's Blog

简介

和 $AC$ 自动机长得很像的东西

题目描述

https://codeforces.com/problemset/problem/1511/E

简要题意：给定一个 $n\times m$ 的网格图，格子有黑色和白色两种，现在你要将每个白色格子染成红色或蓝色，对于每一种染色方案，你需要尽可能的铺上 $1\times 2$ 的骨牌，横着的骨牌必须在两个红色格子上，竖着的骨牌必须在两个蓝色格子上，现在要求所有方案的骨牌数量之和

$n\times m\le 3\times 10^5$

题目描述

http://codeforces.com/gym/103107/problem/L

简要题意：现在有 $n$ 个怪兽，第 $i$ 个怪兽有一个等级限制 $h_i$，只有等级大于等于 $h_i$ 才能杀死第 $i$ 个怪兽。现在还有一个限制，就是每一回合只能杀死一个怪兽，同时每个怪兽还有两个属性 $a_i$ 和 $b_i$，杀死怪兽 $i$ 之后其它怪兽的 $h$ 会增加 $a_i$，而你的等级会增加 $b_i$。现在还有 $q$ 个询问，每次增加一个怪兽，求目前为止你所需要的最低的初始等级杀死所有怪兽

$n\le 10^5,q\le 1000$

题目描述

http://codeforces.com/gym/103107/problem/E

简要题意：给定 $n$ 个字符串，如果串 $t$ 是 $s$，则连一条 $t$ 到 $s$ 的有向边，求这个 $DAG$​ 的最长路

$n\le 5\times 10^5,len\le 5\times 10^5$

题目描述

http://codeforces.com/problemset/problem/1513/F

简要题意：给定两个长度为 $n$ 的序列 $a_i,b_i$，现在至多可以交换一次 $b$ 中两个位置的值，最小化 $\sum_{i=1}^n|a_i-b_i|$

$n\le 2\times 10^5$

题目描述

http://codeforces.com/gym/103107/problem/I

题目描述

https://codeforces.com/contest/1498/problem/D

简介

大概不算是冷门知识吧 = =

题目描述

http://codeforces.com/problemset/problem/1498/E

题目描述

https://codeforces.com/contest/1499/problem/F