G Game SET

链接：https://ac.nowcoder.com/acm/contest/5673/G
题意：
就是多组输入，每次输入给定n个字符串，每个字符串有四个属性，每个属性分别有三个选项，这三个选项用三个不同的字符串，或者用*来表示没有选项来表示，问是否存在三个字符串，他们四个属性各不相同，或者都一样。有的话输出编号，没有输出-1.
题解：先分别将这四种属性的选项用map容器赋值，简化，再O(n^3)进行遍历三个三个进行比较，看他们四个属性是否都不相同，或者都一样
注意：
*与 *之间他们的也算不同，因为表示null，所以不能算属性相同。
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
//const ll mod=998244353;
map<string,int>m;
char str[105];
void init()
{
    m["one"]=1;
    m["two"]=2;
    m["three"]=3;
    m["diamond"]=1;
    m["squiggle"]=2;
    m["oval"]=3;
    m["solid"]=1;
    m["striped"]=2;
    m["open"]=3;
    m["red"]=1;
    m["green"]=2;
    m["purple"]=3;
    m["*"]=0;
}
struct node{int c[5];}trans[300];
bool check(int x,int y,int z)
{
    for(int i=1;i<=4;i++)
    {
        set<int>st;
        int wild=0;
        if(trans[x].c[i]==0)wild++;
        else st.insert(trans[x].c[i]);
        if(trans[y].c[i]==0)wild++;
        else st.insert(trans[y].c[i]);
        if(trans[z].c[i]==0)wild++;
        else st.insert(trans[z].c[i]);
        if(st.size()>1&&st.size()+wild<3)return false;
    }
    return true;
}
int main()
{
        int t,n;
        scanf("%d",&t);
        init();
        int cas=0;
        while(t--)
        {   cas++;
            scanf("%d",&n);
            int i,j,k;
            for( i=1;i<=n;i++)
            {
                scanf("%s",str);
                k=1;
                for(j=1;j<=4;j++)
                {
                    string a;
                    for(k;str[k]!=']';k++)
                    {
                        a+=str[k];
                    }
                    trans[i].c[j]=m[a];
                    k+=2;
                }
            }
            int flag=0;
            for(i=1;i<=n;i++)
            {
                for(j=i+1;j<=n;j++)
                {
                    for(k=j+1;k<=n;k++)
                    {
                        if(check(i,j,k))
                        {
                            flag=1;break;
                        }
                    }
                    if(flag)break;
                }
                if(flag)break;
            }
            if(!flag)printf("Case #%d: -1\n",cas);
            else printf("Case #%d: %d %d %d\n",cas,i,j,k);
        }
        return 0;
}

I Interesting Computer Game

链接：https://ac.nowcoder.com/acm/contest/5673/I
题意：
给出n对数字 a,b。在每一对数中选择一个与之前的不同的数，若没有则不选，求最多能选出多少数
题解：
先离散化一下，构建一个并查集，找出每个根节点能够联通的最多的个数，稍微根据题意修改一下
注意：
若没有出现成环的情况，则需要-1，因为最开始的根节点和它的一个子节点需要二选一
代码：

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

using namespace std;
typedef long long ll;
const int maxn=2e5+7;
//const ll mod=998244353;
int a[maxn],b[maxn],fa[maxn],cnt[maxn],vis[maxn],val[maxn],ans,n,k,T;
int get(int x)
{
    if(fa[x]!=x)fa[x]=get(fa[x]);
    return fa[x];
}//得到x的根节点
void combine(int u,int v)//先把两个点给连接起来成为一条边
{
    int temp1=get(u);
    int temp2=get(v);//
    if(temp1==temp2){vis[temp1]=1;}//说明这是一个环
    else
    {
        if(vis[temp1]||vis[temp2]){vis[temp1]=vis[temp2]=1;}//
        cnt[temp1]+=cnt[temp2];//求出每个节点所包含的节点（包括自己）
        fa[temp2]=temp1;//合并，v是u的父节点。
    }//
}

void init(int t)
{
    for(int i=1;i<=t;i++)
    {
        fa[i]=i;
        cnt[i]=1;
        vis[i]=0;//表示是否有成环
    }
    k=1;ans=0;
}//初始化

int main()
{
    scanf("%d",&T);
    int cas=0;
    while(T--)
    {
        cas++;
        scanf("%d",&n);
        init(n*2);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i],&b[i]);
            val[k++]=a[i];
            val[k++]=b[i];//把所有的数放入一个大的数组里面去
        }
        sort(val+1,val+k);
        int t= unique(val+1,val+k)-val-1;//表示一共有多少个不重复的数字,此时的val已经是去重后的函数
        //printf("%d",t);
        for(int i=1;i<=n;i++)
        {
            a[i]=lower_bound(val+1,val+t,a[i])-val;//表示原先这个数在去重，排大小数列数列中的位置
            b[i]=lower_bound(val+1,val+t,b[i])-val;
            //printf("%d %d\n",a[i],b[i]);
        }//离散化，O（n)//a[i],b[i]就只能是1~t里面的数了
        for(int i=1;i<=n;i++)
        {
            combine(a[i],b[i]);//连接a[i],b[i]的编号。
        }
        for(int i=1;i<=t;i++)
        {
            if(get(i)==i)//根节点（找到根节点）
            {
                ans+=cnt[i]+vis[i]-1;//表示是否成环，若没有成环就要减去初始的一个（根节点直接加进去了）
            }

        }
        printf("Case #%d: %d\n",cas,ans);
        //for(int i=1;i<=t;i++)printf("%d ",val[i]);
        //for(int i=1;i<=t;i++)printf("%d ",get(i));
    }
    return 0;
}

K Kabaleo Lite

链接：https://ac.nowcoder.com/acm/contest/5673/K
题意：
就是说有n盘菜，第i个菜有a[i]个价值，和个数b[i]，然后要求一堆人必须连续的吃，求吃得到的最大的价值
题解：
其实就是求前缀和问题，人数从b[1]开始慢慢减少，然后只要连续的前缀和大于0就进行叠加
注意：
它还卡了快读，最后的和大于ll范围，需要用到__int128，但是windows系统上clion好像又对这个玩意报错，玄学。
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
const int inf=0x3f3f3f3f;
//const ll mod=998244353;
ll a[maxn],b[maxn],s[maxn];

inline __int128 read(){  //__int128 可以换成 int longlong 基于自己的需求即可，板子
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void out(__int128 x){    //输出
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        out(x/10);
    putchar(x%10+'0');
}

int main()
{
    int t,n,l,r;__int128 ans;
    t=read();
    int cas=0;
    while(t--)
    {
        cas++;
        n=read();s[0]=0;b[0]=inf;a[0]=0;
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
            s[i]=s[i-1]+a[i];
        }
        for(int i=1;i<=n;i++)
        {
            b[i]=read();
            b[i]=min(b[i],b[i-1]);//找到当前最小的限制人数
        }
        ans=a[1]*b[1];
        r=l=1;
        while(r<=n)
        {
            while(s[r]<=s[l]&&r<=n)r++;//分块
            if(r==n+1)break;//全是小于s[1]
            ans+=b[r]*(s[r]-s[l]);
            l=r;
        }
        printf("Case #%d: %lld ",cas,b[1]);
        out(ans);
        printf("\n");
    }
    return 0;
}