欢迎来到不对拍就得不了分的竞赛！
2025-08-19 10:13:45
发布于：浙江
93阅读
0回复
0点赞
模拟赛游记 #4，#3 被我吃了
这次依旧 OI 赛制。
T1
题面：给定一个数 ，你可以进行若干次操作，每次操作交换两个数位。问最少进行多少次操作可以使 变成 的倍数。
？能忍住不搜的是这个 👍
注意到 的倍数满足：
- 若倒数第二位为偶数，则最后一位是 的倍数；
- 若倒数第二位为奇数，则最后一位是 的倍数 。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dfs(int ct, string s){
if(stoi(s) % 4 == 0) return ct;
if(ct > 2) return 0x3f3f3f3f;
int ans = 0x3f3f3f3f;
for(int i = 0; i < s.size(); i++){
swap(s[i], s[s.size() - 2]);
ans = min(ans, dfs(ct + 1, s));
swap(s[i], s[s.size() - 2]);
swap(s[i], s[s.size() - 1]);
ans = min(ans, dfs(ct + 1, s));
swap(s[i], s[s.size() - 1]);
}
return ans;
}
void solve(){
string s;
cin >> s;
if(s.size() == 1){
cout << (stoi(s) % 4 == 0 ? "0\n" : "-1\n");
return;
}
int ans = dfs(0, s);
if(ans >= 0x3f3f3f3f) cout << "-1\n";
else cout << dfs(0, s) << '\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
时间复杂度：。
写完后才发现有 组样例，成 Joker 了 
没事，至少我有了一个暴力代码，可以用来攻克一堆特判的正解。
经过特别久的调完改改完调调完改改完调后我终于写出来了以下代码，里面有如下特判：
- 如果初始就是 的倍数，则最少交换次数为 。
- 如果交换了最后两位后是 的倍数，则最少交换次数为 。
- 如果是小于两位并且不符合前面的条件，则无法变成 的倍数。
对于剩下的情况，令 分别为在 的所有数位中，模 为 的数，模 为 的数，模 为 的数的数量，则：
- 如果 且 ，则不能变成 的倍数。
- 如果 且 ，则无法变成 的倍数。
- 如果最后一位是 的倍数，则倒数第二位必不是 的倍数，只需将任何一个是 的倍数的数移过来即可。
- 如果最后一位模 余 ，则倒数第二位必为 的倍数，只需将任何一个不是 的倍数的数移过来即可。
- 否则，最后一位一定不是 的倍数。如果倒数第二位不是 的倍数并且有模 为 的数，只需将任何一个模 为 的数移到最后一位即可。
- 如果倒是第二位是 的倍数并且有除了后两位以外的 的倍数，只需将任何一个 的倍数移到最后一位即可。
- 如果上述情况都不满足，可以证明最少移动次数为 。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
void solve(){
int n;
cin >> n;
if(n % 4 == 0){
cout << "0\n";
return;
}
if(n < 10){
cout << "-1\n";
return;
}
string s = to_string(n);
swap(s[s.size() - 2], s[s.size() - 1]);
if(stoi(s) % 4 == 0){
cout << "1\n";
return;
}
if(n < 100){
cout << "-1\n";
return;
}
int ct1 = 0, ct2 = 0, ct4 = 0;
for(int i = 1; i <= n; i *= 10){
if(n / i % 10 % 2 == 1) ct1++;
if(n / i % 10 % 4 == 2) ct2++;
if(n / i % 10 % 4 == 0) ct4++;
}
if(ct2 == 0 && ct4 <= 1 || ct1 == 0 && ct4 == 0){
cout << "-1\n";
return;
}
if(n % 10 % 2 == 0) cout << "1\n";
else if(n / 10 % 10 % 2 == 1 && ct2 != 0) cout << "1\n";
else if(n / 10 % 10 % 2 == 0 && ct4 > (n / 10 % 10 % 4 == 0)) cout << "1\n";
else cout << "2\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
时间复杂度：。
T2
题面：有一个数组长度为 的数列 ，小明用它生成了一个数列 ，满足 ，他把数列 打乱，又删除了一项。现在他给你这个数列，问你他删除了哪个元素，如果有多种可能输出 Infinite。
唯一没有对拍的一个。
先把 排序。显然，在原来的 种， 会出现 次， 会出现 次， 会出现 次，...， 会出现 次。
我们只需要找哪个数的出现次数不对。
当然，无数种情况当且仅当删除了 。此时删除的可能为任意一个小于等于 的数。
实现的时候直接用 map 解决即可。map/set 太好用了你知道吗
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
int a[1000005];
bool check(map <int, int> &mp){
int cur = 2;
for(auto it:mp){
while(it.second >= cur){
it.second -= cur;
cur++;
}
if(it.second) return 0;
}
return 1;
}
void solve(){
int n;
cin >> n;
map <int, int> mp;
for(int i = 1; i <= n * (n - 1) / 2 - 1; i++) cin >> a[i], mp[a[i]]++;
if(check(mp)){
cout << "Infinite\n";
mp.clear();
return;
}
int cur = 1;
for(auto it:mp){
while(it.second >= cur){
it.second -= cur;
cur++;
}
if(it.second){
cout << it.first << '\n';
return;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
时间复杂度：。
T3 太史了，先看 T4。
T4
题面：定义请输入文本串如下：
一个字符串可以划分成若干个（一个也行）非回文字串。如 abbba 可以划分成 ab bba 两个子串，所以它是请输入文本串。
现给定一个长度为 的数组 和一个正整数 （ 或 ），你可以用 生成一个字符串 ，使 满足：
求你可以生成多少种不同的请输入文本串 。
首先注意到有 的部分分，遇事不决先打暴力：
我们枚举每个 时 的取值，然后再枚举划分点，逐个判断是否是请输入文本串。
暴力最难拿的一集，甚至只占了 分。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int a[8];
int n, m;
bool dfs2(int l, int r){
if(l > r) return 1;
bool flag = 1;
for(int i = l + 1; i <= r; i++){
if(a[i] != a[l]) flag = 0;
}
if(flag) return 0;
vector <int> v;
for(int i = l; i <= r; i++) v.push_back(a[i]);
vector <int> v2 = v;
reverse(v2.begin(), v2.end());
if(v != v2) return 1;
for(int i = l; i < r; i++){
if(dfs2(l, i) && dfs2(i + 1, r)) return 1;
}
return 0;
}
bool check(){
return dfs2(1, n);
}
int dfs(int ct){
if(ct > n) return check();
if(a[ct] != -1) return dfs(ct + 1);
int ans = 0;
for(int i = 1; i <= m; i++){
a[ct] = i;
ans += dfs(ct + 1);
a[ct] = -1;
}
return ans;
}
void solve(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
cout << dfs(1) << '\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
时间复杂度：，卡不满。
好的，暴力有了，接下来就该想正解了。
显然，绝大多数串都是请输入文本串，所以正难则反，先考虑所有不是请输入文本串的串，再拿总方案数减去这些即可。
经过一番对拍，我找到了所有不是请输入文本串的串：
- 前面一半和后面一半都是同一个字符。如
aaaa，bbbbabbbb。显然如何划分都有一个串全是同一个字符。 - 长度为奇数，并且所有奇数下标的字符均为同一个字符，所有偶数下标的字符均为同一个字符。如
ababababa。显然如何划分都会使得它有一个奇回文串。
注意这两种情况可能有重复，实现的时候注意减去重复的情况。
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int mod = 998244353;
int a[100005];
int n, m;
int solve1(){
int val = -1;
for(int i = 1; i <= n / 2; i++){
if(a[i] != -1){
if(val != -1 && val != a[i]){
return 0;
}
val = a[i];
}
}
for(int i = (n - n / 2) + 1; i <= n; i++){
if(a[i] != -1){
if(val != -1 && val != a[i]){
return 0;
}
val = a[i];
}
}
return (val == -1 ? m : 1) * ((n % 2 == 1 && a[n / 2 + 1] == -1) ? m : 1) % mod;
}
int solve2(){
int val1 = -1, val2 = -1;
for(int i = 1; i <= n; i++){
if(a[i] != -1){
if(i % 2 == 1){
if(val1 != -1 && val1 != a[i]) return 0;
val1 = a[i];
}else{
if(val2 != -1 && val2 != a[i]) return 0;
val2 = a[i];
}
}
}
if(val1 > val2) swap(val1, val2);
if(val1 == -1){
if(val2 == -1){
return (m * m - m) % mod;
}
return m - 1;
}else if(val1 != val2){
return 1;
}
return 0;
}
void solve(){
int tot = 1, ans = 0;
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
if(n == 1){
cout << "0\n";
return;
}
for(int i = 1; i <= n; i++){
if(a[i] == -1) tot = tot * m % mod;
}
ans = solve1();
if(n >= 5 && n % 2 == 1) ans = (ans + solve2()) % mod;
cout << (tot - ans + mod) % mod << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
时间复杂度 。
T3 就随便打了个暴力，预估 50。
赛后
分出来了，，喜提 rk1。
T3挂了的原因是因为数组开小了？
有帮助，赞一个