A.XXXXX

题意：

给定个数和，要求找一段最长的子区间使得区间和不能被整除

题解：

先判断整个区间能否被整除，如果不能直接输出，否则分别从前和后开始找一个不能被整除的数，答案是减去较短那一部分的长度

#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;
int a[maxn];
void solve()
{
    int n, x, ans = -1, sum = 0;
    scanf("%d%d", &n, &x);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        a[i] %= x, sum += a[i];
        if (a[i])
            ans = 0;
    }
    if (ans == -1)
        puts("-1");
    else if (sum % x)
        printf("%d\n", n);
    else
    {
        int l = 1, r = n;
        while (l <= n && a[l] == 0)
            l += 1;
        while (r > l && a[r] == 0)
            r -= 1;
        printf("%d\n", max(n - l, r - 1));
    }
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Most socially-distanced subsequence

题意：

给定一个长度为的序列，可以删除任意个数，要求剩下的序列相邻两个数的差值最大且整个序列的长度尽可能短但要

题解：

可以发现对于一段递增或递减的区间，区间内相邻两个数差值之和总相等，因此对于一段连续的区间只要保留最小和最大的即可，即整个序列只保留原序列的极值点即可

#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;
    cin >> n;
    int p[n] = {0};
    vector<int> ans;
    for (int i = 0; i < n; i++)
        scanf("%d", &p[i]);
    for (int i = 0; i < n; i++)
        if (i == 0 || i == n - 1 || ((p[i - 1] < p[i]) != (p[i] < p[i + 1])))
            ans.push_back(p[i]);
    printf("%d\n", ans.size());
    for (int i : ans)
        printf("%d ", i);
    puts("");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Ehab and Prefix MEXs

题意：

给出长度为的单调不降序列序列，满足，要求构造一个长度为的序列，满足

题解：

因为且单调递增，所以一定有解
对于的情况，只需要将
对于或者的情况，只需要将赋为一个不属于的值即可。

#include <bits/stdc++.h>
using namespace std;
#define eps 1e-7
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e5 + 5;
const ll mod = 998244353;
int a[maxn], vis[maxn];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        vis[a[i]] = 1;
    }
    int tot = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] != a[i - 1] && i != 1)
            printf("%d ", a[i - 1]);
        else
        {
            while (vis[tot] == 1)
                tot++;
            printf("%d ", tot);
            tot++;
        }
    }
    puts("");
    return 0;
}

D.Ehab's Last Corollary

题意：

给一个无向连通图（没有自环和多重边），要求选出一个恰好的独立集或者一个不超过个点的环。

题解：

如果环得长度都超过，那么一定可以找出恰好为的独立集，因此问题一定有解。
对整个连通图进行一遍，对于每个环求出其长度，如果，那么直接输出。否则对于一个节点，如果这个点选择了，则相邻的其他所有点都要标记为不可选择，最后输出个未被标记的节点即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e5 + 5;
const ll mod = 998244353;
int n, m, k, d[maxn];
vector<int> G[maxn], s;
bool vis[maxn];

void dfs(int u, int f)
{
    s.push_back(u);
    d[u] = (int)s.size();

    for (int v : G[u])
        if (v != f)
        {
            if (!d[v])
                dfs(v, u);
            else if (d[u] - d[v] + 1 > 1 && d[u] - d[v] + 1 <= k)
            {
                printf("2\n%d\n", d[u] - d[v] + 1);
                for (int i = d[v] - 1; i < d[u]; i++)
                    printf("%d ", s[i]);
                puts("");
                exit(0);
            }
        }
    if (!vis[u])
        for (int v : G[u])
            vis[v] = true;
    s.pop_back();
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    puts("1");
    int need = (k + 1) / 2;
    for (int i = 1; i <= n && need; i++)
        if (!vis[i])
        {
            printf("%d ", i);
            need--;
        }
    puts("");
    return 0;
}