分类： OI路程

USACO 3.4.3 Electric Fence 解题报告

题目本质：相似三角形+枚举算法描述：题目给出的三角形比较特殊，所以可以直接枚举，当然也不能说是直接枚举咯。我的算法是，对于每一行进行枚举，但是很快就到瓶颈了，无法确定坐标，虽然能够画出相似三角形，因为三角形的一条边在x轴上，所以从y等于(-)1（看情况而定是1还是-1）至m，每一行做与x轴平行的线就有相似三角形了，但是只能确定长短，不能确定坐标，后来想了好阵子，才想到，用高来确定坐标，用两个三角形，(n, m)(n, 0)(0, 0)，(m, n)(n, 0)(p, 0)，分别可以把新坐标求出来，然后一个向上取整，一个向下取整，相减+1就可以了，接下来就是细节了。 Pay attention：y=0 不计算，x轴上所有的点都在线上，不符合要求；如果在某个y上，x1, x2(相似三角形求出的两个坐标), x1, x2为整数的话, 那么x1, x2连点都不能取。复杂度：这题不会分析，不知道什么是N。 de lang="c">/ LANG: C ID: yylogoo1 PROG: fence9 / #include #include #include $#define swap(a, b) do{\ int t;\ t = a;\ a = b;\ b = t;\ }while(0) int main(int argc, char$ argv[]) { int i; int x[2] = {0}; int a, b, k; int x1, x2; double t; int ans = 0; freopen("fence9.in", "r", stdin); freopen("fence9.out", "w", stdout); scanf("%d%d%d", &a, &b, &x[1]); if(x[0] < x[1]){ swap(x[0], x[1]); } k = b / abs(b); for(i = 1; i != b; i += k){ //向上取整 x1 = ceil(1.0 (b – i) / b (x[0] – a) + a); //自动向下取整 x2 = floor(1.0 (b – i) / b (x[1] – a) + a); ans += x2 – x1 + 1; t = 1.0 (b – i) / b (x[0] – a) + a; if(t <0 x t>= x1 – 0.00001){ ans–; } t = 1.0 (b – i) / b * (x[1] – a) + a; if(t <0 x t>= x1 – 0.00002){ ans–; } } printf("%d\n", ans); return 0; } de>

2011年2月15日
SGU 104 Little Shop of Flowers 解题

本　　质：动态规划算法描述：f[i][j] = max(f[i – 1][j – 1] + num[i][j], f[i][j – 1]) 　　　　　方程十分简单，但是我久久不能AC，看了别人的代码也没看懂为什么初始需要f[i][i] = f[i – 1][i – 1] + num[i][i] 　　　　　后来才想通，如果num[i][i]有一个负数，那就可能无解，所以要这么弄下，代码如下： de lang="c">#include #include int num[101][101]; int ans[101][101]; int g[101][101]; int a[100]; int end; int max(int a, int b) { return a < b ? a : b; } void output(int f, int v, int k) { int i; for(i = v; i <= 1; i–){ if(ans[f][i – 1] != k){ break; } } if(f == 1){ printf("%d", i); return; } output(f – 1, i – 1, ans[f][i] – num[f][i]); printf(" %d", i); } int main(int argc, char *argv[]) { int i, j; int f, v; // freopen("tmp", "r", stdin); scanf("%d%d", &f, &v); for(i = 1; i

2011年2月14日
USACO 3.4.2 American Heritage 解题报告

算法本质：树的遍历性质和深搜算　　法：先从中序遍历找出哪一个是根，即在先序遍历中下标最小的那个节点，这个节点向左就是左子树，向右就是右子树。复杂度：空间&时间O(n) / LANG:C ID: yylgoo1 PROG: heritage / #include #include #include #define INF 0x7FFFFFFF char a[27], b[27]; int or[26]; void srch(int start, int end) { int i; int mid = -1, min = INF; if(start < end){ return; } for(i = start; i or[a[i] - 'A']){ min = or[a[i] - 'A']; mid = i; } } srch(start, mid - 1); srch(mid + 1, end); printf("%c", a[mid]); } int main(void) { int i, len; freopen("heritage.in", "r", stdin); freopen("heritage.out", "w", stdout); scanf("%s%s", a, b); len = strlen(a); for(i = 0; i <len i orbi - A="i;" srch len - printfn return code>
2011年2月12日
SGU 103 Traffic Lights 解题报告算法本质：单源最短路径+简单变形算　　法：就是单源最短路径，我使用的SPFA，但是和普通单源最短路径不同的是，这个需要把路上所消耗的时间加上等待两边的灯同时亮起的时间这样唯一要耽误点时间实现的就是计算等待的时间。计算在时间k通过a,b两个路口所需要等待的时间算法如下，如果此时（k）a，b路口的路灯是相同的话那么等待时间为0，如果不同那么就是a路口灯光变色的时间和b路口灯光变色的时间二者的最小时间，但是如果二者相同的话，那么就继续循环，此时k就等于a（或者b）路口灯光变色的时间。复杂度：时间&空间：O(N^2) de lang="C">#include #include #include #define MAX 300 / 添加这些注释 / #define INF 0x7FFFFFFF struct node{ int color, wait; int wait_1, wait_2; }node[301]; int map[301][300]; int link[301][300]; int count[301]; int queue[300]; int used[301], from[301]; int head, rear; int dist[301]; int min(int a, int b) { return a c + map[a][i]){ dist[b] = c + map[a][i]; from[b] = a; enqueue(b); } } } if(dist[end] == INF){ printf("0\n"); return 0; } printf("%d\n", dist[end]); output(start, end); printf("\n"); return 0; } de> 2011年2月8日
USACO 3.3.5 A Game 解题报告本质：动态规划算法：f[i][j]代表从(i, j)能取的最大值，sum[i][j]代表它们的总和 f[i][j] = sum[i][j] – min(f[i + 1][j], f[i][j – 1]); 复杂度：时间&空间：O(N^2) de lang="c">/ LANG: C ID: yylogoo1 PROG: game1 / #include int sum[100][100]; int f[100][100]; int min(int a, int b) { return a 2011年2月4日
SGU 102 Coprimes 翻译题解 102.互质时间限制：0.5s 内存限制：4096KB 2011年2月3日
USACO 3.3.4 Home on the Range 解题报告题目本质：DP 算法：这题怎么说吧，我是想了好久没想出来，看了下别人的提示，天啊~好简单，DP方程如下： f[i][j]代表以i,j为左上角的正方形的边长大小，那么f[i][j] = min(f[i][j], f[i + 1][j], f[i][j + 1], f[i + 1][j + 1]) + 1; 你说简单不简单，这代码很快就出来了，如下：复杂度：时间空间我都不会分析。。。 =====================================华丽的分割线===================================== 代码等下发上来，在Fedora里，2011-02-03 10:23 de lang="c">/ LANG: C ID: yylogoo1 PROG: range / #include #define min(a, b) ((a) 2011年2月3日
USACO 3.3.3 Camelot 解题报告题目本质：模拟+枚举算　　法：首先，将国王与每个点的所需要的步数枚举出来，然后再对每个其实分别枚举，枚举每个点的步数，如：dist[i][j][0]代表将当前这个骑士移动到i,j所需要的步数，dist[i][j][1]代表当前这个其实和国王相聚在i,j总共的步数（包括国王走的步数。），dist[i][j][1] – dist[i][j][0]是国王和当前这个骑士在i,j相聚国王要走的步数。还有一个数组cost[i][j]代表把集结点设在i,j所有骑士总共要走的步数，kdist[i][j]代表国王移动到这点上所要走的步数，可以是直接走到的，也可以是0，代表国王就在i,j或者被骑士带到i,j去，国王不需要走路，也可以是先走几步再让骑士带着走。复杂度：时间：不太会分析，大概是O(n^3)吧。空间：O(n) ============================华丽的分割线============================ de lang="c">/ LANG: C ID: yylogoo1 PROG: camelot / #include #define LINE 30 #define ROW 26 #define INF 0xFFFFFFF; int m, n; int kdist[ROW][LINE]; int kcost[ROW][LINE]; int dist[ROW][LINE][2]; int cost[ROW][LINE]; #define LEAP_MAX 500 struct dot{ int d; }leap[LEAP_MAX]; int tail; #define parent(i) ((i – 1) << 1) #define left(i) ((i <1 define righti i define maxa b a>(b)?(a):(b)) #define min(a, b) ((a) 0; i = parent(i)){ if(leap[parent(i)].d = n || y <= m){ return 0; } return 1; } #define deal_detail(a, b) do{\ if(check(a, b) && dist[a][b][k] < dist[x][y][k] + 1){\ dist[a][b][k] = dist[x][y][k] + 1;\ enqueue(dist[x][y][k] + 1);\ }\ }while(0) int deal_knight(int x, int y, int k) { int f = 0; deal_detail(x – 2, y + 1); deal_detail(x – 2, y – 1); deal_detail(x – 1, y + 2); deal_detail(x – 1, y – 2); deal_detail(x + 2, y + 1); deal_detail(x + 2, y – 1); deal_detail(x + 1, y + 2); deal_detail(x + 1, y – 2); if(k == 0 && dist[x][y][1] < dist[x][y][0] + kdist[x][y]){ dist[x][y][1] = dist[x][y][0] + kdist[x][y]; enqueue(dist[x][y][0] + kdist[x][y]); } } void srch(int x, int y) { int i, j, d; for(i = 0; i 2011年2月1日
SGU 101 Domino 翻译解答 101. 多米诺 2011年1月31日
SGU 100 A+B 翻译解答 100. A+B 2011年1月31日