I-Interesting Computer Game

链接：https://ac.nowcoder.com/acm/contest/5673/I
题意：
有T组数据，每组数据有n对数每对数只能选择一个数或者不选，且前面没有选过相同的数，最后保证找到的数最多。
思路:
我们将每对数连成一条边，每次只能选边上的一个顶点，n对数连成一个图，图分为以下两种情况

1.连成一棵树，那么n个点n-1条边中我们最多只能选n-1个点，因为每组数据中我们最多只能选一个
2.连成一个环，那么环上所有点都可以选择，包括与环连接的连通图上所有顶点
那么我们就需要一个布尔数组circle来判断这个点是否是在环内，如果遇到两个点的祖先结点相同那么就说明他们在一个环内，如果不相同就将两者合并
代码：

#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long ll;
const int N = 2e5 + 100;
unordered_map<int,int> mp;
int cnt,f[N];
bool cicle[N];

int Find(int x)//查找祖先结点
{
    if(f[x] == x)
    {
        return x;
    }
    else
    {
        return f[x] = Find(f[x]);
    }
}

void Union(int x, int y)
{
    int xx = Find(x);
    int yy = Find(y);
    if(xx != yy) //如果父结点不相等就合并
    {
        f[xx] = yy;
        cicle[yy] |= cicle[xx];//或等于，将两者的或运算结果赋给cicle[y]，只有两者都为树时合并才为树
    }
    else
    {
        cicle[xx] = true;//如果相等证明是一个环，所有顶点都可以算进去
    }
}

void Init()
{
    mp.clear();
    cnt = 0;
    for(int i = 0 ; i < N; i++)
    {
        f[i] = i;
        cicle[i] = false;
    }
}

int main()
{
    int t,Case = 0;
    cin >> t;
    while(t--)
    {
        Init();
        int n;
        scanf("%d",&n);
        for(int i = 1 ; i <= n ; i++)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            if(!mp[x])
            {
                mp[x] = ++cnt;
            }
            if(!mp[y])
            {
                mp[y] = ++cnt;
            }
            Union(mp[x],mp[y]);
        }
        int ans = cnt;
        for(int i = 1 ; i <= cnt ; i++)
        {
            if(f[i] == i && !cicle[i])//如果遇到一棵树
            {
                ans--;
            }
        }
        printf("Case #%d: %d\n",++Case,ans);
    }
    return 0;
}

K-Kabaleo Lite

链接：https://ac.nowcoder.com/acm/contest/5673/K
题意：
有n种菜，给出两组长度为n的数组，第一组表示每种菜的利润（可能为负），第二组表示每种菜的份数，每次给一个顾客上菜，必须是从第一份开始的连续的菜，问最多可以有给几个顾客上菜（优先保证），最大利润是多少。
思路:
首先求出利润的前缀和，份数只记录min(当前，上一个)，对前缀和降序排序，排序时需要记录原始下标排序，遍历前缀和，记录一个右边界，如果当前前缀和的原始下标在右边界的左边，ans累加利润乘份数，更新当前已经用过的份数即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long

const int maxn = 1e5+5;
struct node{
    ll val;
    __int128 sum;
    int i;
}a[maxn];
ll b[maxn];

bool cmp(node x,node y)
{
    return x.sum>y.sum;
}

inline void print(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}

int main()
{
    int t,cas=0;
    scanf("%d",&t);
    while(t--){
        int n;scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i].val);
            a[i].sum=a[i].val+a[i-1].sum;
            a[i].i=i;
        }
        for(int i=1;i<=n;i++){
            scanf("%lld",&b[i]);
            if(i!=1) b[i]=min(b[i],b[i-1]);
        }
        sort(a+1,a+1+n,cmp);
        int x=n;
        ll cnt=0;//记录已经消耗的数量 
        __int128 ans=0;
        for(int i=1;i<=n;i++){
            if(x>=a[i].i) ans+=a[i].sum*(b[a[i].i]-cnt),cnt=b[a[i].i],x=a[i].i;
        }
        printf("Case #%d: %lld ",++cas,b[1]);
        print(ans);
        puts("");
    }
    return 0;
 }

G-Game SET

链接：https://ac.nowcoder.com/acm/contest/5673/G
题意：
一套牌有四种属性，每种属性都有三种特征，shapes(one,two,orthree)shape(diamond,squiggle,oroval)shading(solid,striped,oropen), color(red,green,orpurple)，如果是 ∗，可以选任意一种。给出 n 套牌，每套牌给出 [<number>][<shape>][<shading>][<color>]，问有没有三张牌符合同一属性的特征要么全都相同，要么全都不同。
思路:
先用 map 将字符串转换为数字记录下每张牌的四种属性，然后三个循环找三张牌，遍历属性，如果全都符合条件就输出三张牌的编号，如果没有符合条件的就输出 −1。
如果遇到了 ∗，如果另外两张相同，那么 ∗ 可以和它们相同，否则和它们都不同，所以该属性只要有一个 ∗ 符合条件。
如果没有∗ ，就要么全都相同，要么全都不同符合条件。
代码</color></shading></shape></number>

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1010;
char s[N][110];
int cas = 1;
bool solve(string a, string b, string c)
{
    if (a == "*" || b == "*" || c == "*")
        return true;
    if (a == b && a != c)
        return false;
    if (a == c && a != b)
        return false;
    if (b == c && a != b)
        return false;
    return true;
}
bool check(int i, int j, int k)
{
    int cnt1, cnt2, cnt3;
    int num = 0;
    cnt1 = cnt2 = cnt3 = 0;
    while (num < 4)
    {
        num++;
        cnt1 += 2, cnt2 += 2, cnt3 += 2;
        string s1, s2, s3;
        while (s[i][cnt1] != ']')
            s1 += s[i][cnt1], cnt1++;
        while (s[j][cnt2] != ']')
            s2 += s[j][cnt2], cnt2++;
        while (s[k][cnt3] != ']')
            s3 += s[k][cnt3], cnt3++;
        if (!solve(s1, s2, s3))
            return false;
    }
    return true;
}
int main()
{
    int T;
    sd(T);
    while (T--)
    {
        int n;
        sd(n);
        rep(i, 1, n)
            ss(s[i] + 1);
        int flag = 0;
        rep(i, 1, min(n, 21))
        {
            rep(j, i + 1, min(21, n))
            {
                rep(k, j + 1, min(21, n))
                {
                    if (check(i, j, k))
                    {
                        flag = 1;
                        printf("Case #%d: %d %d %d\n", cas++, i, j, k);
                        break;
                    }
                }
                if (flag)
                    break;
            }
            if (flag)
                break;
        }
        if (!flag)
            printf("Case #%d: -1\n", cas++);
    }
    return 0;
}