OI路程 – 第 8 页

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

2010年11月4日

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而不是ij
                        /
                        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;
}

2010年11月4日

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

2010年10月31日

[未完成]USACO 1.4.1 Prime Cryptarithm

　　这是这一次做USACO目前唯一一个没做完的题目！第六种情况实在是不知道怎么写，我觉得最好还是不写最好，所以就没去写了。我也尝试了一下自己试着写写，结果写了最后一种情况竟然还不如不写的分数高！但是自己实在是不知道为什么，以前的代码这三行（最后一种情况）也是抄的，不是理解的，所以现在也就忘了……
　　我的思路就是暴搜，用srch0将所用的矩形换位置，srch1将所有的矩阵的长宽交换，然后用count进行判断，代码十分易读（以前别人写的，不过因为确实有特色，所以已经变成了自己的东西了。）
　　总结一下错误：

　　1、把return忘记了，会进入死循环。

　　2、递归调用时应该是srch(0)而不是n + 1。

　　3、在记录答案时竟然没有判断。

　　4、在一种情况的时候把y写成了x。
　　注意：本程序还没AC，但是要他AC只需要最后的两个if，因为我不理解缘由，所以没写第六种情况（代码中注释好了！）

/
LANG: C
ID: yylogoo2
PROG: packrec
/
#include <math.h>
#include <stdio.h>
#include <string.h>
struct box{
int x, y;
}box[4];
int place[4];
int ans = 2501;
int take[2501];

void check(int x, int y)
{
        if(x y < ans){
                ans = x y;
                memset(take, 0, sizeof(take));
        }
        /
        Mistack 3:
        　　没经过任何判断就直接把x, y作为答案了，那么就错了！！
        即刚刚忘记敲入if了。
        /
        if(x y == ans){
                take[x] = 1;
                take[y] = 1;
        }
}

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

void count(int x1, int y1, int x2, int y2,
                int x3, int y3, int x4, int y4)
{
        int x, y;

        x = x1 + x2 + x3 + x4;
        y = max(max(y1, y2), max(y3, y4));
        check(x, y);

        x = max(x1, x2 + x3 + x4);
        y = y1 + max(y2, max(y3, y4));
        check(x, y);

        x = max(x1, x2 + x3) + x4;
        y = max(y4, y1 + max(y2, y3));
        check(x, y);

        x = x1 + max(x2, x3) + x4;
        /
        Mistack 4:
        　　下面把y写成了x
        /
        y = max(y2 + y3, max(y1, y4));
        check(x, y);

/ 最后一种情况 /
}

void output(void)
{
        int i, limit;
        printf("%d\n", ans);
        limit = sqrt(ans);
        for(i = 1; i <= limit; i++){
                if(take[i]){
                        printf("%d %d\n", i, ans / i);
                }
        }
}

void change(struct box a)
{
        a->x ^= a->y;
        a->y ^= a->x;
        a->x ^= a->y;
}

void srch1(int now)
{
        if(now == 4){
                count(  box[place[0]].x, box[place[0]].y,
                        box[place[1]].x, box[place[1]].y,
                        box[place[2]].x, box[place[2]].y,
                        box[place[3]].x, box[place[3]].y);
                return;
        }
        srch1(now + 1);
        change(&box[place[now]]);
        srch1(now + 1);
        change(&box[place[now]]);
}

int used[4];

void srch0(int now)
{
        int i;
        if(now == 4){
                /
                Mistack 2:
                　　是调用srch1(0)而不是srch(now + 1)
                /
                srch1(0);
                /
                Mistack 1:
                　　把函数返回掉了…那样会死循环的..
                /
                return;
        }
        for(i = 0; i < 4; i++){
                if(!used[i]){
                        used[i] = 1;
                        place[now] = i;
                        srch0(now + 1);
                        used[i] = 0;
                }
        }
}

int main(void)
{
        int i;
        freopen("packrec.in", "r", stdin);
        freopen("packrec.out", "w", stdout);
        for(i = 0; i < 4; i++){
                scanf("%d%d", &box[i].x, &box[i].y);
        }
        srch0(0);
        output();
        return 0;
}

2010年10月31日

USACO 1.3.4 Prime Cryptarithm

　　我没找到什么很巧的方法，纯暴力搜索：
　　枚举100~999，10~99然后再分别进行判断，是各个数值否是在范围内，然后是否是输入输入的集合，如果都是ans递增，代码就是这样，犯了两个错误！
　　1、在比较是否属于全集时，我是判断如果都不属于才算不属于，即用的“与”进行连接，应用“或”连接，在有一个不属于全集时就算不属于了。
　　2、在判断是否是千位数时我用的是i >= 999，应该用i>999。
　　不过都是打代码就发现的问题，所以一次性AC！

/
ID: yylogoo2
PROG: crypt1
LANG: C
/
#include <stdio.h>
int num[9];
int used[10];
int n;
int ans;
int tmp[2];

void count(int a, int b)
{
        int i, j;
        /
        Mistack 1:
        　　下面用错逻辑符号了，改用||而用了&&
        /
        if(!check(a) || !check(b)){
                return;
        }
        i = a (b % 10);
        j = a (b / 10);
        /
        Mistack 2:
        　　不允许为千位数，但是允许为999。
        /
        if((i > 999) || (j > 999)){
                return ;
        }
        if(!check(i) || !check(j)){
                return ;
        }
        i = a b;
        if((i >= 1000) && (i <= 9999) && check(i)){
                ans++;
        }
}

int check(int k)
{
        while(k != 0){
                if(!used[k % 10]){
                        return 0;
                }
                k /= 10;
        }
        return 1;
}

int main(void)
{
        int i, j;
        freopen("crypt1.in", "r", stdin);
        freopen("crypt1.out", "w", stdout);
        scanf("%d", &n);
        for(i = 0; i < n; i++){
                scanf("%d", &num[i]);
                used[num[i]] = 1;
        }
        for(i = 100; i <= 999; i++){
                for(j = 10; j <= 99; j++){
                        if(i j > 9999){
                                break;
                        }
                        count(i, j);
                }
        }
        printf("%d\n", ans);
        return 0;
}

2010年10月30日

USACO 1.3.3 Calf Flac

　　这一题是USACO所有题目中我最自豪的一个题目，首先因为大部分人的代码都是在小数后一位上，而我这个算法是O(n)的，所以非常的快。又因为这是我自己想出来的，而且思维角度比较独特，所以我甚为自豪！
　　但是我这个思路很难表达清晰。
　　想把它单独提出来作为一篇文章 (http://zqynux.blog.163.com/blog/static/1674995972010929683892/)写，包裹题解也在左边的链接里面，写好了把链接贴上来。
　　这里我犯的几个错误分别如下：

　　1、在比较不同字母时没注意大小写的区分。

　　2、在查找对应的字母时应该是查找start[i – 1] – 1之前的一个字母而不是start[i] – 1。

　　3、在循环该结束时忘记continue;了。

　　感觉写得比较好，代码如下：

/
LANG: C
ID: yylogoo2
PROG: calfflac
/
#include <ctype.h>
#include <stdio.h>
#include <string.h>
#define EQ(a, b) (toupper(a) == toupper(b))
char str[20001];
/ 记录以i结尾的回文数的另外一头的坐标:start[i] /
int start[20001];
/ 记录纯净长度, 把空格和标点符号去掉的长度 /
int num[20001];

/ 寻找一个字母, way 为1时向后寻找, way为-1时向前寻找 /
int find(int s, int way)
{
        int t = s;
        while(t >= 0 && !isalpha(str[t])){
                t += way;
        }
        return t;
}

int main(void)
{
        int i, t, j;
        int len = 0;
        int max = 1;
        int end = 0;
        freopen("calfflac.in", "r", stdin);
        freopen("calfflac.out", "w", stdout);
        while(fgets(&str[len], 20000 – len, stdin) != NULL){
                len += strlen(&str[len]);
        }
        for(i = 1; i < len; i++){
                if(!isalpha(str[i])){
                        num[i] = num[i – 1];
                        start[i] = start[i – 1];
                        /
                        Mistack 3:
                        　　忘记添加continue了，进入这个的时候num[i]就会改变，
                        下一次DP时会有错误。
                        /
                        continue;
                }
                /
                Mistack 2:
                　　下面应该是使用start[i – 1]的前一个字符进行比较
                /
                t = find(start[i – 1] – 1, –1);
                /
                Mistack 1:
                　　在比较字母是否相等时，忽略了大小写。
                /
                if(t >= 0 && EQ(str[t], str[i])){
                        num[i] = num[i – 1] + 2;
                        start[i] = t;
                }else{
/                      t = find(i – 1, -1);
                        j = find(i + 1, 1);
                        if(str[t] == str[j]){
                                num[i] = 3;
                                start[i] = t;
                        }else if(str[t] == str[i]){
                                num[i] = 2;
                                start[i] = t;
                        }/
                        t = find(i – 1, –1);
                        if(t > 0 && EQ(str[i], str[t])){
                                num[i] = 2;
                                start[i] = t;
                        }else{
                                num[i] = 1;
                                start[i] = i;
                        }
                }
                if(num[i] > max){
                          max = num[i];
                          end = i;
                }
        }
        printf("%d\n", max);
        for(i = start[end]; i <= end; i++){
                printf("%c", str[i]);
        }
        printf("\n");
        return 0;
}

2010年10月30日

USACO 1.3.2 Barn Repair

　　这一题想了好久才想起来以前是怎么做的，直接使用的贪心，首先假设只有一块木板，自然而然是从最小的到最大的全部盖上，此时假设值为ans，那么如果是两块木板，那两块木板之间隔的距离必定是整个牛棚中距离最远的两个牛之间的距离，也就是说答案等于：只有一块木板的长度减去一个最长间隔：ans-max(dis)，那三块木板的话很自然就是只有一块木板的长度减去最长的前两个间隔的值，以此类推，代码就很简单了。
　　但是又由于需要快排的实现，我嫌它麻烦了，就直接使用数组进行排序（这个排序方法准确叫什么名字我也忘了，不记得是基数还是桶还是哈希排序了。），因为数据量并不是特别的大，所以使用这种排序方法也会比快排要好很多（至少自我感觉是这样，我的应该是O(n)而快排最快O(n logn)）！
　　这也是少量提交了两次的题目：

　　1、在程序中如果有n块木板的话，相当于只有一块木板，其中有n-1个洞；也就是说一块肉要3块只要切2刀即可。j = 1; j < m
　　2、比如已有a, b 两点（b > a），代表两个位置，那么b – a – 1代表的是把两点除去，剩下的个数，而b – a + 1代表包括亮点总共的长度，在求只要一块木板长度时应该是b-a+1，我写的是b-a-1。
　　3、程序的设计有误，求下一点应该是从+1开始而不是从当前点开始，这一个我不好形象点地说出来，只能说j要从1开始，之后的内容要修改成dis[j – 1]++。

　　下面这个是第二次提交之后发现的问题。
　　4、下面的代码忽略了一个重要的问题:

for(i = s – 1; i >= 0 && j < m; i–){

if(dis[i] > 0){

ans -= i;

j++;

dis[i]–;

}

　　当dis[i] > 1时只计算一次，剩下的次数就不算了。。

　　修改之后（在dis[i]–;后面插入i++;一行）就能够应付了。
　　还有一个要注意的，就是在循环体退出之后还要一个dis[j – 1]–;因为前面会把最后一个牛和结尾的墙壁之间的距离当作需要考虑的距离来算，要将它除去。
/
LANG: C
ID: yylogoo2
PROG: barn1
/
#include <stdio.h>
int cow[200];
int dis[200];

int main(void)
{
        int t;
        int i, j;
        int m, s, c;
        int fi = 200, la = –1;
        unsigned ans;
        freopen("barn1.in", "r", stdin);
        freopen("barn1.out", "w", stdout);
        scanf("%d%d%d", &m, &s, &c);
        for(i = 0; i < c; i++){
                scanf("%d", &t);
                cow[t – 1]++;
                if(t – 1 < fi){
                        fi = t – 1;
                }
                if(t – 1 > la){
                        la = t – 1;
                }
        }
        i = fi;
        while(i < s){
                /
                Mistack 3:
                　　下面应该从1开始，而不是0，不然会进入死循环，
                但是下面改成一之后dis[j]++就要改成dis[j – 1]++。
                /
                for(j = 1; (cow[i + j] == 0) && (i + j < s); j++){
                }
                dis[j – 1]++;
                /
                Pay attention:
                　　下面-1的原因是再进行计算一次
                /
                i += j;
        }
        /
        　　下面的代码是把最后一个位置和结尾之间的空隙删除了
        其实它可以放在上面的循环体内, 但是这样的话每次循环都
        要判断一次, 很慢!!
        /
        dis[j – 1]–;
        /
        Mistack 2:
        　　下面应该是要+1而不是-1
        +1代表包括两点中间的距离，
        -1代表出去两点中间的距离。
        /
        ans = la – fi + 1;
        /
        Mistack 1:
        　　下面应该是从1开始而不是0, 因为把一块肉切成3分的话，只要2刀
        /
        j = 1;
        /
        Mistack 4:
        　　下面的代码忽略了一个重要的问题:
        for(i = s – 1; i >= 0 && j < m; i–){
                if(dis[i] > 0){
                        ans -= i;
                        j++;
                        dis[i]–;
                }
        }
        　　当dis[i] > 1时只计算一次，剩下的次数就不算了。。
        　　修改之后（在dis[i]–;后面插入i++;一行）就能够应付了。
        /
        for(i = s – 1; i >= 0 && j < m; i–){
                if(dis[i] > 0){
                        ans -= i;
                        j++;
                        dis[i]–;
                        i++;
                }
        }
        printf("%u\n", ans);
        return 0;
}

2010年10月28日

USACO 1.3.1 Mixing Milk

　　这题是个纯贪心题，本来是打算使用快排的，想到考试时可能不允许使用快排，自己写又太麻烦了，所以我就懒得用快排了，题目的数据量也不是很大，直接使用数组进行排序就是！
　　当然没有什么明显的问题，一次AC，代码如下：

/
LANG: C
ID: yylogoo2
PROG: milk
/
#include <stdio.h>
unsigned milk[1001];

int main(void)
{
        int n, m;
        int i, got = 0, ans = 0;
        unsigned a, b;
        freopen("milk.in", "r", stdin);
        freopen("milk.out", "w", stdout);
        scanf("%d%d\n", &n, &m);
        for(i = 0; i < m; i++){
                scanf("%u%u\n", &a, &b);
                milk[a] += b;
        }
        for(i = 0; got != n; i++){
                if(milk[i] != 0){
                        if(milk[i] + got > n){
                                ans += (n – got) i;
                                got = n;
                        }else{
                                ans += milk[i] i;
                                got += milk[i];
                        }
                }
        }
        printf("%u\n", ans);
        return 0;
}

2010年10月27日

USACO 1.2.5 Dual Palindromes

　　本来应该是很简单的一个题目，因为昨天才写前面一题（USACO 1.2.4 Palindromic Squares），就是使用那里写的一些子函数即可AC，但是因为现在是以学习为目的，所以自然是重写一次，但是重写同样的两个函数，却出现了不应该有的错误，具体错误如下：

　　1、在循环之后忘记更改循环变量了，就是说比如：for(i = 0; i <= 10; / 相当于这里没写 / )，自然循环就无法结束了！

　　2、在数组里面直接使用长度作为下表，又比如：char str[10] = "12345"，而我想通过str[strlen(str)]来指向最后一个字符，明显是错误！应该是str[strlen(str) – 1]才能使用最后一个字符！
　　和昨天的代码比较了一下，昨天的代码层次性更强，直接将字符串的长度作为参数传给了判断是否为回文数的函数，而今天是在判断回文数的函数内部进行的！
　　不过因为没有别的问题，所以还是一次性AC了：

/
LANG: C
ID: yylogoo2
PROG: dualpal
/
#include <stdio.h>
#define STR "0123456789"
#define MAX 50
char str[MAX];

int change(int num, int base)
{
        int i = MAX;
        while(num != 0){
                str[–i] = STR[num % base];
                num /= base;
        }
        return i;
}

int ispal(int start)
{
        char num = &str[start];
        /
        Mistack 2:
        　　下面j的赋值错误了。第一次是写成了j = MAX – i，后来修改成了j = MAX – i – 1  还是错了
        最后一次才改对..
        /
        int i = 0, j = MAX – start – 1;
        while(i < j){
                if(num[i] != num[j]){
                        return 0;
                }
                /
                Mistack 1:
                 　　忘记下面的递增和递减！
                */
                i++, j–;
        }
        return 1;
}

int main(void)
{
        int i, j, k, l;
        int m, n;
        freopen("dualpal.in", "r", stdin);
        freopen("dualpal.out", "w", stdout);
        scanf("%d%d", &m, &n);
        for(i = n + 1, k = 0; k < m; i++){
                l = 0;
                for(j = 2; j <= 10 && l != 2; j++){
                        if(ispal(change(i, j))){
                                l++;
                        }
                }
                if(l == 2){
                        printf("%d\n", i);
                        k++;
                }
        }
        return 0;
}

2010年10月26日

USACO 1.2.4 Palindromic Squares

　　这题硬搜就是，不过在提交前找到两个mistack：

　　1、没审清楚题目，题目只要求平方是回文数，而没有要求那个数自身也是个回文数，我以为那个数自身也是回文数。
　　2、在转换进制的时候，犯了一个超级低级的错误，把进制顺着使用了，也就是说比如13的二进制是：1101，而我的程序做出来就是1011，弄翻了！当然，很快就改好了，提交，一次性AC！

/
LANG:
C
ID: yylogoo1
PROG:
palsquare
/
#include <stdio.h>
#define MAP
"0123456789ABCDEFGHIJ"
#define MAX 18
int n;
char str[MAX];

int isreback(char str, int len)
{
        int i, j;
        i = 0, j = len – 1;
        while(i < j){
                if(str[i++] !=
str[j–]){
                        return 0;
                }
        }
        return 1;
}

int change(int num)
{
        /
        mistack
2:
        　　这里写错了，str应该是逆向的方式写的！
        /
        int i = MAX;
        while(num != 0){
                str[–i] = MAP[num %
n];
                num /= n;
        }
        return i;
}

int ispal(int num)
{
        int i, len;
        i =
change(num);
        len = MAX – i;
        return isreback(&str[i], len);
}

void output(int num)
{
        printf("%s",
&str[change(num)]);
}

int main(void)
{
        int i;
        freopen("palsquare.in", "r", stdin);
        freopen("palsquare.out", "w", stdout);
        scanf("%d", &n);
        for(i = 1; i <= 300; i++){
                /
                mistack
1:
                　　题目没审清楚,  只要求平方是回文数,
                而没要求自己也是回文数数
                /
                if(ispal(i
i)){
                        output(i);
                        printf(" ");
                        output(i *
i);
                        printf("\n");
                }
        }
        return 0;
}

2010年10月25日

分类： OI路程