新零点

分类： OI路程

  • 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分！！

  • NOIp 2005 提高组 1 谁拿了最多奖学金

    　　十分简单的题目，以前写过，以为是普及组里最垃圾的题目（普及组的水平都不算），就是算分然后判断，也没什么要注意的（对我来说要注意的就是我错过的地方，这个题目是少量的一次性AC的题目。），代码如下（比以前写的好看很多！）：

    #include <stdio.h>
    struct pep{
            char name[21];
            int grade;
    };

    int getgrade(int a, int b, char c, char d, int e)
    {
            int n = 0;
            if(a > 80 && e > 0){
                    n += 8000;
            }
            if(a > 85 && b > 80){
                    n += 4000;
            }
            if(a > 90){
                    n += 2000;
            }
            if(a > 85 && d == ‘Y’){
                    n += 1000;
            }
            if(b > 80 && c == ‘Y’){
                    n += 850;
            }
            return n;
    }

    int main(void)
    {
            struct pep t, max;
            int a, b, e;
            char c, d;
            int n, i;
            int ans = 0;
            max.grade = 0;
            scanf("%d\n", &n);
            for(i = 0; i < n; i++){
                    scanf("%s %d %d %c %c %d\n", t.name, &a, &b, &c, &d, &e);
                    t.grade = getgrade(a, b, c, d, e);
                    ans += t.grade;
                    if(t.grade > max.grade){
                            max = t;
                    }
            }
            printf("%s\n%d\n%d\n", max.name, max.grade, ans);
            return 0;
    }

  • NOIp 2006 提高组 4 2^k进制数

    　　这题我以前写过的，现在就当是再温习一遍吧，思路就是递推（也就是动态规划）根据一个公式推导出来的DP方程，首先我用f[i][j]表示第i位数以j开头的数字共有多少个，那么最容易得到的一个转移方程是：
    　　f[i][j] = f[i – 1][j + 1] + f[i – 1][j + 2] + ……. + f[i – 1][n – 1] + f[i – 1][n].
    　　但是这个方程给我们的感觉就是一个字——太慢了，为什么这么慢呢？因为它就是这么慢，要把所有的一个个相加一次，但是注意到上面我画红的部分！就是用这个公式，这部分能够表示成啥？很简单啊：
    　　f[i][j + 1] = f[i – 1][j + 2] + ……. + f[i – 1][n – 1] + f[i – 1][n].
    　　那么智商高一点的人就看到玄机了，能够把f[i][j]简化成如下的形式：
    　　f[i][j] = f[i][j + 1] + f[i – 1][j + 1]
    　　如此一来程序就清晰多了，代码也很好写，要注意的是搜索时j是从后向前搜索，我还是使用面向对象的思想，先封装了一套int类型的，然后再修改成高精度类型的，int类型的（40分）如下：

    #include <stdio.h>
    typedef int num;
    num f[61][513];
    num ans;

    void give(num a, int b)
    {
                a = b;
    }

    void add(num a, num b)
    {
            a += b;
    }

    void output(num a)
    {
            printf("%d",     a);
    }

    int main(void)
    {
            int i, j;
            int n, s, k, t, l;
            scanf("%d%d", &s, &n);
            k = 1 << s;
            for(i = 0; i < k; i++){
                    give(&f[0][i], 1);
            }
            t = n / s;
            for(i = 1; i <= t; i++){
                    for(j = k – i – 1; j >= 1; j–){
                            add(&f[i][j], &f[i][j + 1]);
                            add(&f[i][j], &f[i – 1][j + 1]);
                    }
            }
            for(i = 1; i < t; i++){
                    for(j = k – i – 1; j >= 1; j–){
                            add(&ans, &f[i][j]);
                    }
            }
            l = n – t s;
            if(l == 0){
                    l = k;
            }else{
                    l = 1 << l;
            }
            for(i = 1; i < l; i++){
                    add(&ans, &f[t][i]);
            }
            output(&ans);
            printf("\n");
            return 0;
    }
    　　详细修改了一番之后，发现主函数中错了，后来详细修改了一番，弄得我以为高精度写错了，仔细检查之后发现两个地方错了，第一个是数组开小了，本来是num f[61][513]，后来发现要使用f[513][513]，再一个就是不能够直接使用用(n – 1)/s，因为如果用30000/1（k = 1, w = 30000）的话那数组又会显得小了，需要f[30000][513]，但是实际上又跟本用不到（因为k很小时最多只有    !((1 << k) – 1)种情况，那样的情况很少）。
    　　所以最终修改了一大番，确定了AC代码：

    #include <math.h>
    #include <stdio.h>
    #define max(a, b) ((a)>(b)?(a):(b))
    #define used 100000000
    #define bits ((int)log10(used))
    #define MAX 26
    typedef struct{
            int num[MAX];
            int len;
    }num;
    num f[513][513];
    //数组开小了 
    num ans;

    void give(num a, int b)
    {
            int i;
            for(i = 0; b != 0; i++){
                    a->num[i] = b % used;
                    b /= used;
            }
            a->len = i;
    }

    void add(num a, num b)
    {
            int i;
            int len = max(a->len, b->len);
            int re = 0;
            for(i = 0; i < len; i++){
                    a->num[i] += b->num[i] + re;
                    re = a->num[i] / used;
                    a->num[i] %= used;
            }
            if(re > 0){
                    a->num[i] = re;
                    len++;
            }
            a->len = len;
    }

    void output(num a)
    {
            int i;
            int len = a->len,     num = a->num;
            printf("%d", num[len – 1]);
            len–;
            for(i = len – 1; i >= 0; i–){
                    printf("%.*d", bits, num[i]);
            }
    }

    int main(void)
    {
            int i, j;
            int n, s, k, t, l;
            scanf("%d%d", &s, &n);
            k = 1 << s;
            t = (n – 1) / s + 1;
            if(t > k){                     //一直没写这个~!! 所以可能会出现各种想象不到的情况, 如:t = 3000
                    t = k;
            }
            for(i = 0; i < k; i++){
                    give(&f[0][i], 1);
            }
            for(i = 1; i < t; i++){
                    for(j = k – i – 1; j >= 1; j–){
                            add(&f[i][j], &f[i][j + 1]);
                            add(&f[i][j], &f[i – 1][j + 1]);
                    }
            }
            for(i = 1; i < t; i++){
                    for(j = k – i – 1; j >= 1; j–){
                            add(&ans, &f[i][j]);
                    }
            }
            l = n % s;
            if(l == 0){
                    l = k;
            }else{
                    l = 1 << l;
            }
            for(i = 1; i < l; i++){
                    add(&ans, &f[t – 1][i]);
            }
            output(&ans);
            printf("\n");
            return 0;
    }