|
|
Posted on 2007-06-11 19:44 oyjpart 阅读(2873) 评论(13) 编辑 收藏 引用 所属分类: ACM/ICPC或其他比赛
POJ1715 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
能说一下那个1723号题中,你说对X方向上,对每个坐标减去所在位置,是什么意思?
贴下代码，可能容易理解些~
#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;
}
请问1718那道题目是不是:
先对所有a+b求最大公约数，得到最大时间t1。然后在这段时间内做DP （a[t][i]代表t时刻i地址是否可达），每次检查a[t-1][j](0<=i-5<=j<=i-1)是否可达，有一个可达则a[t][i]可达。
请赐教啊，WA了好多次了。。。
你参考下源代码吧，如果还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;
}
呵呵，参考你的源码，终于AC啦。
原来没有考虑过了桥墩可以跳回来的情况，所以条件改为
(0<=i-5<=j<=i+5<=n)就过啦。
1724 roads 双调路径能说进更详细些吗？
我不是很明白，有讲这方面的资料吗？
谢谢了。。。。。。
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;
}
能留个联系方式吗？ 最近也在为ACM努力着。 有不懂的，希望你能帮我！
谢谢了。。。
Contact me via POJ mail : alpc12
email(MSN also) : yescrystalblue@sina.com
# re: 闲来切题 呵呵[未登录] 回复 更多评论
2009-02-03 21:37 by
晕。。。您一天能切多少题。。。
额。。这个说不定啊。。除了比赛一般不超过5道啦。。
|