Competition Between SDNU_ICPC and MMSys_Laboratory(06-24)【解题报告】

发表于 | 更新于 | 分类于
Competition Between SDNU_ICPC and MMSys_Laboratory(06-24) || 第一次对抗赛 —— 山师acm集训队队员 VS MMSys实验室成员 || 友情参赛：齐工大acm集训队队员

前言：

由于OJ服务器时间比北京时间快了9min50s，导致比赛正式开始前已经可以看题目了，在队员发现时部分人已经AC了第一道签到题。

重新出题已经来不及了，只好将比赛隐藏又重新开了一场，题目不变，开始时间改回了北京时间19:00。（由此明白了考试备用试卷存在的原因？

没想到比赛还没正式开始就出锅了，对于造成的不便深表歉意。

题解：

说明：

比赛题目已在OJ公开，PIDs为1591~1598。

这场比赛整体来看难度不大，在中场的时候所有题目就都有人AC了，最终还有一人AK。

下面每道题的“题解”都是按照题目被拿走FB的顺序写的，由于题面并不难懂，且数据都会发送给大家，所以下列“题解”省去题目大意和解题思路，只保留实况记录和AC代码，如果发现一切相关问题可及时与我联系。

1591、Welcome to SDNU【签到】【输出字符串】

直接打印字符串的签到题，00:00:27被QLUmahongru拿走一血。

AcCode：（Python）

1
print("Hello SDNU!")

1592、easy problem【线性基】【裸题】

线性基模板题，没什么好说的，00:03:56被2018lihaoran拿走一血。

AcCode：

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 <bits/stdc++.h>      
#define ll long long 
using namespace std;  
int n;       
ll p[60],a[100000];  
void insert(ll v) 
{
    for(int i=52;i>=0;--i) 
    {
        if((1ll<<i)&v)
        {   
            if(p[i]) v^=p[i];  
            else { p[i]=v; return; }   
        }
    }
}
int main() 
{ 
    scanf("%d",&n); 
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]),insert(a[i]);
    ll ans=0;  
    for(int i=52;i>=0;--i) 
    {
        if(p[i]) ans=max(ans,ans^p[i]);           
    } 
    printf("%lld\n",ans);  
    return 0;  
}

1594、a - b【签到】【大数】

计算大数幂之差，00:08:04被20WangChuntao拿走一血。

AcCode：（Python）

1
2
3
4
5
6
7
while 1:
    try:
        a, b = input().split()
        a, b = int(a), int(b)
        print(pow(a, b) - pow(b, a))
    except:
        break

1595、矩阵链乘【栈】【表达式解析】

考察用栈模拟表达式，为了简化题目，已经保证表达式中的字母均在第一部分出现过，进行相乘的矩阵已用括号括起来，且括号符合匹配规则。00:22:08被sunchenxi_QLU2019拿走一血。

AcCode：

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

string ex;
char op[6];
int n, x, y, k;
struct Matrix
{
    int a, b;
    Matrix(int a = 0, int b = 0) : a(a), b(b) {}
} m[26];
stack<Matrix> s;
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
    {
        scanf("%s", op);
        k = op[0] - 'A';
        scanf("%d%d", &m[k].a, &m[k].b);
    }
    while(cin >> ex)
    {
        int len = ex.size();
        bool f = false;
        int ans = 0;
        for(int i = 0; i < len; ++i)
        {
            if(isalpha(ex[i]))
                s.push(m[ex[i]-'A']);
            else if(ex[i] == ')')
            {
                Matrix m2 = s.top();
                s.pop();
                Matrix m1 = s.top();
                s.pop();
                if(m1.b != m2.a)
                {
                    f = true;
                    break;
                }
                ans += m1.a * m1.b * m2.b;
                s.push(Matrix(m1.a, m2.b));
            }
        }
        if(f)
            puts("error");
        else
            printf("%d\n", ans);
    }
    return 0;
}

1593、No one knows ACM better than me【签到】【打印图形】

模拟签到题，00:33:50被2018lihaoran拿走一血。两个一血了啊，不愧是你，浩然！

AcCode:

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

typedef long long ll;

const int M = (int)1e3;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
const double eps = 1e-6;

char s[200][10000];

void work(int n)
{
    for(int i = 0; i <= n; ++i) for(int j = 0; j < 50 * n; ++j) s[i][j] = ' ';
    for(int i = 1; i <= n; ++i) s[i][n - i] = '/';
    for(int i = 1; i <= n - 2; ++i) s[n / 2][n - n / 2 + i] = '_';
    for(int i = 1; i <= n; ++i) s[i][n + i - 1] = '\\';
    for(int i = 1; i <= n; ++i) s[0][2 * n + 2 + i] = '_'; s[0][2 * n + 2 + n + 1] = '\0';
    for(int i = 1; i <= n; ++i) s[i][2 * n + 2] = '|';
    for(int i = 1; i <= n; ++i) s[n][2 * n + 2 + i] = '_';
    for(int i = 1; i <= n; ++i) s[i][3 * n + 5] = '|';
    for(int i = 1; i <= n; ++i) s[i][3 * n + 5 + i] = '\\';
    for(int i = 1; i <= n; ++i) s[i][5 * n + 6 - i] = '/';
    for(int i = 1; i <= n; ++i) s[i][5 * n + 6] = '|', s[i][5 * n + 7] = '\0';
}

int main()
{
    int n; while(~scanf("%d", &n))
    {
        work(n);
        for(int i = 0; i <= n; ++i) printf("%s\n", s[i]);
    }
    return 0;
}

1596、有手就行【模拟】【26进制】

恶心模拟题，再次被2018lihaoran于01:23:12拿走一血。

AcCode：

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

const int N = 100020;
const int Q = 1e9 + 7;
int n, L;
int num[26][N];
int power[N], sum[N];
bool ban[26];

char str[N];
int a[26];

bool cmp(int A, int B)
{
    for (int i = L - 1 ; i >= 0 ; -- i)
    {
        if (num[A][i] != num[B][i])
        {
            return num[A][i] < num[B][i];
        }
    }
    return 0;
}

void work()
{
    memset(num, 0, sizeof(num));
    memset(ban, 0, sizeof(ban));
    memset(sum, 0, sizeof(sum));
    L = 0;
    for (int i = 0 ; i < n ; ++ i)
    {
        scanf("%s", str);
        int len = strlen(str);
        if (len > 1)
        {
            ban[str[0] - 'a'] = 1;
        }
        reverse(str, str + len);
        for (int j = 0 ; j < len ; ++ j)
        {
            ++ num[str[j] - 'a'][j];
            sum[str[j] - 'a'] += power[j];
            if (sum[str[j] - 'a'] >= Q)
            {
                sum[str[j] - 'a'] -= Q;
            }
        }
        L = max(L, len);
    }
    for (int i = 0 ; i < 26 ; ++ i)
    {
        for (int j = 0 ; j < L ; ++ j)
        {
            num[i][j + 1] += num[i][j] / 26;
            num[i][j] %= 26;
        }
        while (num[i][L])
        {
            num[i][L + 1] += num[i][L] / 26;
            num[i][L ++] %= 26;
        }
        a[i] = i;
    }
    sort(a, a + 26, cmp);
    int zero = -1;
    for (int i = 0 ; i < 26 ; ++ i)
    {
        if (!ban[a[i]])
        {
            zero = a[i];
            break;
        }
    }
    int res = 0, x = 25;
    for (int i = 25 ; i >= 0 ; -- i)
    {
        if (a[i] != zero)
        {
            res += (LL)(x --) * sum[a[i]] % Q;
            res %= Q;
        }
    }
    static int ca = 0;
    printf("Case #%d: %d\n", ++ ca, res);
}

int main()
{
    power[0] = 1;
    for (int i = 1 ; i < N ; ++ i)
    {
        power[i] = (LL)power[i - 1] * 26 % Q;
    }
    while (~scanf("%d", &n))
    {
        work();
    }
    return 0;
}

1598、多人运动【组合数学】【快速幂】

再次出锅，题面把B组和C组描述反了，对不起！最后被浩然发现，浩然还是强啊。

虽然题面出锅，但并不影响老将对题目的理解凭借丰厚的参赛经验，这道题在01:32:15被2017liuyidi拿走一血，闷声发大财，知道题目有问题也不和我反馈一下（记仇.jpg）。

AcCode：

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

typedef long long ll;

const int M = (int)1e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;
const double eps = 1e-6;

ll quick(ll a, ll b, ll c = mod)
{
    ll s = 1;
    while(b)
    {
        if(b & 1) s = s * a % c;
        a = a * a % c;
        b >>= 1;
    }
    return s;
}

int main()
{
//    freopen("input.txt", "r", stdin);
    int T; scanf("%d", &T);
    while(T--)
    {
        int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d); swap(b, c);
        ll s = (((c + d + 1) * quick(2, a + b) % mod + quick(2, a + c) - (c + 1) * quick(2, a) % mod) % mod + mod) % mod;
        printf("%lld\n", s);
    }
    return 0;
}

1597、神秘监考【规律】【循环节】

找规律的题目，01:34:53又又又被2018lihaoran拿走一血！下面代码的注释中包含了浩然的解题思路。

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;

typedef long long ll;

const int M = (int)1e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
const double eps = 1e-6;

/**
未监控：  1 2 3 5
已监控：   4
监控序列：1 2 3 4 5 1 2 3 4 1 2 3 5 1 2 3 4

n = 4: 1 2 3 4 [1 2 3 1 2 4]
n = 5: 1 2 3 4 5 [1 2 3 4 1 2 3 5]
**/

int main()
{
//    freopen("input.txt", "r", stdin);
    int ca = 0;
    ll n, k;
    while(~scanf("%lld %lld", &n, &k))
    {
        printf("Case #%d: ", ++ca);
        if(k <= n) printf("%lld\n", k);
        else
        {
            k = (k - n - 1) % (2 * n - 2);
            if(k <= n - 2)          printf("%lld\n", k + 1);
            else if(k == 2 * n - 3) printf("%lld\n", n);
            else                    printf("%lld\n", k - n + 2);
        }
    }
    return 0;
}

总结：

一周前教练说题目不用太难，于是办了这场几乎不需要算法的“模拟题大赛”。

在写这个解题报告时也觉得没啥好写的，就把优秀的AC代码公布一下作为参考吧。

看到自己带过的师弟实力已碾压两年前的自己，内心深感欣慰，感谢教练的辛勤付出和队员们的共同努力。希望能早日见到集训队队员拿到区域赛金牌，有生之年能见到集训队队员打进WF。

Donate comment here
0%