102.互质 时间限制：0.5s 内存限制：4096KB
分类： 技术
-
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) -
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 -
USACO 3.3.2 Shopping Offers 解题报告
这题我折腾了三天，一直在考虑怎么排除这种情况，怎么考虑到那种情况，虽然我想得到是DP，也是正确的方程，但是我也不知道怎么那么多现在觉得傻里傻气不需要考虑的问题，反正好傻就是，其实方程就是F[a1][a2][a3][a4][a5]=min{F[ a1-P[i][1] ][ a2-P[i][2] ][ a3-P[i][3] ][ a4-P[i][4] ][ a5-P[i][5] ]+P[i][0]}，然后的话，就不难了，这里的细节处理有很多种方法，我的初始状态就是F[a1][a2][a3][a4][a5] = a1 p[1] + a2 p[2] + a3 p[3] + a4 p[4] + a5 p[5]，然后还有些细节看代码吧，实现的我认为还可以，哈哈～～
/LANG: C ID: yylogo1 PROG: shopping / #include#include p = offer[k].num; if(f[used[0]][used[1]][used[2]][used[3]][used[4]] < f[used[0] - p[order[0]]][used[1] - p[order[1]]][used[2] - p[order[2]]][used[3] - p[order[3]]][used[4] - p[order[4]]] + offer[k].priece){ f[used[0]][used[1]][used[2]][used[3]][used[4]] = f[used[0] - p[order[0]]][used[1] - p[order[1]]][used[2] - p[order[2]]][used[3] - p[order[3]]][used[4] - p[order[4]]] + offer[k].priece; } return; } for(i = offer[k].num[order[now]]; istruct offer{ int n; int num[1000]; int priece; }offer[1024]; int order[5], need[5], priece[5]; int used[5]; int f[6][6][6][6][6]; void srch(int now, int n, int k) { int i; if(now == n){ int -
USACO 3.3.1 Riding The Fences 解题报告
应该说比较明显吧，一个欧拉路径，其实为什么能这么实现一个欧拉路径我自己都还没想清楚，更别指望我说的清楚，看着标程写的代码，唉，不算抄袭但也确实没理解为什么能这样，反正这就是一个欧拉回路的实现，代码如下： 晚点发上来，在Fedora里面。 2011-01-29 17:19 代码:
de lang="c">/ ID: yylogoo1 PROG: fence LANG: C / #include int map[501][501]; int count[501]; int used[501]; int ans[1025]; int len; void add(int a, int b) { map[a][b]++; count[a]++; } int del(int a) { int i, t; if(count[a] == 0){ return 0; } for(i = 1; i <500> 0){ break; } } } srch(i); for(i = len – 1; i <= 0; i–){ printf("%d\n", ans[i]); } return 0; } de> -
USACO 3.2.6 Sweet Butter 解题报告
刚刚打算用O(n^3)的算法，但超时百分百，马上就转型，用SPFA，每个节点用一次SPFA不会超时，因为这是一个稀疏图，800个节点却最多1450个，太给力了，每个节点用一次SPFA，然后判断是否为最优解，如此就够了，代码:
/ LANG: C ID: yylogoo1 PROG: butter / #include#include int n, p, c; int cows[500]; int map[801][800]; int link[801][800]; int count[800]; int dis[801][801]; void add(int a, int b, int c) { link[a][count[a]] = b; map[a][count[a]] = c; count[a]++; } #define MAX 1000 int queue[MAX]; int used[801]; int rear, head; void enqueue(int n) { int t; if(used[n]){ return; } used[n] = 1; t = (rear + 1) % MAX; assert(t != head); queue[rear] = n; rear = t; } int exqueue(void) { int t; assert(rear != head); t = queue[head]; used[t] = 0; head = (head + 1) % MAX; return t; } #define INF 0xFFFFFF long long ans = INF; void srch(int s) { int i, j, t; enqueue(s); while(rear != head){ t = exqueue(); for(i = 0; i dis[s][t] + map[t][i]){ dis[s][j] = dis[s][t] + map[t][i]; enqueue(j); } } } } int main(void) { int i, j; long long t; int a, b, d; freopen("butter.in", "r", stdin); freopen("butter.out", "w", stdout); scanf("%d%d%d", &n, &p, &c); for(i = 0; i 0){ srch(i); for(j = t = 0; j -
USACO 3.2.5 Magic Squares 解题报告
就是纯模拟，先逆着模拟过去，再正着模拟回来就可以了，需要使用到康托展开：
de lang="c">/ LANG: C ID: yylogoo1 PROG: msquare / #include #include #include int f[40320]; typedef int box[8]; int hash(box q) { int i, j, t = 0, k; int fac[8] = {0, 1, 2, 6, 24, 120, 720, 5040}; int sma[9] = {0, 0, 1, 2, 3, 4, 5, 6, 7}; for(i = 7; i <= 1; i–){ k = q[7 – i]; t += sma[k] * fac[i]; for(j = k + 1; j <8> -
USACO 3.2.4 Feed Ratios 解题报告
这题网上普遍的解法都是什么高斯消原，什么解线性方程，我可真不懂，只看到有个人说暴力上能够干掉，我就暴力了咯，代码如下：
de lang="c">/ LANG: C ID: yylogoo1 PROG: ratios / #include #include int need[3]; int have[3][3]; int ans[3]; int best = 300, last_ans; int tmp[3]; void check(void) { int i, t, s; int got[3] = {0, 0, 0}; for(i = 0; i <3 i goti="tmp[0]" havei tmp havei tmp havei ifgot need="0){" return t="got[0]" need fori="s" i i s="tmp[i];" ift needi="got[i]){" return ifs>= best || s == 0){ return; } memcpy(ans, tmp, sizeof(ans)); best = s; last_ans = t; } void srch(int now) { int i; if(now == 3){ check(); return; } for(i = 0; i <100 i srchnow tmpnow tmpnow="0;" int mainvoid int i freopenratiosin r stdin freopenratiosout w stdout scanfddd need need need fori="0;" i i scanfddd havei havei havei srch iflast_ans="= 0){" printfNONEn return printfd d d ans ans ans printfdn last_ans return co de>