|
Posted on 2007-09-18 17:00 oyjpart 阅读(2009) 评论(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
我看了很久你第一题的代码,感觉你的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}
|