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-06-11 19:44 oyjpart 阅读(2823) 评论(13)  编辑 收藏 引用 所属分类: ACM/ICPC或其他比赛
POJ

1715 Hexadecimal Numbers Accepted
首先确定位数 比如N位数一共有(16-1) * C(15, N-1); 其中16-1代表第一位不能为0 然后从高位到低位一个一个数确定

1716 Integer Intervals Accepted
可以按照左端点排序(也可以按右端点排序) 比如按左端点排序 贪心向后选择 然后将选择的数存入一个数组中 下一线段只要检查需要多少几个数就可以了 在选择之前可以预先把具有包含关系的线段去掉 排序之后用stack就可以实现了

1717 Dominoes Accepted
典型的状态型DP

1718 River Crossing Accepted
初看起来和PKU的Traffic Light有些像 是否是Dijkstra的变形呢?稍作分析发现并非如此 因为不能停在某个位置去等待下一次行进 这样 无法做标号的永久化 分析发现题目中1<=a,b(上下时间间隔)<=5 这样给我们提供了一个契机 对于每个位置的变换周期都在2~10之间 因此所有位置的变换周期最大将会 = LCM(2,3,4,..9,10) 计算一下发现为2520 这样我们就可以在这段时间内做DP a[t][i]代表t时刻i地址是否可达

1719 Shooting Contest Accepted
建立二分图 做最大匹配(行或列做X集合都可以 用行要方便一点) 如果匹配数达到行数 就满足条件  此题另有贪心算法

1720 SQUARES 不会做 几何题

1721 CARDS  Accepted
我的想法是搜 但是看到师傅是找了一个循环节 并且循环长度不超过n 我试着0MS过了 不过没有证明出来 可能要用置换群的理论 不过我是白痴

1722 SUBTRACT Accepted
如果题目描述改为在这些数中添加+-号 使表达式的值为T 则可以很好的用DP或Memoization解决 这个题目相当于把上述的问题转化为对表达式的+号加上括号 就变成了题目描述中的运算 把所有括号内的运算先输出 若剩余K个数 再输出K-1个1

1723 SOLDIERS Accepted
欲做此题 先证明下列结论:把一个序列{x1,x2..Xn} 通过加减变化变成相同的数Xp 一定 Xp = x[n/2] 通过在坐标轴上画点可以看出Xp无论左移还是右移 必然导致变化数增加 于是此题的y坐标方向既可以转化成此类问题 对于X方向 首先可以对每个坐标减去所在位置 也就转化成了此类问题 这样通过排序就能解决此题

1724 ROADS Accepted
这个题目和“双调路径"的做法有点类似 把每一个点拆成总Money = M个点 然后用优先级队列找最短路径就可以了

1725 BALL 好麻烦呀...

1731 Orders Accepted
深搜 可以先把输入串排序 在搜索的时候碰到同样字符的时候可以只深搜第一个 这样可以去重


1732 Phone numbers Accepted
没想到直接DP就过了 我觉得就是一个1维的DP  时间和空间应该都没问题
dp[i]代表0->i的序列可以用字串组合的最小字串数 对每个i做n次转移 n是单词数

1733 Parity game  Accepted
请参考解题报告http://www.cppblog.com/sicheng/archive/2007/06/25/26945.html

1734 Sightseeing trip Accepted
请参考解题报告http://www.cppblog.com/sicheng/archive/2007/05/28/25027.html

1735 A Game on the Chessboard Accepted
双向广搜 60MS 注意用2进制位压缩存储
写了我3K的代码 不过有一半是复制粘贴的...

1736 Block Town

Feedback

# re: 闲来切题 呵呵  回复  更多评论   

2007-06-11 19:53 by FlyingBear
ym牛人

# re: 闲来切题 呵呵  回复  更多评论   

2007-07-05 10:38 by owen
keke 来仰慕一下~

# re: 闲来切题 呵呵  回复  更多评论   

2008-01-07 13:15 by rushhour
能说一下那个1723号题中,你说对X方向上,对每个坐标减去所在位置,是什么意思?

# re: 闲来切题 呵呵  回复  更多评论   

2008-01-07 17:53 by oyjpart
贴下代码,可能容易理解些~
#include <algorithm>
using namespace std;
const int N = 10010;
int x[N], y[N];

int main() {
//freopen("t.in", "r", stdin);
int n, i;
scanf("%d", &n);
for(i = 0; i< n; i++)
scanf("%d%d", &x[i], &y[i]);
sort(x, x+n);
sort(y, y+n);
for(i = 0; i<n; i++)
x[i] -= i;
sort(x, x+n);
int ans = 0;
for(i = 0; i <n; i++)
ans += abs(x[i] - x[n/2]) + abs(y[i] - y[n/2]);
printf("%d\n", ans);
return 0;
}

# re: 闲来切题 呵呵  回复  更多评论   

2008-04-12 00:58 by 竹苑
请问1718那道题目是不是:
先对所有a+b求最大公约数,得到最大时间t1。然后在这段时间内做DP (a[t][i]代表t时刻i地址是否可达),每次检查a[t-1][j](0<=i-5<=j<=i-1)是否可达,有一个可达则a[t][i]可达。
请赐教啊,WA了好多次了。。。

# re: 闲来切题 呵呵  回复  更多评论   

2008-04-16 13:16 by oyjpart
你参考下源代码吧,如果还WA,我们QQ说。 :)
#include <stdio.h>
#include <string.h>

const int N = 1010;
const int T = 2520;
const int MAXINT = 123456789;
int n;
int u[N], d[N];
bool dp[2][N];
int gcd[11][11];

int GCD(int a, int b) {
if(a < b) return GCD(b, a);
while(b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}

inline int LCM(int a, int b) {
return a * b / GCD(a, b);
}

bool ok(int time, int i) {
int t = time % (u[i] + d[i]);
if(t == 0 || t > u[i]) return false;
return true;
}


int main() {
int ntc, i, t, j;
scanf("%d", &ntc);
while(ntc--) {
scanf("%d", &n);
int lcm = 1;
u[0] = u[n+1] = MAXINT; d[0] = d[n+1] = 0;
for(i = 1; i <= n; ++i) {
scanf("%d %d", &u[i], &d[i]);
lcm = LCM(lcm, u[i] + d[i]);
}
n += 2;
memset(dp, false, sizeof(dp));
dp[0][0] = 1;
for(t = 1; t <= lcm; ++t) {
int now = t % 2;
memset(dp[now], false, sizeof(dp[now]));
for(i = 0; i < n; ++i) if(ok(t, i)) {
for(j = i-5; j <= i+5; j++) if(j >= 0 && j < n) {
if(dp[!now][j]) { dp[now][i] = 1; break; }
}
}
if(dp[now][n-1]) { printf("%d\n", t); break; }
}
if(t > lcm) printf("NO\n");
}
return 0;
}

# re: 闲来切题 呵呵  回复  更多评论   

2008-04-20 14:24 by 竹苑
呵呵,参考你的源码,终于AC啦。
原来没有考虑过了桥墩可以跳回来的情况,所以条件改为
(0<=i-5<=j<=i+5<=n)就过啦。

# re: 闲来切题 呵呵  回复  更多评论   

2008-06-23 20:49 by lihao102
1724 roads 双调路径能说进更详细些吗?

   我不是很明白,有讲这方面的资料吗?

           谢谢了。。。。。。

# re: 闲来切题 呵呵  回复  更多评论   

2008-06-23 22:22 by oyjpart
1724 roads的代码:
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int N = 101;
struct Node {int x, w, f; void set(int xx, int ww, int ff) {x = xx; w = ww; f = ff;} };
vector<Node> adj[N][N];
int money, nv, ne;

bool operator<(const Node& a, const Node& b) { return a.w > b.w; }

void solve() {
int x, i, j, y;
priority_queue<Node> pq;
Node now, cur;
now.set(0, 0, 0);
pq.push(now);
while(!pq.empty()) {
cur = pq.top();
pq.pop();
x = cur.x;
if(x == nv-1) {
printf("%d\n", cur.w);
return;
}
for(i = 0; i < nv; ++i) {
for(j = 0; j < adj[x][i].size(); j++) if(cur.f + adj[x][i][j].f <= money) {
y = adj[x][i][j].x;
now.set(y, cur.w + adj[x][i][j].w, cur.f + adj[x][i][j].f);
pq.push(now);
}
}
}
printf("-1\n");
}

int main() {
int i, u, v, w, f;
Node now;
scanf("%d %d %d", &money, &nv, &ne);
for(i = 0; i < ne; ++i) {
scanf("%d %d %d %d", &u, &v, &w, &f);
--u; --v;
now.set(v, w, f);
adj[u][v].push_back(now);
}

solve();

return 0;
}

# re: 闲来切题 呵呵  回复  更多评论   

2008-06-25 15:37 by lihao102
能留个联系方式吗? 最近也在为ACM努力着。 有不懂的,希望你能帮我!

谢谢了。。。

# re: 闲来切题 呵呵  回复  更多评论   

2008-06-26 11:22 by oyjpart
Contact me via POJ mail : alpc12
email(MSN also) : yescrystalblue@sina.com

# re: 闲来切题 呵呵[未登录]  回复  更多评论   

2009-02-03 21:37 by gb18030
晕。。。您一天能切多少题。。。

# re: 闲来切题 呵呵  回复  更多评论   

2009-02-04 10:03 by oyjpart
额。。这个说不定啊。。除了比赛一般不超过5道啦。。

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理