A. Omkar and Completion

题意：

给定一个，要求构造一个长度为的序列使得任意一个数不是其他两个数的和

题解：

全即可

#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;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        printf("%d ", 1);
    puts("");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B. Omkar and Last Class of Math

题意：

给定一个数，要找到两个数使得且最小。

题解：

其中一个数必定为的最大因子。证明：令一个答案为，当时，，那么，因此；当时，，因此若，那么，不成立，所以当时，，为了使最小只能使最大，所以为的最大因子

#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;
    scanf("%d", &n);
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
        {
            int x = n / i;
            printf("%d %d\n", x, n - x);
            return;
        }
    printf("%d %d\n", 1, n - 1);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Omkar and Baseball

题意：

给定一个长度为的序列，每次操作可以选定一段区间，交换区间内的每个元素，使得每个元素都和原来位置的不同，询问最小的交换次数使得序列变成

题解：

当序列原本就满足就不需要交换；当序列只存在一段连续的需要交换的区间那么只需要交换次，如果存在多端需要交换的区间，那么将所有区间全部合并，次交换即可

#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;
int a[maxn];
void solve()
{
    int n;
    scanf("%d", &n);
    int f1 = 1, f2 = 1;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        if (f1 && a[i] != i)
            f1 = 0;
        else if (!f1 && a[i] != i && a[i - 1] == i - 1 && i >= 2)
            f2 = 0;
    }
    if (!f1 && f2)
        puts("1");
    else if (!f2 && !f2)
        puts("2");
    else
        puts("0");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D. Omkar and Circle(前缀和)

题意：

用长度为的序列组成一个环，可以采用的操作是选取一个数字，用与他相邻的两个数字的和代替他自己，然后删掉相邻的两个数字，重复该操作，直到最后只剩下一个数字，要使得该数字最大，输出该数字。

题解：

可以发现从头开始合并，那么每次都是中间的数消失了，剩余的数之和就是答案，因此可以用前缀和来记录每相邻一个的和，最终答案就是

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
ll a[maxn << 1];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]), a[n + i] = a[i];
    for (int i = 3; i <= 2 * n; i++)
        a[i] += a[i - 2];
    ll ans = 0;
    for (int i = n + 1; i <= 2 * n; i++)
        ans = max(ans, a[i] - a[i - n - 1]);
    printf("%lld\n", ans);
}

E.Omkar and Last Floor(区间dp)

题意：

给定一个的矩阵，每行给定个区间，规定每个区间只能放置一个，令为第列之和，求最大的

题解：

用 表示从第列到第列能够得到的最大值，枚举中间某列，使这一列尽可能多地放（根据每个区间的左右来进行判断），然后就是个区间DP

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int L[maxn][maxn], R[maxn][maxn], dp[maxn][maxn];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        int k, l, r;
        scanf("%d", &k);
        while (k--)
        {
            scanf("%d%d", &l, &r);
            for (int j = l; j <= r; j++)
            {
                L[i][j] = l;
                R[i][j] = r;
            }
        }
    }
    for (int l = m; l >= 1; l--)
        for (int r = l; r <= m; r++)
            for (int k = l; k <= r; k++)
            {
                int a = 0;
                for (int i = 1; i <= n; i++)
                    if (L[i][k] >= l && R[i][k] <= r)
                        a++;
                dp[l][r] = max(dp[l][r], dp[l][k - 1] + a * a + dp[k + 1][r]);
            }
    printf("%d\n", dp[1][m]);
    return 0;
}