总分：250

T1：AC

T2：AC

正解思路：纯模拟

构建地图，找马
循环八个方向并判断别马腿情况，以及是否有小写字母
tips：两个方向为一组开方向数组，可以统一考虑别马腿

T3：30

开一个数组t，有三种情况：

a[i] > a[i - 1]：我们记为
a[i] < a[i - 1]：我们记为
a[i] = a[i - 1]：我们记为

这里波动值就是m，而就是m使用的前缀和

此时又有2种情况：

：这种情况m取任何值都可以
：这种情况m就是

注：一定要判断能否整除以及m>=0

详细见代码

#include<iostream>
#include<map>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;

const int N = 1e6 + 5;

int a[N], op[N]; // a原始数组，op记录±多少次m
map<int, int> mapp;
int n, cnt = 0, maxx = 0;

signed main() {
    // freopen("number.in", "r", stdin);
    // freopen("number.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        if (i != 1) { // 不是起点awa
            if (a[i] == a[i - 1])
                op[i] = 0; // 不用动用m
            if (a[i] < a[i - 1])
                op[i] = -1; // 需要-m
            if (a[i] > a[i - 1])
                op[i] = 1; // 需要+m
        }
    int bd, t = 0; // bd记录波动值，t记录一定相似的部分awa
    for (int i = 2; i <= n; ++i) {
        int now = a[i], start = a[1];
        cnt += op[i]; // 记录用了几次波动值awa
        if (cnt == 0) { // 一次没用（或者说被抵消了）awa
            if (now == start) // 如果与起点相等awa
                t++; // 无论波动值如何一定相似awa
            continue;
        }
        if ((now - start) % cnt == 0){
            int m = now - start / cnt; // 不然差值÷动用m就是波动值，这个波动值的相似度++awa
            if (m > 0)
                mapp[m]++;
        }
    }
    for (auto it = mapp.begin(); it != mapp.end(); ++it) // 遍历每一种波动方案awa
        if (maxx <= it->second) { // 最好的一种awa
            maxx = it->second;
            bd = it->first;
        }
    cout << maxx + t + 1 << "\n" << bd << "\n";
    return 0;
}

T4：20 （输出impossible骗20，老师太善良了）

40分思路：

先判断impossible可能性，然后剩下用bfs暴搜。
用一个map或set去重，但我们不需要排序功能，所以用unordered方案。
记录每一种有变化的序列，即如果swap之后序列改变了，就是一种新的方案，再去判断可不可行。

100分思路：

一个四维dp
整体思路是把整个序列清空，再放回去重新排列。

状态：其中 a、c、k 是已经放回去的a、c、k的个数，last是上一个放下的字母
我们先定义一个变量cost，表示把这个字母放到新序列的花费（即它要移动的步数）。

假设现在要放A，，这里的pos数组表示的是这个字母（此处是A）在原序列的位置，后面要减去c和k是因为要排除掉没被移动的部分，与0去max是为了避免负花费。

假设现在要放A的状态转移方程：。这里面a要减1是因为要知道还没放下A时的花费，上一个有可能放的C，有可能放的K，去其中最小值最后+把A放在新序列里的花费，也就是cost。

最后答案是与与的最小值，其中na、nc、nk指的是A、C、K的数量。取它们仨的最小值是去选第一张为A、C、K三种情况花费（移动步数）最小的那一种方案，输出。

```cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9;

int main() {
    string s;
    cin >> s;
    int n = s.length();
    vector<int> posA, posC, posK;
    vector<int> A(n, 0), C(n, 0), K(n, 0);

    for (int i = 0; i < n; i++) {
        A[i] = A[i - 1] + (s[i] == 'A');
        C[i] = C[i - 1] + (s[i] == 'C');
        K[i] = K[i - 1] + (s[i] == 'K');
        if (s[i] == 'A') posA.push_back(i);
        else if (s[i] == 'C') posC.push_back(i);
        else posK.push_back(i);
    }

    int na = posA.size();
    int nc = posC.size();
    int nk = posK.size();

    int max_allowed = (n + 1) / 2;
    if (na > (n + 1) / 2 || nc > (n + 1) / 2 || nk > (n + 1) / 2) {
        cout << "Impossible!\n";
        return 0;
    }

    vector<vector<vector<vector<int>>>> dp(na + 1, vector<vector<vector<int >>> (nc + 1, vector<vector<int >> (nk + 1, vector<int>(3, INF))));

    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0;

    for (int a = 0; a <= na; a++) 
        for (int c = 0; c <= nc; c++) 
            for (int k = 0; k <= nk; k++) {
                if (a == 0 && c == 0 && k == 0) 
                    continue;

                if (a > 0) {
                    int cost = max(0, C[posA[a - 1]] - c) + max(0, K[posA[a - 1]] - k);
                    dp[a][c][k][0] = min(dp[a - 1][c][k][1], dp[a - 1][c][k][2]) + cost;
                }

                if (c > 0) {
                    int cost = max(0, A[posC[c - 1]] - a) + max(0, K[posC[c - 1]] - k);
                    dp[a][c][k][1] = min(dp[a][c - 1][k][0], dp[a][c - 1][k][2]) + cost;
                }

                if (k > 0) {
                    int cost = max(0, A[posK[k - 1]] - a) + max(0, C[posK[k - 1]] - c);
                    dp[a][c][k][2] = min(dp[a][c][k - 1][0], dp[a][c][k - 1][1]) + cost;
                }
            }
    int ans = min({dp[na][nc][nk][0], dp[na][nc][nk][1], dp[na][nc][nk][2]});
    if (ans >= INF)
        cout << "Impossible!\n";
    else
        cout << ans << "\n";

    return 0;
}

集训a班第一场模拟赛