分类： OI路程

这题我折腾了一个星期，真的好死心，一个多星期一直在查到底是哪里出了问题，从感觉上算法是没有错误的，而且能够拿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

这个题目我也不知道这算法叫什么，反正就是用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)

这题一开始确实会感觉很难，但是罗马数字的个位只有可能是{"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; }

这题的话，话说感觉就是一个暴力的枚举，没多余要考虑的，一方面对所有整数开始枚举，设当前枚举的是i，那么在用i和所有已知的海明码进行比较，海明距离大于等于D的话就成为一个新的海明码，一直枚举出N个海明码。 得出海明距离也很简单，就从第一个位开始，一个不同的就记录一下，我直接把8位都枚举一次，所以B这个数据对我却是没有用，代码如下： de lang="c">/ LANG: C ID: yylogoo1 PROG: hamming / #include int num[64]; int count = 0; int ham(int a, int b) { int c = 0 ; int i; for(i = 0; i <8 i ifa="(b" c a><= 1, b <<= 1; } return c; } int main(void) { int n, b, d; int i, j; freopen("hamming.in", "r", stdin); freopen("hamming.out", "w", stdout); scanf("%d%d%d", &n, &b, &d); for(i = 0; count != n; i++){ for(j = 0; j de>

咋一看，真是一个爆难的题目，但是仔细一想，其实也很简单，怎么个简单呢？对于每种食物来说，只有两种选择：吃或不吃，对吧，暴力枚举就是，只有2^15种方案，虽然数字还是非常大的，但是一秒钟的时限还是超不了，代码晚点发，在Linux下。 代码来了： / ID: yylogoo1 PROG: holstein LANG: C / #include #include int have[15][25]; int need[25]; int v, g; int got[25]; int used[15], ans[15]; int tot = 26, tmp; void check(void) { int i; if(tot tmp){ tot = tmp; memcpy(ans, used, sizeof(used)); }else if(tot == tmp){ for(i = 0; i ans[i]){ tot = tmp; memcpy(ans, used, sizeof(used)); return; }else if(used[i] <ans i return void srchint now int i check ifnow="= g){" return srchnow tmp usednow="1;" fori="0;" i v i goti="have[now][i];" srchnow tmp-- usednow="0;" fori="0;" i v i goti -="have[now][i];" int mainvoid int i j freopenholsteinin r stdin freopenholsteinout w stdout scanfd v fori="0;" i v i scanfd needi scanfd g fori="0;" i g i forj="0;" j v j scanfd haveij srch printfd tot fori="0;" i g i ifansi printf d i printfn return code>