博文
Zju 1196 Fast Food(2006-08-06 23:54:00)
摘要：
2004112
2006-08-06 23:32:06
Accepted
1196
C++
00:00.02
704K
St.Crux
dis[i][k]表示在前k+1个加油站(0-k)中放入(i+1)个补给站所最小达到的距离和。
cost[i][k]表示从点i到点k所需要的最短距离，当且仅当补给站放在i，k的中点时。
方程是dis[i][k] = min(dis[i - 1][j] + cost[j + 1][k]) i - 1 <= j <k
C++的数组下标真是头痛哪
#include <cstdio>
#include <string>
#include <cmath>
int d[201][201], s[201][201], a[201], n, m;
#define MX 99999999
int main()
{
//freopen("in.txt", "r", stdin);
int c = 0;
while(scanf("%d %d", &n, &m) && n)
{
printf("Chain %d\n", ++ c);
int i, k, j;
for(i = 0; i < n; i ++)
{
scanf("%d", &a[i]);
}
memset(s, 0, sizeof(s));
for(i = 0; i < n; i ++)
{
for(k = i; k < n; k ++)
{
int mid = (i + k) / 2;
&nb......
Zju 1524 Supermarket(2006-08-06 15:46:00)
摘要：
2003120
2006-08-06 15:30:49
Accepted
1524
C++
00:00.27
400K
St.Crux
这个题是典型的dp。n = 100, m = 100000，一开始打算对m进行dp，结果显然超时。后来看了几个帖子，明白是对n进行dp，以每一步的总和为状态转移，方程如下：
p(N) = min(p(N - 1) + di, p(N)) p(N) ≠ 0
di p(N) = 0
#include <cstdio>
#include <string>
double a[100];
int b[100], n, m, mx, tmx;
int main()
{
int i, k;
//freopen("in.txt", "r", stdin);
while(scanf("%d %d", &n, &m) && n)
{
memset(a, 0, sizeof(a));
for(i = 0; i < n; i ++)
{
&......
Zju 1366 Cash Machine(2006-08-04 23:05:00)
摘要：
1999291
2006-08-04 22:51:44
Accepted
1366
C++
00:01.23
1176K
St.Crux
终于又ac了一题.....最近几天我被淹没在绿色的wrong answer里。
『这个题很经典』hysbz的admin如是说。但我还是用不那么经典的办法.....用了两个数组，一个存标志位一个存数据。那个排序可有可无。
#include <cstdio>
#include <string>
int a[100001], b[100001], c, n, mx;
int ni[10], di[10];
int main()
{
//freopen("in.txt", "r", stdin);
while(scanf("%d", &c) != EOF)
{
int i, k, j;
scanf("%d", &n);
for(i = 0; i < n; i ++)
{
scanf("%d %d", &ni[i], &di[i]);
}
for(i = 0; i < n - 1; i ++)
{
int j = i, t0 = di[i], t1 = ni[i];
for(k = i + 1; k < n; k ++)
{
if(t0 > di[k])
{
j = k; t0 = di[k];
}
}
&nbs......
Zju 1986 Bridging Signals(2006-08-03 15:42:00)
摘要：
1995605
2006-08-03 15:27:32
Accepted
1986
C++
00:00.20
552K
St.Crux
以前写过一遍。这个算法很不错，时间是O(nlogn)，空间是O(n)，使用了一个栈。
CQF大牛的算法：
1、建立一个栈stack，清空。{stack[i]表示当前状态下，所有长度为i的子序中最后一个数的最小值}。//这个太漂亮了：cqf是大牛大牛大大牛呀：）
2、按先后顺序循环序列的每一个数，用操作3修改当前状态
3、如果这个数不小栈顶或栈为空就++stack的长度，否则就用二分法找出一个最小的i使得stack[i]>这个数.将stack[i]更新为这个数。{可以用二分法是因为stack是有序的}
4、输出stack的长度。{最长不下子序长度}
#include <cstdio>
#include <string>
int a[40000], c;
int main()
{
int m, n, i, k;
//freopen("in.txt", "r", stdin);
scanf("%d", &m);
for(i = 0; i < m; i ++)
{
memset(a, 0, sizeof(a));
scanf("%d", &n);
c = 0;
for(k = 0; k < n; k ++)
{
int t;
scanf("%d", &t);
if(c == 0 || t > a[c - 1])
a[c ++] = t;
else
{
int l = ......
Zju 1530 Find The Multiple(2006-08-02 22:52:00)
摘要：
1994302
2006-08-02 22:41:45
Accepted
1530
C++
00:00.01
440K
St.Crux
好吧，我承认，做这个题之前我犹豫了好一阵子：到底是不是dfs?不过这个数据够小的了，n<=200,递归层数<=100。
#include <cstdio>
int n, t, a[100], ac;
void dfs(int c, int s)
{
if(!s && !ac)
{
ac = 1;
for(int i = 0; i < c; i ++)
{
printf("%d", a[i]);
}
printf("\n");
}
else
{
if(c < 100 && !ac)
{
a[c] = 1;
dfs(c + 1, (s * 10 + 1) % n);
a[c] = 0;
dfs(c + 1, (s * 10) % n);
}
}
}
int main()
{
while(scanf("%d", &n) && n)
{
a[0] = 1, ac = 0;
dfs(1, 1);
}
return 0;
}......
Zju 2042 Divisibility(2006-08-02 21:46:00)
摘要：
1994121
2006-08-02 21:28:14
Accepted
2042
C++
00:00.39
392K
St.Crux
做了一个半钟头，贡献了n个wa和rte，终于ac了。题目还是比较有意思的，在算术式里插加减号，使结果被某个数整除。而且是那么的像bfs......我的dp写的一如既往的烂，而且中途还测试了一下c里%的用法。
其实这些题的做法大同小异，都是用一个数组来表示当前可能达到的状态情况，达到置1，然后在下一步搜索这个数组中上一步的情况，然后再加以处理。只是这个题数据可能比较BT一点。
还有对memcpy的赋值不理解，http://www.kfbb.cn/blog/blogview.asp?logID=482，导致我后来又wa了n次。
#include <cstdio>
#include <string>
int a[100], b[100], m, n, k;
int main()
{
int i, j, u;
//freopen("div.16", "r", stdin);
//freopen("in.txt", "r", stdin);
scanf("%d", &m);
for(i = 0; i < m; i ++)
{
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
if(i) printf("\n");
scanf("%d %d", &n, &k);
int t;
scanf("%d", &t);
t %= k;
if(t < 0) t += k;
a[t] = 1;
for(j = 1; j < n; j ++)......
Zju 1203 Swordfish(2006-08-01 23:01:00)
摘要：
1991483
2006-08-01 22:46:34
Accepted
1203
C++
00:00.01
480K
St.Crux
O(n^3)。用邻接矩阵做的。什么？prim是什么......求最小生成树。不过我总觉得这个算法有待提高......
另：double必须要用%lf来读入
#include <cstdio>
#include <string>
#include <cmath>
double a[100][100], sum, p[100][2];
int b[100], n;
void prim()
{
int i, k, j, sp, ep;
sum = 0;
for(i = 1; i < n; i ++)
{
double min = 30000;
for(k = 0; k < n; k ++) // 起点边
{
if(!b[k]) continue;
for(j = 0; j < n; j ++) // 终点边
{
if(b[j]) continue;
if(a[k][j] < min)
{
min = a[k][j];
sp = k, ep = j;
}
}
}
sum += min;
b[ep] = 1;
}
}
voi......
Zju 1229 Gift?!(2006-08-01 21:55:00)
摘要：
1991363
2006-08-01 21:38:49
Accepted
1229
C++
00:00.00
392K
St.Crux
这个题其实是取巧了。可以证明，当n>=50时均有解。(怎么证??)
而且是自从共和元年史官们拿起笔和墨以来——也许他们拿的是苹果刀和竹子——我第一次在zoj的效率排名上排到第一页，尽管这排名是多么的虚幻和浮于流表.......
其实抛开这个50，题目还是简单的.....oibh的第一题米。类似于bfs的dp，以每一步为状态，跳到则标1。哦，我是标一个步数。
#include <cstdio>
#include <string>
int m, n, g;
int a[49];
int main()
{
//freopen("in.txt", "r", stdin);
while(scanf("%d %d", &n, &m) && m | n)
{
g = 0;
memset(a, 0, sizeof(a));
a[0] = 1;
if(n < 50)
{
int got = 1;
int c = 2;
while(got && !a[m - 1])
{
got = 0;
for(int i = 0; i < n; i ++)
{
if(a[i] == c - 1)
{
&n......
Zju 2271 Chance to Encounter a Girl(2006-08-01 17:02:00)
摘要：
1990623
2006-08-01 16:53:10
Accepted
2271
C++
00:00.77
8324K
St.Crux
过的好不容易......
要求A与B在不同时间点上相遇的概率和。很明显的dp，用不同的时间来区分状态。郁闷的是一开始居然看不懂样例......
p[t][i][k] = OMG([t - 1][ii][kk] / 概率) 这里iikk是与i,k相邻的点。
用了两个优化。一是算概率的时候可以用以下init的方法。二是染色！如5,9,13,17这样的是无解的:(
#include <cstdio>
#include <string>
double p[101][100][100];
int pos[100][100], n;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void init()
{
for(int i = 0; i < n; i ++)
{
for(int k = 0; k < n; k ++)
{
pos[i][k] = 4;
if(i == 0 || i == n - 1)
pos[i][k] --;
if(k == 0 || k == n - 1)
pos[i][k] --;
}
}
}
int main()
{
//freopen("in.txt", "r", stdin);
while(scanf("%d", &n) != EOF)
{
memset(p, 0, sizeof(p));
init();
int t, i, k......
Zju 1101 Gamblers(2006-07-30 23:41:00)
摘要：最简单的bsearch，然而我wa了无数次.......最晕的一次是输错数了-_-
ps：两个小循环要全部遍历。因为有可能是14,0,-2,-16这样的情况。
1986516
2006-07-30 23:28:21
Accepted
1101
C++
00:00.10
444K
St.Crux
#include <stdio.h>
#include <stdlib.h>
int a[1000], n, wi, wj, wk, wu;
int comp(const void *a, const void *b)
{
int aa = *(int*)a, bb = *(int*)b;
return aa > bb;
}
int main()
{
//freopen("in.txt", "r", stdin);
while(scanf("%d", &n) && n)
{
int i, k, j, u;
for(i = 0; i < n; i ++)
scanf("%d", &a[i]);
qsort(a, n, sizeof(int), comp);
wi = 536870912;
if(n < 4)
goto out;
//o(n^3 * logn)
for(i = n - 1; i >= 0; i --)
{
for(k = n - 1; k >= 0; k --)
{
if......