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-09-18 17:00 oyjpart 阅读(2000) 评论(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
12struct 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

# re: 说题~  回复  更多评论   

2007-11-11 00:29 by comiz
我看了很久你第一题的代码,感觉你的SOLVE函数前面的比较部分是哪里错了

# re: 说题~  回复  更多评论   

2007-11-11 13:17 by oyjpart
那你觉得怎么写呢?

# re: 说题~  回复  更多评论   

2007-11-11 19:01 by comiz
我参照的你的思想,用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());

}
我刚刚学算法,可能是我没有充分理解你写的吧.另外我十分佩服你!

# re: 说题~  回复  更多评论   

2007-11-11 23:19 by oyjpart
请问你的24是什么?
还有你的循环是43680*43680*24*24的,不出意外的话就超时了:)

# re: 说题~[未登录]  回复  更多评论   

2007-11-15 22:02 by comiz
24是因为之前排过序了,出现四个1位置相同的情况肯定是4!种,如果使用了相同的数就跳过,理论上是要计算43680*43680次,但是我也没测试过有没有超时,你能不能现把你写的意思告诉我?

# re: 说题~[未登录]  回复  更多评论   

2007-11-16 19:50 by oyjpArt
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}

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