放假啦
3272 Problem A Cow Traffic
由于题目是TOPO有序图 直接DP一次拿到每个点的到达路径条数 dp[i]
然后将所有有向边反向 再做一次DP即得从BARN到每个点的路径条数 rdp[i]
枚举所有边(u,v) 记录dp[u] * rdp[i]的最大值即可
3273 Problem B Monthly Expense
二分枚举答案
3274 Problem C Gold Balanced Lineup
HASH来做 我用排序做超时了.. Hash AC
由于中间把Node的大小定义operator<()中最后一行写成了return true 一直拿不到正确答案... 原来自己定义map元素大小的时候相等情况应该定义为false 我的理解是属于大于等于的范畴
Code follows:
1
#include <iostream>
2
#include <map>
3
#include <vector>
4
using namespace std;
5
6
struct Node { int s[30]; };
7
8
const int N = 100010;
9
int n, K;
10
Node a[N];
11
map<Node, int> mym;
12
vector<int> l[N];
13
14
bool operator<(const Node& a, const Node& b) {
15
int i;
16
for(i = 0; i < K; ++i)
17
if(a.s[i] != b.s[i])
18
return a.s[i] < b.s[i];
19
return false;
20
}
21
22
int main() {
23
scanf("%d %d", &n, &K);
24
int i, t, j, k;
25
for(j = 0; j < K; ++j)
26
a[0].s[j] = 0;
27
for(i = 1; i <= n; ++i) {
28
scanf("%d", &t);
29
for(j = 0; j < K; ++j, t >>= 1)
30
a[i].s[j] = a[i-1].s[j] + (t % 2);
31
for(j = 1; j < K; ++j)
32
a[i].s[j] -= a[i].s[0];
33
a[i].s[0] = 0;
34
}
35
36
j = 0;
37
for(i = 0; i <= n; ++i) {
38
if(mym.find(a[i]) == mym.end())
39
mym[a[i]] = j++;
40
l[mym[a[i]]].push_back(i);
41
}
42
43
int res = 0;
44
for(i = 0; i < j; ++i) {
45
int min = 123456789, max = -1;
46
for(k = 0; k < l[i].size(); ++k) {
47
if(l[i][k] > max) max = l[i][k];
48
if(l[i][k] < min) min = l[i][k];
49
}
50
if(max - min > res) res = max - min;
51
}
52
53
printf("%d\n", res);
54
55
return 0;
56
}
57
3275 Problem D Ranking the Cows
首先可以看出询问的上界是所有的不连通的节点数 因为只要全部query一次就可以全部得到顺序
然后我们可以证明其下界也是这个 因为事实上只要这两个节点在大小序列中相邻 那么他们必须被询问一次
所以我们只要做DFS就可以找出不连通的节点对数
3277 Problem F City Horizon
首先对Y方向做离散化（注意不要用map 容易超时-_-||| 我就超了）
接着构建线段数（区间为0-Y方向点的个数）
然后从左到右扫描 每碰到一个矩形的左竖线就添加到线段数 右竖线则删除 面积 += 扫描间距 * 线段数的测度
3278 Problem G Catch That Cow
BFS
3279 Problem H Fliptile
枚举第一行状态2^m
可以递推出下面所有行的状态
时间复杂度o(2^m * n)
注意用位运算压缩
3280 Cheapest Palindrome
观察可知 其实插入一个字符串在最优插入情况下可以看作是删除一个字符（想想为什么？）
这样就可以得到每个字符的删除耗费
然后可以得到一个和LCS有些像的方程
dp[i, j] = Min( dp[i+1, j] + cost[word[j]], dp[i, j-1] + cost[word[i]], dp[i+1, j-1]->(if(word[i] == word[j]));
找出最开始的那个结论就可以了
3281 Problem J Dining
最大流
从题目描述中比较容易看出网络流可能出解 剩下的就是构造图
我们看到对于一个Cow来说 其必须在满足Food和Drink皆满意的情况下才能算做满意 因此比较好的构图方法是将Food和Drink分别与源点和汇点相连 将cow放在中间 并把点权换成边权（即将每一个cow节点一分为2 将点权放到2点的连边上） 所有权全部设成1 RUN一次最大流 这种图有时候也叫做三分图