E.Enigmatic Partition

题意：

给定一个，，其中相邻两个数之差不超过，并且。给定，要求

题解：

令

n	10	11	12	13	14	15	16	17	18	19	20
5个3									1233333
4个3							1123333	1223333
3个3					1112333	1122333	1222333
2个3			1111233	1112233	1122233	1222233
1个3	1111123	1111223	1112223	1122223	1222223
差分	1		1		1	-1		-1		-1
差分上差分	1					-1	-1				1
对应位置

对于差分，第一层为，表示每个数，第二层为，表示每个数再，第三层为，表示这个数再加。但是对于每个和都要进行多次差分肯定会超时的，观察差分的位置可以发现，都是两两间隔的，因此可以对这个差分数组再进行差分。
对于差分上差分。第一层为，每次间隔为，表示这三个数，对于第二层，每次间隔为，表示这三个数。因此只要for(i=3;i<N;++i) f[i]+=f[i-2];就能还原出原来的差分数组，再对差分数组for(i=1;i<N;++i) f[i]+=f[i-1];就是原数组了，剩下的只需要求出前缀和查询即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll s[N << 1], f[N << 2];
int main()
{
    for (int m = 3; m < N; ++m)
        for (int a = m; a < N; a += m)
        {
            f[a + 3]++;
            f[a + 2 * m]++;
            f[a + m + 1]--;
            f[a + m + 2]--;
        }
    for (int i = 3; i < N; ++i)
        f[i] += f[i - 2];
    for (int i = 1; i < N; ++i)
        f[i] += f[i - 1];
    for (int i = 1; i < N; ++i)
        s[i] = s[i - 1] + f[i];
    int t, caseN = 0;
    scanf("%lld", &t);
    for (int i = 1; i <= t; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("Case #%d: %lld\n", ++caseN, s[r] - s[l - 1]);
    }
}

G.Game SET

题意：

一种牌有四个属性：数字、形状、纹理、颜色。每种属性各可能有三种不同情况,"∗"代表任意情况。
从牌堆里拿出三张牌，如果彼此的四个属性都相同或两两都不同则合法。
请找出一对合法情况，没有合法情况直接出-1。

题解：

暴力枚举即可。。。

#include <bits/stdc++.h>
using namespace std;
struct SET
{
    int std[5];
} a[300];
bool check(int x, int y, int z)
{
    int cnt = 0;
    for (int i = 0; i < 4; i++)
    {
        if (a[x].std[i] == a[y].std[i] && a[x].std[i] == a[z].std[i] && a[y].std[i] == a[z].std[i])
            cnt++;
        else if (a[x].std[i] != a[y].std[i] && a[x].std[i] != a[z].std[i] && a[y].std[i] != a[z].std[i])
            cnt++;
        else if (a[x].std[i] == -1 || a[y].std[i] == -1 || a[z].std[i] == -1)
            cnt++;
    }
    return cnt==4;
}
int main()
{
    int t, caseN = 0;
    scanf("%d", &t);
    while (t--)
    {
        char s[100];
        int n;
        memset(a, 0, sizeof(a));
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%s", s);
            int temp = 0;
            for (int j = 0; j < strlen(s); j++)
                if (s[j] == '[')
                {
                    if (s[j + 1] == '*')
                        a[i].std[temp++] = -1;
                    else
                        a[i].std[temp++] = s[j + 2] - 'a';
                }
        }
        bool flag = false;
        for (int i = 1; i <= n && !flag; i++)
            for (int j = i + 1; j <= n && !flag; j++)
                for (int k = j + 1; k <= n && !flag; k++)
                    if (check(i, j, k) == true)
                    {
                        flag = true;
                        printf("Case #%d: %d %d %d\n", ++caseN, i, j, k);
                        break;
                    }
        if (!flag)
            printf("Case #%d: -1\n", ++caseN);
    }
}

I.Interesting Computer Game

题意：

给定对数，每次可以选取其中一个，询问最多能选取多少个不同的数

题解：

将每个数看成一个点，每对数看成一条边，那么会形成若干个联通块，对于每个联通块，如果恰好构成一棵树，那么总有一种策略可以选择其中的个点；若联通块中存在环的话，那总有一种策略可以选择其中的个点。而可以用并查集来判断联通块中是否为树，因此对于每个联通块分别判断，树则答案，否则

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int a[maxn], b[maxn], fa[maxn << 1], sz[maxn << 1], ed[maxn << 1], vis[maxn << 1];
vector<int> v;
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
int main()
{
    int t, caseN = 0;
    scanf("%d", &t);
    while (t--)
    {
        v.clear();
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d%d", &a[i], &b[i]);
            v.push_back(a[i]);
            v.push_back(b[i]);
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        int cnt = v.size();
        for (int i = 1; i <= cnt; i++)
            fa[i] = i, sz[i] = 1, ed[i] = 0, vis[i] = 0;
        for (int i = 1; i <= n; i++)
        {
            int x = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
            int y = lower_bound(v.begin(), v.end(), b[i]) - v.begin() + 1;
            int dx = find(x);
            int dy = find(y);
            if (dx != dy)
            {
                fa[dx] = dy;
                sz[dy] += sz[dx];
                ed[dy] += ed[dx] + 1;
            }
            else
                ed[dx]++;
        }
        int ans = 0;
        for (int i = 1; i <= cnt; i++)
        {
            int x = find(i);
            if (!vis[x])
            {
                vis[x] = 1;
                if (ed[x] >= sz[x])
                    ans += sz[x];
                else
                    ans += sz[x] - 1;
            }
        }
        printf("Case #%d: %d\n", ++caseN, ans);
    }
    return 0;
}

k.Kabaleo Lite

题意：

有种菜，每种菜的数量为, 每个菜的盈利为
每个顾客必须从第种菜开始，连续地吃，每种吃一个。
保证顾客最多的情况下，盈利最大。

题解：

顾客最多肯定就为，用前缀和来维护前个菜的盈利，收益最大只需要遍历一遍每次只需要判断当前的前缀和有没有比上一次的大，如果有则结果加上两数之差乘前种菜的最小数量。
要注意的是结果会超出，可以使用__int128或者python

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const ll mod = 1e9 + 7;
ll a[maxn], b[maxn];
__int128 sum[maxn];
void print(__int128 x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}
int main()
{
    int t, caseN = 0;
    scanf("%d", &t);
    b[0] = INF;
    while (t--)
    {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &a[i]);
            sum[i] = sum[i - 1] + a[i];
        }
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &b[i]);
            b[i] = min(b[i - 1], b[i]);
        }
        __int128 ans = __int128(a[1]) * b[1];
        ll last = sum[1];
        for (int i = 2; i <= n; i++)
        {
            if (sum[i] > last)
            {
                ans = ans + __int128(sum[i] - last) * b[i];
                last = sum[i];
            }
        }
        printf("Case #%d: %lld ", ++caseN, b[1]);
        print(ans);
        puts("");
    }
    return 0;
}