A.Two Regular Polygons

题意：

给定t组数据，每组给定一个正n边形和正m边形(m<n)，询问是否能在正n边形中找到正m边形，即两个正多边形的顶点是否能完全重合。

题解：

因为n>m,只要判断n%m是否为0即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
void solve()
{
    int n, m;
    scanf("%d%d", &n, &m);
    if (n % m == 0)
        puts("YES");
    else
        puts("NO");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Bogosort

题意：

给一组数组，要求排序，使得任意i，j，i-a[i]!=j-a[j]

题解：

将数组从大到小排序就能满足条件

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[105];
void solve()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    sort(a, a + n, greater<int>());
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    puts("");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Adding Powers

题意：

给定一个n个元素的数组，要求判断是否能由一个全为0的数组，加上k的i次（i=1，2，3，4…)相加得到，并且i不能重复

题解：

把每个数拆成k 进制。依题意，每一位至多是1，否则就不行

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int add[70];
void solve()
{
    memset(add, 0, sizeof(add));
    int n, k;
    scanf("%d%d", &n, &k);
    int f = 0;
    for (int i = 0; i < n; i++)
    {
        ll x;
        scanf("%lld", &x);
        int j = 0;
        while (x)
        {
            add[j] += (x % k);
            if (add[j] > 1)
            {
                f = 1;
                break;
            }
            x /= k;
            j++;
        }
    }
    if (f)
        puts("NO");
    else
        puts("YES");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Count the Arrays

题意：

构造一个长度为n的数组，值的范围1~m的数组，满足下面条件
1.数组中只能且必须出现一对相同的数字
2.先递增再递减
输出所有的构造方案数量

题解：

有且只有两个数相等，所以每个数组有n-1的数，从m中取n-1个数有C(m,n-1)种，只要将最大的数放在中间剩余的n-2个数只要分成两组放在两边即可，每个数都能放在左右两边，为了防止出现数全在一边的情况可以每次取出一个数放在右边，如果剩下的数全出现在左边也满足条件，因为有对称性所以成立，总共为图片说明。所以最终答案为图片说明 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
ll fac[maxn];
ll qpow(ll a, ll b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void init()
{
    fac[0] = 1;
    for (int i = 1; i < maxn; i++)
        fac[i] = fac[i - 1] * i % mod;
}
ll c(int x, int y)
{
    return fac[x] * qpow(fac[y] * fac[x - y] % mod, mod - 2) % mod;
}
int main()
{
    init();
    int n, m;
    scanf("%d%d", &n, &m);
    if (n == 2)
    {
        puts("0");
        return 0;
    }
    printf("%lld\n", ((c(m, n - 1) * qpow(2, n - 3)) % mod * 1ll * (n - 2)) % mod);
    return 0;
}

E.Array Shrinking（DP）

题意：

给定一组长度为n的序列，每次可以将相邻的两个相等元素，即ai==a(i+1) ，合并成一个新的元素，其值为图片说明 ,询问经过多次操作后数组最小长度

题解：

首先可以图片说明 的预处理出所有可以合并的情况用，a[i][j]表示原先数组的[i,j]的数最终会合并成的数的值。dp[i]表示[1~i]中最多能合并的数个数，所以最终答案就是n-dp[n]。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 505;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int n, a[maxn][maxn], dp[maxn];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i][i]);
    for (int i = n; i; i--)
        for (int j = i + 1; j <= n; j++)
            for (int k = i; k < j; k++)
                if (a[i][k] && a[i][k] == a[k + 1][j])
                    a[i][j] = a[i][k] + 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            if (a[j][i])
                dp[i] = max(dp[i], dp[j - 1] + i - j);
    cout << n - dp[n];
}