新零点

分类： 技术

  • tyvj 1005 采药

    　　01背包的例子，不过第一次写的时候不小心把01背包写成了无限背包，代码如下：

    #include <stdio.h>
    #define max(a, b) ((a)>(b)?(a):(b))
    int f[1001];

    int main(void)
    {
            int i, j;
            int t, m;
            int a, b;
            scanf("%d%d", &t, &m);
            for(i = 0; i < m; i++){
                    scanf("%d%d", &a, &b);
                    /
                    Mistack 1:
                    　　把01背包写成了无限背包 
                        /
    /              for(j = a; j <= t; j++){
                            f[j] = max(f[j], f[j – a] + b);
                    }    /
                    for(j = t; j >= a; j–){
                            f[j] = max(f[j], f[j – a] + b);
                    }
            }
            printf("%d\n", f[t]);
            return 0;
    }

  • tyvj 1004 滑雪

    　　上午写了一次(http://zqynux.blog.163.com/blog/static/1674995972010101325737526/)，只有70分，剩下的我也知道为什么错了，所以我的思路是不行的，但是我就想不到另外的方法了，到群里问了下，别人把代码发给我看了,, 汗, 好简单, 纯DP, 没有任何杂念, 我原本以为要排序, 但NOIP的题目似乎涉及不到这么高深的算法, 矩阵+排序+搜索, 就觉得我是想复杂了, 他这个代码太简单了…
    　　但是几乎是纯递归,我以为会爆掉(栈溢出), 结果用最最最大的可能用尽栈的数据测试, 结果没溢出, 后来测试发现,, 栈一般还是够用.. 
    　　但是我犯了一个很严重的错误, 记忆DP竟然没有给它记忆,, 所以导致最后一个数据超时了,,代码如下:

    #include <stdio.h>
    int map[100][100];
    int dis[100][100];
    int r, c;

    int check(int a,
    int b)
    {
            if(a < 0 || a >= r
    || b < 0 || b >= c){
                    return 0;
            }
            return 1;
    }

    int max(int a,
    int b)
    {
            return a > b ? a : b;
    }

    #define deal(i, j) do{\
            if(check(i, j) && map[i][j] >
    map[a][b]){\
                    t = max(srch(i, j),
    t);\
            }\
    }while(0)

    int srch(int a, int b)
    {
            int t = 0;
            if(dis[a][b] != 0){
                    return dis[a][b];
            }
            deal(a +
    1, b);
            deal(a – 1, b);
            deal(a, b + 1);
            deal(a, b – 1);
            /
            Mistack 1:
            　　真是….不好怎么评价自己了,, 记忆DP, 我竟然忘记记忆了..
                /
            dis[a][b]
    = t + 1;
            return dis[a][b];
    }

    int main(void)
    {
            int ans = 1;
            int i, j,
    t;
            scanf("%d%d", &r,
    &c);
            for(i = 0; i < r; i++){
                    for(j = 0; j < c;
    j++){
                            scanf("%d",
    &map[i][j]);
                    }
            }
            for(i = 0; i < r;
    i++){
                    for(j = 0; j < c; j++){
                            t = srch(i,
    j);
                            if(ans <
    t){
                                    ans =
    t;
                            }
                    }
            }
            printf("%d\n", ans);
            return 0;
    }

  • [未AC]tyvj 1004 滑雪

    　　以前看过这题，没看懂，现在是看懂了，就是在这里面找一个最长的递减（递增）序列，我的思路是，从最小的值开始向四周搜索，把每一个比它大的都算是一条路径，结果，很遗憾提交了4次也只70分，现在发现是思路不行，比如最小的0周围都是最大的数字，那么我的程序直接输出2，但是正确答案却不是1，代码先贴上：
    　　AC的解答看这里:http://zqynux.blog.163.com/blog/static/16749959720101013105738935/

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

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