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

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%