oyjpArt ACM/ICPC算法程序設(shè)計(jì)空間

由于題目是TOPO有序圖 直接DP一次拿到每個(gè)點(diǎn)的到達(dá)路徑條數(shù) dp[i]

然后將所有有向邊反向 再做一次DP即得從BARN到每個(gè)點(diǎn)的路徑條數(shù) rdp[i]

枚舉所有邊(u,v) 記錄dp[u] * rdp[i]的最大值即可

3273 Problem B Monthly Expense

二分枚舉答案

3274 Problem C Gold Balanced Lineup

HASH來做 我用排序做超時(shí)了.. Hash AC
由于中間把Node的大小定義operator<()中最后一行寫成了return true 一直拿不到正確答案... 原來自己定義map元素大小的時(shí)候相等情況應(yīng)該定義為false 我的理解是屬于大于等于的范疇
Code follows:

 1#include <iostream>
 2#include <map>
 3#include <vector>
 4using namespace std;
 5
 6struct Node { int s[30]; };
 7
 8const int N = 100010;
 9int n, K;
10Node a[N];
11map<Node, int> mym;
12vector<int> l[N];
13
14bool 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
22int 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 

首先可以看出詢問的上界是所有的不連通的節(jié)點(diǎn)數(shù) 因?yàn)橹灰縬uery一次就可以全部得到順序

然后我們可以證明其下界也是這個(gè) 因?yàn)槭聦?shí)上只要這兩個(gè)節(jié)點(diǎn)在大小序列中相鄰 那么他們必須被詢問一次

所以我們只要做DFS就可以找出不連通的節(jié)點(diǎn)對數(shù)

3277 Problem F City Horizon

首先對Y方向做離散化（注意不要用map 容易超時(shí)-_-||| 我就超了）

接著構(gòu)建線段數(shù)（區(qū)間為0-Y方向點(diǎn)的個(gè)數(shù)）

然后從左到右掃描 每碰到一個(gè)矩形的左豎線就添加到線段數(shù) 右豎線則刪除 面積 += 掃描間距 * 線段數(shù)的測度

3278 Problem G Catch That Cow

BFS

3279 Problem H Fliptile
枚舉第一行狀態(tài)2^m
可以遞推出下面所有行的狀態(tài)
時(shí)間復(fù)雜度o(2^m * n)
注意用位運(yùn)算壓縮

3280 Cheapest Palindrome

觀察可知 其實(shí)插入一個(gè)字符串在最優(yōu)插入情況下可以看作是刪除一個(gè)字符（想想為什么？）

這樣就可以得到每個(gè)字符的刪除耗費(fèi)

然后可以得到一個(gè)和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]));

找出最開始的那個(gè)結(jié)論就可以了

3281 Problem J Dining

最大流

從題目描述中比較容易看出網(wǎng)絡(luò)流可能出解 剩下的就是構(gòu)造圖

我們看到對于一個(gè)Cow來說 其必須在滿足Food和Drink皆滿意的情況下才能算做滿意 因此比較好的構(gòu)圖方法是將Food和Drink分別與源點(diǎn)和匯點(diǎn)相連 將cow放在中間 并把點(diǎn)權(quán)換成邊權(quán)（即將每一個(gè)cow節(jié)點(diǎn)一分為2 將點(diǎn)權(quán)放到2點(diǎn)的連邊上） 所有權(quán)全部設(shè)成1 RUN一次最大流 這種圖有時(shí)候也叫做三分圖