A.Shovels and Swords

题意：

两个木棍一个钻石做一把钻石铲，一个木棍两个钻石做一把钻石剑，现在有个木棍，个钻石，询问能制作的钻石工具之和最大为多少？

题解：

当远小于时，答案为；同理，远小于时，答案为；其余情况答案为。同时答案为

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    ll a, b;
    scanf("%lld%lld", &a, &b);
    printf("%lld\n", min(min(a, b), (a + b) / 3));
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Shuffle

题意：

给定一个长度为的数组，其中只有为，其余均为。现在给出次操作，每次操作给定，可以从中任意选择两个数进行交换，也可以自己与自己进行交换。询问最终可以为的位置最多有多少个。

题解：

区间合并，每次只需要判断两个边界是否相交，相交则更新边界值即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    ll n, x, m;
    scanf("%lld%lld%lld", &n, &x, &m);
    ll l, r, L = x, R = x;
    while (m--)
    {
        scanf("%lld%lld", &l, &r);
        if (l <= L && L <= r)
            L = l;
        if (l <= R && R <= r)
            R = r;
    }
    printf("%lld\n", R - L + 1);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Palindromic Paths

题意：

给定一个的矩阵，一个人从出发到达，只能向右或者向下。现在要他走过的路径会形成一个串，求最少改变多少个位置，使得这个人走过的所有路径形成的串都是回文串。

题解：

分析可得无论怎么走第步和第步都必须一样，因此记录下每步和的数量，对于每个都取和中较小者，答案即为每一步之和

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int a[n + m] = {}, b[n + m] = {};
    for (int i = 0; i < n; i++)
        for (int j = 0, x; j < m; j++)
        {
            scanf("%d", &x);
            if (x)
                a[i + j]++;
            else
                b[i + j]++;
        }
    int ans = 0;
    for (int i = 0, j = n + m - 2; i < j; i++, j--)
        ans += min(a[i] + a[j], b[i] + b[j]);
    printf("%d\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Two Divisors

题意：

给出个数，对每个数，求出一对大于的因子，满足。

题解：

设为的质因子,其中为最小的质因子,那么，其中
当时存在，,；当时，不存在
证明：对于 ,当时，，当时，，得证。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5e5 + 5;
const int MAXN = 1e7 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int ans1[maxn], ans2[maxn], p[MAXN];
void init()
{
    for (int i = 2; i < MAXN; i++)
        if (!p[i])
            for (int j = i; j < MAXN; j += i)
                p[j] = i;
}
int main()
{
    init();
    int n;
    scanf("%d", &n);
    for (int i = 0, x; i < n; i++)
    {
        scanf("%d", &x);
        int t = p[x];
        while (x % t == 0)
            x /= t;
        if (x == 1)
            ans1[i] = -1, ans2[i] = -1;
        else
            ans1[i] = t, ans2[i] = x;
    }
    for (int i = 0; i < n; i++)
        printf("%d ",ans1[i]);
    puts("");
    for (int i = 0; i < n; i++)
        printf("%d ",ans2[i]);
    return 0;
}

E.Two Arrays

题意：

给定一个长度为的数组和一个长度为的递增数组，将分成份，使得每份的最小值等于。询问划分的方案数

题解：

因为递增,所以可以求出的后缀数组,那么答案就是,从开始是因为第一个区间的范围是确定的，就是最后一个。无需另外处理的情况，因为如果找不到，那么肯定有段贡献是，最终答案也为。所以只需要特判一下是否等于即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int mod = 998244353;
multiset<int> s;
int ans, a[maxn], b[maxn];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= m; ++i)
        scanf("%d", &b[i]);
    s.insert(a[n]);
    for (int i = n - 1; i >= 1; --i)
        a[i] = min(a[i], a[i + 1]),
        s.insert(a[i]);
    ll ans = 1;
    for (int i = 2; i <= m; ++i)
        ans = (1ll * ans * s.count(b[i])) % mod;
    if (a[1] != b[1])
        ans = 0;
    printf("%lld\n", ans);
}