2020牛客暑期多校训练营（第八场）
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;
}
