博文
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 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 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 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] ++;
}
......
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 &&am......