山东省第二届ACM大学生程序设计竞赛解题报告【7/10】

发表于 | 更新于 | 分类于
－－－－－－－－－－－山东省第二届ACM大学生程序设计竞赛解题报告－－－－－－－－－－ －

A.Simple Game【NimK博弈】

题意：给出n堆石子，每次可以从其种任选不超过3堆，从每堆中取走任意数量的石子。无法取的输。

思路：NimK博弈。

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

int u[N][32];
int t, n, x, idx, res, tem;
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        memset(u, 0, sizeof(u));
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &x);
            idx = 0;
            while(x)
            {
                u[i][idx++] = x & 1;
                x >>= 1;
            }
        }
        res = 0;
        for(int i = 0; i < 32; ++i)
        {
            tem = 0;
            for(int j = 1; j <= n; ++j)
            {
                if(u[j][i])
                    ++tem;
            }
            if(tem % 4)
            {
                res = 1;
                break;
            }
        }
        puts(res ? "Yes" : "No");
    }
    return 0;
}

B.The Android University ACM Team Selection Contest【结构体排序】

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

int t, n, m, tem;
struct node
{
    char name[33];
    bool girl, sel;
    int solve, pentl, idx;
} a[N];

bool cmp(node u, node v)
{
    if(u.solve != v.solve)
        return u.solve > v.solve;
    return u.pentl < v.pentl;
}

bool cmp2(node u, node v)
{
    return u.idx < v.idx;
}

int main()
{
    scanf("%d", &t);
    for(int cas = 1; cas <= t; ++cas)
    {
        if(cas > 1) puts("");
        int cnt = 0;
        memset(a, 0, sizeof(a));
        scanf("%d%d", &n,&m);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%s%d%d%d", a[i].name, &tem, &a[i].solve, &a[i].pentl);
            a[i].idx = i;
            a[i].girl = tem ? true : false;
            if(a[i].solve)  ++cnt;
        }
        if(cnt < m)
        {
            for(int i = 1; i <= n; ++i)
                printf("%s\n", a[i].name);
            continue;
        }
        sort(a + 1, a + n + 1, cmp);
        bool ok = 0;
        printf("Case %d:\n", cas);
        for(int i = 1; i <= m; ++i)
        {
            if(a[i].solve == 0) break;
            if(a[i].girl)   ok = 1;
            a[i].sel = 1;
        }
        if(!ok)
        {
            for(int i = m + 1; i <= n; ++i)
            {
                if(a[i].solve == 0) break;
                if(a[i].girl)
                {
                    a[i].sel = 1;
                    break;
                }
            }
        }

        sort(a + 1, a + 1 + n, cmp2);
        for(int i = 1; i <= n; ++i)
        {
            if(a[i].sel)
                printf("%s\n", a[i].name);
        }
    }
    return 0;
}

C.Identifiers【签到】

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;

bool f;
int t, len;
char s[111];
bool legal(char ch)
{
    if(!isalpha(ch) && ch != '_' && !isdigit(ch))
        return false;
    return true;
}
int main()
{
    scanf("%d", &t);
    getchar();
    while(t--)
    {
        gets(s);
        len = strlen(s);
        f = (isalpha(s[0]) | s[0] == '_');
        if(f)
            for(int i = 1; i < len; ++i)
                if(!legal(s[i]))
                {
                    f = false;
                    break;
                }
        puts(f ? "Yes" : "No");
    }
    return 0;
}

D.Binomial Coeffcients【组合数】

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>
using namespace std;

typedef long long ll;
const ll mod = 1e7+3;
const int maxn = 1e3+5;

ll c[maxn][maxn];

void init ()
{
    c[0][0] = c[1][0] = c[1][1] = 1;
    for (int i = 2; i < maxn; ++i) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; ++j) {
            c[i][j] = c[i-1][j-1]+c[i-1][j];
            c[i][j] %= mod;
        }
    }
}

int main()
{
    init();
    int t;
    scanf("%d", &t);
    while (t--) {
        int a, b;
        scanf("%d %d", &a, &b);
        cout << c[a][b] << '\n';
    }
    return 0;
}

E.Crack Mathmen【快速幂】

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

typedef long long ll;

const int maxn = 1e6+5;
const int mod = 997;

int n;
char str[maxn];
int ar[1000];
char br[1000];
char ans[maxn];

int qm (int a, int b)
{
    int ans = 1;
    while (b)
    {
        if (b&1)
            ans = ans*a%mod;
        a = a*a%mod;
        b >>= 1;
    }
    return ans;
}

void cal ()
{
    memset(ar, 0, sizeof(ar));
    for (int i = (int)'A'; i <= (int)'Z'; ++i)
    {
        int t1 = qm(i, n);
        int t2 = qm(i+32, n);
        ++ar[t1];
        ++ar[t2];
        br[t1] = (char)i;
        br[t2] = (char)(i+32);
    }
    for (int i = (int)'0'; i <= (int)'9'; ++i)
    {
        int t1 = qm(i, n);
        ++ar[t1];
        br[t1] = (char)i;
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        scanf("%s", str);
        cal();
        int len = strlen(str);
        if (len % 3 != 0)
        {
            cout << "No Solution" << '\n';
            continue;
        }
        bool bul = 1;
        int j = 0;
        for (int i = 0; i < len; i += 3)
        {
            int tmp = 100*(str[i]-'0')+10*(str[i+1]-'0')+1*(str[i+2]-'0');
            if (ar[tmp] != 1)
            {
                bul = 0;
                break;
            }
            else
            {
                ans[j++] = br[tmp];
            }
        }
        if (bul)
        {
            for (int i = 0; i < j; ++i)
                cout << ans[i];
            cout << '\n';
        }
        else
            cout << "No Solution" << '\n';
    }
    return 0;
}

F.Manhattan

送命题

G.Mathman Bank【模拟】

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

map<string, int> acc;
map<string, bool> exi;
map<string, string> pass;

char op;
int n, tem;
string s1, s2, s3;

int main()
{
    scanf("%d", &n);
    while(n--)
    {
        cin >> op;
        if(op == 'O')
        {
            cin >> s1 >> s2 >> tem;
            if(exi[s1])
                puts("Account exists.");
            else
            {
                puts("Successfully opened an account.");
                exi[s1] = 1;
                pass[s1] = s2;
                acc[s1] = tem;
            }
        }
        else if(op == 'D')
        {
            cin >> s1 >> tem;
            if(!exi[s1])
                puts("Account does not exist.");
            else
            {
                puts("Successfully deposited money.");
                acc[s1] += tem;
            }
        }
        else if(op == 'W')
        {
            cin >> s1 >> s2 >> tem;
            if(!exi[s1])
                puts("Account does not exist.");
            else if(s2 != pass[s1])
                puts("Wrong password.");
            else if(tem > acc[s1])
                puts("Money not enough.");
            else
            {
                acc[s1] -= tem;
                puts("Successfully withdrew money.");
            }
        }
        else if(op == 'T')
        {
            cin >> s1 >> s2 >> s3 >> tem;
            if(!exi[s1] || !exi[s3])
                puts("Account does not exist.");
            else if(s2 != pass[s1])
                puts("Wrong password.");
            else if(tem > acc[s1])
                puts("Money not enough.");
            else
            {
                puts("Successfully transfered money.");
                acc[s1] -= tem;
                acc[s3] += tem;
            }
        }
        else if(op == 'C')
        {
            cin >> s1 >> s2;
            if(!exi[s1])
                puts("Account does not exist.");
            else if(s2 != pass[s1])
                puts("Wrong password.");
            else
                printf("%d\n", acc[s1]);
        }
        else
        {
            cin >> s1 >> s2 >> s3;
            if(!exi[s1])
                puts("Account does not exist.");
            else if(s2 != pass[s1])
                puts("Wrong password.");
            else
            {
                puts("Successfully changed password.");
                pass[s1] = s3;
            }
        }
    }
    return 0;
}

H.Mathmen

I.Sequence

DP?

J.The Largest SCC【强连通分量】

https://blog.csdn.net/chenshibo17/article/details/88829368

Donate comment here
0%