新零点

作者： yylogo

  • SGU 100 A+B 翻译 解答

    100. A+B

  • 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 struct 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 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]]; i

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

  • Fedora 删除旧内核

    由于Fedora更新升级非常的频繁， 所以， 非常有必要清除陈旧的内核，方法如下：

    1. 查看当前系统中已安装的内核相关包： [root@knityster ~]# rpm -qa | grep kernel kernel-headers-2.6.32.12-115.fc12.i686 kernel-firmware-2.6.32.12-115.fc12.noarch kernel-PAE-devel-2.6.32.11-99.fc12.i686 kernel-devel-2.6.32.12-115.fc12.i686 kernel-PAE-2.6.32.11-99.fc12.i686 kernel-PAE-devel-2.6.32.12-115.fc12.i686 kernel-PAE-2.6.32.12-115.fc12.i686 kernel-devel-2.6.32.11-99.fc12.i686 abrt-addon-kerneloops-1.0.9-2.fc12.i686
    2. 查看当前使用的内核：
    [root@knityster ~]# uname -r 2.6.32.12-115.fc12.i686.PAE

    3. 确定要删除的内核：
    这里为：kernel-PAE-2.6.32.11-99.fc12.i686
    4. 删除内核：
    [root@knityster ~]# yum remove kernel-PAE-2.6.32.11-99.fc12.i686

    说明：
    不推荐网上到处抄来抄去的，直接使用: rpm -e 的方法删除内核包， 而是使用 yum remove 进行删除，
    因为使用yum remove删除， yum 会自动移除 ： /boot/grub/menu.lst 中的相关启动项。

  • Vim 用户手册一二章主要内容

     

  • USACO 3.2.3 Spinning Wheels 解题报告

    转360次就一定会转回来，刚开始我还在想应该使用最小公倍数吧，后来想了想才发现用360就可以了，用最小公倍数麻烦的多，甚至可能还慢些！ 然后忽然发现比较麻烦的一个地方就是每个轮子有5个孔，不好放在循环里，不知道怎么弄，看了下别人的建议，发现我好傻，直接使用数组记录就可以了，:-)，每个空隙在数组中+1，最后等于5的就是。但是现在觉得可能这么也不好，因为如果出现了某一个轮胎上两个孔重叠不就可能出问题了，但是这个只出现在数据上，不合逻辑所以就没有这种数据吧，所以我AC了，但是这还是要考虑下，如果这样的话，还是是用数组，但是不用+1了，而是用二进制，每个轮胎的缝隙不+1而是把这个轮胎所在的那个位置1，不过其实都是多虑了，代码如下： de lang="c"> / LANG: C ID: yylogoo1 PROG: spin / #include #include int used[360]; struct ro{ int v; int count; struct bug{ int start, width; }bug[5]; }roll[5]; int check(void) { int i, j, k; struct bug t; for(i = 0; i <5 i forj="0;" j rollicount j t="roll[i].bug[j];" fork="0;" k="t.width;" k usedk tstart fori="0;" i i ifusedi>= 5){ return 1; } } memset(used, 0, sizeof(used)); return 0; } int main(void) { int i, j, k; struct bug t; freopen("spin.in", "r", stdin); freopen("spin.out", "w", stdout); for(i = 0; i <5 i scanfdd rolliv rollicount forj="0;" j rollicount j scanfdd rollibugjstart rollibugjwidth fori="0;" i i ifcheck break forj="0;" j j fork="0;" k rolljcount k rolljbugkstart="(roll[j].bug[k].start" rolljv ifi="= 360){" printfnonen return printfdn i return code>

  • USACO 3.2.2 Stringsobits 解题报告

    这题最开始，我是爆搜，从1向上递增地搜，没过，超时了；后来用深搜，直接搜位数小于等于l的，也超时了，实在没有办法了，到网上看了题解，天！好简单阿！ f[i][j]代表i位长的且1最多为j的二进制数的个数，那么就有一个DP方程，f[i][j] = f[i – 1][j] + f[i – 1][j – 1] 因为第i位要么是1要么是0，如果是0那个数就是f[i – 1][l]，如果是1就是f[i – 1][j – 1]。 之后，根据f[i][j]就可以确定输出了，从f[n][l]开始，如果m<=f[n – 1][l]，那么就0，否则就输出1，且l–, m -= f[n – 1][l] 代码如下： de lang="c"> / LANG: C ID: yylogoo1 PROG: kimbits / #include int f[32][32]; int main(void) { int i, j; int n, l; unsigned m; freopen("kimbits.in", "r", stdin); freopen("kimbits.out", "w", stdout); scanf("%d%d%u", &n, &l, &m); for(i = 0; i 0; i–){ if(m