新零点

分类： 算法

  • 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>

  • USACO 2.2.3 Runaround Numbers 解题报告

    这题首先是一个枚举，从输入的数加一开始每个数字都看是不是题目所要的数。判断方法如下： 先把数字用字符串保存起来，然后读取一个数字并且标记为’x’，再读取一个，判断是否为’x’，如果为x就不是要求的数字，如果不是就继续读取，直到每个数字都被读取了，并且最后指针回到了第一个位置，那么这就是所需要的那个数字。因该说清楚了吧，简单的说就是模拟一边，代码如下： de lang="c"> / LANG: C ID: yylogoo1 PROG: runround / #include #include int check(int n) { int len, i, j, t; int used[10]; char num[10]; memset(used, 0, sizeof(used)); sprintf(num, "%d", n); len = strlen(num); for(i = 0; i

  • USACO 2.2.2 Subset Sums 解题报告

    这一题是一个动态规划题，f[i][j]是i个数字（1, 2, 3, 4, .., i）能够组成和为i的个数，那么方程式是f[i][j] = {f[i – 1][j – k] + f[i – 1][j]} (1 <= k <= i)，再DP就是的，代码如下： / LANG: C ID: yylogoo1 PROG: subset / #include long long f[781]; int main(void) { int n, i, j, k; int max = 0; freopen("subset.in", "r", stdin); freopen("subset.out", "w", stdout); scanf("%d", &n); if(((n + 1) n / 2) & 1){ printf("0\n"); return 0; } f[0] = 1; for(i = 1; i = i; j--){ f[j] += f[j - i]; } } printf("%ld\n", f[(n + 1) n / 4] / 2); return 0; }

  • USACO 2.2.1 Preface Numbering 解题报告

    这题一开始确实会感觉很难，但是罗马数字的个位只有可能是{"I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}，同理，十位上的数字也永远都是固定的，所以还是简单吧，实现代码如下： / LANG: C ID: yylogoo1 PROG: preface / #include char num[4][10][5] = { {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}, {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}, {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}, {"", "M", "MM", "MMM"}}; int have[7]; void addnum(int n) { int i = 0; char s; while(n){ s = num[i][n % 10]; while(s != '\0'){ switch(*s){ case 'I': have[0]++; break; case 'V': have[1]++; break; case 'X': have[2]++; break; case 'L': have[3]++; break; case 'C': have[4]++; break; case 'D': have[5]++; break; case 'M': have[6]++; break; } s++; } i++; n /= 10; } } char st[7] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'}; int main(void) { int n; int i; freopen("preface.in", "r", stdin); freopen("preface.out", "w", stdout); scanf("%d", &n); for(i = 1; i 0){ printf("%c %d\n", st[i], have[i]); } } return 0; }