|
|
這題不懂做，一開始想了一個(gè)動(dòng)態(tài)規(guī)劃的方法，復(fù)雜度很高。估計(jì)得幾百ms。
看status，覺得肯定有很低復(fù)雜度的方法。
然后看了 Discuss ，看到某位大牛說的貪心方法，頓時(shí)恍然大悟，嗎的實(shí)在太牛逼了。
這位大牛的解法如下：
想象自己是一個(gè)黑一日游的司機(jī)：
1.如果有乘客要上車，那么就讓他上，收錢！
2.如果超載了，把距目的地最遠(yuǎn)的幾個(gè)乘客踢下去，退錢。
3.行駛到下一站
照著這個(gè)方法編碼，一開始速度很慢，后來改成用一個(gè)隊(duì)列來維護(hù)車上的乘客，速度就很快了，還飚上榜了。
 #include <stdio.h>
#include <stdlib.h>
#define MAX_N 10032
#define MAX_K 50032
  struct slot_node  {
 int end, cap;
struct slot_node *next;
 };
struct stat_node {
int idx[MAX_N], cnt[MAX_N], head, tail, tot;
};
struct slot_node *start[2][MAX_N], slots[MAX_K*2];
struct stat_node stat[2];
int K, N, C, left, right, slots_cnt, ans;
inline int min(int a, int b)
{
return a < b ? a : b;
}
inline void ins(int a, int b, int c, int d)
{
struct slot_node *t;
if (b > right)
right = b;
if (a < left)
left = a;
t = &slots[slots_cnt++];
t->next = start[d][a];
t->end = b;
t->cap = c;
start[d][a] = t;
}
inline void off(int d, int i)
{
struct stat_node *t = &stat[d];
if (t->head == t->tail || t->idx[t->head] != i)
return ;
ans += t->cnt[t->head];
t->tot -= t->cnt[t->head];
t->head++;
}
inline void del(struct stat_node *t)
{
int c;
  while (t->tot > C) {
c = min(t->tot - C, t->cnt[t->tail - 1]);
t->cnt[t->tail - 1] -= c;
t->tot -= c;
if (!t->cnt[t->tail - 1])
t->tail--;
 }
}
inline void add(struct stat_node *t, int cap, int end)
{
int i, j;
t->tot += cap;
for (i = t->tail - 1; i >= t->head; i--) {
if (t->idx[i] == end) {
t->cnt[i] += cap;
return ;
} else if (t->idx[i] < end)
break;
}
i++;
t->tail++;
for (j = t->tail - 1; j > i; j--) {
t->idx[j] = t->idx[j - 1];
t->cnt[j] = t->cnt[j - 1];
}
t->idx[i] = end;
t->cnt[i] = cap;
}
inline void on(int d, int i)
{
struct slot_node *s;
struct stat_node *t = &stat[d];
for (s = start[d][i]; s; s = s->next)
add(t, s->cap, s->end);
del(t);
}
int main()
{
int i, a, b, c;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d", &K, &N, &C);
left = N;
for (i = 0; i < K; i++) {
scanf("%d%d%d", &a, &b, &c);
if (a > b)
ins(N - a, N - b, c, 1);
else
ins(a, b, c, 0);
}
for (i = left; i <= right; i++) {
off(0, i);
off(1, i);
on(0, i);
on(1, i);
}
printf("%d\n", ans);
return 0;
}
思路：
f[a][b] = { 種類數(shù)目為 a，螞蟻數(shù)目為 b 時(shí)候的方案總數(shù) }
轉(zhuǎn)移：
f[a][b] = f[a - 1][0] + f[a - 1][1] + ... + f[a - 1][b]
時(shí)間 O(AT) 如果求 f[a][*] 只用一次循環(huán)的話
可以用循環(huán)數(shù)組
杯具：
把i看成j了，足足調(diào)了3個(gè)小時(shí)，注意，是不吃不喝，也沒有上廁所，沒有聽歌，沒有看優(yōu)酷。。
是精神高度集中地浪費(fèi)了3個(gè)小時(shí)！
與非主流之腦殘相比，有過之而無(wú)不及也。
#include <stdio.h>
#define P 1000000
int T, A, S, B, fam[1024], dp[2][1024*128], *cur, *pre;
inline int min(int a, int b)
{
return a < b ? a : b;
}
int main()
{
int i, j, cnt, end, sum;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d%d", &T, &A, &S, &B);
for (i = 0; i < A; i++) {
scanf("%d", &j);
fam[j]++;
}
for (i = 0; i <= fam[1]; i++)
dp[1][i] = 1;
end = fam[1];
for (i = 2; i <= T; i++) {
cur = dp[i & 1];
pre = dp[(i+1) & 1];
cur[0] = pre[0];
end += fam[i];
for (j = 1; j <= end; j++) {
cur[j] = cur[j - 1] + pre[j];
if (j > fam[i])
cur[j] -= pre[j - fam[i] - 1];
cur[j] += P;
cur[j] %= P;
}
}
sum = 0;
for (i = S; i <= B; i++) {
sum += cur[i];
sum %= P;
}
printf("%d\n", sum);
return 0;
}
首先考慮這個(gè)子問題：
從地圖上的某一點(diǎn)開始一直向右上方發(fā)展，一共能組成多少個(gè)以這個(gè)點(diǎn)的字母為開頭的單詞。
那么要把以這個(gè)點(diǎn)為左下角的矩形中的點(diǎn)全部都考察一遍。
假設(shè)這個(gè)點(diǎn)的字母為'N'，那就要看所有單詞組成的單詞樹里面，所有'N'節(jié)點(diǎn)孩子的字母，是否出現(xiàn)在這個(gè)矩形中。
如果有出現(xiàn)的話，則又是一個(gè)子問題了。
把所有這樣的子問題的和求出來，就是答案了。
再考慮一個(gè)細(xì)節(jié)：
'N'節(jié)點(diǎn)在單詞樹中可以出現(xiàn)很多次，因此每個(gè)'N'節(jié)點(diǎn)都是一個(gè)子問題。表示：
所有組成的單詞，第一個(gè)字母節(jié)點(diǎn)是'N'，余下的字母節(jié)點(diǎn)出現(xiàn)的'N'的子樹里。
動(dòng)態(tài)規(guī)劃的時(shí)候，對(duì)于每個(gè)節(jié)點(diǎn)要處理一次，因?yàn)槊總€(gè)節(jié)點(diǎn)的孩子都不一樣。
在矩形中統(tǒng)計(jì)所有孩子對(duì)應(yīng)的子問題的和。
關(guān)鍵是怎么存放子問題的答案：
我們需要找出矩形中跟指定孩子對(duì)應(yīng)的點(diǎn)。如果把答案存放在地圖W*H的數(shù)組里面，那就比較麻煩，需要枚舉。
但是如果存放在單詞樹里面，就好很多。
如果我們從上往下掃描每一行，每一行從右到左掃描。那就只需要存放長(zhǎng)度為W的一維數(shù)組了。
考慮一個(gè)細(xì)節(jié)：
對(duì)于地圖上的點(diǎn)'N'，要以什么樣的順序處理單詞樹的每個(gè)'N'。
按照單詞樹的位置，應(yīng)該從上到下處理。
代碼寫出來，跑了100ms+，居然排到第9，然后換了gcc編譯，又排前了一點(diǎn)！ 發(fā)現(xiàn)前面的人，除了第二名，估計(jì)算法都是一樣的。
#include <stdio.h>
#define SIZE 64
#define QUEUE_SIZE 4096
struct tree_node {
int end, dp[SIZE];
struct tree_node *child[26], *next;
};
struct queue_node {
int idx;
struct tree_node *ptr;
};
int H, W;
char map[SIZE][SIZE];
struct tree_node nodes[QUEUE_SIZE], root, *hash[26];
int nodes_cnt;
struct queue_node queue[QUEUE_SIZE];
int tail, head;
inline void bfs()
{
struct tree_node *t;
int i;
head = tail = 0;
queue[tail++].ptr = &root;
while (head != tail) {
t = queue[head++].ptr;
for (i = 0; i < 26; i++) {
if (!t->child[i])
continue;
queue[tail].ptr = t->child[i];
queue[tail].idx = i;
tail++;
}
}
for (tail--; tail >= 1; tail--) {
t = queue[tail].ptr;
i = queue[tail].idx;
t->next = hash[i];
hash[i] = t;
}
}
inline void calc(int y, int x)
{
struct tree_node *t, *c;
int i, j, sum;
for (t = hash[map[y][x] - 'A']; t; t = t->next) {
sum = t->end;
for (i = 0; i < 26; i++) {
c = t->child[i];
if (!c)
continue;
for (j = W - 1; j >= x; j--)
sum += c->dp[j];
}
t->dp[x] += sum;
}
}
int main()
{
int i, j, sum;
char str[64], *s;
struct tree_node *t, **p;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &H, &W);
for (i = 0; i < H; i++)
scanf("%s", map[i]);
while (scanf("%s", str) != EOF) {
t = &root;
for (s = str; *s; s++) {
p = &t->child[*s - 'A'];
if (!*p)
*p = &nodes[nodes_cnt++];
t = *p;
}
t->end++;
}
bfs();
for (i = 0; i < H; i++)
for (j = W - 1; j >= 0; j--)
calc(i, j);
sum = 0;
for (i = 0; i < 26; i++) {
t = root.child[i];
if (!t)
continue;
for (j = 0; j < W; j++)
sum += t->dp[j];
}
printf("%d\n", sum);
return 0;
}
思路： 就是一個(gè)最短路徑的問題。但是題目數(shù)據(jù)規(guī)模跟描述不符合。 數(shù)組要開大一些才能過。官方數(shù)據(jù)是描述是符合的，可能是管理員加了一些進(jìn)去。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_E 4096
#define MAX_V 2048
#define MAX_COST (1 << 30)
struct edge_node {
int idx, cost;
struct edge_node *next;
};
struct graph_node {
struct edge_node edges[MAX_E], *map[MAX_V];
int edges_cnt, vertexs_cnt;
int min_dis[MAX_V];
};
inline int min(int a, int b)
{
return a < b ? a : b;
}
inline void graph_init(struct graph_node *g, int vertexs_cnt)
{
g->vertexs_cnt = vertexs_cnt;
g->edges_cnt = 0;
memset(g->map, 0, vertexs_cnt * sizeof(g->map[0]));
}
inline void graph_addedge(struct graph_node *g,
int from, int to,
int cost
)
{
struct edge_node *e;
e = &g->edges[g->edges_cnt++];
e->idx = to;
e->cost = cost;
e->next = g->map[from];
g->map[from] = e;
}
inline void graph_spfa(struct graph_node *g, int idx)
{
static int queue[MAX_V], vis[MAX_V], tm, head, tail;
int i, val;
struct edge_node *e;
for (i = 0; i < g->vertexs_cnt; i++)
g->min_dis[i] = MAX_COST;
g->min_dis[idx] = 0;
head = tail = 0;
tm++;
queue[tail++] = idx;
while (head != tail) {
idx = queue[head++];
vis[idx] = 0;
for (e = g->map[idx]; e; e = e->next) {
val = g->min_dis[idx] + e->cost;
if (val >= g->min_dis[e->idx])
continue;
g->min_dis[e->idx] = val;
if (vis[e->idx] == tm)
continue;
queue[tail++] = e->idx;
vis[e->idx] = tm;
}
}
}
int main()
{
static int loc[MAX_V], i, F, C, P, M, from, to, cost, cnt;
static struct graph_node g;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d%d", &F, &P, &C, &M);
graph_init(&g, F + 1);
while (P--) {
scanf("%d%d%d", &from, &to, &cost);
graph_addedge(&g, from, to, cost);
graph_addedge(&g, to, from, cost);
}
for (i = 0; i < C; i++)
scanf("%d", &loc[i]);
graph_spfa(&g, 1);
cnt = 0;
for (i = 0; i < C; i++)
cnt += (g.min_dis[loc[i]] <= M);
printf("%d\n", cnt);
for (i = 0; i < C; i++)
if (g.min_dis[loc[i]] <= M)
printf("%d\n", i + 1);
return 0;
}
摘要: 第一次寫這玩意，還真有點(diǎn)麻煩，出了點(diǎn)問題。然后看了一下別人的代碼，發(fā)現(xiàn)雙向邊，要分成兩個(gè)單向邊來插入。長(zhǎng)見識(shí)了。而且費(fèi)用的值有正有負(fù)，最好用SPFA來找最短路徑。思路：建立一個(gè)超級(jí)源點(diǎn)，跟點(diǎn)1連起來，容量為2。建立一個(gè)超級(jí)匯點(diǎn)，跟點(diǎn)N連起來，容量為2。其他的邊容量均為1。#include <stdio.h>#include <stdlib.h>#inc... 閱讀全文
#include <stdio.h>
int L, C;
char path[26], arr[26], map[256];
void dfs(int i, int vowels, int idx)
{
if (idx == L) {
if (vowels)
printf("%s\n", path);
return ;
}
for ( ; i <= C - L + idx; i++) {
path[idx] = arr[i];
dfs(i + 1, vowels + (arr[i] == 'a' || arr[i] == 'e' ||
arr[i] == 'i' || arr[i] == 'o' ||
arr[i] == 'u'),
idx + 1);
}
}
int main()
{
int i, j;
char str[8];
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &L, &C);
for (i = 0; i < C; i++) {
scanf("%s", str);
map[str[0]]++;
}
j = 0;
for (i = 'a'; i <= 'z'; i++)
if (map[i])
arr[j++] = i;
path[L] = 0;
dfs(0, 0, 0);
return 0;
}
思路：
留意到題目里面有一句話“All farms are connected one way or another to Farm 1.”。
這貌似說明圖一開始就是連通的。
二分答案，判斷依據(jù)是：
如果將大于某個(gè)長(zhǎng)度的邊都去掉以后，圖就不連通了。
那這個(gè)長(zhǎng)度相對(duì)答案來說，一定是大了。
#include <stdio.h>
#define MAX_M 10032
#define MAX_N 2048
struct edge_node {
int idx, len;
struct edge_node *next;
};
struct edge_node edges[MAX_M*2], *map[MAX_N];
int N, M, vis[MAX_N], tm, stk[MAX_N], *sp;
inline int can(int limit)
{
int cnt;
struct edge_node *e;
tm++;
sp = stk;
*sp++ = 1;
vis[1] = tm;
cnt = 0;
while (sp > stk) {
sp--;
cnt++;
for (e = map[*sp]; e; e = e->next) {
if (vis[e->idx] == tm || e->len > limit)
continue;
vis[e->idx] = tm;
*sp++ = e->idx;
}
}
return cnt == N;
}
inline void insert(struct edge_node *e, int a, int b, int len)
{
e->idx = b;
e->len = len;
e->next = map[a];
map[a] = e;
}
int main()
{
int l, r, m, i, a, b, len;
scanf("%d%d", &N, &M);
l = 0x7fffffff;
r = 0;
for (i = 0; i < M*2; i += 2) {
scanf("%d%d%d", &a, &b, &len);
insert(&edges[i], a, b, len);
insert(&edges[i + 1], b, a, len);
if (len < l)
l = len;
if (len > r)
r = len;
}
while (l <= r) {
m = (l + r) / 2;
if (!can(m))
l = m + 1;
else
r = m - 1;
}
printf("%d\n", r + 1);
return 0;
}
思路：
每天要么以今天的價(jià)格買入，要么前面某天買了存在倉(cāng)庫(kù)里。不存在一半是今天買的，一半是從倉(cāng)庫(kù)拿的，這種情況。
因?yàn)槿绻@樣，肯定有一半具有更高的性價(jià)比，那就全部都改成更高性價(jià)比的方式就好了。。
所以，這題只需要保存一個(gè)當(dāng)前的最大值，掃描一遍就能出結(jié)果了。瞬間就淪為一道水題了。還以為要大動(dòng)作的呢。
#include <stdio.h>
__int64 N, S;
__inline __int64 min(__int64 a, __int64 b)
{
return a < b ? a : b;
}
int main()
{
__int64 best, i, c, y, sum, inc;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%I64d%I64d", &N, &S);
best = 1LL << 60;
sum = 0;
inc = (N - 1) * S;
for (i = 0; i < N; i++) {
scanf("%I64d%I64d", &c, &y);
best = min(best, c + inc);
sum += y * (best - inc);
inc -= S;
}
printf("%I64d\n", sum);
return 0;
}
思路： 深搜的時(shí)候，可以生成一棵樹。 深搜也就是深度遍歷這棵樹，把遍歷的路徑打印出來，就解決了一部分邊了，這部分邊都是經(jīng)過兩次的，來一次去一次。 剩下的邊，就是遍歷的時(shí)候正在訪問的節(jié)點(diǎn)與已經(jīng)訪問的節(jié)點(diǎn)之間的邊，很容易的判斷的。同樣把這部分路徑也打印出來。 后來看了 Discuss 才發(fā)現(xiàn)，這個(gè)東西叫做“歐拉回路”，又長(zhǎng)見識(shí)了。 代碼
#include <stdio.h>
#define MAX_M 50032
#define MAX_N 10032
int N, M;
struct edge_node {
int vis, to;
struct edge_node *next;
};
struct edge_node edges[MAX_M * 2], *map[MAX_N];
int edges_cnt, vis[MAX_N];
inline void insert(struct edge_node *e, int from, int to)
{
e->to = to;
e->next = map[from];
map[from] = e;
}
void dfs(int idx)
{
struct edge_node *e;
int i;
vis[idx] = 1;
printf("%d\n", idx);
for (e = map[idx]; e; e = e->next) {
i = e - edges;
if (vis[e->to]) {
if (e->vis)
continue;
edges[i].vis = 1;
edges[i ^ 1].vis = 1;
printf("%d\n%d\n", e->to, idx);
continue;
}
edges[i].vis = 1;
edges[i ^ 1].vis = 1;
dfs(e->to);
printf("%d\n", idx);
}
}
int main()
{
int from, to, i;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &M);
for (i = 0; i < M*2; i += 2) {
scanf("%d%d", &from, &to);
insert(&edges[i], from, to);
insert(&edges[i + 1], to, from);
}
dfs(1);
return 0;
}
#include <stdio.h>
#include <string.h>
int T, N, arr[16], map[16][16];
int dfs(int idx, int i)
{
if (idx >= N)
return 1;
if (!arr[idx])
return dfs(idx + 1, idx + 2);
for ( ; i < N; i++) {
if (!arr[i])
continue;
arr[i]--;
arr[idx]--;
map[idx][i]++;
map[i][idx]++;
if (dfs(idx, i + 1))
return 1;
arr[i]++;
arr[idx]++;
map[idx][i]--;
map[i][idx]--;
}
return 0;
}
int main()
{
int i, j;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &T);
while (T--) {
scanf("%d", &N);
for (i = 0; i < N; i++)
scanf("%d", &arr[i]);
memset(map, 0, sizeof(map));
if (dfs(0, 1)) {
printf("YES\n");
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++)
printf("%d ", map[i][j]);
printf("\n");
}
printf("\n");
} else
printf("NO\n\n");
}
return 0;
}
|