# abc447_c


给你由大写英文字母组成的字符串 $S$ 和 $T$ 。

您可以按任意顺序执行以下两种类型的运算任意次数（可能为零）：

- 在 $S$ 的任意位置（可能是开头或结尾）插入一个字符 `A`。
- 在 $S$ 中选择一个字符 `A` 并删除。其余字符按原来的顺序连接。

判断是否有可能使 $S$ 等于 $T$ ，如果有可能，求所需运算的最小总数。

https://atcoder.jp/contests/abc447/tasks/abc447_c


# abc447_d

可以在一个字符串中删除一个子序列 `ABC`，问最多可以删除几次

https://atcoder.jp/contests/abc447/tasks/abc447_d

```cpp
#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
	cin>>s;
	int a=0,ab=0,abc=0;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='A')
			a++;
		if(s[i]=='B'&&a!=0)
			a--,ab++;
		if(s[i]=='C'&&ab!=0)
			ab--,abc++;
	}
	cout<<abc;
	return 0;
}
```


# abc447_e


给你一个简单相连的无向图 $G$ ，其中有 $N$ 个顶点和 $M$ 条边。这里是 $N \geq 2$ 。顶点的编号为 $1$ 至 $N$ ，边的编号为 $1$ 至 $M$ ；每条边都有一个称为**成本**的值，边 $i$ 的成本为 $2^i$ 。

现在，您要删除 $G$ 中的一些边，这样 $G$ 的连通部分的数目就会正好变为 $2$ 。可以证明，在本问题的约束条件下，这总是可以实现的。

求删除的边的成本总和的最小值，模数为 $998244353$ 。

https://atcoder.jp/contests/abc447/tasks/abc447_e

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int two[200000 + 5];
int n, m;
int u[200000 + 5], v[200000 + 5];
// 并查集
int fa[200000 + 5];
int findRoot(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = findRoot(fa[x]);
}
int main()
{
    two[0] = 1;
    for (int i = 1; i <= 200000; i++)
        two[i] = two[i - 1] * 2 % MOD;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> u[i] >> v[i];

    for (int i = 1; i <= n; i++)
        fa[i] = i;
    int num = n; // 联通块数量
    int ans = 0;
    for (int i = m; i >= 1; i--)
    {
        int rootU = findRoot[u[i]];
        int rootV = findRoot[v[i]];
        if (num == 2 && rootU != rootV)
        {
            ans = (ans + two[i]) % MOD;
            continue;
        }
        // 添加这条边
        if (rootU != rootV)
        {
            fa[rootU] = rootV;
            num--;
        }
    }
    cout << ans;
}
```

# abc448_c

$n$ 个数 $a_1\sim a_n$。$q$ 次询问。

每次需要求出去掉 $k(k\le 5)$ 个数后，剩下数的最小值。

https://atcoder.jp/contests/abc448/tasks/abc448_c

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

int n, k, Q;
int a[300000 + 5];
int b[6];
int id[300000 + 5];
bool cmp(int x, int y)
{
    return a[x] < a[y];
}
void work()
{
    for (int i = 1; i <= n; i++)
    {
        int now = id[i]; // 当前需要判断是否被删除了的下标
        bool flag = true;
        for (int j = 1; j <= k; j++)
            if (now == b[j])
                flag = false;
        if (flag)
        {
            cout << a[now] << "\n";
            return;
        }
    }
}
int main()
{
    cin >> n >> Q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++)
        id[i] = i;
    sort(id + 1, id + n + 1, cmp);

    while (Q--)
    {
        cin >> k;
        for (int i = 1; i <= k; i++)
            cin >> b[i];
        work();
    }
}
```

# 代码源 R51D

https://bs.daimayuan.top/p/318

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
int lcm(int a, int b)
{
    return a / __gcd(a, b) * b;
}
int n, ans;
// d[1]~d[tot] 都是 n 的因子
int tot, d[1000 + 5];
void dfs(int now, int L)
{
    if (L > n)
        return;
    if (now == tot + 1)
    {
        if (L == n)
            ans++;
        return;
    }
    dfs(now + 1, L);
    dfs(now + 1, lcm(L, d[now]));
}
signed main()
{
    cin >> n;
    tot = 0;
    for (int i = 1; i * i <= n; i++)
    {
        if (n % i != 0)
            continue;
        d[++tot] = i;
        if (n / i != i)
            d[++tot] = n / i;
    }
    ans = 0;
    dfs(1, 1);
    cout << ans;
}
```

## dp

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
int n, ans;
int two[1500 + 5];
// lcm 恰好为 i 有 f(i) 种方案
map<int, int> book;
int f(int x)
{
    if (book[x] != 0)
        return book[x];
    if (x == 1)
        return book[x] = 1;
    int cnt = 2;
    int ans = 0;
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i != 0)
            continue;
        cnt++;
        ans = (ans - f(i)) % MOD;
        if (x / i != i)
        {
            cnt++;
            ans = (ans - f(x / i)) % MOD;
        }
    }
    ans = (ans - 1) % MOD; // -f(1)
    ans = (ans + two[cnt] - 1) % MOD;
    return book[x] = ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    two[0] = 1;
    for (int i = 1; i <= 1500; i++)
        two[i] = two[i - 1] * 2 % MOD;
    cin >> n;
    cout << (f(n) + MOD) % MOD;
    return 0;
}
```