跳至正文

USACO 1.4.3 Arithmetic Progressions

  • OI路程

  算法应该是比较单纯的,先把所有的双平方数找出来,并排序;然后再比如双平方数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

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

发表评论

您的电子邮箱地址不会被公开。