博文
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 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 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 2180 City Game(2006-07-28 22:15:00)
摘要：事实上和1985一摸一样。
#include <cstdio>#include <string>
/* state: 0.34s, 404kb */
int n, a, b;int m[1000], r[1000], l[1000];
void pm(){ for(int i = 0; i < b; i ++) { printf("%d ", m[i]); } printf("\n");}
int main(){ //freopen("in.txt", "r", stdin); int i, k, j; scanf("%d", &n); for(i = 0; i < n; i ++) { memset(m, 0, sizeof(m)); scanf("%d %d ", &a, &b); //pm(); int max = 0; //dp(n^2......) for(k = 0; k < a; k ++) { for(j = 0; j < b; j ++) { char tc; scanf("%c ", &tc); if(tc == 'R') m[j] = 0; else m[j] ++; } //pm(); for(j = 0; j < b; j ++) { l[j] = j;&nb......
Zju 1985 Largest Rectangle in a Histogra(2006-07-27 00:11:00)
摘要：tle了我几个月.......谢谢cqf大牛的算法。
//State: 0.22s 1512kb
//用l,r两个数组保存当前元素向左向右访问能够达到的最大下标，因此可用dp
//另：此题甚bt，数据量大的惊人，而且有陷阱，必须用scanf。我用cin的时候起码读了10s.........
#include <cstdio>
int a[100000], l[100000], r[100000], n;
int main(){ freopen("in.txt", "r", stdin); while(scanf("%d", &n) && n) { int i; double max = 0.00; for(i = 0; i < n; i ++) { scanf("%d", &a[i]); } for(i = 0; i < n; i ++) { l[i] = i; while(l[i] > 0 && a[i] <= a[l[i] - 1]) { l[i] = l[l[i] - 1]; } } //pl(); for(i = n - 1; i >= 0; i --) { r[i] = i; while(r[i] < n - 1 && a[i] <= a[r[i] + 1]) { r[i] = r[r[i] + 1];&nbs......