题解 | 寒假营第五场题解
寒假营第四场题解
Easy：A、B、I、J
Mid：C、E
Hard：D、H、L
AK：F、G、K
前言
整体评价：恶心卡常场。
如果说上一场是典板缝原场，那这一场就是无聊的卡常，全在卡常。
易错题都只给了非常弱的样例、在不同题中使用不同模数。
出题人觉得这场出的非常简单。
剩下的好像就没啥好说的了。
我没有验题，就过来偷偷上分了，然后一开场就红温了，签到题连 WA 三发，后续题也不是很顺，写了一堆弱智 BUG 。
签完到之后写 G 题倒是挺顺，然后看 F 一会就想到了个会超时的做法，优化后还是被卡到结束，赛后发现写 K 题说不定早都过了。
感觉还是不能碰数学题，真的会变得不幸。
最近越来越菜了，两小时连签到都没签完。
写到这里的时候刚好发现出分了，还没橙，可以再偷一把。
但是下一场是火鸡场，虽然号称很简单，但总感觉此乃谎言！
A 小L的三则运算
分类讨论
就是按题意，不过要注意是正整数。
时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n;
char c;
cin >> n >> c;
if(c == '+') cout << 1 << " " << n - 1 << endl;
if(c == '*') cout << 1 << " " << n << endl;
if(c == '-') cout << n + 1 << " " << 1 << endl;
}
B 小L出师了
数学
小学奥数题。
时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin >> T;
while(T--){
int n, t, k;
cin >> n >> t >> k;
int ans = (n - k) / t;
ans = min(ans, k + 1);
cout << ans << endl;
}
}
I 小L的数学题
猜
猜测一下，只要初始值不是 0 ，那么就可以变成除了 0 以外的所有数字。
尝试一发果然如此。
时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin >> T;
while(T--){
int n, m;
cin >> n >> m;
if(n == m) cout << "Yes" << endl;
if(!n || !m) cout << "No" << endl;
else cout << "Yes" << endl;
}
}
J 小L的汽车行驶问题
模拟
按照题意模拟即可。
时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
string s;
cin >> s;
int v = 0;
auto sum = 0ll;
for(auto &i : s){
if(i == '0') v += 10;
if(i == '1' && v) v -= 5;
int t = v;
if(i == '2') v = max(0, v - 10);
sum += v;
if(i == '2') v = t;
}
cout << sum << endl;
}
C 小L的位运算
思维、分类讨论
这题太恶心了，不想写。
明明是个容易错的分类讨论，出题人还只放了一组样例，该骂。
小道消息（也不是很小道）：这题数据很弱，有一堆错误做法通过，所以并不确定代码是否正确。
时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
int n, x, y;
cin >> n >> x >> y;
string a, b, c;
cin >> a >> b >> c;
LL zzo = 0;
LL ooo = 0;
LL zoz = 0;
LL ozz = 0;
for(int i = 0; i < n; i++){
if(a[i] == b[i]){
if(c[i] == '1'){
if(a[i] == '1') ooo++;
else zzo++;
}
}
else{
if(c[i] == '0'){
if(a[i] == '0') zoz++;
else ozz++;
}
}
}
if(x * 2 <= y){
LL ans = zzo + ooo + zoz + ozz;
ans *= x;
cout << ans << endl;
return 0;
}
if(ozz + zoz >= ooo + zzo){
LL ans = 0;
LL t = ooo + zzo;
ans += t * y;
if(ozz + t <= zoz){
zoz -= t;
zoz -= ozz;
ans += ozz * y;
ans += zoz * x;
}
else if(zoz + t <= ozz){
ozz -= t;
ozz -= zoz;
ans += zoz * y;
ans += ozz * x;
}
else{
LL k = zoz + ozz;
k -= t;
ans += k / 2 * y;
if(k & 1) ans += x;
}
cout << ans << endl;
return 0;
}
if(ooo >= zzo + ozz + zoz){
LL ans = 0;
LL t = zzo + ozz + zoz;
ooo -= t;
ans += t & y;
ans += ooo * x;
cout << ans << endl;
return 0;
}
if(zzo >= ooo + ozz + zoz){
LL ans = 0;
LL t = ooo + ozz + zoz;
zzo -= t;
ans += t & y;
ans += zzo * x;
cout << ans << endl;
return 0;
}
LL t = zzo + ooo + ozz + zoz;
LL ans = t / 2 * y;
if(t & 1) ans += x;
cout << ans << endl;
}
E 小L的井字棋
思维、贪心、枚举、分类讨论
首先要得出一个结论： 'O' 的个数小于等于 2 的话，是必胜的，否则直接枚举所有下棋的方案，判断是否可以直接获得胜利即可。
也可以按照下面进行分类讨论：
1） 如果为 1 ，那么在有一个的地方连续画 2 个就赢了。
2） 如果为 0 ，随便画一个地方，就变成了（1）的情况。
3） 如果为 2 ，只有下图一种情况无法连续画 2 个 'X' 直接获胜。
OXG
XOG
GGG
但此时我们只要在右下角画一个 'X' ，下一步不论鸡堵上面还是左边，我们往另一个方向连续画 2 个 'X' 就赢了。
4） 如果为 3 ，那么我们只剩下两次下棋的机会了，因此一定会连续下两颗，我们枚举所有情况，判断是否可以获胜即可。
5） 如果为 4 ，那么显然只剩一个空位，我们只能把这个空位填上，再判断是否可以获胜。
时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
int main(){
int T = 1;
cin >> T;
while(T--){
vector<string> s(3);
int sum = 0;
for(int i = 0; i < 3; i++){
cin >> s[i];
sum += ranges::count(s[i], 'O');
}
int n = 3;
auto check = [&](){
for(int i = 0; i < 3; i++){
if(s[i] == "XXX") return 1;
}
if(s[0][0] == s[1][1] && s[0][0] == s[2][2] && s[1][1] == 'X') return 1;
if(s[2][0] == s[1][1] && s[2][0] == s[0][2] && s[1][1] == 'X') return 1;
for(int i = 0; i < 3; i++){
if(s[0][i] == s[1][i] && s[0][i] == s[2][i] && s[0][i] == 'X') return 1;
}
return 0;
};
if(sum <= 2) goto yes;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(s[i][j] != 'G') continue;
s[i][j] = 'X';
if(check()) goto yes;
for(int k = 0; k < n; k++){
for(int l = 0; l < n; l++){
if(s[k][l] != 'G') continue;
s[k][l] = 'X';
if(check()) goto yes;
s[k][l] = 'G';
}
}
s[i][j] = 'G';
}
}
goto no;
if(0) yes: cout << "Yes" << endl;
if(0) no: cout << "No" << endl;
}
}
D 小L的字符串翻转
前缀和、埃氏筛、贪心
首先需要想到一个结论，如果一段中既有 0 又有 1 ，那么一定会把 0 放在一起， 1 放在一起，然后选择与前面相同的字符朝前，不同的字符朝后。
如果只有 1 或者只有 0 ，那么只要选择翻转或者不翻转，变成和前面相同的字符，再直接接上即可。
那么实际上最后得到的贡献值就是既有 0 又有 1 的段数加一。
如果我们只要求一个 ，我们可以使用暴力的方法判断每一段 0 和 1 的数量。
现在 从 1 到
各询问一遍，我们对每一个
进行暴力的话，实际上就是类似埃氏筛的复杂度，是一个调和级数。
那判断 0 和 1 的数量实际上也可以通过前缀和进行加速。
时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
string s;
cin >> s;
s = " " + s;
vector<int> f(n + 1);
for(int i = 1; i <= n; i++){
f[i] = f[i-1] + (s[i] == '1');
}
int sum = 0;
for(int i = 1; i <= n; i++){
int ans = 1;
for(int j = i; j <= n + i - 1; j += i){
int r = min(j, n);
int x = f[r] - f[j - i];
int y = (r - (j - i)) - x;
if(x && y) ans++;
}
sum ^= ans;
}
cout << sum << endl;
}
L 小L的构造
构造、打表、思维
这题忘记删除打表验证的代码，导致 TLE 了两发。
手玩发现，如果 是 6 的倍数，可以使用 6 个数凑出 {1,2,4} 和 {3,5,6} 两个三元组，之后用这两个三元组加 6 即可。
为什么加 6 也是合法的三元组呢？使用暴力代码加了一百万次 6 后，没有出现不合法的反例，因此数据范围内这个结论可行。
如果 模 6 等于 1 或 2 的话，实际上多出来的几个数都无法凑出三元组了，可以不考虑。
如果 模 6 等于 3 的话，也就是
时，按照我们刚才的想法，会多出 {7,8,9} 这三个数，而且这个三元组不合法。
继续手玩，发现把 {7,8,9} 的 9 和 {3,5,6} 的 6 交换的话，就变成了两个合法的三元组 {6,7,8} 和 {3,5,9} 。
那接下来再用 {10,11,14} 和 {12,13,15} 这两个合法的三元组，每次加 6 ，即可用完剩余的所有数字。
至于为什么合法？参考第三行的一百万次。
如果 模 6 等于 4 或 5 的话，同第四行。
注意要特判 的情况。
时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin >> T;
while(T--){
int n;
cin >> n;
if(n % 6 < 3){
vector<int> a = {2, 4, 1};
vector<int> b = {3, 6, 5};
cout << n / 3 << endl;
set<int> st;
for(int i = 1; i <= n / 6; i++){
for(auto &i : a){
cout << i << " ";
i += 6;
}
cout << endl;
for(auto &i : b){
cout << i << " ";
i += 6;
}
cout << endl;
}
}
else{
if(n == 3){
cout << 0 << endl;
continue;
}
if(n <= 5){
cout << 1 << endl;
cout << "2 4 1" << endl;
continue;
}
cout << n / 3 << endl;
cout << "2 4 1" << endl;
cout << "3 9 5" << endl;
cout << "6 8 7" << endl;
vector<int> a = {14, 11, 10};
vector<int> b = {12, 15, 13};
int t = n / 3 - 3;
t /= 2;
set<int> st;
for(int i = 1; i <= t; i++){
for(auto &i : a){
cout << i << " ";
i += 6;
}
cout << endl;
for(auto &i : b){
cout << i << " ";
i += 6;
}
cout << endl;
}
}
}
}
H 小L的min-max问题
组合数学、计数
这题的模数和 F 题不同，该骂。
数据范围只有 3000 ，实际上完全用不到 ST 表。
我们分割成每一种方法，再对每一种方法分出的区间的权值求和，实际上等价于对一个区间，先算出它的权值，看有多少种分割方法可以使得这个区间在方法中存在。
如果只能切一段，那切法显然是唯一的，可以特判。
那么接下来就是数组切段的问题了，由于这一个区间已经占据了一部分，那么剩下其他部分共要分成 段，我们可以用组合数学选每一段的右端点，那么左端点也可以直接得出。
如果这一段区间 在数组中间（前后都不为空），由于前面区间的最后一段右端点（
）和后面区间的最后一段右端点（
）都是固定的，因此我们还要选出
个位置作为其他段的右端点。
如果这一段区间占据了开头或结尾，那我们就只需要选出 个位置作为其他段的右端点。
组合数部分可以用 DP 或者暴力预处理出来。
时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
const int M = 998244353;
int main(){
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for(int i = 1; i <= n; i++){
cin >> a[i];
}
vector C(n + 1, vector<int>(n + 1));
for(int i = 0; i <= n; i++){
C[i][0] = 1;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % M;
}
}
int ans = 0;
if(k == 1){
auto [mi, ma] = minmax_element(a.begin() + 1, a.end());
cout << (1ll * *mi * *ma) % M << endl;
return 0;
}
for(int i = 1; i <= n; i++){
int ma = a[i];
int mi = a[i];
for(int j = i; j <= n; j++){
ma = max(ma, a[j]);
mi = min(mi, a[j]);
int len = j - i + 1;
int t = n - len;
if(t < k - 1) continue;
int x;
if(i != 1 && j != n) x = (__int128)1 * C[t - 2][k - 3] * ma * mi % M;
if(i == 1 || j == n) x = (__int128)1 * C[t - 1][k - 2] * ma * mi % M;
ans = (ans + x) % M;
}
}
cout << ans << endl;
}
G 小L的三元组
离散化、图论、树上启发式合并、数据结构
这题卡常，该骂。
首先点权具体的值不重要，只需要考虑点权与点权之间的大小关系，因此我们可以先将点权进行离散化。
接下来，枚举一个点 ，以
为中心的三元组里其他两个点一定来自
的两棵不同子树（包括往根的方向）。
如果两个点都来自 的孩子方向，这一部分比较好算，我们可以在启发式合并时枚举两棵子树点权相同的点在两棵子树中各有多少个直接计算贡献。
然后就是计算一个点来自根的方向，另一个点来自孩子的方向时的贡献。
我们可以知道孩子方向点权为 的点的个数
，再用整棵树点权为
的点的个数减一下
就能得到根方向的点权为
的点的个数
，二者乘积可以对三元组产生贡献记为
。
但是上述产生贡献的前提是 ，因此我们需要快速求出所有
的
之和，也就相当于是一个前缀和，由于这个前缀和需要进行修改，因此我们要使用树状数组。
由于每一个点需要的树状数组都是不同的，因此我们得对每一个点建立一棵树状数组，朴素的树状数组空间肯定是会超限的，因此我们还要用 代替数组，对每一个点维护一个离散的树状数组。
两个树状数组进行合并时和启发式合并类似，也需要从小合并到大。
由于这题卡常，还需要使用 来优化常数。
由于 是同阶的，因此时间复杂度
。
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
int n;
cin >> n;
vector<int> a(n + 1);
vector<int> tong(n + 1);
int m;
{
map<int, int> mp;
for(int i = 1; i <= n; i++){
cin >> a[i];
mp[a[i]]++;
}
int pt = 0;
for(auto &[x, y] : mp){
y = ++pt;
}
m = mp.size();
for(int i = 1; i <= n; i++){
a[i] = mp[a[i]];
tong[a[i]]++;
}
}
vector tr(n + 1, unordered_map<int, LL>());
vector b(n + 1, unordered_map<int, LL>());
auto update = [&](auto t, auto u, LL x){
x -= b[t][u];
b[t][u] += x;
for(; u <= m; u += -u & u){
tr[t][u] += x;
}
};
auto query = [&](auto t, auto u){
LL ans = 0;
for(; u >= 1; u -= -u & u){
ans += tr[t][u];
}
return ans;
};
vector ve(n + 1, vector<int>());
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
ve[u].push_back(v);
ve[v].push_back(u);
}
vector mp(n + 1, unordered_map<int, int>());
LL ans = 0;
auto dfs = [&](auto &dfs, int u, int fa) -> void{
for(auto &i : ve[u]){
if(i == fa) continue;
dfs(dfs, i, u);
if(mp[u].size() < mp[i].size()){
swap(tr[u], tr[i]);
swap(b[u], b[i]);
swap(mp[u], mp[i]);
}
for(auto &[x, y] : mp[i]){
if(mp[u].count(x)){
if(x < a[u]){
ans += 1ll * y * mp[u][x];
}
}
mp[u][x] += y;
update(u, x, 1ll * mp[u][x] * (tong[x] - mp[u][x]));
}
}
mp[u][a[u]]++;
update(u, a[u], 1ll * mp[u][a[u]] * (tong[a[u]] - mp[u][a[u]]));
ans += query(u, a[u] - 1);
};
dfs(dfs, 1, 0);
cout << ans << endl;
}
K 小L的几何
勾股定理、ChatGPT
本题又是卡常题。。。。。。。
赛时没看，赛后一看就想到了要枚举勾股数。
打了个表找了下勾股数规律，没找到。
百度搜了一下似乎也没找到。
于是去问 gpt ，得到了枚举方法，尝试了一下并发现似乎不会超时。
那么剩下的东西就很简单了。
然后又被卡常了。
时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
int n;
cin >> n;
vector<array<int, 3>> ve(n);
unordered_set<LL> st;
for(auto &[x, y, r] : ve){
cin >> x >> y >> r;
st.insert(1ll * x * 1e6 + y);
}
int limit = 3e5;
set<array<int, 3>> st1;
for(int m = 2; m <= sqrt(limit); m++){
for(int n = 1; n <= m; n++){
if((m - n)&1 && gcd(m, n) == 1){
int a = m * m - n * n;
int b = 2 * m * n;
int c = m * m + n * n;
if(c >= limit) break;
if(a > b) swap(a, b);
st1.insert({a,b,c});
}
}
}
vector d(limit + 1, vector<pair<int, int>>());
for(auto &[x, y, z] : st1){
for(int i = 1; i <= limit; i++){
if(z * i > limit) break;
d[z * i].push_back({x * i, y * i});
}
}
int ans = 0;
auto ch = [&](auto &x, auto &y, auto &dx, auto &dy){
if(st.count(1ll * (x + dx) * 1e6 + y + dy)) ans++;
if(st.count(1ll * (x + dx) * 1e6 + y - dy)) ans++;
if(st.count(1ll * (x - dx) * 1e6 + y + dy)) ans++;
if(st.count(1ll * (x - dx) * 1e6 + y - dy)) ans++;
if(st.count(1ll * (x + dy) * 1e6 + y + dx)) ans++;
if(st.count(1ll * (x + dy) * 1e6 + y - dx)) ans++;
if(st.count(1ll * (x - dy) * 1e6 + y + dx)) ans++;
if(st.count(1ll * (x - dy) * 1e6 + y - dx)) ans++;
};
auto ch1 = [&](auto &x,auto &y,auto &r){
if(st.count(1ll * x * 1e6 + y + r)) ans++;
if(st.count(1ll * x * 1e6 + y - r)) ans++;
if(st.count(1ll * (x + r) * 1e6 + y)) ans++;
if(st.count(1ll * (x - r) * 1e6 + y)) ans++;
};
for(auto &[x, y, r] : ve){
if(r > limit) continue;
for(auto &[dx, dy] : d[r]){
ch(x, y, dx, dy);
}
ch1(x, y, r);
}
cout << ans << endl;
}
F 小L的抽卡
DDP、矩阵乘法、概率、数论、数据结构
这题依然是卡常题。。。。。。。。。。
小道消息：这题 std 需要 400ms ，时限只放了 1s 。
思考了一会，得出了一个线段树维护矩阵乘法的做法，也就是 DDP 。
后续发现矩阵是循环矩阵，将矩阵乘法进行了优化，但是还是过不去。
赛后被告知，需要将线段树替换成猫树，但我觉得，按照我的常数，即使替换了也无法通过。
似乎理论上猫树对时间复杂度只优化了一个为 常数。
喵喵喵~
腾讯一面1690人在聊
查看30道真题和解析
