SDNU_ACM_ICPC_2019_Winter_Practice_1st【解题报告】

发表于 | 更新于 | 分类于
－－－－－－－－－－－－－SDNU ACM集训队 2019寒假训练 第一场－－－－－－－－－－－－－ 

        

        

A - The kth great number【模拟】【vector】
[HDU - 4006 ]


一看这个题，求第k大数，以为是主席树呢。仔细一看，哦，用vector模拟一下就行了。


后来看其他队员也有用multiset和priority_queue的，嗯，可以趁这个机会学习一下它们的用法。


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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

char op;
int n, k, t;
int main()
{
    while(~scanf("%d%d", &n,&k))
    {
        vector<int> G;
        while(n--)
        {
            cin >> op;
            if(op == 'I')
            {
                scanf("%d", &t);
                int pos = lower_bound(G.begin(), G.end(), t) - G.begin();
                G.insert(G.begin() + pos, t);
            }
            else
            {
                printf("%d\n", G[G.size() - k]);
            }
            /*
            for(int i = 0; i < G.size(); ++i)
                cout << G[i] << ' ';
            cout << '\n';
            */
        }
    }
    return 0;
}


B - A Trivial Problem【数学】
CodeForces - 633B


题意：
给出一个数m，求阶乘末尾有m个0的数的个数及这些数。


思路：
一眼望去，以为是这个题，又读了一遍发现这个是“反着求”。


以为是规律，然后写几项看看吧，写了m = 30多时的答案还是没看出什么来。


休息了一会想到还是用上面那个题的代码，因为要求的序列和m的关系是单调的，所以或许可以通过二分枚举答案，接着试了试上界，序列中的数最大到400009，好了可以二分了。最后只要把符合要求的存一下，问题就解决了。


MyCode：
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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

int n;
int solve(int t)
{
    int cnt = 0;
    while(t)
    {
        t /= 5;
        cnt += t;
    }
    return cnt;
}
int main()
{
    scanf("%d", &n);
    int r = 400010, l = 0, m;
    int idx = 0;
    while(l <= r)
    {
        m = (r + l) >> 1;
        if(solve(m) < n)
        {
            idx = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }
    vector<int> res;
    for(int i = idx; ; ++i)
    {
        if(solve(i) == n)
            res.push_back(i);
        else if(solve(i) > n)
            break;
    }
    printf("%d\n", res.size());
    for(int i = 0; i < res.size(); ++i)
        printf("%d ", res[i]);
    return 0;
}


C - New Skateboard【模拟】【分类讨论】
CodeForces - 628B


题意：
给出一个字符串，求出其中的连续&&满足“数值”为4的倍数的子序列的数量。


思路：
纸上写一写，然后分类讨论一下就行了。


MyCode：
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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 300010;

int len;
char s[N];
long long res;
int main()
{
    scanf("%s", s);
    len = strlen(s);
    for(int i = len - 1; i >= 0; --i)
    {
        if((s[i] - '0') % 4 == 0)   //0、4、8
        {
            ++res;
            if(i > 0)
            {
                res += ((s[i-1] - '0') % 2 == 0) ? i : 0;
            }
        }
        else if((s[i] - '0') % 2 == 0) //2、6
        {
            if(i > 0)
            {
                res += ((s[i-1] - '0') % 2 != 0) ? i : 0;
            }
        }
    }
    printf("%lld\n", res);
    return 0;
}


D - Color the ball【前缀和或线段树】
HDU - 1556 


一眼望去线段树。观察选手代码长度，自信$n^2​$莽了一发，收获TLE。老老实实上线段树AC。


AC后发觉事情不太对，这个前缀和应该也可以的，但一时没想起来怎么写。赛后搜了一下不由感叹：秒啊秒啊。


具体一点就是在增加数字的区间两端进行标记，左端点+1右端点的右边坐标-1，这样某个区间的次数就是从1坐标到这个位置的数值之和了。


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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 100010;

int n, x, y, a[N];
int main()
{
    while(scanf("%d", &n) && n)
    {
        memset(a, 0, sizeof(a));
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d%d", &x,&y);
            ++a[x];
            --a[y + 1];
        }
        for(int i = 1; i <= n; ++i)
        {
            a[i] += a[i-1];
            printf("%d%c", a[i], i == n ? '\n' : ' ');
        }
    }
    return 0;
}


E - 非常可乐【BFS或数学】
HDU - 1495


kuangbin专题一做过，当时BFS过的，看选手代码发现怎有如此短的代码？打开一看用了gcd什么的，不太懂，等督促数学选手水哥写完博客后大家可直接去访问他的博客(UPD:已更新，点击打开对应文章链接)。


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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int N = 111;

int s, n, m, rq[5];
bool vis[N][N][N];
struct node
{
    int num[3], out;
} now, nex;

void BFS(int s, int n, int m)
{
    memset(vis, 0, sizeof(vis));
    queue<node> Q;
    now.num[0] = s;
    now.num[1] = n;
    now.num[2] = m;
    now.out = 0;
    Q.push(now);
    vis[s][n][m] = 1;
    while(!Q.empty())
    {
        now = Q.front();
        Q.pop();
        for(int i = 0; i < 2; ++i)
            for(int j = 0; j < 3; ++j)
            {
                if(i == j)
                    continue;
                if(now.num[i] == now.num[j] && now.num[3-i-j] == 0)
                {
                    printf("%d\n", now.out);
                    return ;
                }
            }

        for(int i = 0; i < 3; ++i)
        {
            for(int j = 0; j < 3; ++j)
            {
                if(i == j)
                    continue;
                if(now.num[i] + now.num[j] <= rq[j])
                {
                    nex.num[j] = now.num[j] + now.num[i];
                    nex.num[i] = 0;
                }
                else
                {
                    nex.num[i] = now.num[i] - (rq[j] - now.num[j]);
                    nex.num[j] = rq[j];
                }
                for(int k = 0; k < 3; ++k)
                {
                    if(k == i || k == j)
                        continue;
                    nex.num[k] = now.num[k];
                }
                nex.out = now.out + 1;
                if(vis[nex.num[0]][nex.num[1]][nex.num[2]] == 0)
                {
                    vis[nex.num[0]][nex.num[1]][nex.num[2]] = 1;
                    Q.push(nex);
                }
            }
        }
    }
    puts("NO");
}

int main()
{
    int s, n, m;
    while(scanf("%d%d%d", &s,&n,&m) && s)
    {
        rq[0] = s, rq[1] = n, rq[2] = m;
        BFS(s, 0, 0);
    }
    return 0;
}


F - 今夕何夕【模拟】
HDU - 6112 


2017百度之星初赛签到题。。其实并不难的，就是模拟一下日期，注意一下闰年就完了，不知道为啥做的人这么少。


记得有个公式(蔡勒公式)直接算日期的，找之前的板子没找到，然后直接按百度百科的抄上了，结果姿势有点不太对TLE了两次，最后老老实实模拟了。


哦对了，这题的输入格式，还有大爷直接字符串 + gets然后再转化为int变量，为啥不直接格式读入。。？？


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 <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int t, yy, mm, dd, res;
bool leap(int year)
{
    if(year % 400 == 0) return 1;
    if(year % 100 == 0) return 0;
    return year % 4 == 0;
}
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d-%d-%d", &yy,&mm,&dd);

        int sum = 0;
        if(mm == 2 && dd == 29)
        {
            for(int i = yy + 1; ; ++i)
            {
                sum += 365;
                if(leap(i)) ++sum;
                sum %= 7;
                if(leap(i) && !sum)
                {
                    res = i;
                    break;
                }
            }
        }
        else if(mm < 3)
        {
            for(int i = yy + 1; ; ++i)
            {
                sum += 365;
                if(leap(i - 1)) ++sum;
                sum %= 7;
                if(!sum)
                {
                    res = i;
                    break;
                }
            }
        }
        else
        {
            for(int i = yy + 1; ; ++i)
            {
                sum += 365;
                if(leap(i)) ++sum;
                sum %= 7;
                if(!sum)
                {
                    res = i;
                    break;
                }
            }
        }

        printf("%d\n", res);
    }
    return 0;
}


G - 第几天？【模拟】
HDU - 2005 


签到题，判断闰年。简单提一点，还是上面说的，注意格式读入。。


等会，有人写了好几kb的代码，打开一看十几个if-else，我哭了。。你们通过这种写法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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int yy, mm, dd, res;
int a[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
bool leap(int year)
{
    if(year % 400 == 0) return 1;
    if(year % 100 == 0) return 0;
    return year % 4 == 0;
}
int main()
{
    while(~scanf("%d/%d/%d", &yy,&mm,&dd))
    {
        res = dd;
        for(int i = 1; i < mm; ++i)
            res += a[i];
        if(mm > 2 && leap(yy))
            ++res;
        printf("%d\n", res);
    }
    return 0;
}


H - 最大子矩阵【二维前缀和】
HDU - 1559 


典型的动态规划问题，也是利用前缀和进行求解。


用$sum[i][j]$表示起点为矩形左上角这个点为右下角的矩阵的元素之和，最后枚举大小为$x \times y$的矩阵时枚举左上角位置后，右下角的位置就是$(i+x-1,j+x-1)$，自己画图减一下就能看出来，最后的答案就是：


$sum[i+x-1][j+y-1] - sum[i+x-1][j-1] - sum[i-1][j+y-1] + sum[i-1][j-1]$，


为了避免数组下标出现负数的情况，我存图用的下标是从1开始的。


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 <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1111;

int t, n, m, x, y, a[N][N], sum[N][N];
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d%d", &n,&m,&x,&y);
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                scanf("%d", &a[i][j]);

        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                sum[i][j] = a[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];

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

        printf("%d\n", res);
    }
    return 0;
}


I - Help is needed for Dexter【规律】
UVA - 11384 


不知道如此简单的一道题为啥没人做。。


题目大意：
这里有1~n共n个数，你每次可以选取其中的若干数个让他们减去一个你指定的数(中途不得出现负数)，问最少经过多少次操作能使得所有的数变为0。


解题思路：
找了几个数写出来看了看，很显然的规律题。


具体过程：


1        1次


1 2        经过一次变换可以转化为1 1        共需要2次


1 2 3    经过一次变换可以转化为1 0 1        共需要2次


1 2 3 4    经过一次变换可以转化为1 2 1 2    共需要3次


1 2 3 4 5 经过一次变换可以转化为1 2 0 1 2    共需要3次


…………


就是经过尽量少次数的变换让他们变成前面出现过的就行了，就提示到这，一定要自己推出来并AC掉呀。


MyCode：
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 <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
int res[33] = {1, 2};
void init()
{
    for(int i = 2; i <= 32; ++i)
        res[i] = res[i - 1] * 2;
}
int main()
{
    init();
    while(~scanf("%d", &n))
    {
        for(int i = 1; ; ++i)
        {
            if(res[i] > n)
            {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}


J - find your present (2)【二进制】
HDU - 2095 


签到题，可以直接stl容器存，也可以直接利用异或的性质进行求解。


这个题开场4分钟就被A掉，看来确实是有人对学过的知识还有印象。


代码还是不够精简啊，根本不需要数组，直接三个变量就能A掉，精简代码也是挺重要的。。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int t, res, tem;
int main()
{
    while(scanf("%d", &t) && t)
    {
        res = 0;
        for(int i = 0; i < t; ++i)
        {
            scanf("%d", &tem);
            res ^= tem;
        }
        printf("%d\n", res);
    }
    return 0;
}


END：
这里面大部分是QDU去年算法协会给17级的出的题目，所以并不难，大家做成这样emmm。总之还差得远呢，好好利用寒假吧，开学后各种事又会忙起来，争取这个假期能有质的飞跃。


自己还感受到好久不打比赛后，这样一做还真有些吃力，这个东西，还是不要放下太久，不然要重新捡起来又要费好大劲。


      
    

    
    
    

    

    
      

        

  
Donate comment here

  
  



      

    

    
      

        

      

    

    
  


  
  
  
  




    

      


      

      
    

  



          

          


          
  

    
      

    
  



        

        
          
  
  

    

      
      
      
    

  


  


        
      

    


    

    
      

        
        
          0%