|
|
Posted on 2007-09-18 17:00 oyjpart 閱讀(2015) 評論(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}
|