|
|
Posted on 2007-06-11 19:44 oyjpart 閱讀(2902) 評論(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://m.shnenglu.com/sicheng/archive/2007/06/25/26945.html
1734 Sightseeing trip Accepted
請參考解題報告http://m.shnenglu.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道啦。。
|