文章目录

• A - Swap Odd and Even
• B - Call the ID Number
• C - Make Takahashi Happy
• D - Tying Rope
• E - Geometric Progression
• F - Zero or One
• G - Triple Index
• Ex - Optimal Path Decomposition

A - Swap Odd and Even

https://atcoder.jp/contests/abc293/tasks/abc293_a
给出一个字符串 $s$，交换 $s$ 的奇数位与偶数位。

纯纯的模拟。

#include
using namespace std;
int main()
{
//    freopen("input.in","r",stdin);
//    freopen("output.out","w",stdout);string s;cin>>s;for(int i=0;i<s.size();i+=2){swap(s[i],s[i+1]);}cout<<s;return 0;
}

B - Call the ID Number

https://atcoder.jp/contests/abc293/tasks/abc293_b
给出 $n$ 和 $a$ 序列。

• 如果第 $i$ 个人被打过了，他什么事都不用做。
• 如果第 $i$ 个人没有被打过，那他打电话给第 a i a_i ai​ 个人。

#include
using namespace std;
int n,a[200100],sum=0;
int main()
{
//    freopen("input.in","r",stdin);
//    freopen("output.out","w",stdout);cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;if(!a[i]) a[x]=1;}for(int i=1;i<=n;i++){if(!a[i]) sum++;}cout<<sum<<endl;for(int i=1;i<=n;i++) {if(!a[i]) cout<<i<<' ';}return 0;
}

C - Make Takahashi Happy

https://atcoder.jp/contests/abc293/tasks/abc293_c

本题题解转载于这里

AT_abc293_c 题解

闪现
洛谷 abc293c | AtCoder abc293c

题目大意

给你一个 $ H $ 行 $ W $ 列的方阵，高桥要从这个方阵的 $ (1 , 1) $ 走到 $ (H , W) $ ，如果他在这个过程中经过的所有数字都不相同，那么他就会开心；如果他经过的数字中有相同的，他就会不开心。输出高桥所有走法中，可以使他开心的走法的数量。

题目分析

因为是要找到使高桥开心的所有的路径，我便想到了 for 循环，但是又一想，发现 for 循环的话既慢又不好控制层数，因此我想到了递归。

思路拆分 and 代码实现

• 输入
• 递归 and 判断函数
• 输出

输入和输出部分在此处不再多说，让我们直接进入下面的递归和判断部分。

递归部分需要一个数组 $ qk $ 存高桥经过的数，还需要判断：如果他没有到第 $ H $ 行，那么就递归到下一行；如果他没有到地 $ W $ 列，那么就递归到下一列… …直到他走到了第 $ H $ 行 $ W $ 列，然后就运行判断的函数，用一个数组 $ fuzhi $ 来复制一份 $ qk $ 中的数，排序后再看相邻的两个数有没有重复，有则不记录这一条路径，否则就记录。

为什么不能对原来的 $ qk $ 数组排序？

因为这个数组是存储高桥经过的数，如果对它排序，这个数组的顺序就会被打乱，体现不出高桥经过数的顺序，为了方便理解，让我们以一个样例加深理解：

以 AtCoder 原题中的样例 $ 1 $ 为例：

3 3
3 2 2
2 1 3
1 5 4

高桥先以 $ (1 , 1) , (2 , 1) , (3 , 1) , (3 , 2 ) , (3 , 3) $ 的路径移动，此时 $ qk $ 数组中存储的是 $ 3 , 2 , 2 , 3 , 4 $ 排序后是 $ 2 , 2 , 3 , 3 , 4 $ ，下一步递归时，高桥的路径变成了 $ (1 , 1) , (2 , 1) , (2 , 2) , (3 , 2 ) , (3 , 3) $ ， 数组中应该是$ 3 , 2 , 1 , 3 , 4 $ ，而因为经过了一次排序，现在变成了 $ 2 , 2 , 1 , 3 , 4 $ ，已经和原来的不一样了。

综上，不能对原来的 $ qk $ 数组排序。

由以上的分析，代码如下：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int qk[25] , fuzhi[25];
int sz[15][15];
int h , w;
int ans;
//qk，fuzhi：含义如题解中
//sz：存储方阵	h，w：存储行和列 
//ans：存储答案数量 
bool right(int cnt) //判断函数 
{for(int i = 1 ; i <= cnt ; i++){fuzhi[i] = qk[i]; //复制 }sort(fuzhi + 1 , fuzhi + cnt + 1); //排序 for(int i = 1 ; i <= cnt - 1 ; i++){if(fuzhi[i] == fuzhi[i + 1]) //有重复 {return 0;  //答案增加 0 个  }}return 1; //答案增加 1 个 
}
void dfs(int a , int b , int c)
//a，b：存现在高桥的行和列
//c：存储高桥这条路径现在在走第几个数 
{qk[c] = sz[a][b]; //存储高桥经过的数 if(a == h && b == w) //到终点 {ans += right(c); //判断并累加 return ; //返回上一层递归 }if(a != h){dfs(a + 1 , b , c + 1); //到下一行 }if(b != w){dfs(a , b + 1 , c + 1); //到下一列 }
}
int main()
{cin >> h >> w;for(int i = 1 ; i <= h ; i++){for(int j = 1 ; j <= w ; j++){cin >> sz[i][j];}}dfs(1 , 1 , 1); //递归 cout << ans << endl;return 0;
}

还有无注释版：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int qk[25] , fuzhi[25];
int sz[15][15];
int h , w;
int ans;
bool right(int cnt)
{for(int i = 1 ; i <= cnt ; i++){fuzhi[i] = qk[i];}sort(fuzhi + 1 , fuzhi + cnt + 1);for(int i = 1 ; i <= cnt - 1 ; i++){if(fuzhi[i] == fuzhi[i + 1]){return 0;}}return 1;
}
void dfs(int a , int b , int c)
{qk[c] = sz[a][b];if(a == h && b == w){ans += right(c);return ;}if(a != h){dfs(a + 1 , b , c + 1);}if(b != w){dfs(a , b + 1 , c + 1);}
}
int main()
{cin >> h >> w;for(int i = 1 ; i <= h ; i++){for(int j = 1 ; j <= w ; j++){cin >> sz[i][j];}}dfs(1 , 1 , 1);cout << ans << endl;return 0;
}

最后，附上 AC 的截图：

D - Tying Rope

https://atcoder.jp/contests/abc293/tasks/abc293_d
本题题解转载于这里

基础图论题。
值得一提的是，此题与 ABC292D 有异曲同工之妙：都是无向图，都是并查集。
由这篇题解，得前置知识：并查集。

题意

有 $n$ 根绳子，编号为 $1\sim n$，每根绳子都一端是蓝色，一端是红色。
有 $m$ 次操作，每次操作给定 $abcd$（其中字符 $b,d$ 表示颜色），表示将第 $a$ 根绳子颜色为 $b$ 的一端与第 $c$ 根绳子颜色为 $d$ 的一端连接。
操作完成后形成了一些连通块，问这些连通块中有几个是环，有几个不是环。
保证同一条绳子的同一端不会被连接两次。

例如，本题第一个样例：

其中橙色线段为原来的绳子，灰色为之后进行的连接。

分析

我们可以把绳子的端点看作点，绳子或绳子之间的连接看作边来建立无向图。图中共有 $2n$ 个点，存储时设第 $i$ 条绳子红色端点的编号为 $\mathrm{red}(i)=2i$，蓝色的为 $\mathrm{blue}(i)=2i+1$。
题中：保证同一条绳子的同一端不会被连接两次，即任意点的度数 $\le 2$。这就是说，一个连通块要么是环，要么是链。
无向图连通块问题，可以使用并查集解决：连接 $u,v$，等价于在并查集中合并 $u,v$ 所在集合。如果在连接 $u,v$ 前发现 $u,v$ 已经在同一个集合里了，那么这个集合（连通块）就是一个环，计数器 $ans+1$。

之后看第二个输出，它等于连通块个数减去环的个数，即 $t-ans$（$t$ 为最后的集合数量）。
如果计算 $t$？显然，最初（没有绳子，仅有端点）时，$t=2n$；之后每合并两个集合，$t$ 均减一。可以在合并集合时顺便计算 $t$ 的值。

依次操作完后，输出 $ans$ 和 $t-ans$ 的值即可。

代码

#include 
using namespace std;
int n,m,a,c,ans=0,t;
char b,d;
#define maxn 400002
#define maxm 400002
#define red(k) (k<<1)
#define blue(k) (k<<1|1)
int f[maxn];
inline int find(int k)
{if(f[k]==k)return k;return f[k]=find(f[k]);
}
// add(u,v) 合并 u,v 所在的两个集合，顺便统计 ans 和 t
inline void add(const int &u,const int &v)
{if(find(u)==find(v)){// 找到环++ans;return;}f[find(u)]=find(v);--t;
}
int main()
{cin >> n >> m;t=2*n;// 初始化勿忘for(int i=1;i<=2*n+2;++i)f[i]=i;for(int i=1;i<=n;++i)add(red(i),blue(i));for(int i=1;i<=m;++i){cin >> a >> b >> c >> d;// u,v 为 a,b 上对应颜色的点编号int u,v;if(b=='R') u=red(a);else u=blue(a);if(d=='R') v=red(c);else v=blue(c);add(u,v);}cout << ans << " " << t-ans << endl;return 0;
}

E - Geometric Progression

https://atcoder.jp/contests/abc293/tasks/abc293_e

本题题解转载于这里

题意
给定 $A,X,M$，求 ( ∑ i = 0 X − 1 A i ) m o d M (\sum\limits_{i=0}^{X-1}A^i)\bmod M (i=0∑X−1​Ai)modM。

• A , M ≤ 1 0 9 A,M\le 10^9 A,M≤109
• M ≤ 1 0 12 M\le 10^{12} M≤1012

题解
由于看到 $X$ 很大，又和 A i A^i Ai 有关，所以很自然的就会想到快速幂。

考虑把 $X$ 二进制分解，如果 $X$ 的二进制表示从右往左数第 $i$ 位是 $1$，那么答案 $ans$ 就要变为 a n s × a 2 i + 1 + a + ⋯ + a 2 i − 1 ans\times a^{2^i}+1+a+\cdots+a^{2^i-1} ans×a2i+1+a+⋯+a2i−1 。而 a 2 i a^{2^i} a2i 和 1 + a + ⋯ + a 2 i − 1 1+a+\cdots+a^{2^i-1} 1+a+⋯+a2i−1 可以在类快速幂算法中进行计算。
代码

#include 
using namespace std;
typedef long long LL;
LL a,x,m;
LL get_ans (LL a,LL b,LL m) {LL ans = 0,aa = a,bb = 1;while (b) {if (b & 1) ans = (ans * aa + bb) % m;bb = (bb * aa + bb) % m,aa = aa * aa % m;b >>= 1;}return ans;
}
int main () {cin >> a >> x >> m;cout << get_ans (a,x,m) << endl;return 0;
}

F - Zero or One

https://atcoder.jp/contests/abc293/tasks/abc293_f

暂无题解，静待更新。

G - Triple Index

https://atcoder.jp/contests/abc293/tasks/abc293_g

暂无题解，静待更新。

Ex - Optimal Path Decomposition

https://atcoder.jp/contests/abc293/tasks/abc293_h

暂无题解，静待更新。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！