寒假第一场组队赛，19:00打到24:00，真的挺累的，队友齐心协力最后4道题收场。这次的题也有很多可以学到的知识，一道暴力水题，一道二分图模板题，其他都是思维+模拟的题，写个题解，A题数学题没做出来，补一下。
A – Carryless Square Root（数论）
题意
本题定义加法为不进位加法，如 $3 + 8 = 1 3 + 8 = 13+8=1$，乘法按竖式乘法计算，不进位。给定n$(1 \leq n \leq 10^{25})$，求满足 $a ∗ a = n $ 的最小的 a，无解输出 − 1。
题目分析
n的第一位和最后一位等于a的第一位和最后一位的不进位平方，且若n的位数为偶数，则无解，否则a的位数为（n的位数+1）/2，直接从低位向高位dfs暴力枚举0-9即可。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int a[maxn], b[maxn], c[maxn], n;
bool check(int pos) {
memset(c, 0, sizeof c);
for (int i = 0; i <= pos; i++) {
for (int j = 0; j <= pos; j++) {
if (pos != n - 1 && i + j > pos) break;
c[i + j] += (b[i] * b[j]) % 10;
c[i + j] %= 10;
}
}
for (int i = 0; i <= (pos == n - 1 ? n * 2 - 2 : pos); i++) {
if (c[i] != a[i]) return false;
}
return true;
}
void dfs(int pos) {
if (pos == n) {
if (!check(pos - 1)) return;
for (int j = 0; j < pos; j++) cout << b[j];
exit(0);
}
for (int i = 0; i <= 9; i++) {
b[pos] = i;
if (check(pos)) {
dfs(pos + 1);
}
}
}
int main(int argc, char const *argv[]) {
string s;
cin >> s;
if (!s.size()&1) {
cout << "-1\n";
return 0;
}
for (int i = 0; i < s.size(); i++) {
a[i] = s[i] - '0';
}
n = (s.size() + 1) / 2;
dfs(0);
cout << "-1\n";
return 0;
}
D – Swap Free（二分图 最小点覆盖）
题意
给定 n 个不同的字符串（字符串中字符不重复），在其中找到最大的一个字符串集合，不能通过交换任意一个字符串中的两个字符使得它与集合中的另一个字符串相同。
题目分析
若a可以通过一次变化变成另外b，b可以通过一次变化变成c，则c一定不能通过一次变化变成a，因为由于字符中字符不重复，每次变换就会改变字符串逆序对个数的奇偶性，故a和b奇偶性不同，b和c奇偶性不同，则a和c奇偶性相同，故a不能通过一次变化变成c，所以将a与所有可以一次变化变成的字符串连边，构造成一个天然的二分图，求二分图的最小点覆盖。由于是无向图建图，所以Hungry算出来的最大匹配数/2才是实际最大匹配数，最小点覆盖 = 点数 – 最大匹配数。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
char str[N][30];
int match[N];
bool vis[N];
vector<int> g[N];
bool check(char s[], char str[], int n) {
int num = 0;
for (int i = 0; i < n; i++)
if (s[i] != str[i]) num++;
return num == 2;
}
bool dfs(int u) {
for (int i = 0, v; i < g[u].size(); i++) {
if (!vis[v = g[u][i]]) {
vis[v] = true;
if (!match[v] || dfs(match[v])) {
match[v] = u;
return true;
}
}
}
return false;
}
int Get(int n) {
memset(match, 0, sizeof match);
int num = 0;
for (int i = 1; i <= n; i++) {
memset(vis, 0, sizeof vis);
if (dfs(i)) num++;
}
return num / 2;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%s", str[i]);
}
int len = strlen(str[1]);
for (int i = 1; i <= n; i++)
for (int j = 1; j < i; j++)
if (check(str[i], str[j], len)) {
g[i].push_back(j);
g[j].push_back(i);
}
int res = n - Get(n);
printf("%d\n", res);
return 0;
}
H – Levenshtein Distance（签到）
题意
给你一个字母表和一个字符串s，按字典序输出 s 通过一次删除、添加、修改得到的所有字符串（修改和添加的字符必须从字母表中选取）。
题目分析
直接暴力分别进行增删改的操作，将得到的字符串压入set中，由于set自动排序和去重，直接遍历输出set就行。
代码
#include <bits/stdc++.h>
using namespace std;
set<string> se;
string s, str;
int main() {
ios::sync_with_stdio(false);
cin >> s >> str;
for (int i = 0; i < str.size(); i++) {
string s2 = str;
auto it = s2.begin() + i;
s2.erase(it);
se.insert(s2);
}
for (auto c : s) {
for (int i = 0; i < str.size(); i++) {
char cc = str[i];
if (c == cc) continue;
str[i] = c;
se.insert(str);
str[i] = cc;
se.insert(str.substr(0, i) + c +
str.substr(i, (int)str.size() - i));
}
se.insert(str + c);
}
for (auto ss : se) {
cout << ss << '\n';
}
return 0;
}
I – Maze Connect （思维）
题意
要求删去尽量少的墙使得所有空的区域都和外面相连。
分析
一个封闭区域必须删去一个墙才能和外部相连，所以求出地图一共有几个封闭区域，就是删去的墙数。问题变为找地图中有几个封闭区域，首先一个由四个斜线组成的菱形算一个封闭区域（样例1），其次若干个“.”也会组成一个封闭区域，所有先统计出所有封闭菱形，再从每个“.” 开始进行bfs，标记走过的点，然后统计有几个封闭区域，注意可能可以斜着走，需要特殊判断。
代码
#include <bits/stdc++.h>
#define LL long long
#define fi first
#define se second
using namespace std;
const int maxn = 1e5 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int qr() {
int f = 0, fu = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') fu = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
f = (f << 3) + (f << 1) + c - 48;
c = getchar();
}
return f * fu;
}
const int N = 1e3 + 10;
int n, m, cnt;
char a[N][N];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
bool check(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m; }
void bfs(int x, int y) {
queue<PII> q;
a[x][y] = '*', q.push({x, y});
while (!q.empty()) {
PII t = q.front();
q.pop();
for(int i = 0; i < 4; i++) {
int nx = t.fi + dx[i], ny = t.se + dy[i];
if (check(nx, ny) && a[nx][ny] == '.')
a[nx][ny] = '*', q.push({nx, ny});
}
if (t.fi > 1 && t.se < m &&
!(a[t.fi][t.se + 1] == '\\' && a[t.fi - 1][t.se] == '\\') &&
a[t.fi - 1][t.se + 1] == '.')
a[t.fi - 1][t.se + 1] = '*', q.push({t.fi - 1, t.se + 1});
if (t.fi < n && t.se < m &&
!(a[t.fi][t.se + 1] == '/' && a[t.fi + 1][t.se] == '/') &&
a[t.fi + 1][t.se + 1] == '.')
a[t.fi + 1][t.se + 1] = '*', q.push({t.fi + 1, t.se + 1});
if (t.fi > 1 && t.se > 1 &&
!(a[t.fi - 1][t.se] == '/' && a[t.fi][t.se - 1] == '/') &&
a[t.fi - 1][t.se - 1] == '.')
a[t.fi - 1][t.se - 1] = '*', q.push({t.fi - 1, t.se - 1});
if (t.fi < n && t.se > 1 &&
!(a[t.fi + 1][t.se] == '\\' && a[t.fi][t.se - 1] == '\\') &&
a[t.fi + 1][t.se - 1] == '.')
a[t.fi + 1][t.se - 1] = '*', q.push({t.fi + 1, t.se - 1});
}
}
int main() {
n = qr(), m = qr();
for(int i = 1; i <= n; i++) scanf("%s",a[i] + 1);
for(int i = 1; i <= n - 1; i++)
for(int j = 1; j <= m-1; j++)
if (a[i][j] == '/' && a[i][j + 1] == '\\' && a[i + 1][j] == '\\' && a[i + 1][j + 1] == '/') cnt++;
for (int i = 1; i <= n; i++) {
if (a[i][1] == '.') bfs(i, 1);
if (a[i][m] == '.') bfs(i, m);
}
for (int i = 1; i <= m; i++) {
if (a[1][i] == '.') bfs(1, i);
if (a[n][i] == '.') bfs(n, i);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i][j] == '.') cnt++, bfs(i, j);
printf("%d",cnt);
return 0;
}
J – One of Each
题意
给你n个数字组成的序列，且n个数字都小于k，找到一个字典序最小的子序列，子序列中包含1-k的所有数字且只出现一次。
题目分析
先记录序列中每个数字后面有几个一样的数字，如果后面没有一样的数字了，那么这个数字是必须选择的，称之为关键数字。用贪心的思想，从前往后遍历整个序列，对于每个数字如果它是关键数字则必选，如果它比前面的所有数字都小，则暂时先选上，再判断下一个位置，如果下一个位置比上一个还小，则用它替换上一个数字（由于上一个数字不是关键数字，说明可以再后面再选，那么肯定要先选择更小的数更优），对于每个数字都进行这样的贪心判断。代码实现依靠一个栈即可，将已经选择的数字压入栈中，将每个数字与栈顶比较，如果栈顶不是关键数字并且栈顶数字大于当前数字，则用当前数字替换掉栈顶数字，遍历一遍整个序列即可。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 2e5 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int a[maxn], tong[maxn];
bool vis[maxn];
vector<int> ans;
int main(int argc, char const *argv[]) {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {scanf("%d", &a[i]);tong[a[i]]++;}
stack<int> sta;
for(int i = 0; i < n; i++) {
if(vis[a[i]]) {
tong[a[i]]--;
continue;
}
while(sta.size() && a[i] < sta.top() && tong[sta.top()] != 0) {
vis[sta.top()] = 0;
sta.pop();
}
sta.push(a[i]);
vis[a[i]] = 1;
tong[a[i]]--;
}
while(sta.size()) {
ans.push_back(sta.top());
sta.pop();
}
for (int i = ans.size() - 1; i >= 0; i--) {
printf("%d%c", ans[i], i == 0 ? '\n' : ' ');
}
return 0;
}
