新零点

分类： 技术

  • USACO 2.4.4 comehome 解题报告

    这一题其实很简单，只是有个陷阱，考验你们细心与否，就是两个牧场之间可能不只有一条路径，所以这里注意一下就不会出大问题，代码如下所示： de lang="c">/ LANG: C ID: yylogoo1 PROG: comehome / #include #define INF 0xFFFFFF int map[52][52]; int getnum(char c) { if(c <= ‘a’ && c map[i][k] + map[k][j]){ map[i][j] = map[i][k] + map[k][j]; } } } } for(i = 26; i <51 i ifmin> map[i][51]){ c = i – 26; min = map[i][51]; } } printf("%c %d\n", c + ‘A’, min); return 0; } de>

  • USACO 2.4.3 Cow Tours 解题报告

    这个题目涉及的算法真的好多好多，一下子还真摸不着头脑，但摸着没摸着都先听我说。 首先要把链接在一起的那些牧区之间的距离算出来（勾股定理），然后要把各个牧场的牧区标示出来（洪水填充），这样就能进行下一步了，再把各个节点之间的距离算出来，用floyd-warshall算法，O(n^3)的那个算法，然后，再把每个牧区在这个牧场距离最远的节点之间的距离算出来，再把每个牧场的直径算出来，这题目就大概出来了。 最后在循环两个牧区，如果是在一个牧场就退出循环，如果是在两个不同的牧场的话，那如果连接起来这个新的牧场的直径就有三种可能：a牧区所在的牧场的直径；b牧区所在的牧场的直径；a牧区在牧场中距离最远的距离加上b牧区在牧场中距离最远的距离再加上a，b之间的距离。 代码如下： / LANG: C ID: yylogoo1 PROG: cowtour / #include #include #define INF 1000000.0 int x[150], y[150]; double map[150][150]; int group[150]; int n; double getdis(int i, int j) { return sqrt((x[i] - x[j]) (x[i] - x[j]) + (y[i] - y[j]) (y[i] - y[j])); } void fool(int a, int k) { int i; if(group[a]){ return; } group[a] = k; for(i = 0; i b ? a : b; } int main(void) { int i, j, k; int ch; double max, t; freopen("cowtour.in", "r", stdin); freopen("cowtour.out", "w", stdout); scanf("%d\n", &n); for(i = 0; i map[i][k] + map[k][j]){ map[i][j] = map[i][k] + map[k][j]; } } } } for(i = 0; i

  • USACO 2.4.2 Overfencing 解题报告

    题目看了之后容易发现就是广搜，从两个入口对全图进行广搜，搜到最后一个所需要的路程就是答案，广搜实现一点儿也不难，我的实现感觉还是比较好的，用一个宏和一个函数实现这个功能，然后用数字代表前进的方向，0：北，1：南，2：西，3：东。 但这题难的地方我觉得是把图转化成数据和寻找入口，其实难也不难，只是希望实现的代码简单些。刚开始我想根据变量循环的位置来判断，但这种方法的弊端就是代码量太大，要好多好多的判断，难的写，就直接使用-和|（墙的标识。）来标记数据就可以了，发现这个实现很简单，但是麻烦的就是找入口，最后我还是用了好多代码。 最开始我是把图转化成为数组的值之后再在数组里寻找，这么实现的话可以，只是说代码要多好几行，就换了种方法，放到和读取数据的循环了（看不懂这些话就看代码吧。） 代码： de lang="c">/ LANG: C ID: yylogoo1 PROG: maze1 / #include #include #define UP 1 #define DOWN 2 #define LEFT 4 #define RIGHT 8 //为0和39都提供空间, 在程序处理中会方便些 int map[102][40]; int ways[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int queue[3800][2]; int mark[101][39]; int head, end; int w, h; void enqueue(int i, int j, int k) { if(mark[i][j]){ return; } queue[end][0] = i; queue[end][1] = j; mark[i][j] = k; end++; } void exqueue(int *a) { assert(head h || b <1 b> w){ return 0; } return 1; } int main(void) { int i, j; char ch; int t[2]; freopen("maze1.in", "r", stdin); freopen("maze1.out", "w", stdout); scanf("%d%d\n", &w, &h); for(i = 1; i <2>

  • USACO 2.4.1 The Tamworth Two 解题报告

    这题模拟的这个细节不用说把？就是俺顺序来，如果不知道的话看我的代码，这部分(deal函数)写的比较清楚，但是比较麻烦的问题是循环多久才结束呢？题目并没有说什么特殊条件那？呵呵，暗示的条件还是有的，在1010的牛和人在每个格子上最多就是4种方向吧?也就是说每个格子对每个人来说都有400种状态，那么400400就是所有的状态，如果在160000种情况都没有相遇的话那么一定是在死循环中间（即死追死跑。） 代码如下： de lang="c"> / LANG: C ID: yylogoo1 PROG: ttwo / #include int map[10][10]; int c[3], f[3]; int way[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; int check(int a, int b) { if(a <0 b a>= 10 || b <= 10 || !map[a][b]){ return 0; } return 1; } void deal(int k[3]) { int t[2]; t[0] = k[0] + way[k[2]][0]; t[1] = k[1] + way[k[2]][1]; if(check(t[0], t[1])){ k[0] = t[0]; k[1] = t[1]; }else{ k[2] = (k[2] + 1) % 4; } } int main(void) { int i, j; char ch; freopen("ttwo.in", "r", stdin); freopen("ttwo.out", "w", stdout); for(i = 0; i <10 i forj="0;" j j ch="getchar();" switchch case mapij="1;" break case C c="i;" c="j;" mapij="1;" break case F f="i;" f="j;" mapij="1;" break getchar fori="0;" i i ifc="= f[0]" c="= f[1]){" break dealc dealf printfdn i return code>

  • USACO 2.3.5 Controlling Companies 解题报告

    读取a公司控制b公司的股份c，再把这个股份加给所有控制a的公司上，如果可以产生控制一个公司的情况，那么就控制该公司，并且把其公司占有其他公司的所有股份都自己加一份，如果有可以控制的情况，那么继续控制。 代码如下： / LANG: C ID: yylogoo1 PROG: concom / #include #define MAX 101 int have[MAX][MAX], con[MAX][MAX]; void con(int a, int b) { int i; if(con[a][b]){ return; } con[a][b] = 1; for(i = 1; i 50){ con(a, i); } if(con[b][i]){ con(a, i); } } } void addcent(int a, int b, int c) { int i; for(i = 1; i 50){ con(i, b); } } } } void init(void) { int i; for(i = 1; i

  • USACO 2.3.4 Money Systems 解题报告

    这个题目就是一个无限背包的例子，没有任何的修改，没有任何的特殊化，直接把代码搬进去就是的： / LANG: C ID: yylogoo1 PROG: money / #include long long f[10000]; int main(void) { int i, j, t; int v, n; freopen("money.in", "r", stdin); freopen("money.out", "w", stdout); scanf("%d%d", &v, &n); f[0] = 1; for(i = 0; i <v i scanfd t forj="t;" j="n;" j fj="f[j" - t printflldn fn return code>

  • USACO 2.3.3 Zero Sum 解题报告

    这个题目刚看到谁都觉得简单，爆容易，但是仔细一想，怎么去组合数字？怎么去把符号和数字放在循环里？都是需要解决的问题，我刚开始使用的是全局变量保存那些数据，忽然发现用全局的数据太复杂了，有好多数据需要改变再还原，所以只能用局部变量，每个函数拥有一套独立的参数变量，这样及时修改了也影响不到别的函数（这里有一种操作系统的感觉，一个程序被多次执行，每个进程独立的空间）。 这题谈不上什么算法不算法的，就是纯粹的暴力循环，每种情况都考虑一次。唯一要说的就是这个srch的参数： 1.now就是枚举的标示量，表示这是第几层枚举了。 2.dea是前面一个的操作方式，比如1 2 3 4+5 6现在now = 5(指向数字中的6)了，那么dea就是代表加法。它用1，-1来表示加减法，非常的快速，不需要任何判断。 3.tmp就是用空格组合成的数字，又如上面一个例子，那么就tmp=5，如果再前进一层1 2 3 4+5 6 7，那么tmp=56。 4.总共的累加和，还没有包括tmp的值。 最开始dea=1，即要把累积的数加起来，如果是空格就把数累加进tmp，如果是加法或减法，就把tmp放进sum中，并且自己作为tmp，dea设置成为加法或减法(1,2)，然后继续循环。 / LANG: C ID: yylogoo1 PROG: zerosum / #include int sum; int tmp, n, dea; int used[9]; void output(void) { int i; printf("%d", 1); for(i = 1; i <n i switchusedi case printf break case printf break case - printf- break printfd i printfn void srchint now int dea int tmp int sum int t ifnow="= n){" sum="sum" dea tmp ifsum="= 0){" output return usednow="0;" srchnow dea tmp now sum sum="sum" dea tmp usednow="1;" srchnow now sum usednow="-1;" srchnow - now sum int mainvoid freopenzerosumin r stdin freopenzerosumout w stdout scanfd n srch return code>

  • USACO 2.3.2 Cow Pedigrees 解题报告

    这题我折腾了一个星期，真的好死心，一个多星期一直在查到底是哪里出了问题，从感觉上算法是没有错误的，而且能够拿90分，那问题到底出在哪里呢？这一题我反反复复得找，再看标程，对着看，终于昨晚上找到了，算法没有一点问题，实现上有问题，超过了int 的范围，所以数据就出现了错误，然后就OVER了。 题目的思路是这样的，f[i][j]代表i个节点构成j层的树的个数，那么dp方程就是f[i][j] = {2 f[k][j – 1] f[i – k – 1][l]}(l = 1….j – 2, k = 1..i – 2) {f[k][j – 1] f[i – k – 1][l]} (l == j – 1, k = 1…i – 2) 这个算法的优化： 其实不需要从1循环到n，或者什么的，因为树和题目的特殊性质，不需要完全枚举，比如说当i=7的时候就不可能构成一层的树，就没必要考虑，当i=7的时候至少是3层，怎么计算呢？当已知节点数，log2(i) + 1的是最少的层数，(i – 1) / 2 + 1 是最大的层数。 当已知层数i时，最少的节点数是i 2 – 1，每层都有两个，但第一层只有一个；最多为2^i – 1，所以时间的优化还可以。 代码实现如下: de lang="c">/ LANG: C ID: yylogoo1 PROG: nocows / #include #include #define MOD 9901 int f[200][100]; int table[101][202],N,K,c; int smalltrees[101][202]; int getend(int i) { // return i / 2 + 1; return (i << 1) + 1; } int getstart(int i) { return ((int)log2(i)) + 1; } int main(void) { int i, j, k, l, t; int n, m, lim, lim2; freopen("nocows.in", "r", stdin); freopen("nocows.out", "w", stdout); scanf("%d%d", &n, &m); f[1][1] = 1; for(i = 3; i

  • USACO 2.3.1 Longest Prefix 解题报告

    这个题目我也不知道这算法叫什么，反正就是用f[i]记录第i个字符能否到达，如果可以到达再把所有的元素一个个和i之后的进行比较，如果完全相同那么就把f中那个元素的长度加上i的值标记为1。 其实怎么说呢，就是有一个大的数组记录第i个是否能够有那些元素组成，如果可以就从这里再和所有的元素比较下，如果有相匹配的话就产生了一个更长的前缀，把它标记，然后再进行循环。 如果还是没有懂的话，那就看代码吧： / LANG: C ID: yylogoo1 PROG: prefix / #include #include char sub[200][11]; int count; char str[200001]; int len; int f[200001]; int main(void) { int i, j, k; int ans; freopen("prefix.in", "r", stdin); freopen("prefix.out", "w", stdout); while(scanf("%s", sub[count]) && sub[count][0] != '.'){ count++; } while(scanf("%s", &str[len]) == 1){ len += strlen(&str[len]); } f[0] = 1; / Misatck 1: 当答案是len时就会出问题 for(i = 0; i 20001的时候就可能会溢出了. for(k = 0; sub[j][k] != '\0'; k++){ / for(k = 0; sub[j][k] != '\0' && (i + k)

  • USACO 2.2.4 Party Lamps 解题报告

    初看到题目，十个有九个人想用暴力枚举又不知道何从下手吧，哈哈，其实你把这几种按钮的所有组合在一起尝试一下可以清晰地发现只有八种情况，而且只用保存前6位数字就够了，因为后面都是循环的，啥？看不懂这鬼解题报告？话说其实这题你看代码最直截了当： de lang="c">/ LANG: C ID: yylogoo1 PROG: lamps / #include int lamps[8][6] = { {0, 0, 0, 0, 0, 0}, //(<1>= 1){ add(0); add(2); add(5); } if(c <= 2){ add(1); add(4); add(6); add(7); } if(c <= 3){ add(3); } scanf("%d", &i); while(i != -1){ for(j = 0; j <8 j ifansj getj i="= 0){" ansj="0;" scanfd i scanfd i whilei="-1){" forj="0;" j j ifansj getj i="= 1){" ansj="0;" scanfd i fori="0;" i i ifansi k="0;" forj="1;" j="n;" j printfd geti j printfn ifk printfIMPOSSIBLEn return code>