|
|
Posted on 2007-06-11 19:44 oyjpart 閱讀(2885) 評(píng)論(13) 編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽
POJ1715 Hexadecimal Numbers Accepted
首先確定位數(shù) 比如N位數(shù)一共有(16-1) * C(15, N-1); 其中16-1代表第一位不能為0 然后從高位到低位一個(gè)一個(gè)數(shù)確定 1716 Integer Intervals Accepted
可以按照左端點(diǎn)排序（也可以按右端點(diǎn)排序） 比如按左端點(diǎn)排序 貪心向后選擇 然后將選擇的數(shù)存入一個(gè)數(shù)組中 下一線段只要檢查需要多少幾個(gè)數(shù)就可以了 在選擇之前可以預(yù)先把具有包含關(guān)系的線段去掉 排序之后用stack就可以實(shí)現(xiàn)了 1717 Dominoes Accepted
典型的狀態(tài)型DP 1718 River Crossing Accepted
初看起來(lái)和PKU的Traffic Light有些像 是否是Dijkstra的變形呢？稍作分析發(fā)現(xiàn)并非如此 因?yàn)椴荒芡Ｔ谀硞€(gè)位置去等待下一次行進(jìn) 這樣 無(wú)法做標(biāo)號(hào)的永久化 分析發(fā)現(xiàn)題目中1<=a，b（上下時(shí)間間隔)<=5 這樣給我們提供了一個(gè)契機(jī) 對(duì)于每個(gè)位置的變換周期都在2~10之間 因此所有位置的變換周期最大將會(huì) = LCM(2,3,4,..9,10) 計(jì)算一下發(fā)現(xiàn)為2520 這樣我們就可以在這段時(shí)間內(nèi)做DP a[t][i]代表t時(shí)刻i地址是否可達(dá) 1719 Shooting Contest Accepted
建立二分圖 做最大匹配（行或列做X集合都可以 用行要方便一點(diǎn)） 如果匹配數(shù)達(dá)到行數(shù) 就滿足條件 此題另有貪心算法 1720 SQUARES 不會(huì)做 幾何題 1721 CARDS Accepted
我的想法是搜 但是看到師傅是找了一個(gè)循環(huán)節(jié) 并且循環(huán)長(zhǎng)度不超過(guò)n 我試著0MS過(guò)了 不過(guò)沒(méi)有證明出來(lái) 可能要用置換群的理論 不過(guò)我是白癡 1722 SUBTRACT Accepted
如果題目描述改為在這些數(shù)中添加+-號(hào) 使表達(dá)式的值為T(mén) 則可以很好的用DP或Memoization解決 這個(gè)題目相當(dāng)于把上述的問(wèn)題轉(zhuǎn)化為對(duì)表達(dá)式的+號(hào)加上括號(hào) 就變成了題目描述中的運(yùn)算 把所有括號(hào)內(nèi)的運(yùn)算先輸出 若剩余K個(gè)數(shù) 再輸出K-1個(gè)1 1723 SOLDIERS Accepted
欲做此題 先證明下列結(jié)論：把一個(gè)序列{x1,x2..Xn} 通過(guò)加減變化變成相同的數(shù)Xp 一定 Xp = x[n/2] 通過(guò)在坐標(biāo)軸上畫(huà)點(diǎn)可以看出Xp無(wú)論左移還是右移 必然導(dǎo)致變化數(shù)增加 于是此題的y坐標(biāo)方向既可以轉(zhuǎn)化成此類問(wèn)題 對(duì)于X方向 首先可以對(duì)每個(gè)坐標(biāo)減去所在位置 也就轉(zhuǎn)化成了此類問(wèn)題 這樣通過(guò)排序就能解決此題 1724 ROADS Accepted
這個(gè)題目和“雙調(diào)路徑"的做法有點(diǎn)類似 把每一個(gè)點(diǎn)拆成總Money = M個(gè)點(diǎn) 然后用優(yōu)先級(jí)隊(duì)列找最短路徑就可以了 1725 BALL 好麻煩呀... 1731 Orders Accepted
深搜 可以先把輸入串排序 在搜索的時(shí)候碰到同樣字符的時(shí)候可以只深搜第一個(gè) 這樣可以去重
1732 Phone numbers Accepted
沒(méi)想到直接DP就過(guò)了 我覺(jué)得就是一個(gè)1維的DP 時(shí)間和空間應(yīng)該都沒(méi)問(wèn)題
dp[i]代表0->i的序列可以用字串組合的最小字串?dāng)?shù) 對(duì)每個(gè)i做n次轉(zhuǎn)移 n是單詞數(shù)
1733 Parity game Accepted
請(qǐng)參考解題報(bào)告http://www.shnenglu.com/sicheng/archive/2007/06/25/26945.html
1734 Sightseeing trip Accepted
請(qǐng)參考解題報(bào)告http://www.shnenglu.com/sicheng/archive/2007/05/28/25027.html
1735 A Game on the Chessboard Accepted
雙向廣搜 60MS 注意用2進(jìn)制位壓縮存儲(chǔ) 寫(xiě)了我3K的代碼 不過(guò)有一半是復(fù)制粘貼的... 1736 Block Town
Feedback
能說(shuō)一下那個(gè)1723號(hào)題中,你說(shuō)對(duì)X方向上,對(duì)每個(gè)坐標(biāo)減去所在位置,是什么意思?
貼下代碼，可能容易理解些~
#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;
}
請(qǐng)問(wèn)1718那道題目是不是:
先對(duì)所有a+b求最大公約數(shù)，得到最大時(shí)間t1。然后在這段時(shí)間內(nèi)做DP （a[t][i]代表t時(shí)刻i地址是否可達(dá)），每次檢查a[t-1][j](0<=i-5<=j<=i-1)是否可達(dá)，有一個(gè)可達(dá)則a[t][i]可達(dá)。
請(qǐng)賜教啊，WA了好多次了。。。
你參考下源代碼吧，如果還WA，我們QQ說(shuō)。 :)
#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啦。
原來(lái)沒(méi)有考慮過(guò)了橋墩可以跳回來(lái)的情況，所以條件改為
(0<=i-5<=j<=i+5<=n)就過(guò)啦。
1724 roads 雙調(diào)路徑能說(shuō)進(jìn)更詳細(xì)些嗎？
我不是很明白，有講這方面的資料嗎？
謝謝了。。。。。。
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;
}
能留個(gè)聯(lián)系方式嗎？ 最近也在為ACM努力著。 有不懂的，希望你能幫我！
謝謝了。。。
Contact me via POJ mail : alpc12
email(MSN also) : yescrystalblue@sina.com
額。。這個(gè)說(shuō)不定啊。。除了比賽一般不超過(guò)5道啦。。
|