新零点

分类： 算法

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

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

  • USACO 1.2.3 Name That Number

    　　这题我用的方法就是将dict.txt中的每一个字符串读出来，并判断是否满足输入的那个数字，如果满足输出就是。
    　　我还有另外一个算法，就是首先根据输入的数字来确定范围，然后逐步缩小，最后确定到个数，但是很快就发现这是（我）无法实现的高难度算法。
    　　再一个，我上面的那个算法要注意的是数的长度，最长是12位的数字！int存不进，必须要用long long！
    　　代码如下：

    /
    LANG: C
    ID: yylogoo1
    PROG: namenum
    /
    #include <stdio.h>
    #include <assert.h>
    FILE fp;
    char str[13];
    char map[26] = {2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6,
            7, 0, 7, 7, 8, 8, 8, 9, 9, 9, 0};

    long long change(char str)
    {
            long long t = 0;
            while(str != ‘\0’){
                    t     = 10;
                    t += map[*str – ‘A’];
                    str++;
            }
            return t;
    }

    int main(void)
    {
            int i;
            long long n;
            unsigned ans = 0;
            freopen("namenum.in", "r", stdin);
            freopen("namenum.out", "w", stdout);
            fp = fopen("dict.txt", "r");
            assert(fp != NULL);
            scanf("%lld", &n);
            while(fscanf(fp, "%s", str) == 1){
                    if(change(str) == n){
                            printf("%s\n", str);
                            ans++;
                    }
            }
            if(ans == 0){
                    printf("NONE\n");
            }
            return 0;
    }

  • USACO 1.2.2 Transformations

    　　这题没什么别的巧，就是硬搜，我犯的唯一一个错误就是使用了strcmp来进行判断，但是又没有给字符串设置结尾标识’\0’，幸运的是我在提交前查出来了，所以还是一次性提交成功，哈哈 ！代码如下：

    /
    LANG:
    C
    ID: logoo2
    PROG:
    transform
    /
    #include <stdio.h>
    #include
    <string.h>
    typedef struct{
            char map[10][11];
    }pic;
    int n;
    pic map, end;

    pic change1(pic
    box)
    {
            int i, j;
            pic
    tmp;
            for(i = 0; i < n; i++){
                    for(j = 0; j < n;
    j++){
                            tmp.map[j][n – 1 –
    i] = box.map[i][j];
                    }
                    /
                    mistack
    1:
                    　　忘记增加结束标识
                        /
                    tmp.map[i][n] = ‘\0’;
            }
            return tmp;
    }

    int com(pic a, pic b)
    {
            int i;
            for(i = 0; i < n;
    i++){
                    if(strcmp(a.map[i],
    b.map[i]) != 0){
                            return 1;
                    }
            }
            return 0;
    }

    pic
    change2(pic box)
    {
            int i,
    j;
            pic tmp;
            for(i =
    0; i < n; i++){
                    for(j = 0; j < n;
    j++){
                            tmp.map[i][n – 1 –
    j] = box.map[i][j];
                    }
                    tmp.map[i][n] =
    ‘\0’;
            }
            return tmp;
    }

    int main(void)
    {
            int i;
            freopen("transform.in", "r", stdin);
            freopen("transform.out", "w", stdout);
            scanf("%d", &n);
            for(i = 0; i < n;
    i++){
                    scanf("%s\n", map.map[i]);
            }
            for(i = 0; i < n;
    i++){
                    scanf("%s\n", end.map[i]);
            }
            if(com(change1(map), end) == 0){
                    printf("1\n");
            }else if(com(change1(change1(map)), end) == 0){
                    printf("2\n");
            }else if(com(change1(change1(change1(map))), end) == 0){
                    printf("3\n");
            }else if(com(change2(map), end) == 0){
                    printf("4\n");
            }else if((com(change1(change2(map)), end) == 0)
    ||
                    (com(change1(change1(change2(map))), end) == 0)
    ||
                    (com(change1(change1(change1(change2(map)))), end) ==
    0)){
                    printf("5\n");
            }else if(com(map,
    end) == 0){
                    printf("6\n");
            }else{
                    printf("7\n");
            }
            return 0;
    }

  • USACO 1.2.1 Milking Cows

    　　这一次刷题目纯粹是为了Noip的复赛，因为不知道Noip复赛是否能够使用qsort函数，所以就只能自己写了，在函数实现方面出现了不少错误，原计划时提交一次就AC的，但是却提交了4次，下面先贴出思路，再贴出具体的错误。
    　　现将程序按照开始的时间进行一次排序，然后对排序后的数组进行一次迭代(far[i])，用一个now结构记录当前最长连续的开始时间和结束时间，如果far[i]的结束时间小于等于now的开始时间，那么now的开始时间不变，因为是排过续得了，但是结束时间就可能要更新了，如果far[i]的结束时间大于now的结束时间的话；如果far[i]的开始时间大于now的结束时间的话，那就是说这期间有一个没有人挤牛奶的时间，那就先判断now的开始时间到结束时间是否是最长的有人挤奶的时间，然后判断far[i]的开始时间和now的结束时间的差是否是最长无人挤奶的时间。
    　　错误如下：

    　　1、唯一一个不是快排实现的问题，在退出循环之后应该是还要判断一下now的时间是否是最长有人挤奶的时间。
    　　2、好久没写快排了，这一次写了快排的函数，但是竟然忘记递归调用自己了！有些吓人的错误。。
    　　3、我的快排的话，在元素个数在较少时直接调用插入排序，但是插入排序中间的第二层循环的条件写错了，把j>=s 写成了 j >=0。
    　　4，5、都是出现在选择枢纽元的函数里面，有一个确实错的很惨，可以这么表示：
    　　　　　　　　　　　　　if(a > b){
    　　　　　　　　　　　　　　　max = b;
    　　　　　　　　　　　　　}
    　　明显应该是max = a，这种错误，确实很惨，还有另外一个错误可以这么表示，有三个数a, b, c要求按顺序排序这三个数，我的错误的排序方法是：

    if(com(&a, &b) < 0){
    swap(a, b);
    }
    if(com(&b, &c) > 0){
    swap(b, c);
    }
    if(com(&a, &c) > 0){
    swap(a, c);
    }
    　　这样的话，如果a = 3, b = 2, c = 1，那么排序之后的结果是2, 1, 3而不是期望的1, 2, 3，原因很简单，因为最小的被放在了中间，而两边的却不是最小的，所以正确的方法应该是先把最小/最大的位置放对，然后再把剩下的一对比较放好就是：
    if(com(&a, &b) < 0){
    swap(a, b);
    }
    if(com(&a, &c) > 0){
    swap(a, c);
    }
    if(com(&b, &c) > 0){
    swap(b, c);
    }
    　　Ok了，把错误终结了，我就能够继续前进了，代码如下：
    /
    LANG: C
    ID: logoo2
    PROG: milk2
    /
    #include <stdio.h>
    #define max(a, b) ((a)>(b)?(a):(b))
    #define min(a, b) ((a)<(b)?(a):(b))
    #define swap(a, b) do{\
            struct far tmp;\
            tmp = a;\
            a = b;\
            b = tmp;\
    }while(0)
    struct far{
            int start, end;
    }far[5000];

    int com(struct far a, struct far b)
    {
            return a->start – b->start;
    }

    void insert_sort(int s, int t)
    {
            int i, j;
            struct far key;
            for(i = s + 1; i <= t; i++){
                    key = far[i];
                    /
                    mistack 3:
                    　　下面的j >= s 写成了 j >= 0
                        / 
                    for(j = i – 1; com(&key, &far[j]) < 0 && j >= s; j–){
                            far[j + 1] = far[j];
                    }
                    far[j + 1] = key;
            }
    }

    void choose(int s, int t)
    {
            int mid = (s + t) / 2;
    /
    mistack 5:
    　　下面比较的顺序原来是:
            if(com(&far[mid], &far[s]) < 0){
                    swap(far[mid], far[s]);
            }
            if(com(&far[mid], &far[t]) > 0){
                    swap(far[mid], far[t]);
            }
            if(com(&far[s], &far[t]) > 0){
                    swap(far[s], far[t]);
            }
    　　但是碰到, far[s] > far[mid] > far[t] 的情况就会出问题.. 
    /
            if(com(&far[mid], &far[s]) < 0){
                    swap(far[mid], far[s]);
            }
            if(com(&far[s], &far[t]) > 0){
                    swap(far[s], far[t]);
            }
            if(com(&far[mid], &far[t]) > 0){
                    /
                    mistack 4:
                    　　误把下面的far[t]写成了far[s]
                        /
                    swap(far[mid], far[t]);
            }
            swap(far[t – 1], far[mid]);
    }

    void sort(int s, int t)
    {
            int i, j;
            if(t – s < 9){
                    insert_sort(s, t);
                    return ;
            }
            choose(s, t);
            i = s, j = t – 1;
            while(i < j){
                    while(com(&far[++i], &far[t – 1]) < 0){
                            continue;
                    }
                    while(com(&far[–j], &far[t – 1]) > 0){
                            continue;
                    }
                    if(i < j){
                            swap(far[i], far[j]);
                    }
            }
            swap(far[t – 1], far[i]);
            /
            mistack 2:
            　　对快排的代码并不是特别的熟练，打完了上面的代码后忘记继续进行递归了。。 
                /
            sort(s, i – 1);
            sort(i + 1, t);
    }

    int main(void)
    {
            int n;
            int i;
            struct far now;
            int ans1 = 0, ans2 = 0;
            freopen("milk2.in", "r", stdin);
            freopen("milk2.out", "w", stdout);
            scanf("%d\n", &n);
            for(i = 0; i < n; i++){
                    scanf("%d%d", &far[i].start, &far[i].end);
            }
    //      qsort(far, n, sizeof(struct far), com);
            sort(0, n – 1);
            now = far[0];
            for(i = 1; i < n; i++){
                    if(far[i].start <= now.end){
                            now.end = max(now.end, far[i].end);
                    }else{
                            if(now.end – now.start > ans1){
                                    ans1 = now.end – now.start;
                            }
                            if(far[i].start – now.end > ans2){
                                    ans2 = far[i].start – now.end;
                            }
                            now = far[i];
                    }
            }
            /
            mistack 1:
            　　在退出循环时应该把最后剩下的数据进行判断. 
                /
            if(now.end – now.start > ans1){
                    ans1 = now.end – now.start;
            }
            printf("%d %d\n", ans1, ans2);
            return 0;
    }

  • USACO 1.1.4 Broken Necklace

    　　这一题以前我就有疑问，为什么代码一定是：

    a = b – w;
    b = w + 1;
    　　而不能是:
    a = b;
    b = 1;
    　　今天终于是把它给想通了，理由如下：
    　　这里之所以要写成a = b – w, b = w + 1 而不是a = b, b = 1 的原因我终于是找到了.原因如下:
    　　假设: 此时 b = 2, w = 1 则执行
    　　a = b, b = 1 之后的
    　　1.a = 2, b = 1
    　　而下一次就又进入这里,
    　　2.a = 1, b = 1
    　　但是不是有更好的分配方法么:

    　　1.a = b – w = 1, b = w + 1 = 2
    　　虽然和上面的和相同都是3, 但是对后面结果的影响不同了:
    　　2.a = b – w = 2 – 0 = 2, b = 1
    　　不久比上面的要好上1 ?  
    　　代码附上:
    /
    LANG:
    C
    ID: logoo2
    PROG:
    beads
    /
    #include
    <stdio.h>
    #include <string.h>

    char str[10001];

    int main(void)
    {
            int a = 0, b = 0, w = 0;
            char ch = ‘w’;
            int i,
    n;
            int ans = 0;
            freopen("beads.in", "r", stdin);
            freopen("beads.out", "w", stdout);
            scanf("%d\n", &n);
            scanf("%s",
    str);
            for(i = 0; i < n; i++){
                    str[i + n] =
    str[i];
            }
            str[i + n] = ‘\0’;
            for(i =
    0; i < 2  n &&
    ans < n; i++){
                    if(str[i]
    == ‘w’){
                            b++,
    w++;
                    }else if(str[i] != ch){
                            if(a + b >
    ans){
                                    ans = a +
    b;
                            }
                            /
                            　　这里之所以要写成a = b – w, b = w + 1
    而不是
                            a = b, b = 1
    的原因我终于是找到了.原因如下:
                            假设: 此时 b
    = 2, w = 1 则执行
                            a = b, b =
    1 之后的
                            1.a = 2, b =
    1
                            而下一次就又进入这里,
                            2.a = 1, b = 1
                            但是不是有更好的分配方法么:

                            1.a = b – w = 1, b = w + 1 =
    2
                            虽然和上面的和相同都是3,
    但是对后面结果的影响不同了:
                            2.a = b – w
    = 2 – 0 = 2, b = 1
                            不久比上面的要好上1 ?  
                            */
                            a = b –
    w;
                            b = w + 1;
                            w = 0;
                            ch =
    str[i];
                    }else{
                            b++, w = 0;
                    }
            }
            if(a + b > ans){
                    ans = a +
    b;
            }
            if(ans >
    n){
                    ans = n;
            }
            printf("%d\n", ans);
            return 0;
    }

  • USACO 1.1.3 Friday the Thirteenth

    　　这一个题目着实考察程序员的其他能力，时间方面我的能力真的很差，总是能把日期记错，把时间弄反，庆幸的是，我还是会看闹钟的，也不知道现在还有没有不会看的人，哈哈。
    　　代码实现如下：

    /
    LANG: C
    ID: logoo2
    PROG: friday
    /
    #include <stdio.h>
    int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int now = 6;
    int ans[7];

    int isry(int year)
    {
            return (((year % 4 == 0) && (year % 100 != 0)) || (year % 400 == 0));
    }

    int main(void)
    {
            int n;
            int i, j;
            freopen("friday.in", "r", stdin);
            freopen("friday.out", "w", stdout);
            scanf("%d", &n);
            n += 1900 – 1;
            for(i = 1900; i <= n; i++){
                    if(isry(i)){
                            day[1] = 29;
                    }
                    for(j = 0; j < 12; j++){
                            ans[now]++;
                            now = (now + day[j]) % 7;
                    }
                    day[1] = 28;
            }
            printf("%d", ans[6]);
            for(i = 0; i < 6; i++){
                    printf(" %d", ans[i]);
            }
            printf("\n");
            return 0;
    }

  • USACO 1.1.2 Greedy Gift Givers

    　　这个题目唯一要注意的就是被除数不为0的问题，别的的话就是别太粗心就是，代码如下：

    /
    LANG: C
    ID: logoo2
    PROG: gift1
    /
    #include <stdio.h>
    #include <string.h>
    struct peo{
            char name[15];
            int get, give;
    }pep[10];
    int n;

    int getid(char str)
    {
            int i;
            for(i = 0; i < n; i++){
                    if(!strcmp(str, pep[i].name)){
                            return i;
                    }
            }
            return –1;
    }

    int main(void)
    {
            int i, j;
            char name[15], tmp[15];
            int t, s, m, av;
            freopen("gift1.in", "r", stdin);
            freopen("gift1.out", "w", stdout);
            scanf("%d\n", &n);
            for(i = 0; i < n; i++){
                    scanf("%s\n", pep[i].name);
            }
            while(scanf("%s\n", name) == 1){
                    t = getid(name);
                    scanf("%d%d\n", &m, &s);
                    if(s == 0){
                            av = 0;
                    }else{
                            av = m / s;
                    }
                    pep[t].get += m – av     s;
                    pep[t].give = m;
                    for(i = 0; i < s; i++){
                            scanf("%s", tmp);
                            t = getid(tmp);
                            pep[t].get += av;
                    }
            }
            for(i = 0; i < n; i++){
                    printf("%s %d\n", pep[i].name, pep[i].get – pep[i].give);
            }
            return 0;
    }

  • USACO 1.1.1 Your Ride Is Here

    　　这一题的话，觉得我的代码函数独立的不错，因为题目毕竟简单，所以也就这么写吧:

    /
    LANG:C
    ID:zqynux2
    PROG: ride
    /
    #include <stdio.h>
    #include <string.h>
    typedef char string[7];

    int get_num(char ch)
    {
            return ch – ‘A’ + 1;
    }

    int change_to_num(string str, int n)
    {
            int i, sum = 1;
            int len;
            len = strlen(str);
            for(i = 0; i < len; i++){
                    sum *= get_num(str[i]);
                    sum %= n;
            }
            return sum;
    }

    int main(void)
    {
            int i, j;
            string team, star;
            freopen("ride.in", "r", stdin);
            freopen("ride.out", "w", stdout);
            scanf("%s%s", team, star);
            i = change_to_num(team, 47);
            j = change_to_num(star, 47);
            if(i == j){
                    printf("GO\n");
            }else{
                    printf("STAY\n");
            }
            return 0;
    }

  • NOIp 2005 提高组 篝火晚会 解题报告

    　　这道题目我的思路很简单，就是模拟，然后每个人都只考虑自己旁边的，后来发现这种思路错了，写出来竟然是0分！！