SDNU_ACM_ICPC_2019_Winter_Practice_1st题解报告

这篇文章是关于SDNU_ACM_ICPC_2019_Winter_Practice_1st的题解.

这几天四处去过年，闲下来建博客，抽时间打比赛，现在终于建立好了博客，也到快到大年三十了，终于闲下来可以理理题解发发博文了。 我t喵的建好了博客，想什么时候提交博文就什么时候提交，csdn再贱!

这是寒假第一场，，有些没回过来，，，放纵自己的后果，，就是比赛只能三题下场，，

A - The kth great number

HDU - 4006

题意：找出第k大数，输入n和k，之后n行输入，前缀为Q输出第k大数，前缀为I输入数据进入队列

题解：这题证明我还没熟练stl，，，第一下想到的是数组，用数组模拟一下也能出来，就是麻烦 当时模拟出来了，，但是没看到题干的多组数据输入，就一直w，， 

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
#include<bits/stdc++.h>
using namespace std;

int nn[1000010];

bool cmpp(int a, int b)
{
    return a > b;
}

int main()
{
    int n, k;
    while(~scanf("%d%d", &n, &k)){

    for(int i = 0; i < n; i++){
        char aim;
        int num;
        cin>> aim;
        if(aim == 'I')scanf("%d", &num);
        if(i == k)sort(nn, nn + k, cmpp);//凑满k个数后sort一下，然后就从第k个替换就行
        switch(aim){
    case 'I':if(i < k)nn[i] = num;
            else {
                if(num <= nn[k - 1])continue;
                else {
                        nn[k - 1] = num;
                            for(int j = k - 1; j  >= 1; j--){
                                if(nn[j] > nn[j - 1])
                                {
                                    int t = nn[j];
                                    nn[j] = nn[j - 1];
                                    nn[j - 1] = t;
                                }
                                else break;
                            }
                    }
            }
            break;
    case 'Q':
        cout<< nn[k - 1] <<'\n';
        }
    }
    }

    return 0;
}

用上stl后便能简便解决了，用lower函数找到输入数字应该在的地方插进去就行 

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
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n, k;
    while(~scanf("%d%d", &n, &k)){

    vector<int>v;

    while(n--){
        char aim;
        cin>> aim;
        if(aim == 'I'){
            int num;
            scanf("%d", &num);
            int pla = lower_bound(v.begin(), v.end(), num) - v.begin();
            v.insert(v.begin() + pla, num);
        }
        else {
            printf("%d\n", v[v.size() - k]);
        }
    }
    }

    return 0;
}
--- ## B - A Trivial Problem CodeForces - 633B

题意：问有哪些数的阶乘末尾有m个0，输入m，输出总共有几个数达到要求，再输出是哪几个数

题解：数的阶乘：n！ = n(n-1)(n-2)...21 阶乘有几个零和阶乘中出现了几个5有关，且25 == 155， 50 == 255， 从1往后数每五个数出现一个5， 每55个数出现两个五，以此类推，所以 

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
#include<bits/stdc++.h>
using namespace std;

int five(int n)
{
    int q = 0;
    while(n){
        q += n / 5;
        n /= 5;
    }
    return q;
}

int main()
{
    int n;
    scanf("%d", &n);
    int i = 5, t;
    while(1){
        t = five(i);
        if(t >= n)break;
        i += 5;
    }
    if(t == n){
        puts("5");
        printf("%d", i);
        for(int j = 0; j < 4; j++)printf(" %d", ++i);
    }
    else puts("0");

    return 0;
}

## C - New Skateboard CodeForces - 628B
题意：输入一个数字字符串，求其中有多少个能被四整除的连续子串 ### 参考资料：整除规则（原理，性质）
题解：根据参考资料， 一个整数的末尾两位数能被4整除则这个数能被4整除，单独判断第一个数能否被四整除，如果能本身就作为一个子串加一，之后除了单独判断当前数本身， 再判断i - 1的数和当前位i组成的两位数能否被四整除，如果能，加上前面那些数就能组成i个能被四整除的字串,还有一个坑就是这道题数据很多，得用longlong，， 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int Ma = 3e5 + 100;
char s[Ma];

int main()
{
    gets(s);
    int n = strlen(s);
    ll sum = 0;
    for(int i = 0; i < n; i++){
        if((s[i] - '0') % 4 == 0)sum++;
        if(i != 0 && ((s[i] - '0') + 10 * (s[i - 1] - '0')) % 4 == 0)sum += i;
    }

    printf("%lld\n", sum);
    return 0;
}

D - Color the ball

HDU - 1556

题意：给n个气球， 再有n行输入数据，分别为a和b，每行把气球编号a到b都涂一次色，问最后每个气球被涂色的次数

题解：把区间左端加一，右端外面减一，输出时从左段加到右端，边加边输出，正解Albert_s说是线段树，muyu_说是差分，只有我什么都不会，，那我去把这两个都学了吧，， 

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
#include<bits/stdc++.h>
using namespace std;

int ball[100100];

int main()
{
    int t;
    while(~scanf("%d", &t) && t != 0){
        memset(ball, 0, sizeof(ball));
        int a, b;
        for(int jj = 0; jj < t; jj++){
        scanf("%d%d", &a, &b);
        ++ball[a], --ball[b + 1];
        }

        for(int i = 1; i <= t; i++){
            if(i != 1)putchar(' ');
            printf("%d", ball[i] += ball[i - 1]);
        }
        putchar('\n');
    }

    return 0;
}

E - 非常可乐

HDU - 1495

题意：裸bfs题，，但我常年bfs细节出错，，，re日常，，是时候总结一下了，，，

题解：裸的，但比赛时还是出错，，怎么就是会写错那些地方呢，，这次又是变量名写错了，，得总结学习一波命名艺术了看来，， 

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
#include<bits/stdc++.h>
using namespace std;

int s, n, m;
bool visit[110][110];

struct pz
{
    int ss, nn, mm, cs;
    pz(int sss, int nnn, int mmm, int cc): ss(sss), nn(nnn), mm(mmm), cs(cc) {};
};

bool bfs()
{
    queue<pz>q;
    q.push(pz(s, 0, 0, 0));
    visit[s][0] = false;
    while(!q.empty()){
        pz te = q.front();
        q.pop();
        if(te.ss == te.nn && te.ss + te.nn== s){
//            printf("%d %d\n", te.ss, te.nn);
            cout<< te.cs <<'\n';
            return false;
        }
        /*能用循环优化这里，，但当时没有这么写，，也加入总结计划里面吧*/
        int si = te.ss, ni = te.nn, mi = te.mm, ci = te.cs;
        /****************s倒入n和m***********safe***/
        if(si + ni >= n && visit[si - n + ni][n])q.push(pz(si - n + ni, n, mi, ci + 1)), visit[si - n + ni][n] = false;
        else if(visit[0][ni + si])q.push(pz(0, ni + si, mi, ci + 1)), visit[0][ni + si] =false;

        if(si + mi >= m && visit[si - m + mi][ni])q.push(pz(si - m + mi, ni, m, ci + 1)), visit[si - m + mi][ni] = false;
        else if(visit[0][ni])q.push(pz(0, ni, mi + si, ci + 1)), visit[0][ni] =false;
        /*****************n和m分别倒入s********safe*****/
        if(si + ni >= s && visit[s][ni - s + si])q.push(pz(s, n - s + si, mi, ci + 1)), visit[s][ni - s + si] = false;
        else if(visit[si + ni][0])q.push(pz(si + ni, 0, mi, ci + 1)), visit[si + ni][0] =false;

        if(si + mi >= s && visit[s][ni])q.push(pz(s, ni, m - s + si, ci + 1)), visit[s][ni] = false;
        else if(visit[si + mi][ni])q.push(pz(si + mi, ni, 0, ci + 1)), visit[si + mi][ni] =false;
        /*****************n和m互倒************/
        if(mi + ni >= m && visit[si][ni - m + mi])q.push(pz(si, ni - m + mi, m, ci + 1)), visit[si][ni - m + mi] = false;
        else if(visit[si][0])q.push(pz(si, 0, mi + ni, ci + 1)), visit[si][0] =false;

        if(ni + mi >= n && visit[si][n])q.push(pz(si, n, mi - n + ni, ci + 1)), visit[si][n] = false;
        else if(visit[si][ni + mi])q.push(pz(si, ni + mi, 0, ci + 1)), visit[si][ni + mi] =false;
    }
}

int main()
{
    while(~scanf("%d%d%d", &s, &n, &m) && s != 0){
    if(s % 2){
            cout<<"NO\n";
            continue;
    }
    memset(visit, 1, sizeof(visit));
    int t;
    if(n < m)t = m, m = n, n = t;

    if(bfs())cout<< "NO\n";
    }

    return 0;
}

## F - 今夕何夕 HDU - 6112
题意：给T个日期，求最近哪一年里同一个日子和今天的星期数一样（比赛根本没看这题，，
题解：模拟，注意二月二十九日和闰年，我看了Albert_s的题解后了解到了蔡勒公式，就帖蔡勒公式版的代码吧
对了，当我把蔡勒公式单独拿出来计算时tle了，直接return就a了，具体原因再看下，我觉得应该是取模运算的原因 
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
#include<bits/stdc++.h>
using namespace std;

int cl(int year, int month, int day)
{
  if (month == 1 || month == 2)
   year--, month += 12;
  int c = year / 100;
  int y = year % 100;
  return ((y + y / 4 + c / 4 - 2 * c + 26 * (month + 1) / 10 + day - 1)%7 + 7) % 7;
}

bool ryear(int n)
{
    return n % 400 == 0 ? true : n % 100 != 0 ? n % 4 == 0 : false;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--){
        int nn, yy, rr;
        scanf("%d-%d-%d", &nn, &yy, &rr);
        int aim = cl(nn, yy, rr);
        int i = 0;
        do{
            if(yy == 2 && rr == 29){
                i += 4;
                if(!ryear(nn + i))i += 4;
            }
            else ++i;
        }while(cl(nn + i, yy, rr) != aim);
        printf("%d\n", nn + i);
    }

    return 0;
}

G - 第几天？

HDU - 2005

题意：中文题意， 比上一题模拟简单，，而且是同类型的，，自己跟不动榜后还是该看下其他题，万一有会的呢， 总结， 为什么这么菜呢？？

题解：模拟，注意闰年

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
#include<bits/stdc++.h>
using namespace std;

int er;

void year(int n){
    if(n % 400 == 0 || n % 4 == 0 && n % 100 !=0)er = 29;
    else er = 28;
}

int main()
{
    int n, y, r;

    while(~scanf("%d/%d/%d", &n, &y, &r)){
    year(n);
    int sum = 0;
    for(int i = 1; i < y; i++)
    if(i == 2)sum += er;
    else if(i <= 7){
        if(i % 2)sum += 31;
        else sum += 30;
    }
    else {
        if(i % 2)sum += 30;
        else sum += 31;
    }

    printf("%d\n", sum + r);
    }
    return 0;
}
## H - 最大子矩阵 HDU - 1559
题意：中文题意，get到了新dp姿势，叫二维前缀和，画个图能很好很快理解
题解：新姿势的dp，存好每个点到最右下的那个点的和就好了 
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
#include<bits/stdc++.h>
using namespace std;

const int Ma = 1010;
int juz[Ma][Ma];

int main()
{
    int t;
    scanf("%d", &t);

    while(t--){
        int m, n, x, y;
        memset(juz, 0, sizeof(juz));
        scanf("%d%d%d%d", &m, &n, &x, &y);
        for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++){
            int t;
            scanf("%d", &t);
            juz[i][j] = t + juz[i - 1][j] + juz[i][j - 1] - juz[i - 1][j - 1];
        }

        int sum = 0;
        for(int i = 1; i <= m - x + 1; i++)
            for(int j = 1; j <= n - y + 1; j++)
            sum = max(sum, juz[i - 1][j - 1] - juz[i + x - 1][j - 1] - juz[i - 1][j + y - 1] + juz[i + x - 1][j + y - 1]);

        printf("%d\n", sum);
    }

    return 0;
}

I - Help is needed for Dexter

UVA - 11384

题意：给一个数n，生成一个1到n的序列，每次选任意数减去一个数，最后整个序列全为0，且中途不能出现负数，求最小次数

题解：找规律类型

1~n|最小次数

1 1

1 2 | 同时减去1，得到1，同上，所以为2；

1 2 3 | 2，3同时减去2，得1，同1，所以为2；

1 2 3 4 | 3， 4同时减去2，得1 2 1 2，同二，所以为3；

很快，我们便能发现规律，当数位偶数时，能一步处理后一半，得到与前一半相同，也是与n/2相同的序列，能通过递归解决，当数为奇数时，能一步减去中间的数，得到前半部分+0+与前半部分相同的后半部分，等同于[n/2],所以可以利用递归解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;

int dep(int n)
{
    if(n == 1)return 1;
    else return 1 + dep(n / 2);
}

int main()
{
    int n;
    while(~scanf("%d", &n)){
        printf("%d\n", dep(n));
    }

    return 0;
}

J - find your present (2)

HDU - 2095

题意：找到序列中出现一次的数

题解：做过相同的题，被强调过，异或解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    while(~scanf("%d", &n))
{
    if(n == 0)break;
    int t, tt;
    scanf("%d", &t);
    for(int i = 1; i < n; i++){
        scanf("%d", &tt);
        t ^= tt;
    }
    cout<< t <<'\n';
}
    return 0;
}

位运算的奇淫技巧

感觉又忘得差不多了呢

Comments

⬆︎TOP