博文
Zju 1638 Greedy Island(2007-01-24 13:43:00)
摘要：以下是xavier_lt的解题报告。稍微分析一下，不难发现O(nabc)的DP方程：f[0,0,0]=0;f[i,j,k]=max{ f[i-1,j,k] + attack[i+j+k], f[i,j-1,k] + defence[i+j+k], f[i,j,k-1] + special[i+j+k] }这样，求总的属性值只要加一个第二关键字c[i,j,k]就可以了。但是通过题目，发现N是一个很大的数，于是用这种方法将会非常慢!但是，很显然有一些牌是可以完全忽略掉的，就像[0,0,0]这样的牌。要怎么删掉一定不需要的牌呢？令S=a+b+c，则对于每种属性，只需要前S张即可了，而总计只需要3S<=300张牌。这样优化后，算法的速度就会大大的提高了，优化后的时间复杂度是O(nlgn+min(n,3s)*a*b*c)。-------------------------------------------------------------------我只看的懂这些了。但是这个办法真的很经典，一道难题就这样变成了O(1004)的简单题。-------------------------------------------------------------------进一步分析，此题的总属性值不会超过300*100，个体属性值不会超过100*100，所以，可以建立一个二分图来解决此题。令左边为N个红节点（攻击属性），N个黄节点（防御属性），N个蓝节点（特殊属性），右边是A+B+C个节点，第I个红节点到第J个右节点的边权为Attack[I]*100000+Attack[I]+Defence[I]+Special[I]，同理建立其他颜色的左节点到每个右节点的边。这样我们只需对这个二分图求最大全匹配就可以了，复杂度将会下降到O(nlgn+min(n,3s)*(a+b+c)^2)，优化后的时间还是很不错的^_^。
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
#define S 102
#define SS 100001
int opt[S][S][S], sum[S][S][S], n, a[SS],......
Zju 1004 Anagrams by Stack(2007-01-23 20:57:00)
摘要：挺早的时候写的。那个时候还不知道C的读入效率比C++高，用的还是vector。
/* source: zju 1004 */
/* algo: dfs */
/* date: 2006/5/17 */
/* author: Crux.D */
#include <iostream>
#include <fstream>
#include <string>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
string str0, str1;
stack<char> cs;
vector<char> cv;
int l;
void prints()
{
for(int i = 0; i < cv.size(); i ++)
{
cout << cv[i] << " ";
}
cout << endl;
}
void dfs(int ii, int oi)
{
if(ii == l && oi == l)
prints();
if(ii + 1 <= l)
{
cs.push(str0[ii]);
cv.push_back......
Zju 1349 Four Quarters(2007-01-23 15:07:00)
摘要：A分布
Player B
Player A
HH
HT
TT
HH
1
1
2
HT
0
0
1
TT
-1
0
0
B分布
Player B
Player A
HH
HT
TT
HH
0
-1
-1
HT
1
0
0
TT
2
0
-1
A和B在此分布下进行20轮累计，求每轮分数的胜负概率。第一次做的时候以为A和B是独立的，分别计算他们得分的概率，再计算大小，结果第一轮的数据就卡住。然后想到了一个取巧的办法，把A和B的得分相减，得到一个新的分布，最后判断总分是否大于0。
随便说一句，我的代码风格向软件工程的标准又迈进了一步，这是人类的一小步，却是我的一大步。
#include <cstdio>
#include <string>
#define def 100
double p[7], s[2][200];
int mx, mn;
void ps (int c)
{
int i;
double sum_w, sum_l, sum_t;
sum_w = sum_l = sum_t = 0;
for ( i = mn - 3; i <= mx + 3; i ++ )
{
if ( i > def )
sum_w += s[0][i];
if ( i < def )
sum_l += s[0][i];
if ( i == def )
sum_t += s[0][i];
}
printf ( "%5d%10.4f%%%9.......
Zju 1642 Match for Bonus(2007-01-23 00:04:00)
摘要： 这是一题典型的最大公共子序列。一开始没看出来，直到写dp写不下去，赶紧去翻busycai大牛的程序才恍然大悟。
用f[i][k]表示a取到i，b取到k时最大的权值。f[i][k] = max (f[i - 1][k - 1] + v[i], f[i][k - 1], f[i - 1][k])。其中第一个表示i和k时取到相同的字符。
#include <cstdio>
#include <string>
int v[501], n, ans, f[2001][2001], len;
char str[2][2001];
int dp ()
{
int i, k;
len = strlen (str[0]);
memset (f, 0, sizeof(f));
for (i = 1; i <= len; i ++)
{
for (k = 1; k <= len; k ++)
{
if (str[0][i - 1] == str[1][k - 1])
{
f[i][k] = f[i - 1][k - 1] + v[str[0][i - 1]];
}
int mx = f[i - 1][k] > f[i][k - 1] ? f[i - 1][k] : f[i][k - 1];
if (mx > f[i][k]) f[i][k] = mx;
}
}
return f[len][len];
}
int main ()
{
//freopen ("in.txt", "r", stdin);......
Zju 1387 Decoding Morse Sequences(2007-01-21 21:43:00)
摘要： 老实的说，我对自己解出这道题并不抱很大的希望——不比今天上午的考试及格的概率大。众所周知，今天是研究生入学考试的第二天，上午这门是最头疼的数学，高考那年的数学就特别难……当然这和我的人品没有半点联系。
幸好我对这门课的期望值相当的低。每次我很低调地打出我的数学宣言，周围总是用看野生大熊猫的目光看着我。本来这种行为相当低调，当重复了一百遍以后就变成了高调。所以我的希望是数学要么就考中考卷——我中考很不谦虚地拿了全市第一，但是我怕让我现在去考也会落榜；要么就越难越好，要死一起死。
我的祈祷果然生效了。当我做到大题第二题的时候，我还信心满满，想象着浙大的幸福生活。
要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎。
我低声告诫自己，一边翻开第三题。不会做——不要紧。第四题，做不来。还有四题。我向来保持革命乐观的精神，这是江总的教导。
当我把整张试卷全部翻阅一遍，突然发现自己能做的不过区区七、八十分时，革命精神立刻被轰到片·甲·不·留。呜呜呜，我要回家找妈妈。
当然，这同样和我的人品没有任何联系。我现在只希望两件事。
一、数学分数线被轰到最低。
二、让——我——过——线。
罗里八索地扯了一大堆。正题只写两句话 = =
1.把字典里的char*变成莫尔码。
2.对要求的morse码dp。
#include <cstdio>
#include <string>
char tran[26][5] = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..",
&n......
Zju 1893 A Multiplication Game(2007-01-01 19:43:00)
摘要：
2187944
2007-01-01 19:14:20
Accepted
1893
C++
00:00.00
388K
Crux.D
这题好X难。
题目大概意思是：两人轮流乘一个2－9的数，从1开始乘，求谁的乘积先大于N。
如果是加法就好做了。凑到剩下的数能整除11，然后对称着加。问题是乘法。
所以寻找必胜点（段）。以1000为例。
1000 | 999 ... 112 | 若占住999到112，则对手必胜。必须让对手占领此段。
1000 | 999 ... 112 | 111 ... 56 | 因此必占段是 111 －? 。如果56被对手占住，则56×2＝112，入必败段。问题转化成为占56。
如此循环。如下 1000 | 999 ... 112 | 111 ... 56 | 55 ... 7 | 6 ... 4 | 3 ... 1
仔细考虑端点，我在处理端点情况时想了好久。
这是牛人的代码。
#include <stdio.h>
unsigned int N;
bool StanWins ()
{
// printf ( "%u\n" , N );
if ( N == 1 ) return true;
int step;
for ( step = 1; N > 1; step ++ )
if ( step & 1 ) N = ( N - 1 ) / 9 + 1;
else N = ( N + 1 ) / 2;
return ( step &a......
Zju 1200 Mining(2006-12-23 15:54:00)
摘要：
2178592
2006-12-23 15:29:25
Accepted
1200
C++
00:00.00
428K
Crux.D
堆维护。这个模拟题根本没有思路，看了论坛上AndyZh的算法才明白的。
把每个机器人到达矿区的时间排序，从中选出最小时间，然后更新此时间，重排堆。
（最小）堆排的算法是：与下面子节点中较小的节点比较，大则交换，小则停止。
#include <cstdio>
int s, w, c, l, m, h[10000], t, ans;
bool init()
{
if (scanf("%d", &s) == EOF) return false;
scanf("%d %d %d %d", &w, &c, &l, &m);
int i;
ans = 0, t = 9999 / c + 1;
if(l > t) l = t;
for(i = 0; i < t; i ++)
h[i] = m * i + m + s;
return true;
}
void push()
{
int cur = 0, j = h[0], next = cur * 2 + 1;; // h[0] min
if(ans < h[0]) ans = h[0];
h[cur] += s + s + w; ans += w;
// heap-lize
while(next < l)
{
if(next + 1 < l && h[next] > h[next + 1]) next ++;
if(j > h[next])
&n......
Zju 1163 The Staircases(2006-12-18 23:19:00)
摘要：
2174729
2006-12-18 23:13:20
Accepted
1163
C++
00:00.02
2384K
Crux.D
很好的一道dp题，积压已久。这让我想起小学生时代的作文了：
“今天我又做了一件好事，我真高兴呀。”
这道题的陷阱是大数，用double即可避过。方程是b[i][k] = b[i - k][k - 1]，i代表N，k代表最高层的块数。然后把b[i][k]累加起来就可。
另外这题只用了23行，和今天做的另一道题1111比起来，简直是他喵的奇迹。那道题整整花了我半个下午，调试了3次，写了400多行……
#include <cstdio>
#include <string>
double a[505][505];
int main()
{
int i, k, n;
memset(a, 0x00, sizeof(a));
a[0][0] = 1;
for(i = 0; i < 505; i ++)
{
for(k = 1; k <= i; k ++)
a[i][k] = a[i - k][k - 1] + a[i][k - 1];
for(k = i + 1; k < 505; k ++)
a[i][k] = a[i][i];
}
while(scanf("%d", &n) && n)
{
printf("%0.0f\n", a[n][n] - 1);
}
return 0;
}
----------------------------
对比的程序，zju 1111
#include <......
Zju 1097 Code the Tree(2006-12-17 23:23:00)
摘要：
2173944
2006-12-17 23:15:34
Accepted
1097
C++
00:00.02
876K
Crux.D
烦题，输入巨无聊。如果不想自己写的话参考一下吧。
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
string s;
int a[51][51], b[51], c[51], si, mx;
int node()
{
int t = 0;
while(s[si] >= '0' && s[si] <= '9')
{
t *= 10;
t += s[si ++] - '0';
}
return t;
}
void build(int n)
{
int t;
if(n > mx) mx = n;
while(s[si] == '(')
{
si ++;
t = node();
if(n)
{
b[n] ++;
b[t] ++;
a[t][n] = 1;
a[n][t] = 1;
}
build(t);
si ++;
}
}
void init()
{
si = 0, mx = 0;
memset(b, 0, sizeof(b));
memset(a, 0,......
Zju 1508 Intervals(2006-12-15 14:22:00)
摘要： 差分约束的入门题。比2770稍复杂，需要稍微转化一下。
设S[i]是前i个数中选出的个数，则ai到bi的个数即S[bi] - S[ai-1]。因此有S[bi] - S[ai-1] >= ci。另外有S[i] - s[i - 1] >= 0 && S[i] - S[i - 1] <= 1，故建图。
使图中每一组uv，满足
S[ai - 1] <= S[bi] + ci
S[i] <= S[i - 1] + 1
S[i - 1] <= S[i]
当不满足时，更新即可。
tips：因为此题必有解（题给出），因此bellmanford只需更新至全部满足即可。
#include <cstdio>
#include <string>
#define inf 99999
struct Edge
{
int u, v, w;
} edge[50001];
int n, a[50001], mn, mx;
void init()
{
int i;
for(i = 0; i < 50001; i ++)
a[i] = 0;
mx = 1, a[0] = 0, mn = inf;
}
bool bellman_ford()
{
int i, t, f = 1;
// pa();
// must satisfy following aspects:
// s[v] <= s[u] - w
// s[i] <= s[i - 1] + 1
// s[i - 1] <= s[i]
while(f)
{
f = 0;
for(i = 0; i &l......