Contestant. Rank 2467. Rating +89.
A. Swap Odd and Even
题意
给定一个字符串，将所有 \(2x\) 和 \(2x+1\) 位字符交换位置，输出操作后的字符串。
思路
模拟即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 1e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void init(){}
void solve() {
string s;
cin >> s;
for(int i=0;i<s.size()/2;i++){
char t = s[2 * i];
s[2 * i ] = s[2 * i + 1];
s[2 * i + 1] = t;
}
cout << s;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
init();
int t = 1;
//cin >> t;
while (t --) solve();
}快速签到
B. Call the ID Number
题意
给定一个序列 \(a\)，对于第 \(i\) 个元素，若 \(i\) 没被标记，那么将 \(a_i\) 标记。遍历序列后，输出剩余未标记的数。
思路
模拟即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 1e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void init(){}
void solve() {
int n;
cin >> n;
vector<bool> vis(n + 1);
int cnt = n;
for(int i=1;i<=n;i++){
int cur;
cin >> cur;
if(vis[i] || vis[cur]) continue;
cnt --;
vis[cur] = true;
}
cout << cnt << '\n';
for(int i=1;i<=n;i++){
if(!vis[i]) cout << i << ' ';
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
init();
int t = 1;
//cin >> t;
while (t --) solve();
}依然快速签到
C. Make Takahashi Happy
题意
给定一个 \(H \times W\) 的加权矩阵，规定一次移动只能向下或向右走，且不能超出矩阵范围。对于起点 \((1,1)\) 和终点 \((H, W)\)，输出满足路径中无重复元素的路径数。
思路
考虑到题给范围特别小，我们不妨直接 \(Dfs\)，用回溯搜索的方式记录当前元素出现了几次，若出现两次跳出搜索即可。
时间复杂度：\(O(n^2)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 1e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
int a[20][20], h, w, ans;
map<int, int> cnt;
void init(){}
void dfs(int x, int y){
if(x == h && y == w){
ans ++;
return;
}
if(x + 1 <= h && cnt[a[x + 1][y]] == 0) {
cnt[a[x + 1][y]] ++;
dfs(x + 1, y);
cnt[a[x + 1][y]] --;
}
if(y + 1 <= w && cnt[a[x][y + 1]] == 0) {
cnt[a[x][y + 1]] ++;
dfs(x, y + 1);
cnt[a[x][y + 1]] --;
}
}
void solve() {
cin >> h >> w;
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++)
cin >> a[i][j];
cnt[a[1][1]] ++;
dfs(1, 1);
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
init();
int t = 1;
//cin >> t;
while (t --) solve();
}就很暴力
D. Tying Rope
题意
定义一段绳子有两个端点，一端为红色，另一端为蓝色。对于 \(k\) 次操作，将第 \(A\) 个绳子颜色为 \(B\) 的一端和第 \(C\) 个绳子颜色为 \(D\) 的一端连接。
特别地，满足一端绳子不会和两条及以上绳子连起来。
输出连通块中环和链的个数。
思路1
首先，既然考虑到这个特别的条件，我们完全可以不管颜色，因为题目一定有解，对于一段绳子，它的一个端点只会出现在最多一次操作里。所以，在本次操作后，下一次再访问到这个绳子，一定是另一个点了。
为了读入数据方便，我们定义绳子左端点是红色的、右端点是蓝色的。
那么，按照上述方法，我们可以很简单地得到一条绳子它的左端点和右端点分别和哪条绳子连起来了。
接着，我们只需遍历所有绳子，对于第 \(i\) 个绳子，若它未被访问到，那么他一定是新的连通块的一部分，我们向左和向右找寻边界。当我们遍历到端点未和其他点连接时，结束寻找，此时枚举到的所有点都是这个连通块的一部分。但，若我们遍历到了之前遍历过的绳子，那么很显然存在了环，所以我们直接统计个数并跳过这个连通块继续寻找。
在找寻边界的时候，因为读入数据的特殊性，对于 \(A \rightarrow B \rightarrow C\)，若 \(B\) 的右端点和 \(A\) 的右端点连接，那么会出现死循环，但是此时会出现回到上一个相邻点的情况，而且我们不难发现，只有这种特殊情况才会出现"回溯"。所以，我们只需记录前一个绳子 \(A\)，找到 \(B\) 的左右端点中不是 \(A\) 的那个点所连接的绳子 \(C\) 即可。
时间复杂度：\(O(m + n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void init(){}
void solve() {
int n, m;
cin >> n >> m;
//规定左红右蓝
vector<vector<int>> ac(n + 1, vector<int>(2, -1));
for(int i=1;i<=m;i++){
int a, b, c, d;
char bc, dc;
cin >> a >> bc >> c >> dc;
b = bc == 'R' ? 0 : 1;
d = dc == 'R' ? 0 : 1;
ac[a][b] = c;
ac[c][d] = a;
}
vector<bool> vis(n + 1);
int ans1 = 0, ans2 = 0;
for(int i=1;i<=n;i++){
if(vis[i]) continue;
int now, pre;
vis[i] = true;
pre = i, now = ac[i][0];
bool ok = false;
if(now != -1){
vis[now] = true;
while(true){
int tmp = now;
now = ac[now][0] == pre ? ac[now][1] : ac[now][0];
pre = tmp;
if(now == -1) break;
if(vis[now]){
ans1 ++;
ok = true;
break;
}
vis[now] = true;
}
}
pre = i, now = ac[i][1];
if(!ok && now != -1) {
vis[now] = true;
while (true) {
int tmp = now;
now = ac[now][1] == pre ? ac[now][0] : ac[now][1];
pre = tmp;
if (now == -1) break;
if (vis[now]) {
ans1++;
ok = true;
break;
}
vis[now] = true;
}
}
if(!ok) ans2 ++;
}
cout << ans1 << ' ' << ans2 << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
init();
int t = 1;
//cin >> t;
while (t --) solve();
}无脑模拟（（
思路2
本题也可以用并查集完成。
待补充
磕了半天居然磕出来了
E. Geometric Progression
题意
给定三个整数 \(A, X, M\)，输出 \((\displaystyle{\sum^{X-1}_{i=0} A ^ i) \bmod M}\)。
思路
首先，很明显这是等比数列求和公式，最后的答案就是 \(\frac{A ^ X - 1}{A-1} \bmod M\)。
但是，问题在于这个除法取模。
一般除法取模需要求逆元，但是本题的 \(A, M\) 是任意的，所以 \(M\) 不是质数并且 \(A, M\) 不互质的时候，无法求出逆元。
但是，若我们对 \(A^X - 1\) 因式分解，当 \(A = 1\) 时一定是一个让式子为 \(0\) 的根，也就是说可以提出 \(A - 1\)。
那么，\(A - 1\) 就可以消掉了。
为了取模计算方便，我们不妨在求快速幂的时候，对 \(M(A - 1)\) 取模，最后除掉 \(A - 1\) 即可。
因而，最后我们可以得到一个式子：\(\frac{A ^ X \bmod (M(A - 1)) - 1}{A-1}\)。
当然，当 \(A = 1\) 的时候需要特判，这只和 \(X \bmod M\) 的奇偶性有关。
时间复杂度：有点复杂
注意M(A-1)会爆long long，需要用__int_128
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int __int128_t
#define pii pair<int, int>
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void init(){}
int qp(int a, int b, int m) {
a %= m;
int res = 1;
while (b > 0) {
if (b & 1) res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
void solve() {
long long a, x, m;
cin >> a >> x >> m;
cout << (a == 1 ? x % m : (((long long) qp(a, x, m * (a - 1)) - 1) / (a - 1)) % m) << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
init();
int t = 1;
//cin >> t;
while (t --) solve();
}麻了，被逆元坑了