博文
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; for(j = i; j <= k; j ++) { ......
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 ++) { scanf("%d", &b[i]);&nbs......
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]; } } di[j] = di[i]; di[i] = t0; ni[i] = ni[j]; ni[j] = t1; } ......
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 = 0, h = c - 1, mid = (l + h) / 2; while(l < h) ......
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 ++) { scanf("%d", &t); for(u =......
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; }}
void init(){ int i, k; memset(b, 0, sizeof(b)); b[0] = 1; for(i = 0; i < n; i ++)&nb......
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) { int i0 = i + 2 * c - 1; int i1 = i - 2 * c + ......
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, u; double p_p = 1.0000, s_p = 0.0000; if((n - 3) % 4 == 0) ......
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(i == k) continue; for(j = k - 1; j > 0; j --) &nbs......