A.Two Regular Polygons—规律

题意：有一个 n 条边的正凸多边形，需要构造出一个有 m 条边的正凸多边形使得这个多边形的中心与给定的正凸多边形重合且构造的多边形的顶点都在给定的正多边形的顶点上。判断能否构造出要求的正凸多边形

思路：中心重合并且顶点也重合，那么也就说名构造的正凸多边形的每一条边应该对应给定的正凸多边形的整数倍条边，也就是说 n 能被 m 整除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        if (n % m == 0)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    // system("pause");
    return 0;
}

B.Bogosort—思维

题意：对于给定的序列 a，通过任意排序使得 j-a[j]!=i-a[i](i<j)

思路：因为 i 到 j 是严格单调递增的，所以我们保证让 a[i] 到 a[j] 单调递减，这样整体 i-a[i] 到 j-a[j] 肯定是严格单调递增的了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105;

int a[maxn];

bool cmp(int a, int b) {
    return a > b;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        sort(a, a + n, cmp);
        for (int i=0;i<n;++i)
            cout << a[i] << " ";
        cout << endl;
    }
    // system("pause");
    return 0;
}

C.Adding Powers—进制转换+思维

题意：能否对一个全为 0 的数组执行任意次操作后使其变为目标数组，对于第 i 次操作我们可以选择放弃或者给数组中任意一个元素加上 ki (n<=30,k<=100,a[i]<=1e16)

思路：每个数肯定都能够用唯一的 k 进制表示，但是注意题目要求 ki 只能用一次，所以：

  • 如果这个数 k 进制表示上的某位数 >1，说明这个数根本不能通过上述操作成功拆解不满足要求
  • 或者这个数能够按照上述操作拆解成多个不同的 k 次幂之和，但是存在之前的数和当前数的拆解的 k 次幂有重合那么也不满足要求

综上：我们就对每个数进行 k 进制的拆解，并统计拆解出来的 k 次幂的次数，如果存在 >1 了必然是上述两个情况之一造成的输出 NO，否则就是 YES

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 100;

ll n, k;
ll a[maxn];
map<int, int> mp;

bool check(ll x) {
    while (x) {
        ll base = 1;
        ll cnt = 0;
        while (x >= base) {	
            base *= k;
            ++cnt;
        }
        base /= k;
        --cnt;
        ++mp[cnt];  //通过循环找到当前 x 可以拆解出的最高幂次的 k 的次幂
        if (mp[cnt] > 1) return 1;
        x -= base;
    }
    return 0;
}

void solve() {
    mp.clear();
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    if (k == 1) {
        cout << "YES" << endl;
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (a[i]) {
            if (check(a[i]) == 1) {
                cout << "NO" << endl;
                return;
            }
        }
    }
    cout << "YES" << endl;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    // system("pause");
    return 0;
}

D.Count the Arrays—组合数+逆元+快速幂+思维

题意：求出满足如下条件的长度为 n 的序列 a 的个数，答案对 998,244,353 取模：

  • 对于任意的 1<=i<=n 都有 1<=a[i]<=m
  • 序列 a 中存在且仅存在一对相同的元素
  • 存在一个位置 p,使得 a[1]~a[p] 为严格单增序列，a[p]~a[n] 为严格单减序列，即序列整体是一个塔尖形状（单增单间序列是不符合要求的）

思路：既然有且仅有一对元素是相同的，所以我们从 1~m 中挑出 n-1 个不同的元素，除去最大值不可以是那个相同元素对其他 n-2 个元素都可以所以元素的总共挑法有 C(m,n-1)*(n-2)，下面考虑方法因为要保证是塔尖状的所以我们固定最大的三个元素位置，然后对于剩下 n-3 个元素我们考虑从大到小为他们选择放的位置，因为可以选择左边或者右边所以总共的方法有 2n-3 种，根据乘法原理最终序列 a 的个数就是 C(m,n-1)*(n-2)*pow(2,n-3) 种，中间运算组合数需要将模除法转换为逆元乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;	//查过了是素数逆元可以直接用费马小定理

ll n, m;

ll fac(ll x) {	//阶乘
    ll fc = 1;
    for (int i = 1; i <= x; ++i)
        fc = fc * i % mod;
    return fc;
}

ll quick_pow(ll a, ll b) {	//快速幂
    ll ans = 1, base = a;
    while (b > 0) {
        if (b & 1) ans = (ans * base) % mod;
        base = base * base % mod;
        b >>= 1;
    }
    return ans;
}

ll C(ll x, ll y) {	//组合数
    return fac(x) * quick_pow(fac(y) * fac(x - y) % mod, mod - 2) % mod; //转换为逆元乘法
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    while (cin >> n >> m) {
        ll ans = 1;	//答案
        ans = ans * C(m, n - 1) % mod;
        ans = ans * (n - 2) % mod;
        ans = ans * quick_pow(2, n - 3) % mod;
        cout << ans << endl;
    }
    // system("pause");
    return 0;
}

E.Array Shrinking—区间dp

题意：已知有一个长度为 n 的数组 a，每次你可以进行下述的操作：找到一对相邻的且相同的元素对 (a[i],a[i+1)，将他们替换为一个元素，其数值为 a[i]+1，也就是说每轮操作之后数组的长度可以减小 1，问剩余数组长度的最小值

思路： 参考博客 另 dp[l][r] 表示 [l,r] 区间合并后最小的长度，同时开一个 w 数组辅助记录 [l,r] 区间合并最小长度后区间的权值和，那么转移方程就是：dp[l][r]=min(dp[l][mid]+dp[mid+1][r])，每次区间的最小长度先用由两个子区间的最小长度和转移过来，再考虑这两个子区间是否还可以进一步合并 ，合并的条件是两个区间的长度都是 1 并且权值和相同

自己还是太菜看到这类题一点感觉也没有，写的过程中也犯了细节的错误（对于长度为 2 的区间转移要注意枚举 mid 的范围）

递推写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 505;

int a[maxn], dp[maxn][maxn], w[maxn][maxn];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    while (cin >> n) {
        memset(dp, 0x3f, sizeof dp);
        for (int i = 1; i <= n; ++i)
            cin >> a[i], dp[i][i] = 1, w[i][i] = a[i];                                                  //初始化
        for (int j = 2; j <= n; ++j) {                                                                  //长度为2区间开始向后递推
            for (int l = 1; l + j - 1 <= n; ++l) {                                                      //区间左边界
                int r = l + j - 1;                                                                      //区间右边界
                for (int mid = l; mid < r; ++mid) {                                                     //因为可能有长度为2的所以注意mid枚举的范围
                    dp[l][r] = min(dp[l][r], dp[l][mid] + dp[mid + 1][r]);                              //由左右两个子区间合并过来,找出最优的两个合并区间
                    if (dp[l][mid] == dp[mid + 1][r] && dp[l][mid] == 1 && w[l][mid] == w[mid + 1][r])  //判断两个区间能否合并
                        dp[l][r] = 1, w[l][r] = w[l][mid] + 1;
                }
            }
        }
        cout << dp[1][n] << endl;
    }
    // system("pause");
    return 0;
}

记忆化递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 505;

int a[maxn], dp[maxn][maxn], w[maxn][maxn];

int func(int l, int r) {
    if (dp[l][r] != 0x3f3f3f3f) return dp[l][r];    //记忆化
    for (int k = l; k < r; ++k) {
        dp[l][r] = min(dp[l][r], func(l, k) + func(k + 1, r));  //向下递归
        if (dp[l][k] == dp[k + 1][r] && dp[l][k] == 1 && w[l][k] == w[k + 1][r])
            dp[l][r] = 1, w[l][r] = w[l][k] + 1;
    }
    return dp[l][r];
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    while (cin >> n) {
        memset(dp, 0x3f, sizeof dp);
        for (int i = 1; i <= n; ++i)
            cin >> a[i], dp[i][i] = 1, w[i][i] = a[i];
        cout << func(1, n) << endl;
    }
    // system("pause");
    return 0;
}