A.Short Substrings

题意：

对于字符串，每次取两位字符，最终将所有的字串拼接在一起组成新的字符串。现在给定字符串要求还原字符串。

题解：

从开始每隔一个取即可

#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 = 1e9 + 7;
void solve()
{
    string s;
    cin >> s;
    cout << s[0];
    for (int i = 1; s[i - 1]; i += 2)
        cout << s[i];
    cout << endl;
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.

题意：

给定，每次操作可以交换任意两个，输出最少的操作次数使数组元素奇偶性与下标奇偶性相同，

题解：

分别记录需要交换的奇数和偶数个数，如果两者不相同则输出，否则输出个数即为答案

#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 = 1e9 + 7;
void solve()
{
    int n, x, y;
    scanf("%d", &n);
    x = y = 0;
    for (int i = 0, a; i < n; ++i)
    {
        scanf("%d", &a);
        (i & 1 ? x : y) += (i ^ a) & 1;
    }
    printf("%d\n", (x == y) ? x : -1);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Social Distance

题意：

给定一个长度为的串，表示空位，表示占座，人与人之间最少间隔个单位，询问还能占位的最大数量，即满足条件的变为的数量

题解：

求出相邻之间有多少个，每个位置可以占位。

#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 = 1e9 + 7;
void solve()
{
    int n, k, cnt, ans = 0;
    string s;
    cin >> n >> k >> s;
    cnt = k;
    for (int i = 0; i < s.size(); i++)
        if (s[i] == '0')
            cnt++;
        else
            ans += (cnt - k) / (k + 1), cnt = 0;
    ans += cnt / (k + 1);
    cout << ans << endl;
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Task On The Board

题意：

给定一个字符串，和一个长度为的数组，询问能否从中选出个字母组成一个字符串，使得该字符串满足：等于比大所有字符到的距离之和。

题解：

可以确定中最大的那个字符对应的一定为，因此可以从字符往字符遍历，如果已经确定位置的字符(即比它大的字符)到它的距离之和为，就判断中是否存在这么多数量的该字符，如果存在则将这个字符赋给每个满足条件的位置，否则就继续遍历比它小的字符

#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 = 1e9 + 7;
void solve()
{
    int n;
    string s;
    cin >> s >> n;
    string ans(n, '.');
    int a[n];
    for(int i=0;i<n;i++)
        cin >> a[i];
    char now = 'z';
    while (now >= 'a')
    {
        vector<int> v;
        for (int i = 0; i < n; ++i)
        {
            if (ans[i] != '.')
                continue;
            int tmp = 0;
            for (int j = 0; j < n; ++j)
                if (ans[j] != '.')
                    tmp += abs(i - j);
            if (tmp == a[i])
                v.push_back(i);
        }
        while (count(s.begin(), s.end(), now) < v.size())
            --now;
        for (int i : v)
            ans[i] = now;
        --now;
    }
    cout << ans << '\n';
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

E.Necklace Assembly

题意：

给定一个长度为的字符串，从中选取字符组成最长的序列，使得序列顺时针选择次后与原序列相同。

题解：

记录每个字符出现的次数，假设最终答案为，那么可以发现只需要每隔相同的话，则就可以满足条件，相当于看成个长度均为且各个环内元素均相同的环，因此只需要在中找到最大的，使得存在个长度为的相同字符组即可。

#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 = 1e9 + 7;
map<int,int> cnt;
void solve()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    cnt.clear();
    for (int i = 0; i < n; ++i)
        cnt[s[i] - 'a']++;
    int res = 1;
    for (int i = 1; i <= n; ++i)
    {
        int l = __gcd(i, k);
        int x = i / l;
        int sum = 0;
        for (int j = 0; j < 26; ++j)
            sum += cnt[j] / x;
        if (sum >= l)
            res = max(res, i);
    }
    cout << res << "\n";
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

F1.Flying Sort (Easy Version)

题意：

给定个不同的数，每次可选择一个数，移到头部或尾部，询问最少的操作次数使得数组单调不降

题解：

只需要找出最长的连续单调不降序列，将它保持不变，其余的数按一定顺序分别加到首部和尾部即可，答案即为总长度减去最长的连续单调不降序列的长度（这里的连续都指的是离散化后的数为相邻的两个值）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 3e3 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int dp[maxn], a[maxn], tem[maxn];
void solve()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        tem[i] = a[i];
        dp[i] = 0;
    }
    sort(tem + 1, tem + n + 1);
    int m = unique(tem + 1, tem + n + 1) - tem - 1;
    int mx = 0;
    for (int i = 1; i <= n; i++)
    {
        int d = lower_bound(tem + 1, tem + m + 1, a[i]) - tem;
        dp[d] = dp[d - 1] + 1;
        mx = max(dp[d], mx);
    }
    printf("%d\n", n - mx);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}