I – Interesting Computer Game
链接：https://ac.nowcoder.com/acm/contest/5673/I
思路：这题起初我想先读入数据，记录数字个数，然后从后往前判断。这个思路应该是没有问题的，但是最后T了。虽然脑子有闪过并查集的念头，但实在不太熟悉这类题型，更不知道怎么用并查集操作。正解应该是先读入不同的数字的个数，用并查集维护不同数字之间的关系，同时再用一个same[]作为标记，可判断数字是否可以取到。例如起初的（1，2），此后fa[1]=f[2]=2,same[2]=0,只能取一个，但是再读入第二组（1，2）时，same[2]=1,可以取的数字数加一。

#include<map>
#include<cstdio> 
using namespace std;
int t,n,fa[200005],cnt,ans,a[100005],b[100005];
bool same[200005];
map<int,int> mp;
int find(int x){
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
int main(){
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++){
        cnt=0;
        int minus=0;
        mp.clear();
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d%d",&a[i],&b[i]);
            if(mp[a[i]]==0) mp[a[i]]=++cnt;
            if(mp[b[i]]==0) mp[b[i]]=++cnt;
        }
        for(int i=1;i<=cnt;i++) fa[i]=i,same[i]=0;
        for(int i=0;i<n;i++){
            int fx=find(mp[a[i]]),fy=find(mp[b[i]]);
            if(fx!=fy){
                fa[fx]=fy;
                if(same[fx]||same[fy]) same[fy]=1,same[fx]=0;
            }
            else same[fy]=1;
        }
        for(int i=1;i<=cnt;i++) if(fa[i]==i&&!same[i]) minus++;
        printf("Case #%d: %d\n",cas,cnt-minus);
    }
    return 0;
}

K – Kabaleo Lite
链接：https://ac.nowcoder.com/acm/contest/5673/K
有n道菜，第i道菜有bi盘，每盘利润为ai（利润可能为负）。遵循以下规则为每个顾客上菜：
● 每位顾客至少有一道菜。
● 每位顾客都得到从1开始的连续编号的菜，每道菜只吃一盘。
问能容纳的最大的顾客数，已经可赚取的最大利润。
思路：易得，第一盘菜的数量即为最大顾客数量。关键在于前缀和的计算和一个数组b[]保存每种菜前面最少的菜的数量。

#include<cstdio>
#include<iostream>
using namespace std;
#define N 233333
#define ll long long
int ttt,n,a[N],b[N];
long double pre[N];
int main(){
    scanf("%d",&ttt); 
    for(int tt=1;tt<=ttt;tt++){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            pre[i]=pre[i-1]+a[i];
        }
        ll pd=pre[1]; 
        a[1]=1;
        for(int i=2;i<=n;i++){
            if(pre[i]<=pd)    a[i]=0;
            else{
                a[i]=1;
                pd=pre[i];
            }
        }
        b[0]=100000;
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
            b[i]=min(b[i-1],b[i]);
        }
        int st=0; 
        long double ans=0;
        for(int i=n;i>=1;i--) 
            if(a[i]){
                ans+=pre[i]*(b[i]-st);
                st=b[i];
            }
        printf("Case #%d: %d %.0Lf\n",tt,b[1],ans);
    }
}