2019 SDNU Contest 15 赛后总结

发表于 | 更新于 | 分类于 | 阅读次数：

比赛链接

5月4日比赛总结：各种纠结，各种WA。共A了4题，赛后又补了1道，也是因为细节问题，赛中没有过。

A题

告诉你出行的两种方式，就是日常中的出租车，起步价多少钱，超过几公里多少钱，然后让你求两种方式的差价是多少。关键问题在于要四舍五入。第一次WA是忘记返回double, 第二次WA是因为不是最终的答案四舍五入，而是说两种方式的答案分别进行四舍五入，再求差值（队友点睛之笔）。

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 <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
double jisuan1(int n,int wait)
{
    double sum = 0;
    if(n <= 3)
        return 10;
    if(n > 3 && n <= 10)
    {
        return 10 + (n - 3)*2;
    }
    if( n > 10)
    {
        return 24 +  (n - 10)*3;
    }
}
double jisuan2(int n ,int wait)
{
    double sum = 0;
    if(n <= 3)
        return 11.0;
    if(n > 3 && n <= 10)
    {
        return 11.0 + (n - 3)*2.5;
    }
    if( n > 10)
    {
        return 28.5 +  (n - 10)*3.75;
    }
}
int main()
{
    int t;
    int n,wait;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&wait);
        double a = jisuan1(n,wait);
        a += 0.4 * wait + 1;
        double b = jisuan2(n,wait);
        b += 0.625 * wait;
        if(b - int(b) >= 0.5)
        {
            b = ceil(b);
        }
        else{
            b = floor(b);
        }
         if(a - int(a) >= 0.5)
        {
            a = ceil(a);
        }
        else{
            a = floor(a);
        }
        cout << b- a << endl;
    }
}

B题

一度写的崩溃，本来写完了，后来发现我理解错了题，交上去WA了， 发现是n == 1的时候没有处理好，再交，AC。

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
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
int main()
{
    int t;
    cin >> t;
    int vis[13];
    int n;
    while(t--)
    {
        vector<char>V[21];
        scanf("%d",&n);
        string s[21];
        cin >> s[0];
        for(int i = 0; i < 12; ++i)
        {
            V[0].push_back(s[0][i]);
        }
        if(n == 1)
        {
            sort(s[0].begin(),s[0].end());
            cout << s[0] << '\n';
            continue;
        }
        memset(vis,0,sizeof(vis));
        for(int i = 1; i < n; ++i)
        {
            cin >> s[i];
            memset(vis,0,sizeof(vis));
            for(int j = 0; j < s[i].size(); ++j)
            {
                for(int k = 0; k < V[i - 1].size(); ++k)
                {
                    if(s[i][j] == V[i - 1][k] && !vis[k])
                    {
                        vis[k] = 1;
                        V[i].push_back(s[i][j]);
                        break;
                    }
                }
            }
        }
        string s3;
        for(int i = 0; i < V[n - 1].size(); ++i)
        {
            s3 += V[n-1][i];
        }
        sort(s3.begin(),s3.end());
        cout << s3;
        cout << '\n';
    }
}

H题

一个女孩，非常懒惰，喜欢睡觉，套用高中级部主任的话： 喜欢睡，回家睡去，然后她要卖东西给顾客，输入的是： 从第i个顾客获得利益，以及第i个顾客几分钟之后来。 现在让你求最大的平均利润，以及该利润下的最小的睡眠时间（为什么说最小呢，因为最大的平均利润可能有好几种情况），与队友已经讨论的很明白了，发现题目也并不难，但是后来才知道我们忽略了一个问题，也是网上很多人也犯得错误。 就是这句话：

1
if(i < n && t[i] + Max[i] >= t[i + 1]) continue;

我们只考虑了他在这种情况下可以卖给前i个人的最大平均利益，但是忘记了也要保证在此状态下，他必须在第i + 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
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
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
#include <cmath>
using namespace std;
const double inf = 0x3f3f3f3f;
int main()
{
    int T,n;
    double tt[1001],sump[1001],Max[1001],t[1001],p[1001];
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        sump[0] = 0;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%lf",&p[i]);
            sump[i] = sump[i - 1] + p[i];
        }
        tt[0] = 0;
        Max[0] = -1;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%lf",&t[i]);
            tt[i] = t[i] - t[i - 1];
            Max[i] = max(Max[i - 1], tt[i]);
        }
        double v[1001];
        double miner = -1.0;
        double miner1 = inf;
        for(int i = 1; i <= n; ++i)
        {
            v[i] = sump[i] / (i * 1.0);
            if(i < n && t[i] + Max[i] >= t[i + 1]) continue;
            if(v[i] >= miner)
            {
                miner = v[i];
            }
        }
        for(int i = 1; i <= n; ++i)
        {
            if(v[i] == miner)
            {
                if(i < n && t[i] + Max[i] >= t[i + 1]) continue;
                if(Max[i] < miner1)
                {
                    miner1 = Max[i];
                }
            }
        }
        printf("%.6f %.6f\n",miner1,miner);
    }
}

J题

求逆元模板，最让我们崩溃的题目，开场一出题，我直接开A这道，好兴奋啊，模板上去，第一个A完就行。嗯 ，就这样直到比赛剩下不到一个小时，我真的是最后一个A过去的QAQ。而且最后过的还是用的暴力，没用模板，因为此题的数据范围很小。我和队友一直在讨论拓展欧几里得的模板为什么不行，各种样例都试了。在比赛的最后几分钟，我想起来了一个问题。题目要求的是 (a x) % m == 1 % m , 在我的思想中，包括师哥在讲的时候，我始终认为右边的 % m是无关紧要的。因为我认为 1 % m 都为 1，直到遇到这个题，我想到如果m == 1，其实就是让你求 (a x) % 1 == 0 了 那么 x == 1 ，需要单独把这个样例特判一下就过了。看来主观臆断害人不浅。中间WA了大于3到4次还是因为 Exist 没有大写，我和队友都惊呆了。

代码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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
using namespace std;
int extend(int a,int b,int &x, int &y)
{

    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int d = extend(b, a % b,x,y);
    int t = x;
    x = y;
    y = t - a/b*y;
    return d;
}
int mod(int a,int n)
{
    int x,y;
    int d = extend(a,n,x,y);
    if(d == 1)return (x % n + n)% n;
    else return -1;
}
int main()
{
    int t;
    int a,n;
    cin >> t;
    while(t--)
    {
        cin >> a >> n;
        if(n == 1)
        {
        cout << 1 << '\n';
        continue;
        }
        int c = mod(a,n);
        if(c <= 0)
        {
            cout << "Not Exist" << '\n';
        }
        else
            cout << c << '\n';
    }
}

代码2：

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
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
#include <cmath>
using namespace std;
int main()
{
    int t, i, a, m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&a,&m);
        int flag = 0;
        for( i = 1; i <= 10000; ++i)
        {
            if((a * i) % m == (1 % m))
            {
                flag = 1;
                printf("%d\n",i);
                break;
            }
        }
        if(!flag)
        {
            printf("Not Exist\n");
        }
    }
}

K题

签到题目，题目挺长的。

说的是一男一女完猜拳的游戏。他们一开始约定好都出相同的姿势，但是男孩想赢，女孩想输，现在给你男，女的名字，以及他们开始约定好的出的姿势。问最后谁会赢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
using namespace std;
int main()
{
    int t, n;
    string s,s1,s2;
    scanf("%d",&t);
    while(t--)
    {
            cin >> s >> s1 >> s2;
            cout << s1 << " will survive" << '\n';

    }
}