2024算法基础公选课练习八（综合4）

一、前言

前面几个题都是考察字符串处理，后面的都是偏难的思维和图论题

二、题目总览

三、具体题目

3.1 问题 A: 昊城的分割游戏

思路

枚举前几项，然后发现规律

我的代码

#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;
#define pb emplace_back
#define all(v) v.begin(),v.end()/*
1 => 1
1 2 => 1
1 2 3 => 0
1 2 3 4 => 1
1 2 3 4 5 => 1
1 2 3 4 5 6 => 1
1 2 3 4 5 6 7 => 0
1 2 3 4 5 6 7 8 => 0
1 ... 9 => 1
*/void solve(){int n;std::cin >> n;std::cout << (n%4==1||n%4==2?1:0) << '\n';
}int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int tt = 1;// std::cin >> tt;for(int ti = 0;ti<tt;++ti){solve();}return 0;
}

3.2 问题 B: 盲兔打字

思路

分左右，注意边界不能越出

我的代码

#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;
#define pb emplace_back
#define all(v) v.begin(),v.end()
/*
qwertyuiop
asdfghjkl;
zxcvbnm,./ 
*/
void solve(){std::string line1 = "qwertyuiop";std::string line2 = "asdfghjkl;";std::string line3 = "zxcvbnm,./";std::string dir;std::cin >> dir;std::string s;std::cin >> s;std::string ans;if(dir=="R"){for(const auto& c:s){int pos;if((pos =line1.find(c))!=std::string::npos){if(pos!=0){ans+=line1[pos-1];}else{ans+=line1[pos];}}else if((pos =line2.find(c))!=std::string::npos){if(pos!=0){ans+=line2[pos-1];}else{ans+=line2[pos];}}else if((pos =line3.find(c))!=std::string::npos){if(pos!=0){ans+=line3[pos-1];}else{ans+=line3[pos];}}}}else{//dir=="L"for(const auto& c:s){int pos;if((pos =line1.find(c))!=std::string::npos){if(pos!=line1.size()-1){ans+=line1[pos+1];}else{ans+=line1[pos];}}else if((pos =line2.find(c))!=std::string::npos){if(pos!=line2.size()-1){ans+=line2[pos+1];}else{ans+=line2[pos];}}else if((pos =line3.find(c))!=std::string::npos){if(pos!=line3.size()-1){ans+=line3[pos+1];}else{ans+=line3[pos];}}}}std::cout << ans << '\n';
}int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int tt = 1;// std::cin >> tt;for(int ti = 0;ti<tt;++ti){solve();}return 0;
}

3.3 问题 C: 兔兔的故障键盘

思路

根据题意，枚举'a'到'z'每一个字母，如果有出现字母连续出现的次数为奇数，那么这个字符一定没有故障，如果连续出现次数为偶数，则无法判断这个字母是否出现故障

我的代码

#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;
#define pb emplace_back
#define all(v) v.begin(),v.end()void solve(){std::vector<char> ans;std::string s;std::cin >> s;for(char c = 'a';c<='z';++c){bool flag = false;int cnt = 0;for(int i = 0;i<s.size();++i){if(s[i]==c){if(!flag) flag = true;++cnt;}else{if(cnt&1){ans.pb(c);break;}flag = false;cnt = 0;}}if(flag&&cnt&1){ans.pb(c);}}std::sort(all(ans));ans.erase(std::unique(all(ans)),ans.end());for(const auto &c:ans) std::cout << c;std::cout << '\n';
}int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int tt = 1;std::cin >> tt;for(int ti = 0;ti<tt;++ti){solve();}return 0;
}

3.4 问题 D: 一锐的字符串游戏

思路

根据题意，只看当前是否有连续两个相同的字符，因此考虑使用栈，如果当前没有两个相邻的两个字符，那么就一锐就输了，否则就是一锐赢了

我的代码

注意使用std::stack的时候要先判断栈非空才能取出top()元素，或者放入一个哨兵也可以解决这个问题

#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;
#define pb emplace_back
#define all(v) v.begin(),v.end()void solve(){std::string s;std::cin >> s;std::stack<char> stack;bool flag = false;for(const auto& c:s){if(!stack.empty()&&stack.top()==c){flag = !flag;stack.pop();}else{stack.emplace(c);}}std::cout << (flag?"Yes":"No") << '\n';
}int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int tt = 1;// std::cin >> tt;for(int ti = 0;ti<tt;++ti){solve();}return 0;
}

3.5 问题 E: 奇怪的整数序列

思路

由于数据范围限制，不能暴力求解，我们只考虑O(n*logn)的时间复杂度，因此求解f()函数的时候，需要将时间复杂度降至O(logn)的级别，我们发现2的i(i>=0)次方的值都是1，又发现任何偶数的f()值与它除以2的值是相同的，而奇数只能通过减一才能变成偶数（至于为什么只能减一，不能加一，因为我们是反着求f函数的，因此跟正着求的相反的操作）。然后通过cnt数组计数一个f()值出现的次数，计算累加cnt，即加上(1+cnti-1)*(cnti-1)/2。具体实现见代码

我的代码

#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;
#define pb emplace_back
#define all(v) v.begin(),v.end()/*
f(0) = 0;
f(2·x) = f(x);
f(2·x + 1) = f(x)+1f(0) = 0;f(1) = 1;f(2) = 1;
f(3) = 2;f(4) = 1;f(5) = 2;
f(6) = 2;
f(7) = 3;f(8) = 1;f(9) = 2;
f(10) = 2;
f(11) = 3;
f(12) = 2;
*/int n;
std::vector<int> a(N,0);
std::vector<int> cal(N,0);
std::vector<int> cnt(N,0);
std::vector<int> fac;void pre(){int t = 1;while(t<=int(1e9)){fac.pb(t);t*=2;}
}int f(int x){int cnt = 0;while(*std::lower_bound(all(fac),x)!=x){//O(logn*logn)if(x&1){x-=1;++cnt;}else{x/=2;}}return ++cnt;
}void solve(){std::cin >> n;for(int i = 1;i<=n;++i) std::cin >> a[i];for(int i = 1;i<=n;++i){cal[i] = f(a[i]);++cnt[cal[i]];}i64 ans = 0;for(int i = 1;i<N;++i){if(cnt[i]>1){ans+=1LL*cnt[i]*(cnt[i]-1)/2;}}std::cout << ans << '\n';
}int main(){std::cin.tie(nullptr)->sync_with_stdio(false);pre();int tt = 1;// std::cin >> tt;for(int ti = 0;ti<tt;++ti){solve();}return 0;
}

3.6 问题 F: 兔兔的和谐图

思路

考察并查集，难在后续的check和merge，以及如何控制时间复杂度，暴力使用并查集判断是否成为和谐图会超时，这块也不知道怎么说思路，大家直接看代码吧

我的代码

#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using pii = std::pair<int,int>;
constexpr int N = 2e5+5,M = 1e6+5,INF = 0x3f3f3f3f;
#define pb emplace_back
#define all(v) v.begin(),v.end()int n,m;struct DSU {int _n;std::vector<int> _fa,_size,_max,_min;DSU(){}DSU(int n){init(n);}void init(int n) {_fa.resize(n);_max.resize(n);_min.resize(n);std::iota(_fa.begin(),_fa.end(),0);std::iota(_max.begin(),_max.end(),0);std::iota(_min.begin(),_min.end(),0);_size.assign(n,1);}int find(int x) {if(x!=_fa[x]) {_fa[x] = find(_fa[x]);}return _fa[x];}bool same(int x,int y) {return find(x)==find(y);}bool merge(int x,int y) {int fx = find(x);int fy = find(y);if(fx!=fy) {_size[fx] += _size[fy];_fa[fy] = fx;_min[fx] = std::min(_min[fx],_min[fy]);_max[fx] = std::max(_max[fx],_max[fy]);return true;}return false;}
};std::vector<bool> vis(N,false);void solve(){std::cin >> n >> m;DSU dsu(n+5);for(int i = 0;i<m;++i){int u,v;std::cin >> u >> v;// edges[u].pb(v);// edges[v].pb(u);dsu.merge(u,v);}int cur_fa = 0,cur_min = 0,cur_max = 0;int ans = 0;for(int i = 1;i<=n;++i){if(vis[i]) continue;cur_fa = dsu.find(i);cur_min = dsu._min[cur_fa];cur_max = dsu._max[cur_fa];for(int j = cur_min;j<=cur_max;++j){if(!vis[j]){int j_fa = dsu.find(j);if(cur_fa!=j_fa){dsu.merge(cur_fa,j_fa);++ans;cur_max = dsu._max[cur_fa];}vis[j] = true;}}}std::cout << ans << '\n';
}int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int tt = 1;// std::cin >> tt;for(int ti = 0;ti<tt;++ti){solve();}return 0;
}