1 周一
1.1 C
输入两个数a, b表示a和b信仰同一个宗教。求有多少种不同的宗教信仰。
先看第二个样例
10 4
2 3
4 5
4 8
5 8
画图可得：![[Pasted image 20230115154805.png]]
一共7个蓝色圈, 7种宗教信仰。
可以定义一个并查集, 初始时每个集合只有自己, 输入a,b就将a,b合并为一个集合。统计已做的有效合并次数, 4-5, 4-8 是有效合并, 而5-8并不是, 本身就在一个并查集里。最后用总个数减去有效合并次数就是集合数量。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 5e4 + 10;
int f[N];
int find(int x)
{
if (f[x] != x)
f[x] = find(f[x]);
return f[x];
}
int main()
{
int n, m;
int kast = 0;
while (cin >> n >> m, n || m)
{
int cnt = 0;
for (int i = 1; i <= n; i++)
f[i] = i;
while (m--)
{
int a, b;
cin >> a >> b;
a = find(a), b = find(b);
if (a != b)
{
f[b] = a;
cnt++;
}
}
cout << "Case " << ++kast << ": " << n - cnt << endl;
}
return 0;
}
2 周二
2.1 C
对第一组样例画个图：![[Pasted image 20230115164110.png]]
根据题目性质, 只要社团内一人感染, 整个社团都会被感染。 创建一个并查集, 将同一社团的人合并, 若存在一个人加入了两个社团, 则会将这两个社团一起合并。
然后遍历一次所有学生, 若当前点的父亲与0号点的父亲相同, 则说明会与0号接触, 属于密接, 统计加一即可。
记得访问父亲时使用 find(x), 避免因使用f[x]导致未经路径压缩得到错误结果。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 3e4 + 10;
int f[N];
int find(int x)
{
return f[x] != x ? f[x] = find(f[x]) : f[x];
}
void merge(int a, int b)
{
a = find(a), b = find(b);
if (a != b)
f[a] = b;
}
int main()
{
int n, m;
while (cin >> n >> m, n || m)
{
for (int i = 0; i < n; i++)
f[i] = i;
while (m--)
{
int cnt, a;
cin >> cnt >> a;
for (int i = 0; i < cnt - 1; i++)
{
int b;
cin >> b;
merge(a, b);
}
}
int suspect = find(0), res = 0;
for (int i = 0; i < n; i++)
res += find(i) == suspect;
cout << res << endl;
}
return 0;
}
3 周三
3.1 C
题意概括一下为, 求从起点开始长度为\(1,3,5,..,\frac{N+1}{2}\) 的乱序序列的中位数。
可以想象为起始是一个空序列, 然后每读入一个数就用插入排序放进序列中, 当序列长度为奇数且小于\(\frac{N+1}{2}\)时输出当前中位数。
中位数即排完序后在中间的数。
创建一个大根堆, 一个小根堆。 大根堆维护前半段的最大值, 小根堆维护后半段的最小值, 这样在长度为奇数时, 存数最多的堆的堆顶元素就是要求的中位数。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n, m;
int mid;
int main()
{
cin >> n >> mid;
priority_queue<int, vector<int>, less<int>> q1; // 大根堆
priority_queue<int, vector<int>, greater<int>> q2; // 小根堆
cout << mid << endl;
for (int i = 2; i <= n; i++)
{
int x;
cin >> x;
if (x > mid)
q2.push(x);
else
q1.push(x);
if (i & 1)
{
while (q1.size() != q2.size())
{
if (q1.size() < q2.size())
{
q1.push(mid);
mid = q2.top();
q2.pop();
}
else
{
q2.push(mid);
mid = q1.top();
q1.pop();
}
}
cout << mid << endl;
}
}
return 0;
}
4 周四
4.1 B
题意概括一下为, 从一系列单词中找出最短连续的一段, 其中包含最多个“要背单词”, 输出包含数量和该段的长度。
需要一个实现判断当前单词是否为“要背单词”, 可以使用map/set哈希表, 将起初的“要背单词”存下来, 然后用 map.count(s) != 0 来判断是不是“要背单词”。
接着需要找出连续的一段, 其中包含最多个“要背单词”, 且长度最短。
朴素写法是用两层循环枚举所有长度\(O(n^{2})\) , 这里显然会超时, 得优化一下。题目说一段中重复的单词只会计算一次, 为了保持长度最小, 我们需要去重。
定义 res1 为区间内“要背单词”个数, res2 为区间长度。
先枚举区间终点 r, 若当前单词是“要背单词”且第一次出现, 则更新res1和res2。接着开始缩短区间并判重。让l往后枚举, 若当前单词不是“要背单词”则直接l++即可, 若是, 接着判断是否在区间内出现过两次及以上, 如果是就继续l++。直到遇见只出现过一次的”要背单词“时停止缩短。此时再更新一次答案即可。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <set>
using namespace std;
const int N = 1e5 + 10;
map<string, int> cnt;
set<string> S;
string s[N];
int main()
{
int n, m, res1 = 0, res2 = 0;
cin >> n;
while (n--)
{
string s;
cin >> s;
S.insert(s);
}
cin >> m;
int l = 1;
for (int r = 1; r <= m; r++)
{
cin >> s[r];
if (S.count(s[r]))
{
if (!cnt[s[r]]) // 若是第一次出现
res1++, res2 = r - l + 1;
cnt[s[r]]++; // 单词出现次数+1
}
for (l; l <= r; l++)
{
if (S.count(s[l]))
{
if (cnt[s[l]] == 1)
break;
else
cnt[s[l]]--;
}
}
res2 = min(res2, r - l + 1);
}
cout << res1 << endl
<< res2 << endl;
return 0;
}
4.2 C
题意：给两个最长为80的字符串a,b。求最长的一个字符串c, 使得c是a的后缀, b的前缀 或者 a的前缀, b的后缀。
也就80字符长度, 长度为n的字符串可以贡献n个子串, 加上逆向2n, 一共两个串为4n种, 即 320 种可能的答案。直接枚举答案然后判断可行性求出最长的那个就行。
我猜没人写的原因是看见前面一段英语就弃了（
答案肯定是从a,b的前后缀中得出, 故可以枚举结果串的长度, 用substr函数切割出来对应的前后缀, 若此时满足a的前缀等于b的后缀, 或者a的后缀等于b的前缀, 那么当前长度就是结果长度。
记得从大到小枚举, 这样才是最长。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
int main()
{
string a, b;
cin >> a >> b;
int n = min(a.size(), b.size()); // 最大长度
for (int i = n - 1; i >= 0; i--)
{ // pre为字符串长度为i的前缀, last为字符串长度为i的后缀
string prea = a.substr(0, i), lasta = a.substr(a.size() - i, i);
string preb = b.substr(0, i), lastb = b.substr(b.size() - i, i);
if (prea == lastb || preb == lasta)
{
cout << i << endl;
break;
}
}
return 0;
}
5 周五
5.1 B
该题需要记录三个状态, 当前点是否被搜过st, 已经搜了多少个点res, 搜完所有点的方案ans。
其中ans就是我们要求的, 当dfs中res为点总数时将ans++即可。
代码
const int N = 22;
int n, m;
int st[N][N];
int ans;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
void dfs(int x, int y, int res)
{
if (res == n * m)
{
ans++;
return;
}
st[x][y] = true;
for (int i = 0; i < 8; i++)
{
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m)
continue;
if (st[a][b])
continue;
dfs(a, b, res + 1);
}
st[x][y] = false;
}
int main()
{
int T;
cin >> T;
while (T--)
{
int x, y;
cin >> n >> m >> x >> y;
memset(st, false, sizeof st);
ans = 0;
dfs(x, y, 1);
cout << ans << endl;
}
return 0;
}
5.1 C
搜索顺序：
flower为还可以遇见花的次数, beer为还可以遇见店的个数, sum为当前酒剩余。
当前次遇见若可以是花, 即flower>0, 则继续递归 sum - 1, flower+1。
若可以是点, 即beer>0, 则继续递归 sum*=2, beer+1。
终点条件就当flower和beer都为0, 且sum也为0时, 将最终方案数res++。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
int res;
int n, m;
void dfs(int flower, int beer, int sum)
{
if (flower == 0 && beer == 0)
{
if (!sum)
res++;
return;
}
if (!sum)
return;
if (flower > 0)
dfs(flower - 1, beer, sum - 1);
if (beer > 0)
dfs(flower, beer - 1, sum * 2);
}
int main()
{
cin >> m >> n;
dfs(n, m, 2);
cout << res << endl;
return 0;
}