|
|
Posted on 2007-09-18 17:00 oyjpart 阅读(2010) 评论(6) 编辑 收藏 引用 所属分类: ACM/ICPC或其他比赛
pku2380 Balancing the Scale ： 上海的题。看到这题我立刻想到了以前做过的一道：sumset。用类似的方法，可以把任意4个数连接起来作为一个整体。然后分别放到两个数组中，排序。之后从左到右分别检验左右是否相等（具体参考程序），注意使用位运算压缩。
1 #include <string.h>
2#include <algorithm>
3#include <stdio.h>
4
5using namespace std;
6
7#define two(x) (1<<(x))
8#define contain(S, x) (((S)&(two(x))) != 0)
9
10const int MAX = 43680;
11
12  struct Node  {
13 int mask, w;
14  Node() {}
15 Node(int mm, int ww) {
16 mask = mm;
17 w = ww;
18 }
19 }A[MAX];
20
21int cnt[two(16)];
22
23bool operator<(const Node& a, const Node& b) {
24 return a.w < b.w;
25}
26
27int a[16], nA;
28
29void solve() {
30 int beg = 0, end = 0, i, j, k;
31 for(i = 1; i < nA; ++i) {
32 if(A[i].w != A[i-1].w) {
33 for(j = beg; j <= end; ++j)
34 for(k = j+1; k <= end; ++k)
35 if((A[j].mask&A[k].mask) == 0)
36 cnt[A[j].mask|A[k].mask]++;
37 beg = end = i;
38 }
39 else
40 end = i;
41 }
42 int ans = 0;
43 for(i = 0; i < two(16); ++i) {
44 if(cnt[i] != 0 && cnt[(two(16)-1)^i] != 0)
45 ans += cnt[i] * cnt[(two(16)-1)^i];
46 }
47 printf("%d\n", ans/2);
48}
49
50int main() {
51
52// freopen("t.in", "r", stdin);
53
54 int i, j, k, m, tc = 0;
55 for(tc = 1; ; tc++) {
56 scanf("%d", &a[0]);
57 if(a[0] == 0)
58 break;
59 for(i = 1; i < 16; ++i)
60 scanf("%d", a+i);
61 nA = 0;
62 for(i = 0; i < 16; ++i)
63 for(j = 0; j < 16; ++j) if(j != i)
64 for(k = 0; k < 16; ++k) if(k != i && k != j)
65 for(m = 0; m < 16; ++m) if(m != i && m != j && m != k) {
66 int t = two(i)+two(j)+two(k)+two(m);
67 A[nA++] = Node(t, 4*a[i]+3*a[j]+2*a[k]+a[m]);
68 }
69 sort(A, A+nA);
70
71 memset(cnt, 0, sizeof(cnt));
72 printf("Case %d: ", tc);
73 solve();
74
75 }
76
77 return 0;
78}
79
80
81
82
PKU1637 Sightseeing tour 老题了，混合图的欧拉回路。 首先是预判，然后建图。我的建图方法是这样的： 对于每个点都有自己的入度需求量，将其作为到T的容量。 对于每个无向边看一个点，都可以提供1的入度，所以连接S的1容量的边。 最后把无向边连向其能够提供入度的2个点。 PKU1848 Tree 很好的树形DP，由于题目不允许两点之间连第3边（题目没说-_-|||) 所以要3个状态才能搞定。 PKU3042 Grazing on the Run 类似于 PKU2671 Jimmy's Bad Day
很好的区间DP模型。关键代码如下
1
2 dp[0][n-1][0] = dp[0][n-1][1] = 0;
3
4 for(i = n-1; i >= 1; --i) {
5 for(j = 0; j + i - 1 <= n-1; ++j) {
6 k = j+i-1;
7 if( Beg >= j && Beg <= k ) {
8 if(j > 0) {
9 dp[j][k][0] = Min(dp[j][k][0], dp[j-1][k][0] + (a[j]-a[j-1])*(j+n-1-k));
10 dp[j][k][1] = Min(dp[j][k][1], dp[j-1][k][0] + (a[k]-a[j-1])*(j+n-1-k));
11 }
12 if(k < n-1) {
13 dp[j][k][0] = Min(dp[j][k][0], dp[j][k+1][1] + (a[k+1]-a[j])*(j+n-1-k));
14 dp[j][k][1] = Min(dp[j][k][1], dp[j][k+1][1] + (a[k+1]-a[k])*(j+n-1-k));
15 }
16// for(int l = 0; l < 2; ++l) printf("dp[%d][%d][%d] = %d\n", j, k, l, dp[j][k][l]);
17 }
18 }
19 }
20
PKU2795 Exploring Pyramids DP。用到了树形DP的思想（算是吧？） 关键代码如下：
1 for(i = 0; i < len; ++i)
2 dp[i][i] = 1;
3
4 for(l = 3; l <= len; l += 2) {
5 for(i = 0; i+l-1<=len-1; ++i) {
6 j = i+l-1;
7 dp[i][j] = 0;
8 if(s[i] == s[j]) {
9 for(k = i+2; k <= j; k+=2) {
10 dp[i][j] = (int)((dp[i][j] + (long long)dp[i+1][k-1] * dp[k][j])%MAX);
11 }
12// printf("dp[%d][%d] = %d\n", i, j, dp[i][j]);
13 }
14 }
15 }
16
PKU3111 K Best 好题。 看到了之后，会想到这个和曾经一道最有比率生成树非常相似。用类似的方法进行二分求解是正途。但是到这里还是复杂度太高（二分里面有一个排序），考虑到只要排序出前K个元素，可以考虑部分排序（用的是快排的原理）。 PKU1932 XYZZY
bellman_Ford求负权最短路, 当有负权圈的时候可以检测到.
对于这道题而言,我们可以建模为:
加HP: 负权点
减HP: 正权点
将点权化作边权后(可以拆点,或者直接将点权加入入边)run一次bellman_ford
bellman_ford中只扩展标号<100的点
如果无负权圈,显然只需判终点的最短路是否<100
如果有负权圈,就判bellman_ford是否可能到达任何一个负权圈上的点. PKU3411 Paid Roads
初看像状态压缩DP，写完之后才发现有环。
其实只需要拆点转化成最短路模型就可以了。
Feedback
我看了很久你第一题的代码,感觉你的SOLVE函数前面的比较部分是哪里错了
我参照的你的思想,用c#写的
private void solve()
{
int count=0,n=0;
for(int i=0;i<43680;i+=24)
for(int j=i+24;j<43680;j+=24)
if((A[i].flag&A[j].flag)==0)
for(int k=0;k<24;k++)
for(int l=0;l<24;l++)
if(A[i+k].result==A[j+l].result)
No[A[i+k].flag|A[j+l].flag]++;
for(count=0;count<two(16);count++)
if(No[count]!=0&&No[(two(16)-1)^count]!=0)
{
n+=No[count]*No[(two(16)-1)^count];
}
Console.WriteLine("count:"+(n/2).ToString());
}
我刚刚学算法,可能是我没有充分理解你写的吧.另外我十分佩服你!
请问你的24是什么？
还有你的循环是43680*43680*24*24的，不出意外的话就超时了:)
# re: 说题~[未登录] 回复 更多评论
2007-11-15 22:02 by
24是因为之前排过序了,出现四个1位置相同的情况肯定是4!种,如果使用了相同的数就跳过,理论上是要计算43680*43680次,但是我也没测试过有没有超时,你能不能现把你写的意思告诉我?
# re: 说题~[未登录] 回复 更多评论
2007-11-16 19:50 by
29void solve() {
30 int beg = 0, end = 0, i, j, k;
31 for(i = 1; i < nA; ++i) {
32 if(A[i].w != A[i-1].w) { //某一个相同w的段
33 for(j = beg; j <= end; ++j) //段的开始何结束的2重枚举
34 for(k = j+1; k <= end; ++k)
35 if((A[j].mask&A[k].mask) == 0) //如果没有相同的数
36 cnt[A[j].mask|A[k].mask]++; //计数器增加
37 beg = end = i;
38 }
39 else
40 end = i;
41 }
42 int ans = 0;
43 for(i = 0; i < two(16); ++i) {
44 if(cnt[i] != 0 && cnt[(two(16)-1)^i] != 0) //如果某些数字的集合的计数>0 并且他的补集也>0,就是都用上了
45 ans += cnt[i] * cnt[(two(16)-1)^i];
46 }
47 printf("%d\n", ans/2);
48}
|