oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

奶牛题比赛

Posted on 2007-07-21 23:19 oyjpart 阅读(3702) 评论(4)  编辑 收藏 引用 所属分类: ACM/ICPC或其他比赛

放假啦

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>
 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 

首先可以看出询问的上界是所有的不连通的节点数 因为只要全部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一次最大流 这种图有时候也叫做三分图

Feedback

# re: 奶牛题比赛  回复  更多评论   

2007-08-08 02:39 by 冰上极光
学习了.....
欢迎光临我的博客啊.....
http://hi.baidu.com/liguanbin
有不少ACM的心得体会哦~~互相学习

# re: 奶牛题比赛  回复  更多评论   

2008-09-06 21:48 by sai90
怎么个个都想的这么複杂?

# re: 奶牛题比赛  回复  更多评论   

2008-09-07 14:59 by oyjpart
请教简单的方法

# re: 奶牛题比赛  回复  更多评论   

2009-10-01 14:05 by 搜咯翻车鱼
3274,
a[i].s[j] -= a[i].s[0];
什么意思啊大牛?

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理