19thZJCPC
B. JB Loves Comma
给定字符串 S，在每个 “cjb” 子串后面添加一个逗号 ,就一签到题没什么难度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
//#define int long long
//#define N 105
using namespace std;
void solve() {
string s ;
cin >> s ;
for (int i = 0 ; i < (int)s.size() ; i++) {
cout << s[i] ;
if (i >= 2 && s.substr(i - 2, 3) == "cjb") {
cout << "," ;
}
}
}
signed main() {
cin.tie(nullptr), cout.tie(nullptr);
ios::sync_with_stdio(false);
int T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}
C. JB Wants to Earn Big Money
给定 n 个人的预期价格和股票交易价格，统计参与交易的人数。每次读入判断一下就好了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
using namespace std;
void solve() {
int n, m, z, ans = 0;
cin >> n >> m >> z;
for (int i = 1, t; i <= n; ++i) {
cin >> t;
ans += t >= z;
}
for (int i = 1, t; i <= m; ++i) {
cin >> t;
ans += t <= z;
}
cout << ans;
}
signed main() {
cin.tie(nullptr), cout.tie(nullptr);
ios::sync_with_stdio(false);
int T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}
A. JB Loves Math
给定两个正整数 a, b，你需要选定一个正奇数 x 和一个正偶 数 y。 之后的每一步操作中，你可以将 a 增大 x 或者将 a 减小 y。 求把 a 变成 b 的最少操作次数。
稍微有点头疼的模拟题，要考虑一些细节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
//#define int long long
//#define N 105
using namespace std;
void solve() {
int a, b;
cin >> a >> b;
int diff = abs(a - b);
if (a == b)
return cout << 0 << endl, void();
if (a < b) {
if (diff & 1)
return cout << 1 << endl, void();
if ((diff >> 1) & 1)
cout << 2 << endl;
else
cout << 3 << endl;
} else {
if ((diff & 1) == 0)
return cout << 1 << endl, void();
cout << 2 << endl;
}
}
signed main() {
cin.tie(nullptr), cout.tie(nullptr);
ios::sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}
L. Candy Machine
给定 N 个正整数，从中选择一个子集使得严格大于该集合平均数的数字个数尽可能多。
注意选的是子集，所以选的和顺序无关，不难发现从小到大添加数据是最优的，感性理解一下这样能保证每次对于平均值不会增加太多导致不行。可以用反证法证明：
假设不按照这样添加更优，那么必存在a>b，a和b按照a,b的顺序依次进入平均值是average2，原先按照b,a顺序进入时平均值为average1，显然有average1<average2,那么当有：
时，显然原先的排序更优于假设的排序，与假设矛盾故从小到大添加数据是最优的。
那么从小到大添加数据后，可以发现存在一个最小元素，在他之后的元素都是满足条件的，由于存在单调性所以考虑二分优化，使用自带的upper_bound函数找到严格大于的前一位，总复杂度O(nlogn)可以通过1e6的规模
1 |
|
G. Easy Glide
给定平面上 n 个滑行点以及起点 S 和终点 T。 行走速度为 V1，每次经过某个滑行点后可以按 V2 速度滑 行 3 秒。 求从 S 滑行到 T 所需的最少时间。
显然可以建图，每个点之间连一条边，边权是时间，跑一遍最短路即可。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
104
105
106
107
using namespace std;
typedef pair<int, int> PII;
int n;
double walk, glid;
PII gpos[N], s, t;
struct edge {
int to;
double w;
edge(int a, double b) {
to = a;
w = b;
}
};
typedef pair<int, int> PII;
vector<edge> edge[N];
double dist[N];
bitset<N> st;
void clear() { for (auto &i: edge) i.clear(); }
double dijkstra() {
fill(dist, dist + N + 1, 1e9);
dist[0] = 0;
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>> heap;
heap.emplace(0, 0);
while (!heap.empty()) {
auto ver = heap.top().second;
heap.pop();
if (st[ver]) continue;
st[ver] = true;
for (auto &i: edge[ver]) {
int j = i.to;
if (dist[j] > dist[ver] + i.w) {
dist[j] = dist[ver] + i.w;
heap.emplace(dist[j], j);
}
}
}
return dist[n + 1];
}
double getT(int x1, int x2, int y1, int y2, bool ok) {
// cout<<'('<<x1<<','<<y1<<')'<<'('<<x2<<','<<y2<<')'<<' ';
double res, d = sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
if (ok) {
res = d / glid;
if (res > 3)
res = 3 + (d - glid * 3.0) / walk;
} else {
res = d / walk;
}
// cout<<d<<' '<<res<<endl;
return res;
}
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> gpos[i].fi >> gpos[i].se;
cin >> s.fi >> s.se >> t.fi >> t.se;
cin >> walk >> glid;
double c = getT(s.fi, t.fi, s.se, t.se, false);
edge[0].emplace_back(n + 1, c), edge[n + 1].emplace_back(0, c);
for (int i = 1; i <= n; ++i) {
c = getT(s.fi, gpos[i].fi, s.se, gpos[i].se, false);
edge[0].emplace_back(i, c), edge[i].emplace_back(0, c);
}
for (int i = 1; i <= n; ++i) {
c = getT(gpos[i].fi, t.fi, gpos[i].se, t.se, true);
edge[i].emplace_back(n + 1, c), edge[n + 1].emplace_back(i, c);
for (int j = i + 1; j <= n; ++j) {
c = getT(gpos[i].fi, gpos[j].fi, gpos[i].se, gpos[j].se, true);
edge[i].emplace_back(j, c), edge[j].emplace_back(i, c);
}
}
// for (int ver = 0; ver <= n + 1; ++ver) {
// cout << ver << '(' << gpos[ver].fi << ',' << gpos[ver].se << ')' << ':' << endl;
// for (auto i:edge[ver]) {
// cout << i.to << '(' << gpos[i.to].fi << ',' << gpos[i.to].se << ')' << ':' << i.w << ';';
// }
// cout << endl;
// }
// cout << dijkstra();
printf("%.6lf\n" , dijkstra()) ;
}
signed main() {
// cin.tie(nullptr), cout.tie(nullptr);
// ios::sync_with_stdio(false);
int T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}
主要难在实现，感觉要比L题要容易想一些，需要注意的是最后一定要写printf()，不能直接写cout不加精度的控制，因为题目要求精度不低于1e-6，而cout默认是输出六位有效数字。
M. BpbBppbpBB
给定使用两种印章无重叠可旋转地打印出的字符画，统计每 种印章的使用次数。没想到正解…有空补
队友想到了用的鸡兔同笼原理，根据黑点总数和洞的总数解方程。模拟了一下然后做出来了
1 |
|
I. Barbecue
给定一个长度为 n 的字符串 S，q 次询问，每次询问指定 S 的一个子串，两个人在该子串上进行博弈。 博弈双方轮流删去当前串开头或结尾的一个字符，碰到回文串的人输。 预测两人都按最优策略操作时最终谁会获胜。
没学过博弈，会了之后再补思路。Putata先手，Budada后手，手模一下可以发现最后的情况必定是形如ab,abab,ababab…这样的才能让此时的人不管是撕左边的还是右边的都会输（其实做题的时候只发现了ab这种情况才一定输，但最后结论推出来居然还是对了），所以可以发现和初始状态的长度的奇偶性有关。并且还要判断一下初始态是不是回文串，快速判断一个子串是否是回文串可以使用进制哈希，我用的是manacher（好像跑的比哈希还快一些）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
//#define int long long
using namespace std;
typedef pair<int, int> PII;
struct MLC {
int n, p[2 * N + 2];
char t[N * 2 + 3], s[N + 2];
void manacher() {
n = (int) strlen(s + 1);
int m = 0;
t[++m] = '#';
for (int i = 1; i <= n; ++i) t[++m] = s[i], t[++m] = '#';
int mid = 0, r = 0;
for (int i = 1; i <= m; ++i) {
if (i > r) p[i] = 1;
else p[i] = min(p[2 * mid - i], r - i + 1);
while (i - p[i] > 0 && i + p[i] <= m && t[i - p[i]] == t[i + p[i]])++p[i];
if (i + p[i] - 1 > r) mid = i, r = i + p[i] - 1;
}
}
} manacher{};
void solve() {
int l, r, len;
cin >> l >> r;
len = r - l + 1;
int t = manacher.p[l + r];
if (t >= len) return cout << "Budada" << endl, void();
if (len & 1) cout << "Putata" << endl;
else cout << "Budada" << endl;
}
signed main() {
cin.tie(nullptr), cout.tie(nullptr);
ios::sync_with_stdio(false);
int T = 1, n;
cin >> n >> T >> (manacher.s + 1);
manacher.manacher();
while (T--) solve();
return 0;
}
个人感觉这一年的中等偏简单题偏多但完全做对有些困难，而且因为疫情线上每队有三台电脑编辑器随便选，如果队友之间没有配合好或者没使用更好的编辑器作为辅助，容易出现一道题卡很久的情况