新零点

博客

  • tyvj 1003 越野跑

    　　咋一看去感觉是一个很复杂的题目，不过仔细一想，可以以最坏时间O(n)来完成，因为来回一趟的路线是固定的——去一次，回一次，如果是平地的话需要的时间总量就是2f, 无论是上坡还是下坡, 来去一趟的时间都是u+d，所以就没什么考虑的了，输入一个就把要花的时间加上，判断下是否大于u，是就退出循环，不是就继续循环。。
    　　代码如下：

  • NOIP 2003 神经网络 解体报告

    　　其实这个题目很简单, 你们仔细想想,最像什么? 很多讨论图论第一个讨论得就是这个问题——拓扑排序, 不是吗? 几乎不用我提示了吧? 这里还有一个要注意的地方就是, 一个神经输入节点的u[i] > 0时也不回影响c[i]. 比如c[i] = 2, u[i]=100, 那么这个输入节点的c[i] 依然是2而不是-98。
    　　要说得救是这些, 代码如下:

    #include <stdio.h>
    #include <assert.h>
    #define MAX 200
    int c[200], u[200];

    int queue[MAX];
    int head, rear;

    void enqueue(int k)
    {
            queue[rear++] = k;
    }

    int exqueue(void)
    {
            return queue[head++];
    }

    int map[200][200];
    int link[200][200];
    int in[200], out[200];

    void add(int a, int b, int d)
    {
            link[a][out[a]] = b;
            map[a][out[a]] = d;
            out[a]++, in[b]++;
    }

    int main(void)
    {
            int a, b, d;
            int n, p;
            int i, j;
            scanf("%d%d", &n, &p);
            for(i = 0; i < n; i++){
                    scanf("%d%d", &c[i], &u[i]);
                    /
                    Mistack 1:
                        把下面的c[i] > 0 写成了c[i] == 0
                        /
                    if(c[i] > 0){
                            enqueue(i);
                    }
                    /
                    Mistack 3:
                        作为输入神经, 无论u为多少, c都应该是固定的!
                        /
                    if(c[i] == 0){
                            c[i] -= u[i];
                    }
            }
            for(i = 0; i < p; i++){
                    scanf("%d%d%d", &a, &b, &d);
                    a–, b–;
                    add(a, b, d);
            }

            while(head != rear){
                    a = exqueue();
                    if(c[a] > 0){
                            for(i = 0; i < out[a]; i++){
                                    b = link[a][i];
                                    c[b] += map[a][i] c[a];
                                    in[b]–;
                                    assert(in[b] >= 0);
                                    if(in[b] == 0){
                                            enqueue(b);
                                    }
                            }
                    }
            }
            /
            Mistack 2:
            　　当都为0时要输出NULL
            */
            d = 1;
            for(i = 0; i < n; i++){
                    if(out[i] == 0 && c[i] > 0){
                            printf("%d %d\n", i + 1, c[i]);
                            d = 0;
                    }
            }
            if(d){
                    printf("NULL\n");
            }
            return 0;
    }

  • 我的WordPress开张了

    　　163的博客实在是不太好用, 在千辛万苦之下, 成功自己搭建一个LAMP(Linux Apache MySQL PHP), 这是传统地说法, 要我说应该是LAMPW, 因为我是用的是WordPress. 在报废了3个Linux系统之后, 第四个Fedora 14成功的将Apache MySQL PHP 都安装成功, 并且将WordPress给装好了, 只是这个机子(Fedora 14)的配置不怎么样(CPU: AMD 3200+, 　　内存: 512M, 硬盘:80G), 网络也不怎么样, 2MB的, 接了6台电脑, 不过暂时用着还是不错,, 这几天想办法把163的博客搬过来..

    　　记得我把AMP半个小时就在Windows下装好了, Linux咋这么麻烦呢? 技术要求高些啊~~我要学得还很多很多..

    　　经过几次的失败, 我也有了不少经验了, 哈哈, Linux的经验就是这么慢慢来的. 不过要说的话, 从编译的方式我还弄不好LAMP, 是直接使用的yum install, 编译真的很痛苦….

    　　不过真的可以休息一阵子了, NOIP复赛即将开始, 我要全力备战It.. By the way, 这WordPress还不太会用, 有空还是琢磨下.

  • [转]解决Linux 下 Gvim 菜单栏没有字

    正确的解决方法请参考这个：http://liulang.is-programmer.com/posts/329.html

    输 入locale查看到的是

    LOCALE="zh_CN.utf8"
    LANG="zh_CN.utf8"

    上面的是不标准的写法。

    标 准的写法应该是：zh_CN.UTF-8

    export LANG=’zh_CN.UTF-8′


    后马上 恢复正常可以显示菜单。



    之前的解决办法(不修改系统的locale设置):

    今天在arch linux上装了gvim，发现打开之后看不到菜单文字，上网搜索到以下解决方法，经测试，问题解决了：

    参考：http://superxgz.javaeye.com/blog/81161

    在 当前用户下新建一个.gvimrc文件，内容为 


    set encoding=utf8

    set langmenu=zh_CN.UTF-8

    set imcmdline

    source $VIMRUNTIME/delmenu.vim

    source $VIMRUNTIME/menu.vim

  • USACO 1.5.3 SuperPrime Rib

    　　这一题刚开始我是打算把所有的数都遍历一次，如当n=4时，就把1000~9999全部遍历，然后以此判断，但很快发现会超时，也可能是想起来以前刷的时候这个方法就是超时的，后来仔细想了一下，需要深搜！前遍历最高位，然后依次到个位，额，文字解释不清楚，用代码解释吧：

    　　问题出现了一些，但是因为是把程序的思路改了一两次，所以我就不好写哪里是错误了：
    /
    LANG: C
    ID: yylogoo2
    PROG: sprime
    /
    #include <math.h>
    #include <stdio.h>
    int n;

    int isprime(int num)
    {
            int i, li;
            if(num == 1){
                    return 0;
            }
            if(num == 2 || num == 3 || num == 5 || num == 7 || num == 11 ||
                            num == 13){
                    return 1;
            }
            if(num % 2 == 0 || num % 3 == 0 || num % 5 == 0 ||
                            num % 7 == 0 || num % 11 == 0 || num % 13 == 0){
                    return 0;
            }
            li = sqrt(num);
            for(i = 17; i <= li; i += 2){
                    if(num % i == 0){
                            return 0;
                    }
            }
            return 1;
    }

    int tmp = 0;

    void srch(int now)
    {
            int i;
            if(now == n){
                    printf("%d\n", tmp);
                    return ;
            }
            tmp *= 10;
            tmp -= 1;
            for(i = 1; i <= 9; i += 2){
                    
                    tmp += 2;
                    if(isprime(tmp)){
                            srch(now + 1);
                    }
            }
            tmp /= 10;
    }

    int count[6] = {2, 3, 5, 7};

    int main(void)
    {
            int i;
            freopen("sprime.in", "r", stdin);
            freopen("sprime.out", "w", stdout);
            scanf("%d", &n);
            for(i = 0; i < 4; i++){
                    tmp = count[i];
                    srch(1);
            }
            return 0;
    }

  • USACO 1.5.2 Prime Palindromes

    　　这一题我用的依然是以前的解法，现只求回文数，而且偶数回文数不需要求（如：312213）必定是11的倍数但是11要特殊处理，反正这一次我错了不少地方。
    　　1，把变量名写错了，上面分明是给a赋值，下面却写成了对b进行操作。

    　　2，对于回文数的制造的下标弄错了（不好细说，看代码里的注释和上下文把。）
    　　3，循环的范围错误，也是制造回文的错误！
    　　4，字符串的结尾忘记’\0’了。
    　　5，搜索的范围错误！！
    　　一次AC，代码如下：
    /
    LANG: C
    ID: yylogoo2
    PROG: pprime
    /
    #include <math.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int a, b;

    int isprime(int num)
    {
            int i, li;
            if(num == 2 || num == 3 || num == 5 || num == 7 || num == 11 ||
                            num == 13){
                    return 1;
            }
            if(num % 2 == 0 || num % 3 == 0 || num % 5 == 0 || num % 7 == 0 ||
                    num % 11 == 0 || num % 13 == 0){
                    return 0;
            }
            li = sqrt(num);
            for(i = 17; i <= li; i++){
                    if(num % i == 0){
                            return 0;
                    }
            }
            return 1;
    }

    void check(int num)
    {
            if(num > b){
                    exit(0);
            }
            if(num < a){
                    return ;
            }
            if(isprime(num)){
                    printf("%d\n", num);
            }
    }

    char tmp[9];

    int makenum(int num)
    {
            int i, j;
            sprintf(tmp, "%d", num);
            i = j = strlen(tmp);
            /
            Mistack 2:
            　　i的初始值错误!
                /
            i -= 2;
            /
            Mistack 3:
            　　范围错误了,, 应该是i >= 0, 不是i != 0
                /
            while(i >= 0){
                    tmp[j] = tmp[i];
                    i–, j++;
            }
            /
            Mistack 4:
            　　字符串没有以’\0’结尾
                /
            tmp[j] = ‘\0’;
            sscanf(tmp, "%d", &num);
            return num;
    }

    void srch(int i, int j)
    {
            int num;
            while(i <= j){
                    num = makenum(i);
                    /
                    Mistack 1:
                    　　把下面的参数num写成了i, 所以导致错误!
                        /
                    check(num);
                    i++;
            }
    }

    int main(void)
    {
            int i;
            freopen("pprime.in", "r", stdin);
            freopen("pprime.out", "w", stdout);
            scanf("%d%d", &a, &b);
            check(5);
            check(7);
            check(11);
            /
            Mistack 5:
            　　应该是从10开始, 而不是100
                /
            srch(10, 9999);
            return 0;
    }

  • USACO 1.5.1 Number Triangles

    　　明显是一个动态规划，有两种思路，一种是至上而下的，一种是至下而上的，让我联想到了几个大国家的革命和改革，我支持改革，革命总是要留下一些历史痕迹，漏洞，所以我选择的是至下而上的改革。至下而上的DP有什么好处呢？好处多了，因为没有任何特殊情况要考虑，如果是至上而下的DP的话，首先有特殊情况，对于每一个内层循环的值等于外层的值的话，但是这个处理得好的话还是可以做到不要多余的if来判断i是否等于j，在输出答案时不需要遍历底层，在这里的代码我犯了一个小错误导致我的代码丢了最后一个点。
    　　犯的错误：数组的下标使用错误了，在极限值（1000）时会溢出！
    　　提交了两次，代码如下：

    /
    LANG: C
    ID: yylogoo2
    PROG: numtri
    /
    #include <stdio.h>
    #define max(a, b) ((a)>(b)?(a):(b))
    int f[1000][1000];
    int n;

    int main(void)
    {
            int i, j;
            freopen("numtri.in", "r", stdin);
            freopen("numtri.out", "w", stdout);
            scanf("%d", &n);
            for(i = 0; i < n; i++){
                    for(j = 0; j <= i; j++){
                            scanf("%d", &f[i][j]);
                    }
            }
            /
            Mistack 1:
            　　下面的i我写的是i–, 因为前面的代码. 但是删掉之后忘记修改这里了,
            i要从n – 2开始枚举..
                /
            for(i = n – 2; i >= 0; i–){
                    for(j = 0; j <= i; j++){
                            f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
                    }
            }
            printf("%d\n", f[0][0]);
            return 0;
    }

  • USACO 1.4.4 Mother's Milk

    　　这一题经过反复的深思熟虑，使用三元数组作为牛奶桶中的牛奶，可以解决很多不必要的纠纷！这个题目充分体现了数据结构对算法影响力的巨大！如果不使用数组而使用三个变量作为参数传递的话，真的会很麻烦的，虽然程序大致的时间复杂度不会改变，但是其常数项会大大增加！所以这题的数据结构选择十分重要。
    　　我的思路就是暴力枚举所有牛奶可能的情况，反复搜索，用used[a][c]防止重复搜索。

    　　这里我还有一个空间的优化，不需要单独为答案开辟一个数组，直接使用防止重复的used二维数组来输出就是，也省去了枚举中很多不必要的判断时间，所以我认为这一招是高明的，我直接使用A和C作为used的下标，那么输出答案的时候就用used[0][..]来进行遍历。
    　　这一题没有一个Mistack，代码具体如下：
    /
    LANG: C
    ID: yylogoo2
    PROG: milk3
    /
    #include <stdio.h>
    #include <string.h>
    int limit[3];
    int used[21][21];
    #define move_to(a, b) do{\
            memcpy(tmp, num, sizeof(tmp));\
            if(sub_move_to(tmp, a, b)){\
                    srch(tmp);\
            }\
    }while(0)

    int sub_move_to(int num[3], int from, int to)
    {
            int t;
            if(num[from] == 0 || num[to] == limit[to]){
                    return 0;
            }
            t = num[from];
            if(t + num[to] > limit[to]){
                    t = limit[to] – num[to];
            }
            num[from] -= t;
            num[to] += t;
            return 1;
    }

    void srch(int num[3])
    {
            int tmp[3];
            if(used[num[0]][num[2]]){
                    return;
            }
            used[num[0]][num[2]] = 1;

            move_to(0, 1);
            move_to(1, 0);

            move_to(2, 1);
            move_to(1, 2);

            move_to(2, 0);
            move_to(0, 2);
    }

    int main(void)
    {
            int i, k = 0;
            freopen("milk3.in", "r", stdin);
            freopen("milk3.out", "w", stdout);
            for(i = 0; i < 3; i++){
                    scanf("%d", &limit[i]);
            }
            srch((int [3]){0, 0, limit[2]});
            for(i = 0; i <= 20; i++){
                    if(used[0][i]){
                            if(k){
                                    printf(" ");
                            }
                            k = 1;
                            printf("%d", i);
                    }
            }
            printf("\n");
            return 0;
    }

  • USACO 1.4.3 Arithmetic Progressions

    　　算法应该是比较单纯的，先把所有的双平方数找出来，并排序；然后再比如双平方数num[i], num[i + 1]，那么a = num[i], b = num[i + 1] – num[i] (num已经排序了)，然后便利他们就是，唯一要注意的就是一个大的剪支，当a + (n – 1) b > 最大的双平方数时，那么就结束循环，把所有的答案a, b排序一次输出即可。

    　　Mistacks:
    　　1、求双平方数的时候，应该是i i + j j，我却写成i j。
    　　2、双平方数应该是两个同时从0开始遍历的数的双平方，而我是一个i = 0, j = 1开始遍历的。
    　　3、忘记了没有答案输出NONE了。
    　　Code:
    /
    LANG: C
    ID: yylogoo2
    PROG: ariprog
    /
    #include <stdio.h>
    #include <stdlib.h>
    int bits[125001];
    int num[125001];
    int len;

    struct box{
            int x, y;
    }ans[10000];
    int end;

    void add(int a, int b)
    {
            ans[end].x = a;
            ans[end].y = b;
            end++;
    }

    int com(const void a, const void b)
    {
            return (int )a – (int )b;
    }

    int com1(const void a, const void b)
    {
            struct box i = (struct box)a, j = (struct box)b;
            if(i.y != j.y){
                    return i.y – j.y;
            }
            return i.x – j.x;
    }

    int main(void)
    {
            int i, j, k;
            int a, b;
            int n, m;
            freopen("ariprog.in", "r", stdin);
            freopen("ariprog.out", "w", stdout);
            scanf("%d%d", &n, &m);
            for(i = 0; i <= m; i++){
                    /
                    Mistack 2:
                    　　下面是从0开始, 我以为从1开始会把零包涵进去..
                        /
                    for(j = 0; j <= m; j++){
                            /
                            Mistack 1:
                            　　这个地方代码弄错了，题目没审清楚，是i^2+j^2而不是i    j 
                            /
                            a = i     i + j j;
                            if(!bits[a]){
                                    num[len++] = a;
                                    bits[a] = 1;
                            }
                    }
            }
            qsort(num, len, sizeof(int), com);
            for(i = 0; i < len; i++){
                    a = num[i];
                    for(j = i + 1; j < len; j++){
                            b = num[j] – num[i];
                            if(a + (n – 1)     b > num[len – 1]){
                                    break;
                            }
                            for(k = 1; k < n; k++){
                                    if(!bits[a + k b]){
                                            break;
                                    }
                            }
                            if(k == n){
                                    add(a, b);
                            }
                    }
            }
            qsort(ans, end, sizeof(struct box), com1);
            for(i = 0; i < end; i++){
                    printf("%d %d\n", ans[i].x, ans[i].y);
            }
            /
            Mistack 3:
            　　忘记如果没有答案时应该输出NONE了
            */
            if(end == 0){
                    printf("NONE\n");
            }
            return 0;
    }

  • USACO 1.4.2 The Clocks

    　　这一个题目我还算是自豪吧，代码比以前写的好看一点，仅仅是因为几行代码的原因，但是这几行代码我觉得挺好的！具体是哪几行，看代码的注释，代码中唯一的一个错误就是判断一个数据是否为答案时竟然忘记判断了！！

    　　代码如下：
    /
    LANG: C
    ID: yylogoo2
    PROG: clocks
    /
    #include <stdio.h>
    #include <string.h>
    int clocks[9];
    char ways[9][6] = {"ABDE", "ABC", "BCEF", "ADG", "BDEFH", "CFI",
                            "DEGH", "GHI", "EFHI"};
    int used[9];
    int ans[9];
    int len = 50;

    void change(int a)
    {
            char str = ways[a];
            while(    str != ‘\0’){
                    clocks[str – ‘A’]++;
                    if(clocks[    str – ‘A’] == 5){
                            clocks[str – ‘A’] = 1;
                    }
                    str++;
            }
    }

    void check(int sum)
    {
            int i;
            if(sum > len){
                    return;
            }
            /
            Mistack 1:
            　　刚刚忘记判断下面的for了
            /
            for(i = 0; i < 9; i++){
                    if(clocks[i] != 4){
                            return;
                    }
            }
            if(sum < len){
                    memcpy(ans, used, sizeof(used));
                    len = sum;
            }else if(sum == len){
                    for(i = 0; i < 9; i++){
                            if(used[i] >= ans[i]){
                                    break;
                            }
                    }
                    if(i != 9){
                            memcpy(ans, used, sizeof(used));
                            len = sum;
                    }
            }
    }

    void srch(int now, int sum)
    {
            int i;
            check(sum);
            if(now == 9){
                    return;
            }
            /
                    对下面我解释一下：
            　　要知道的是，任何一个移动方法，当同一种移动方式出现四次之后，
            都可以将其无视掉。如：1212212因为其中2出现了4次，那么相当于没有
            2的存在，即:111，又如：21121211，其中有5个1，那么就相当于3个2和
            1个1，又要按照最小顺序排序，即：1222。
            　　下面巧用了这个性质，就不许要将其复原，因为四次循环之后自然而
            然就已经复原了！
            */
            for(i = 1; i <= 4; i++){
                    srch(now + 1, sum + used[now]);
                    used[now]++;
                    change(now);
            }
            used[now] = 0;
    }

    int main(void)
    {
            int i, j, k = 0;
            freopen("clocks.in", "r", stdin);
            freopen("clocks.out", "w", stdout);
            for(i = 0; i < 9; i++){
                    scanf("%d", &clocks[i]);
                    clocks[i] /= 3;
            }
            srch(0, 0);
            for(i = 0; i < 9; i++){
                    for(j = 0; j < ans[i]; j++){
                            if(k){
                                    printf(" ");
                            }
                            k = 1;
                            printf("%d", i + 1);
                    }
            }
            printf("\n");
            return 0;
    }