博文
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]) { if(u && j && mx &......
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) { ans = tpt.c; break; } for(i = 0; i < n; i ++) { if(......
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; //清零 } } cin >> t; for(i = 0; i < t; i ++......
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; scanf("%d ", &n); for(k = 0; k < n; k ++) { &......
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(); for(j = 0; j < n; j ++) { for(i = 0; i < n; i ++) ......
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) { int x0 = 10000, x1 = 0, y0 = 10000, y1 = 0; for(i = 0; i < n; i ++) { ......
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 ++) { if(r[k] > mx) { j ......
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); } for(i = 1; i <= n - m; i ++) { pb /= double(i); }&nbs......
错排问题的递推解决(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
暴寒。。求子矩阵和。只做一个方向的优化的下场就是这样呀！
先存着，晚上再优化。......