Atcoder Beginner Contest #293

A:

Description:

给出一个字符串 $S$，其长度为 $|S| \ (1 \le |S| \le 100)$，将所有 $S_{2i}$ 和 $S_{2i-1}$ 对调后输出。

Solution:

直接模拟。因为读入量较小，所以可以直接用字符数组然后存下标为 $1 \sim |S|$，然后枚举 $i$ 操作即可。时间复杂度 $O(n)$，可以稳定通过。

Code:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    char s[110];
    cin >> s + 1;
    int len = strlen(s + 1);
    for(int i = 1;i <= len / 2;i++)
        cout << s[i * 2] << s[i * 2 - 1];
    if(len & 1) cout << s[len];
    cout << endl;
    system("pause");
    return 0;
}

B:

Description:

给出一个长为 $n \ (1 \le n \le 2 \times 10^5)$ 的数组 $A = \{A_1,A_2,A_3,......A_n\}$。按照 $1 \sim n$ 的顺序进行如下操作：

当操作到第 $A_i$ 时，如果 $i$ 在前面的数种没有被“覆盖”过，那么“覆盖”$A_i$。如果 $i$ 被覆盖了，那么跳过。

举个例子：$n = 3,A = \{2,3,1\}$。按照如下顺序操作：

$(1):i = 1$，此时 $i$ 未被“覆盖”。那么“覆盖” $A_1=2$ 。

$(2):i = 2$，此时 $i$ 被覆盖过了。那么跳过。

$(3):i = 3$，此时 $i$ 未被“覆盖”，那么“覆盖” $A_3 = 1$ 。

最后，我们发现仅有 $3$ 这一编号未被覆盖。

你要做的是找到共有多少个编号 $i$ 直到所有操作结束都未被覆盖，并增序输出他们的编号。

Solution:

简单模拟，关键是看懂并理解题目。

分析后可以很快发现，这道题是否能 $O(n)$ 扫描解决的关键因素在于每次决策的影响是否会改变。而每次决策只会影响到 $A_i$ 这一位置。并且第一次操作不受任何影响。所以实际上在一开始处理第一次操作时，整个序列的影响就已经确定了。那么直接模拟即可。

时间复杂度 $O(n)$ ，可以稳定通过。

Code:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;cin >> n;
    vector<int> v(n + 1,0);
    vector<bool> c(n + 1,0);
    for(int i = 1;i <= n;i++)
        cin >> v[i];
    for(int i = 1;i <= n;i++)
        if(!c[i])
            c[v[i]] = true;
    int ans = 0;
    for(int i = 1;i <= n;i++)
        ans += !c[i];
    cout << ans << "\n";
    for(int i = 1;i <= n;i++)
        if(!c[i]) cout << i << " ";
    cout << "\n";
    system("pause");
    return 0;
}

C:

Description:

给出一个 $n \times m \ \ (1 \le n,m \le 10)$ 的矩阵，问从 $(1,1)$ 走到 $(n,m)$，且每次只能向下或向右走，最终使得整条路径上的所有数组均互不相同的路径共有多少种？

Solution:

注意到 $n,m$ 的范围。同时因为只能向下或向右，所以路径长度是固定的：$(1,1)$ 到 $(n,m)$ 的曼哈顿距离。即 $n + m - 1$。这个数最多不超过 $10 + 10 - 1 = 19$，则可以考虑直接使用深搜枚举。在每个点分别做一次向下/右的决策，最大总计算量为 $2^{19} = 524288$，可以通过。

总体时间复杂度 $O(nm + 2^{n + m - 1})$，可以稳定通过。

Code:

#include <bits/stdc++.h>
using namespace std;
int n,m,ans,g[15][15];
map<int,bool> mp;

inline void dfs(int i,int j)
{
    if(mp[g[i][j]]) return;
    else if(i > n || j > m) return ;
    else if(!mp[g[i][j]] && i == n && j == m){ans++;return ;}
    else mp[g[i][j]] = true,dfs(i + 1,j),dfs(i,j + 1),mp[g[i][j]] = false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)   
        for(int j = 1;j <= m;j++)
            cin >> g[i][j];
    dfs(1,1);
    cout << ans << endl;
    system("pause");
    return 0;
}

D:

Description:

给出 $n \ (1 \le n \le 2 \times 10^5)$ 根绳子，每根绳子的两端分别被染上红/蓝色。现在要进行 $m\ (1 \le m \le 2 \times 10^5)$ 次操作，第 $i$ 次操作会将第 $A_i$ 根绳子的任意一端($B_i \in [\texttt{‘R’,’B’}]$)和第 $C_i$ 根绳子的任意一端($D_i \in [\texttt{‘R’,’B’}]$) 绑在一起。保证任意一根绳子的任意一端最多只会被绑一次。所有操作结束后，绳子会形成若干个“块”。试求这若干个块中有多少个块呈现出环状，即所有绳子头尾相连的情况。

Solution:

结合样例分析，将整个过程抽象为图：一共有 $n$ 条固有边连接 $2 \times n$ 个点，再在这些点之间连 $m$ 条另外的边。不难发现因为所有端点最多仅会被连一次，所以要么整个块只有一个环，要么没有环。那么判断的标准就是这个块中所有的绳子的头尾均被连接(因为题目说了，不会出现三岔路口的情况)。所以用布尔数组记录每条绳子左右端点是否被连。

接下来，要想如何将这些点的联通关系保存起来。建图当然是可行的。不过还有更加便捷的办法：直接使用并查集。并查集最大的弊端是无法很好地保存若干元素之间的某些相对逻辑关系，但因为我们判定的充要条件是所有绳子两个端点均被连接，所以这实际上和块内绳子的联通关系无关。(无论是 $1 \to 2 \to 3 \to 4$，还是 $1 \to 4 \to 2 \to 3$ 都能形成环。)所以只要满足上面的计数条件即可。那么直接使用并查集保存从属关系，然后在块内统计即可。

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
bool R[N],B[N];
int n,m,p[N];

inline int find(int u)
{return p[u] == u ? u : p[u] = find(p[u]);}

inline void merge(int a,int b)
{
    int ll = find(a);
    int rr = find(b);
    if(ll != rr)
        p[ll] = rr;
    return ;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    vector<bool> rec(n + 1,true);
    for(int i = 1;i <= n;i++)
        p[i] = i;
    for(int i = 1;i <= m;i++)
    {
        int a,c;
        char b,d;
        cin >> a >> b;
        cin >> c >> d;
        if(b == 'R') R[a] = true;
        if(b == 'B') B[a] = true;
        if(d == 'R') R[c] = true;
        if(d == 'B') B[c] = true;
        // cout << a << " " << c << endl;
        merge(a,c);
    }
    for(int i = 1;i <= n;i++)
        if(!(R[i] && B[i]))
            rec[i] = false;
    for(int i = 1;i <= n;i++)
        if(!rec[i])
            rec[find(i)] = false;
    int ans = 0,sum = 0;
    for(int i = 1;i <= n;i++)
        if(find(i) == i) sum++;
    vector<bool> vis(n + 1,false);
    for(int i = 1;i <= n;i++)
        if(rec[find(i)] && !vis[find(i)])
            ans++,vis[find(i)] = true;
    cout << ans << " " << sum - ans << endl;
    system("pause");
    return 0;
}

E:

Description:

给出三个正整数 $A,X,M \ (1 \le A,M \le 10^9,1 \le X \le 10^{12})$，试求以下式子：
$$\sum_{i = 0}^{X - 1}A^i \ \bmod M$$

Solution:

先计算原式，不考虑取模等问题：
$$S = \sum_{i = 0}^{X - 1} A^i = A^0 + A^1 + \cdots +A^{X-1} \\\\ A \times S = A \times {\bigg (}\sum_{i = 0}^{X - 1}A^i{\bigg )} = A^1 + A^2 + \cdots + A^X\\\\ (A - 1) \times S = (A \times S) - S = A^X + (A^{X-1} - A^{X-1}) + \cdots + (A^{1} - A^1) - A^0\\\\ $$
那么，可以得到 $(A-1) \times S = A^{X} - 1$。
所以，我们要求的原式为 $\frac{A^{X} - 1}{A - 1}$。答案就应该是 $\frac{A^X-1}{A-1} \bmod M$。

接下来看取模。首先想到了逆元，但是有可能出现 $\gcd(ans,M) \gt 1$ 的情况，故可能没有逆元，排除。

其实，可以从一开始那个同余式上面找突破口。

因为 $ans \equiv \frac{A^X-1}{A-1} \pmod M$，又因为同余式的基本性质中有这样一条：如果 $a \equiv b \pmod x,a \times c \equiv b \times c \pmod {M \times c}\ \ (c \in \mathbb{Z^+})$。那么，我们可以直接将原等式两边乘上一个 $(A - 1)$，得到 $(A - 1) \times ans \equiv A^X - 1 \pmod {M \times (A-1)}$。同时，因为原式中 $ans = \frac{A^X - 1}{A-1}$ 本身就是一个整数，所以最终结果也一定能够被整除。因此，可以直接用快速幂算出 $M \times (A - 1)$ 意义下的 $A^X - 1$，再除上 $A - 1$ 即可。这样便能在 $O(\log_2M)$ 时间内解决本题。可以稳定通过。

Code:

#include <bits/stdc++.h>
#define int __int128
using namespace std;
int a,x,m;

inline int qmi(int a,int b,int p)
{
    int ans = 1 % p;
    while(b != 0)
    {
        if(b & 1)
            ans = (ans % p) * (a % p) % p;
        a = (a % p) * (a % p) % p;
        b >>= 1;
    }
    return ans;
}

inline int read()
{
    char c = getchar();
    int val = 0,sign = 1;
    while(c < 48 || c > 57)
        sign = (c == 45) ? -1 : sign,
        c = getchar();
    while(c <= 57 && c >= 48)
        val = (val << 1) + (val << 3) + c - '0',
        c = getchar();
    return sign * val;
}

inline void write(int x)
{
    if(x < 0)
        putchar(45),
        x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

signed main()
{
    a = read(),x = read(),m = read();
    if(a == 1)
    {
        write(x % m);
        putchar('\n');
        system("pause");
        return 0;
    }
    int modn = m * (a - 1);
    int original = qmi(a,x,modn);
    int ans = 0;
    original = (original + modn) % modn;
    if(a - 1 == 0) ans = 0;
    else ans = original / (a - 1);
    write(ans);putchar('\n');
    system("pause");
    return 0;
}