博文
Zju 1425 Crossed Matchings(2006-08-21 15:49:00)
摘要：
2035433
2006-08-21 15:25:00
Accepted
1425
C++
00:00.01
432K
St.Crux
这是一道典型的dp题。ZC的解题报告告诉我.......
自己看吧。辛辛苦苦写了15分钟的我的解题报告被Maxthon的鼠标手势给毁了，我真倒霉。
我的算法更加保险，也可以理解为更加笨拙。有一点不明白的地方是为什么他可以用该杀的贪心？这怎么可以用贪心？呜......我就等于O(n^4)了。
#include <cstdio>
#include <string>
int n, an, bn, a[101], b[101], r[101][101];
void dp()
{
int i, k, mx, j, u;
memset(r, 0, sizeof(r));
for(i = 1; i <= an; i ++)
{
for(k = 1; k <= bn; k ++)
{
mx = 0;
if(a[i] != b[k])
{
for(j = i - 1; j > 0; j --)
{
if(a[j] == b[k])
{
for(u = k - 1; u > 0; u --)
{
if(b[u] == a[i])
{<......
Zju 1103 Hike on a Graph(2006-08-16 19:28:00)
摘要：
2025283
2006-08-16 19:12:19
Accepted
1103
C++
00:00.07
1544K
St.Crux
这个题其实不难。可是我用了半个下午的时间研究如何dp......这件事告诉我一个深刻的道理......下次用一个小时研究就可以了。
好吧，这个题还是有写头滴，幸好queue让我简便了不少。还有一开始看错题意，每一枚棋子是不能同时移动的。
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
class pt
{
public:
int i, k, j, c;
};
queue<pt> pq, tq, ttq;
int n, p1, p2, p3, b[50][50][50], ans;
char a[50][50];
void init()
{
p1 --, p2 --, p3 --;
memset(b, 0, sizeof(b));
ans = -1;
pq = tq;
b[p1][p2][p3] = 1;
pt tpt;
tpt.i = p1, tpt.k = p2, tpt.j = p3, tpt.c = 0;
pq.push(tpt);
}
void bfs()
{
while(!pq.empty())
{
//pb();
pt tpt, ttpt;
int i, k, j;
tpt = pq.front();
if(tpt.i == tpt.k && tpt.k == tpt.j)
{
&nb......
Zju 1092 Arbitrage(2006-08-14 23:33:00)
摘要：
2021578
2006-08-14 23:10:47
Accepted
1092
C++
00:00.37
856K
St.Crux
输出的时候犯了一个小错误："Yes"当作“YES”了。
这个题是很基础的最短路径题，不限次数倒买倒卖，求能否过一定的收益率（这里为1）。我记得uva上有一个题是问在t次交换内能否达到一定的汇率......那样似乎还要记录路径了......上次学校里搞选拔赛的时候做过，做不出。现在还是做不出 TAT
另，memset(a, 0, sizeof(a))对double数组无效。但可以写memset(a, 0x00, sizeof(a))
#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <map>
using namespace std;
double a[30][30];
map<string, int> sm, dm;
int n, c = 0, ac;
int main()
{
//ifstream cin("in.txt");
while(cin >> n && n)
{
sm = dm;
int i, k, t, j;
for(i = 0; i < n; i ++)
{
string s;
cin >> s;
sm[s] = i;
for(k = 0; k < n; k ++)
{
a[i][k] = 0; //清零
&n......
Zju 1027 Human Gene Functions(2006-08-14 18:05:00)
摘要：
2021057
2006-08-14 17:39:09
Accepted
1027
C++
00:00.01
428K
St.Crux
两个字符串si和sk，每个字符匹配都有一个权值，要求他们的最大匹配权值。
很久以前在论坛上看过介绍，说和求最长子序列十分类似，因此很快就联想到了dp:)
事实上，这个题和LCS......确实很相似。同样是用一个二维数组来表示si的前i个数与sk的前k个数（字符）匹配的最大值，同样在f(n, m)处得解。不同的是LCs求的是最大长度，而这个求的是最大值。
所以用从下向上递推的思想分析。比如si＝AT，sk＝TA。当A和T匹配后，显然有一种情况：f(2, 2) = f(1,1) + a[2][2]； 那么移一位如何？即把si的T移动到TA的后面，使A和TA匹配，得f(2, 2) = f(1, 2) + T与-的匹配值。同理可得其他情况，在这些情况中取最大值即可。
#include <cstdio>
#include <string>
int a[5][5] = { {5, -1, -2, -1, -3}, {-1, 5, -2, -3, -4}, {-2, -3, 5, -2, -2},
{-1, -2, -2, 5, -1}, {-3, -4, -2, -1, 0} }, b[101][101], s0[101], s1[101];
int n, m, t, ans;
int mx(int a, int b, int c)
{
if(a >= b && a >= c)
return a;
if(b >= a && b >= c)
return b;
if(c >= a && c >= b)
return c;
else
return -99999999;
}
void read()
{
char tc; int k;
sca......
Zju 1082 Stockbroker Grapevine(2006-08-12 20:45:00)
摘要：
2017811
2006-08-12 20:23:54
Accepted
1082
C++
00:00.00
428K
St.Crux
最短路径的前提就是i点到k点能够访问。反之就是访问不能。
W.Floyd把j放在外面，i，k放在循环里面。我曾经错误的认为i和k是应该在外层循环，结果造成了长期的心理错觉，以致于一遇见这样的题目就ac不能，进而对Floyd先生产生了强烈的怨念。但是Floyd有证明么？
#include <cstdio>
#include <string>
#define MX 1001
int a[100][100], n, m;
int main()
{
//freopen("in.txt", "r", stdin);
while(scanf("%d", &n) && n)
{
int i, k, j, ac = 1;
for(i = 0; i < n; i ++)
{
scanf("%d", &m);
for(k = 0; k < n; k ++)
{
a[i][k] = MX;
}
for(k = 0; k < m; k ++)
{
int ti, tn;
scanf("%d %d", &ti, &tn);
a[i][ti - 1] = tn;
}
}
//pa();
f......
Zju 1901 A Star not a Tree?(2006-08-10 21:37:00)
摘要：
2014083
2006-08-10 20:56:11
Accepted
1901
C++
00:00.06
516K
St.Crux
这个题如果用穷举则超时：总共10000*10000个点。因此考虑从中心点出发向四周扩散搜索。这还是上个学期做的题，一直wronganswer。
#include <cstdio>
#include <cmath>
int xi[100], yi[100];
int dir[8][2] = {{-1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 0}, {0, -1}, {1, -1}, {-1, 1}};
double min;
int n;
void dfs(int x, int y)
{
int i, k;
double tm = 0;
for(i = 0; i < n; i ++)
{
tm += sqrt((x - xi[i]) * (x - xi[i]) + (y - yi[i]) * (y - yi[i]));
}
if(tm < min)
{
min = tm;
for(k = 0; k < 8; k ++)
{
int xx = x + dir[k][0];
int yy = y + dir[k][1];
dfs(xx, yy);
}
}
else
return;
}
int main()
{
int i;
//freopen("in.txt", "r", stdin);
while(scanf("%d", &n) != EOF)
Zju 2109 FatMouse' Trade(2006-08-10 01:03:00)
摘要：
2012463
2006-08-10 00:50:36
Accepted
2109
C++
00:00.17
408K
St.Crux
菜题。最简单的排序＋贪婪就可以过。但是有一些陷阱。
是贡献了三次wa。我居然把忘了把调试部分注释掉—_—
#include <cstdio>
int n, m, a[1000], b[1000];
double r[1000];
void pt()
{
for(int i = 0; i < m; i ++)
{
printf("%d %d %0.3f\n", a[i], b[i], r[i]);
}
}
int main()
{
//freopen("in.txt", "r", stdin);
while(scanf("%d %d", &n, &m) && n != -1)
{
int i, k, j;
for(i = 0; i < m; i ++)
{
scanf("%d %d", &a[i], &b[i]);
if(b[i] == 0) r[i] = 99999999;
else
r[i] = double(a[i]) / double(b[i]);
}
//select sort
for(i = 0; i < m - 1; i ++)
{
double mx = r[i]; j = i;
for(k = i + 1; k < m; k ++)
&nbs......
Zju 1619 Present(2006-08-08 22:40:00)
摘要：
2009974
2006-08-08 22:21:50
Accepted
1619
C++
00:00.02
392K
St.Crux
首先要知道什么是错排。
清楚了以后这个题就是弱题。即求：
C（n，m）——n个数里取m个的组合数 × 剩下的（n－m）个数的错排数
注意n＝＝m的情况
#include <cstdio>
int m, n;
double a[101];
int main()
{
//freopen("in.txt", "r", stdin);
a[1] = 0, a[2] = 1;
int i;
for(i = 3; i < 101; i ++)
{
a[i] = (i - 1) * (a[i - 1] + a[i - 2]);
}
while(scanf("%d %d", &n, &m) != EOF)
{
double pb = 1;
if(n == m)
{
//pb *= a[n];
for(i = 1; i <= n; i ++)
{
pb /= double(i);
}
}
else
{
pb *= a[n - m];
for(i = 1; i <= m; i ++)
{
pb /= double(i);
}
f......
错排问题的递推解决(2006-08-08 22:35:00)
摘要：也谈“装错信封问题”
广东省江门一中 王 旭（ 529000 ）
颜书先生《“装错信封问题”的数学模型与求解》一文（见《数学通报》 2000 年第 6 期
p.35 ），给出了该经典问题的一个模型和求解公式：
编号为 1 ， 2 ，……， n 的 n
个元素排成一列，若每个元素所处位置的序号都与它的编号不同，则称这个排列为 n
个不同元素的一个错排。记 n 个不同元素的错排总数为 f(n) ，则
f(n) = n![1-1/1!+1/2!-1/3!+……+(-1)^n*1/n!]（ 1 ）
本文从另一角度对这个问题进行一点讨论。
1. 一个简单的递推公式
n 个不同元素的一个错排可由下述两个步骤完成：
第一步，“错排” 1 号元素（将 1 号元素排在第 2 至第 n 个位置之一），有 n - 1
种方法。
第二步，“错排”其余 n - 1 个元素，按如下顺序进行。视第一步的结果，若 1
号元素落在第 k 个位置，第二步就先把 k 号元素“错排”好， k
号元素的不同排法将导致两类不同的情况发生：（ 1 ） k 号元素排在第 1
个位置，留下的 n - 2 个元素在与它们的编号集相等的位置集上“错排”，有 f(n -2)
种方法；（ 2 ） k 号元素不排第 1 个位置，这时可将第 1 个位置“看成”第 k
个位置，于是形成（包括 k 号元素在内的） n - 1 个元素的“错排”，有 f(n - 1)
种方法。据加法原理，完成第二步共有 f(n - 2)+f(n - 1) 种方法。
根据乘法原理， n 个不同元素的错排种数
f(n) = (n-1)[f(n-2)+f(n-1)] (n>2) 。 （ 2 ） ......
Zju 1636 Evaluate Matrix Sum(2006-08-08 16:37:00)
摘要：
2008922
2006-08-08 16:20:43
Accepted
1636
C++
00:00.97
1368K
St.Crux
暴寒。。求子矩阵和。只做一个方向的优化的下场就是这样呀！
先存着，晚上再优化。......