T1
80分算法
写了一个最水的贪心(毫无正确性)，每次取最大得数给 Bob，取完后其他的给 Alice，用 max_element 很短就能实现…
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 <bits/stdc++.h>
using namespace std;
char num[40], tmp[40];
int n, tot, BobRemain, pos = 1, zeroNum;
long long AliceVal, BobVal;
inline int getMaxPos(const char* num) {
return max_element(num + pos, num + tot - BobRemain + 2) - num;
}
inline long long solve() {
memcpy(tmp, num, sizeof(num));
for (register int i = 1; i <= n; i++) {
pos = getMaxPos(tmp);
BobVal = BobVal * 10 + tmp[pos] - '0';
tmp[pos] = -1;
BobRemain--;
}
for (register int i = 1; i <= tot; i++) {
if (tmp[i] != -1) {
AliceVal = AliceVal * 10 + tmp[i] - '0';
}
}
BobRemain = n;
return AliceVal + BobVal;
}
int main() {
freopen("hello.in", "r", stdin);
freopen("hello.out", "w", stdout);
cin >> n >> num + 1;
tot = n << 1, BobRemain = n;
cout << solve();
return 0;
}
|
100分算法
此题应该 dp，状态转移方程为
$$f[i][j] = \max(f[i - 1][j] + num[i + j] \times 10^{n-i}, f[i][j - 1] + num[i + j] \times 10^{n-j})$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <bits/stdc++.h>
using namespace std;
int n;
long long f[21][21];
char s[40];
int num[40];
int main() {
cin >> n >> s + 1;
for (register int i = 1; i <= (n << 1); i++)
num[i] = s[i] ^ '0';
for (register int i = 1; i <= n; i++)
f[i][0] = f[0][i] = f[i - 1][0] + num[i] * (long long)pow(10, n - i);
for (register int i = 1; i <= n; i++)
for (register int j = 1; j <= n; j++)
f[i][j] = max(f[i - 1][j] + num[i + j] * (long long)pow(10, n - i), f[i][j - 1] + num[i + j] * (long long)pow(10, n - j));
cout << f[n][n];
return 0;
}
|
T2
玄学骗分 by hyj
hyj 表示此题可以骗分，10 行的玄学方法即可骗到 40 分…
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main() {
freopen("rect.in", "r", stdin);
freopen("rect.out", "w", stdout);
int a;
string s;
ios::sync_with_stdio(0);
cin.tie(0);
cin >> a;
cin >> s;
int num[4001], n = s.length();
for (register int i = 1; i <= n; ++i)
num[i] = s[i - 1] - '0';
int ans = 1;
for (register int i = 1; i <= n; ++i) {
ans *= num[i];
}
ans = (ans / a) / 2;
cout << ans;
return 0;
}
|
100分
由于此题的矩阵由 $s[i] \times s[j]$ 构成的，故 $a$ 为 $sum[x_1..x_2]$ 的倍数，故可以先把满足条件的 $sum$ 全部放进一个 HashMap 里，对应的值为方案数，如果 $a$ 不为 $0$，则遍历 HashMap 乘上对应方案数，再累加即可。当 $a$ 为 $0$ 时，$sum[y]$ 是可以随便取的，$ans = h[0] \times (len \times (len + 1) - h[0])$。
注意对0的特殊判断
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
| #include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef cc_hash_table<int, int> HashMap;
int a, len;
char str[10001];
long long ans;
HashMap h;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> a >> str + 1;
len = strlen(str + 1);
for (register int i = 1; i <= len; i++) {
register int cnt = 0;
for (register int j = i; j <= len; j++) {
cnt += str[j] ^ '0';
if (!cnt || !(a % cnt))
h[cnt]++;
}
}
if (a) {
for (HashMap::iterator it = h.begin(); it != h.end(); it++)
if (it->first && h.find(a / it->first) != h.end())
ans += (long long)it->second * h[a / it->first];
} else {
ans = (long long)h[0] * (len * (len + 1) - h[0]);
}
cout << ans;
return 0;
}
|
T3
此题暴力求最短路可以得 30 分，正解应逆向思考，把一个个删点看成一个个加点，相当于每次往闭包里加一个点，然后不断更新这样就可以的到复杂度为 $O(n ^ 3)$ 的算法，但需要注意一下常数…
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
| #include <bits/stdc++.h>
using namespace std;
#define inline __attribute__((optimize("O3"))) inline
const int iol = 1024 * 1024;
char buf[iol], *s, *t, ioc;
bool iosig;
inline char read() {
if (s == t) {
t = (s = buf) + fread(buf, 1, iol, stdin);
if (s == t) return -1;
}
return *s++;
}
template<class T>
inline bool read(T& x) {
iosig = false;
for (ioc = read(); !isdigit(ioc); ioc = read()) {
if (ioc == -1) return false;
if (ioc == '-') iosig = true;
}
x = 0;
while (ioc == '0') ioc = read();
for (; isdigit(ioc); ioc = read())
x = (x << 1) + (x << 3) + (ioc ^ '0');
s--;
if (iosig) x = -x;
return true;
}
using namespace std;
int n, a[501], g[501][501];
bool vis[501];
int f[501][501], ans[501];
__attribute__((optimize("O3"))) int main() {
read(n);
for (register int i = 1; i <= n; i++)
for (register int j = 1; j <= n; j++)
read(g[i][j]);
for (register int i = 1; i <= n; i++)
read(a[i]);
memset(f, 127, sizeof(f));
for (register int i = n; i >= 1; i--) {
vis[a[i]] = true;
f[a[i]][a[i]] = 0;
for (register int j = 1; j <= n; j++) {
if (vis[j]) {
for (register int k = 1; k <= n; k++) {
if (vis[k]) {
f[j][a[i]] = min(f[j][a[i]], f[j][k] + g[k][a[i]]);
f[a[i]][j] = min(f[a[i]][j], f[k][j] + g[a[i]][k]);
}
}
}
}
ans[i] = 0;
for (register int j = 1; j <= n; j++) {
if (vis[j]) {
for (register int k = 1; k <= n; k++) {
if (vis[k]) {
f[j][k] = min(f[j][k], f[j][a[i]] + f[a[i]][k]), ans[i] += f[j][k];
}
}
}
}
}
for (register int i = 1; i <= n; i++)
cout << ans[i] << " ";
return 0;
}
|
