题解 - 兰州大学第一届『飞马杯』程序设计竞赛

比赛链接

因为我的做法和官方题解高度重合,所以略去大多数内容

题目概览

题号标题做法
A★★ 比赛新机制 ★★前缀和
B★★ 体育课排队 ★★最大流
C★★ 生命的游戏 ★★模拟
D★★ 飞马祝福语 ★★动态 DP
E★★ 序列大团结 ★★hash
F★★ 飞马分隔符 ★★签到
G★★ 糖果魔法阵 ★★数学
H★★ 温暖的力量 ★★签到
I★★ 平形四边行 ★★数学
J★★ 翻滚吧硬币 ★★几何
K★★ 快乐苹果树 ★★期望,树链剖分
L★★ 星星收集者 ★★博弈论

官方题解

A - ★★ 比赛新机制 ★★

Show code

Aview raw
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
/*
* @Author: Tifa
* @Description: From <https://github.com/Tiphereth-A/CP-archives>
* !!! ATTENEION: All the context below is licensed under a
* GNU Affero General Public License, Version 3.
* See <https://www.gnu.org/licenses/agpl-3.0.txt>.
*/
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
for (decltype(l + r) i = (l), ##vals; i <= (r); ++i)
#define _rfor(i, r, l, vals...) \
for (decltype(r - l) i = (r), ##vals; i >= (l); --i)
const int OFFSET = 5;
const int N = 5e5 + OFFSET;
template <class T>
bool chkmin(T &a, T b) {
return b < a ? a = b, true : false;
}
i64 a[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int _t;
cin >> _t;
while (_t--) {
int n;
cin >> n;
_for(i, 1, n) cin >> a[i];
i64 sum = 0;
_for(i, 1, n) sum += a[i];
i64 sum1 = 0, sum2 = 0;
_for(i, 1, n) {
sum1 += i * a[i];
sum2 += (n - i + 1) * a[i];
}
i64 ans = INT64_MAX;
_rfor(i, n, 1) chkmin(ans, sum1 += sum - n * a[i]);
_for(i, 1, n) chkmin(ans, sum2 += sum - n * a[i]);
cout << ans << '\n';
}
return 0;
}

B - ★★ 体育课排队 ★★

Show code

C - ★★ 生命的游戏 ★★

Show code

Cview raw
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
/*
* @Author: Tifa
* @Description: From <https://github.com/Tiphereth-A/CP-archives>
* !!! ATTENEION: All the context below is licensed under a
* GNU Affero General Public License, Version 3.
* See <https://www.gnu.org/licenses/agpl-3.0.txt>.
*/
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define _for(i, l, r, vals...) \
for (decltype(l + r) i = (l), ##vals; i <= (r); ++i)
const int OFFSET = 5;
const int N = 100 + OFFSET;
const pii d[8] = {
{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
int maps0[N][N], maps[N][N], maps2[N][N];
int n;
int cnt(int i, int j) {
int ret = 0;
for (const pii &p : d)
ret += maps[(i + p.first + n - 1) % n + 1][(j + p.second + n - 1) % n + 1];
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int _t;
cin >> _t;
while (_t--) {
int k;
cin >> n >> k;
_for(i, 1, n)
_for(j, 1, n) cin >> maps[i][j];
_for(i, 1, n)
_for(j, 1, n) maps0[i][j] = maps[i][j];
_for(t, 1, k, _) {
_for(i, 1, n)
_for(j, 1, n) {
_ = cnt(i, j);
maps2[i][j] = (maps[i][j] == 0 && _ == 3) ? 1 :
(maps[i][j] == 1 && (_ > 3 || _ < 2)) ? 0 :
maps[i][j];
}
_for(i, 1, n)
_for(j, 1, n) maps[i][j] = maps2[i][j];
bool f = 1;
_for(i, 1, n)
_for(j, 1, n) f &= maps0[i][j] == maps[i][j];
if (f) {
cout << "YES\n" << t << '\n';
return;
}
}
cout << "NO\n";
}
return 0;
}

D - ★★ 飞马祝福语 ★★

Show code

E - ★★ 序列大团结 ★★

Show code

Eview raw
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
/*
* @Author: Tifa
* @Description: From <https://github.com/Tiphereth-A/CP-archives>
* !!! ATTENEION: All the context below is licensed under a
* GNU Affero General Public License, Version 3.
* See <https://www.gnu.org/licenses/agpl-3.0.txt>.
*/
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using u64 = uint64_t;
#define _for(i, l, r, vals...) \
for (decltype(l + r) i = (l), ##vals; i <= (r); ++i)
const int OFFSET = 5;
const int N = 1e5 + OFFSET;
const int P = 1e9 + 1;
u64 a[N];
u64 qpow(u64 a, u64 b) {
u64 res(1);
for (; b; b >>= 1, (a *= a))
if (b & 1) (res *= a);
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int _t;
cin >> _t;
while (_t--) {
int n, k;
cin >> n >> k;
_for(i, 1, n) cin >> a[i];
map<u64, i64> _ans, cnt;
_ans[0] = 1;
i64 ans = 0;
u64 _hash = 0;
_for(i, 1ll, n) {
if (a[i] % k) {
_hash += ((cnt[a[i]] + 1) % k - cnt[a[i]]) * qpow(P, a[i]);
cnt[a[i]] = (cnt[a[i]] + 1) % k;
}
ans += _ans[_hash]++;
}
cout << ans << '\n';
}
return 0;
}

G - ★★ 糖果魔法阵 ★★

Show code

Gview raw
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
/*
* @Author: Tifa
* @Description: From <https://github.com/Tiphereth-A/CP-archives>
* !!! ATTENEION: All the context below is licensed under a
* GNU Affero General Public License, Version 3.
* See <https://www.gnu.org/licenses/agpl-3.0.txt>.
*/
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
for (decltype(l + r) i = (l), ##vals; i <= (r); ++i)
template <typename Tp = i64>
class rpow final {
private:
uint32_t mod;
Tp base;
std::array<Tp, 65536> block1, block2;

public:
rpow(const Tp &_base, const uint32_t &_mod): base(_base), mod(_mod) {
block1[0] = block2[0] = 1;
for (uint32_t i = 1; i < 65536; i++) block1[i] = block1[i - 1] * base % mod;
Tp _(block1.back() * base % mod);
for (uint32_t i = 1; i < 65536; i++) block2[i] = block2[i - 1] * _ % mod;
}
Tp &&get_base() { return std::move(base); }
uint32_t &&get_mod() { return std::move(mod); }
Tp operator()(std::make_unsigned_t<Tp> &&exponent) {
return block1[exponent & 65535] * block2[exponent >> 16] % mod;
}
};
const i64 mod = 998244353;
const i64 sqrt2 = 116195171;
const i64 sqrt2plus1 = sqrt2 + 1, msqrt2plus1 = mod + 1 - sqrt2;
const i64 phi_mod = mod - 1, phi_phi_mod = 402653184;
template <typename Tp = i64>
Tp inv(Tp a) {
a %= mod;
Tp b(mod - 2), res(1);
for (; b; b >>= 1, (a *= a) %= mod)
if (b & 1) (res *= a) %= mod;
return res;
}
rpow<i64> a(sqrt2plus1, mod);
rpow<i64> b(msqrt2plus1, mod);
rpow<i64> _4(4, phi_mod);
int main() {
i64 s, c, q;
cin >> s >> c >> q;
_for(i, 1ll, q, _, ans, t) {
cin >> _;
ans = s;
_for(i, 1, _, k = 0) {
k += ans / c;
t = _4(k = k % phi_phi_mod + (k >= phi_phi_mod) * phi_phi_mod);
ans = ((a(t) + b(t)) * sqrt2 % mod) * i % mod;
}
cout << ans * (inv(_) * inv(a(t) - b(t) + mod) % mod) % mod << '\n';
}
return 0;
}

I - ★★ 平形四边行 ★★

Show code

Iview raw
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
/*
* @Author: Tifa
* @Description: From <https://github.com/Tiphereth-A/CP-archives>
* !!! ATTENEION: All the context below is licensed under a
* GNU Affero General Public License, Version 3.
* See <https://www.gnu.org/licenses/agpl-3.0.txt>.
*/
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define _for(i, l, r, vals...) \
for (decltype(l + r) i = (l), ##vals; i <= (r); ++i)
vector<pii> points;
map<pii, pii> midp;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
_for(i, 1, n, x, y) {
cin >> x >> y;
points.emplace_back(x, y);
}
for (auto it = points.begin(); it != points.end(); ++it)
for (auto it2 = points.begin(); it2 != it; ++it2) {
auto mid = make_pair(it->first + it2->first, it->second + it2->second);
auto i = it - points.begin(), j = it2 - points.begin();
if (!midp.count(mid)) {
midp[mid] = {i, j};
continue;
}
if (midp[mid].first == i || midp[mid].first == j ||
midp[mid].second == i || midp[mid].second == j)
continue;
cout << "YES\n"
<< i + 1 << ' ' << j + 1 << ' ' << midp[mid].first + 1 << ' '
<< midp[mid].second + 1 << '\n';
return;
}
cout << "NO\n";
return 0;
}

J - ★★ 翻滚吧硬币 ★★

Show code

Jview raw
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
/*
* @Author: Tifa
* @Description: From <https://github.com/Tiphereth-A/CP-archives>
* !!! ATTENEION: All the context below is licensed under a
* GNU Affero General Public License, Version 3.
* See <https://www.gnu.org/licenses/agpl-3.0.txt>.
*/
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using ldb = long double;
const ldb PI = acos(-1.0l);
ldb __(i64 a, i64 b, i64 c) {
ldb _a = a + b, _b = a + c, _c = c + b;
return ((PI - acos((_a * _a + _b * _b - _c * _c) / (2 * _a * _b))) * _b +
(PI - acos((_a * _a + _c * _c - _b * _b) / (2 * _a * _c))) * _c) /
(PI * c);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int _t;
cin >> _t;
while (_t--) {
i64 a, b, c;
cin >> a >> b >> c;
cout << fixed << setprecision(12)
<< min(
min(__(a, b, c), __(a, c, b)),
min(min(__(b, a, c), __(b, c, a)), min(__(c, a, b), __(c, b, a))))
<< '\n';
}
return 0;
}

K - ★★ 快乐苹果树 ★★

Show code

L - ★★ 星星收集者 ★★

Show code