欢迎
首页 标签 归档 友链 Page

HDU Page11(2051～2066)

2020-03-15

2053 Switch Game

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>

void switchLamp(int * status) {
    if (*status) {
        *status = 0;
    } else {
        *status = 1;
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    
    //注意题中0<n<=10^5,我一开始写成了10005，所以出现了Runtime Error(ACCESS_VIOLATION)
    int n, statuss[100005];
    
    while (scanf("%d", &n) != EOF) {
        for (int i=1; i<=n; i++) {
            statuss[i] = 0;
        }
        for (int i=1; i<=n; i++) {
            for (int j=i; j<=n; j += i) {
                switchLamp(&statuss[j]);
            }
        }
        printf("%d\n", statuss[n]);
    }

    return 0;
}

2054 A == B ?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/*
 这道题目中没有说数字的大小所以不能用判断整数是否相等的方法，而且有可能是小数，换言之，
 不能定义成int型，可能数字很大，所以只能用字符串来存储。。
 判断字符串是否相等，要先去掉其前面的0，还有去掉后面的0，还要判断去掉后面的0后，最后一个字符是不是小数点，如果是的话，也要去掉。。。
 */

#include <stdio.h>
#include <string.h>

int main(int argc, const char * argv[]) {
    // insert code here...

    char n[100005], m[100005];
    
    while (scanf("%s %s", n, m) != EOF) {
        int nn = 0, mm = 0, nlength = 0, mlength = 0;
        nlength = (int)strlen(n);
        mlength = (int)strlen(m);
        for (int i=0; i<strlen(n); i++) {
            if (n[i] == '.') {
                nn = 1;
                
;
            }
        }
        if (nn) {
            for (int i=(int)strlen(n)-1; i>=0; i--) {
                if (n[i] == '0')
                    nlength--;
                else
                    
;
            }
        }
        //若是100.00这样，去除末尾的0后小数点也要去掉
        if (n[nlength-1] == '.')
            nlength--;
        for (int i=0; i<strlen(m); i++) {
            if (m[i] == '.') {
                mm = 1;
                
;
            }
        }
        if (mm) {
            for (int i=(int)strlen(m)-1; i>=0; i--) {
                if (m[i] == '0')
                    mlength--;
                else
                    
;
            }
        }
        if (m[mlength-1] == '.')
            mlength--;
        if (nlength == mlength) {
            int i;
            for (i=0; i<nlength; i++) {
                if (n[i] != m[i]) {
                    
;
                }
            }
            if (i == nlength)
                printf("YES\n");
            else
                printf("NO\n");
        } else
            printf("NO\n");
    }

    return 0;
}

2055 An Easy Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//a = -(ASCII: 97 - 96)
//A = ASCII: 65 - 64
//getchar（）用于接收每次scanf后多余的字符‘\n’，注意啊，因为这里有一个是取%c的，所以一定要，否则错误

#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...

    int n, y;
    char x;

    scanf("%d", &n);
    getchar();
    while (n--) {
        int f = 0;
        scanf("%c %d", &x, &y);
        getchar();
        if (x >= 65 && x <= 90)
            f = x - 64;
        else
            f = 96 - x;
        
        printf("%d\n", f + y);
    }
    
    return 0;
}

2056 Rectagles

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>

void swap(double *a, double *b) {
    double temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

double min(double a, double b) {
    return a > b ? b : a;
}

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

int main(int argc, const char * argv[]) {
    // insert code here...

    double x1, y1, x2, y2, x3, y3, x4, y4;
    
    while (scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4) != EOF) {
        //保证左边是右下角，右边的数是左上角
        if (x1 > x2)
            swap(&x1, &x2);
        if (y1 > y2)
            swap(&y1, &y2);
        if (x3 > x4)
            swap(&x3, &x4);
        if (y3 > y4)
            swap(&y3, &y4);
        
        double myX1 = max(x1, x3);
        double myY1 = max(y1, y3);
        double myX2 = min(x2, x4);
        double myY2 = min(y2, y4);
        
        printf("%.2lf\n", myX1 > myX2 || myY1 > myY2 ? 0: (myY2-myY1) * (myX2-myX1));
    }
    
    return 0;
}

2057 A+B Again

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//#include <stdio.h>
//#include <string.h>
//#include <stdlib.h>
//
//long long int HexaStrToDec(char *a) {
//    long long int sum = 0;
//    long long int index = 1;
//    for (int i=(int)strlen(a)-1; i>=0; i--) {
//        if (a[i] >= 'A' && a[i] <= 'Z')
//            sum += index * (a[i] - 55);
//        else
//            sum += index * (a[i] - 48);
//
//        index *= 16;
//    }
//    return sum;
//}
//
//char str[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
//char* decToStr(long long int sum) {
//    char *s;
//    s = (char *)malloc(sizeof(char)*16);
//    int index = 0;
//
//    if (sum == 0) {
//        return "0\0";
//    }
//    while (sum) {
//        s[index++] = str[sum % 16];
//        sum /= 16;
//    }
//    int length = (int)strlen(s);
//    for (int i=0; i<length/2; i++) {
//        char temp = s[i];
//        s[i] = s[length-i-1];
//        s[length-i-1] = temp;
//    }
//
//    return s;
//}
//
//int main(int argc, const char * argv[]) {
//    // insert code here...
//
//    char a[17], b[17];
//
//    while (scanf("%s %s", a, b) != EOF) {
//        if (!(a[0] == '+' || a[0] == '-')) {
//            for (int i=(int)strlen(a)-1; i>=0; i--) {
//                a[i+1] = a[i];
//            }
//            a[0] = '+';
//        }
//        if (!(b[0] == '+' || b[0] == '-')) {
//            for (int i=(int)strlen(b)-1; i>=0; i--) {
//                b[i+1] = b[i];
//            }
//            b[0] = '+';
//        }
//        long long int aa = HexaStrToDec(a+1);
//        long long int 百度翻译 = HexaStrToDec(b+1);
//
//        if (a[0] == '+' && b[0] == '+') {
//            printf("%s\n", decToStr(aa + 百度翻译));
//        } else if (a[0] == '-' && b[0] == '-') {
//            printf("-%s\n", decToStr(aa + 百度翻译));
//        } else if (a[0] == '-' && b[0] == '+') {
//            if (aa > 百度翻译)
//                printf("-%s\n", decToStr(aa-百度翻译));
//            else
//                printf("%s\n", decToStr(百度翻译-aa));
//        } else if (a[0] == '+' && b[0] == '-') {
//            if (aa >= 百度翻译)
//                printf("%s\n", decToStr(aa-百度翻译));
//            else
//                printf("-%s\n", decToStr(百度翻译-aa));
//        }
//    }
//
//    return 0;
//}

//哇，原来C语言对于16进制的额支持也不错啊，牛逼
#include<stdio.h>
int main()
{
    long long n,m,v;
    while(scanf("%llx %llx",&n,&m)==2)
    {
        v=n+m;
        if(v<0)
        {
            v=-v;
            printf("-%llX\n",v);
        }
        else
            printf("%llX\n",v);
    }
     return 0;
}

2058 The Sum Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//以下超时哥，连续数组么，首相加尾乘项除以二啊，傻了
//#include <stdio.h>
//
//int main(int argc, const char * argv[]) {
//    // insert code here...
//
//    long long int a, b;
//
//    while (scanf("%lld %lld", &a, &b) && (a || b)) {
////        if (a == 0 && b == 0) {
////            
;
////        }
//
//        long long int sum = 0, start = 1;
//
//        for (long long int i=1; i<=b+1; i++) {
//            if (sum == b) {
//                printf("[%lld,%lld]\n", start, i-1);
//                sum += i;
//            } else if (sum > b) {
//                sum -= start;
//                start++;
//                i--;
//            } else
//                sum += i;
//            if (start > b) {
//                
;
//            }
//        }
//    }
//
//    return 0;
//}


/*
 我本来的想法是考虑子列的起点和终点，分别以s和e表示，由等差数列求和公式有
 （s+e）*（e-s+1）/2==M（1式），化为e*(e+1)-s*(s-1)==2*M, so ,e=(int)sqrt(2*M+s*(s-1)),
 将得到的e再代回1式，成立则[s,e]满足条件。
 但是，2*M+s*(s-1)太大……

 后来参考网上的一个算法，不考虑子列的终点，而是考虑子列的起点和子列元素的个数，分别记为i，j。
 由等差数列求和公式，得(i+(i+j-1))*j/2==M，即（2*i+j-1）*j/2==M（2式），
 故得i=（2*M/j-j+1）/2，将i，j代回2式，成立则[i,i+j-1]满足条件。注意j最小为1，而由2式，
 得（j+2*i）*j=2*M，而i>=1，故j*j<=(int)sqrt(2*M).
 */
#include <stdio.h>
#include <math.h>

int main(int argc, const char * argv[]) {
    // insert code here...

    long long int a, b;
    
    while (scanf("%lld %lld", &a, &b) && (a || b)) {
        
        int num = sqrt(2 * b);//数列的个数
        
        for (int j=num; j>0; j--) {
            int i = (int)(2 * b / j - j + 1) / 2; //首项
            if (j * (i + i + j-1) / 2 == b) {
                printf("[%d,%d]\n", i, i+j-1);
            }
        }
        printf("\n");
    }

    return 0;
}

2063 过山车

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//趣写算法系列之--匈牙利算法 https://blog.csdn.net/dark_scope/article/details/8880547

#include <stdio.h>
#include <string.h>

int k, m, n;
int rel[510][510];  //男生和女生的关系
int used[510];      //main中一个for循环一次中有没有被标记过已经查找了女生是否已经找到
int boy[510];       //表示这个男的已经被哪一个编号的人找到了

int find(int x) {
    //查找这个女生x能匹配到的男生，我对对每一个要被匹配的男生都遍历的
    //注意是1～m
    for (int j=1; j<=n; j++) {
        //如果这个男的和女的可以有关系，而且对这个女生查找的所有遍历过程中这个男我曾试图改变过他所属的女生，但是没有结果
        if (rel[x][j] && !used[j]) {
            used[j] = 1;

            //如果这个男的还没有被匹配或者（可以改变这个男的现在匹配到的女的匹配男），就把这个男的给让出来了
            if (boy[j]==0 || find(boy[j])) {
                boy[j] = x;//将这个男的的归属定为 x
                return 1;
            }
        }
    }

    return 0;
}

int main(int argc, const char * argv[]) {
    // insert code here...

    while (scanf("%d", &k) && k != 0) {
        scanf("%d %d",&m, &n);
        //m是女生，n是男生
        //现在是女生可以配对多个男生，问最多一一的组合

//        for (int i=0; i<501; i++) {
//            for (int j=0; j<501; j++) {
//                rel[i][j] = 0;
//            }
//        }
//        for (int i=0; i<501; i++) {
//            used[i] = 0;
//        }
        //memset在string.h中
        memset(rel, 0, sizeof(rel));
        memset(boy, 0, sizeof(boy));
        memset(used, 0, sizeof(used));

        int a, b;
        for (int i=0; i<k; i++) {
            scanf("%d %d", &a, &b);
            rel[a][b] = 1;
        }
        int sum = 0;
        //注意1～m
        for (int i=1; i<=m; i++) {
            //menset在string.h中
            memset(used, 0, sizeof(used));    //这个在每一步中清空
            if (find(i))
                sum++;
        }
        printf("%d\n",sum);
    }

    return 0;
}

2064 汉诺塔3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
 题中改变了原有的汉诺塔规则，而是每次必须经过中间的柱子，尽管有些许变化但是推到过程是一样的
（现设有A，B，C三个柱子，以及标号为1-N的盘子），既然不能将编号为N的盘子移动到C上，那么就
必须先移动N到B上，这样的话就先有N- 1个盘子在C上这个状态，然后在移动N到C上之前又要把N-1个
盘子移动到A上，要达到最终目的的话，就要再把N-1个盘子移动到C上。
上述过程就得到一个递推式 F[N]= 3 F[N-1]+ 2, 得到F[N]= 3^ N- 1*。
该3与普通的区别就是需要从中间过渡，所以这个3必须要从柱1到柱3经柱2才能算一个，
 或者从柱3到柱1经柱2才能算一个，而普通的只要柱子1到柱子2也可以算一个的，品、细品
 */

#include <stdio.h>

long long int hannuota3(int hight) {
    if (hight == 1)
        return 2;
    else
        return 3 * hannuota3(hight-1) + 2;
}

int main(int argc, const char * argv[]) {
    // insert code here...

    int hight;
    
    while (scanf("%d", &hight) != EOF) {
        printf("%lld\n", hannuota3(hight));
    }

    return 0;
}

2065 “红色病毒”问题（指数型母函数）

“红色病毒”问题
母函数问题
解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//https://blog.csdn.net/yu121380/article/details/79914529
//https://www.cnblogs.com/whatbeg/p/3729019.html
//https://cloud.tencent.com/developer/article/1390233

#include <stdio.h>

//这样超时，要更快一点才行
//int myPow(int a, int b) {
//    int sum = 1;
//
//    while (b--) {
//        sum = sum * a % 100;
//    }
//
//    return sum;
//}

//快速幂
//快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高
//啊啊啊，一开始我使用了快速幂还是超时呀，然后我发现这个b是long int，太小了所以还是超时呀
int myFastPow(int a, long long b) {
    int sum = 1;

    a %= 100;
    while (b) {
        if(b&1)
            sum = (sum*a) % 100;
        b >>= 1;
        a = (a * a) % 100;
    }

    return sum;
}

int main(int argc, const char * argv[]) {
    // insert code here...

    int cases;
    long long int n;

    while (scanf("%d", &cases) && cases) {
        for (int i=1; i<=cases; i++) {
            scanf("%lld", &n);
            
            printf("Case %d: %d\n", i, (myFastPow(4, n-1) + myFastPow(2, n-1)) % 100);
        }
        printf("\n");
    }

    return 0;
}

//#include <stdio.h>
//
//#define MODER 100
//
////快速幂
////快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高
//int QPow(int base, long long pow)
//{
//    int res = 1;
//
//    if (pow == 0)
//        return 1;
//
//    base %= MODER;
//    while(pow) {
//        if (pow&1) {
//            res = (res*base)%MODER;
//        }
//        base *= base;
//        base %= MODER;
//        pow >>= 1;
//    }
//
//    return res%MODER;
//}
//
//int main()
//{
//    int T;
//    long long N;
//    int i;
//    while(scanf("%d", &T) == 1 && T) {
//        for(i=1;i<=T;++i) {
//            scanf("%lld", &N);
//            printf("Case %d: %d\n", i, (QPow(4, N-1) + QPow(2, N-1)) % MODER);
//        }
//        printf("\n");
//    }
//    return 0;
//}
//

2066 一个人的旅行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//需要用到Dijkstra算法
//https://blog.csdn.net/winter2121/article/details/55805391
//https://blog.csdn.net/winter2121/article/details/55805210

#include <stdio.h>
#include <string.h>

//9个0
int maxNum = 1000000000;

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

int main(int argc, const char * argv[]) {
    // insert code here...
    
    int distances[1005][1005], favoriteCities[1005], shortestDistances[1005], marked[1005], cityNumbers = 0;
    int T, S, D;
    
    while (scanf("%d %d %d", &T, &S, &D) != EOF) {
        //这个初始化好像不太好，如果不是全部初始化成0的话
//        memset(distances, maxNum, sizeof(distances));
        for(int i=0; i<1005; i++) {
            for (int j=0; j<1005; j++) {
                distances[i][j] = maxNum;
            }
        }
        memset(favoriteCities, 0, sizeof(favoriteCities));
        memset(marked, 0, sizeof(marked));
//        memset(shortestDistances, maxNum, sizeof(shortestDistances));
        for (int i=0; i<1005; i++) {
            shortestDistances[i] = maxNum;
        }
        cityNumbers = 0;
        
        int a, b, c;
        for (int i=0; i<T; i++) {
            scanf("%d %d %d", &a, &b, &c);
            if(c>distances[a][b])  //坑, 这两城市有重复的路
                continue;
            distances[a][b] = distances[b][a] = c;
            cityNumbers = max(max(a, b), cityNumbers);
        }
        
        //与草儿家相邻的城市，直接距离为0貌似
        for (int i=0; i<S; i++) {
            scanf("%d", &a);
            distances[0][a] = distances[a][0] = 0;
        }
        
        //草儿想去的城市,一开始误写成了S，所以WA
        for (int i=0; i<D; i++) {
            scanf("%d", &a);
            favoriteCities[a] = 1;
        }
        
        //初始化，只有草儿家在内,其实这里面只会有相邻的城市且距离0
        //i=0,表示草儿家
        for (int i=1; i<=cityNumbers; i++) {
            shortestDistances[i] = distances[0][i];
        }
        
        //虽然题目只要找到喜爱的城市的最短距离，我现在找了草儿家到所有，而且一次循环能找到一个
        for (int i=1; i<=cityNumbers; i++) {
            //此循环为了找到 目前未访问(不在S中的，S为已求的的最短路径的点的集合) 的且 距起点最近 的城市
            int min = maxNum, minNum = -1;
            for (int j=1; j<=cityNumbers; j++) {
                //一开始不小心下面有一个j写成了i
                if (!marked[j] && min > shortestDistances[j]) {
                    min = shortestDistances[j];
                    minNum = j;
                }
            }
            //如果没找到未标记的城市号，说明计算结束
            //下面这个
是要的，因为可能有的地方到不了都是max的，所以这个时候可以退出循环了，剩下没有标记的city都去不了
            if(minNum==-1)
                
;
            marked[minNum] = 1;
            
            //已经找到了未在S中的点，现在加入，所以要更新shortestDistances
            for (int j=1; j<=cityNumbers; j++) {
                if (shortestDistances[j] > shortestDistances[minNum] + distances[minNum][j]) {
                    shortestDistances[j] = shortestDistances[minNum] + distances[minNum][j];
                }
            }
        }
        
        int shortest = maxNum;
        for (int j=1; j<=cityNumbers; j++) {
            if (favoriteCities[j] && shortest > shortestDistances[j]) {
                shortest = shortestDistances[j];
            }
        }
        
        printf("%d\n", shortest);
    }

    return 0;
}

Author: Jcwang

Permalink: http://example.com/2020/03/15/HDU-Page11(2051%EF%BD%9E2065)/

updated at 2022-10-15

# OJ
Previous Post
HDU Page11(2067～2080)
Next Post
HDU Page11(2041～2050)递推