G Game SET
题意：
一套牌有四种属性，每种属性都有三种特征，,
,
,
，如果是
，可以选任意一种。给出
套牌，每套牌给出
，问有没有三张牌符合同一属性的特征要么全都相同，要么全都不同。
先用 将字符串转换为数字记录下每张牌的四种属性，然后三个循环找三张牌，遍历属性，如果全都符合条件就输出三张牌的编号，如果没有符合条件的就输出
。
如果遇到了 ，如果另外两张相同，那么
可以和它们相同，否则和它们都不同，所以该属性只要有一个
符合条件。
如果没有
AC代码：
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;
}
I Interesting Computer Game
题意：
一个游戏有 个回合，每回合提供两个整数
和
不做任何操作。
如果 没被选过（指
的数值），可以选择
。
如果 没被选过，可以选择
。
先给出所有 与
，求出选择的最多整数数量。
如果 和
的父亲一样，即堆中有环，我们就用数组来记录这里的父亲（父亲一直在变，所以这里先数组记录，后面再找这个父亲的父亲解决问题）；我们将每一轮游戏当成一条边，如果成环了，则该环所以端点都能选择，且与环连通的点也能全部选择。如果连通块无环，则有一个端点无法选择。我们把
和
我们的答案就是每个堆中数（不重复）的个数，如果一个堆里没有环就再减去
AC代码：
const int N = 2e5 + 50;
int a[N], b[N], pre[N * 2];
bool vis[N * 2];
map<int, int> m;
int T, n, tot, ans, x, y;
int cas = 1;
int find(int x)
{
if (pre[x] != x)
pre[x] = find(pre[x]);
return pre[x];
}
int main()
{
sd(T);
while (T--)
{
tot = 0;
m.clear();
sd(n);
rep(i, 1, n)
{
sdd(a[i], b[i]);
if (!m[a[i]])
m[a[i]] = ++tot;
if (!m[b[i]])
m[b[i]] = ++tot;
}
rep(i, 1, tot)
{
vis[i] = 0;
pre[i] = i;
}
rep(i, 1, n)
{
x = find(m[a[i]]);
y = find(m[b[i]]);
if (x != y)
{
pre[x] = y;
if (vis[x] || vis[y])
vis[y] = 1, vis[x] = 0;
}
else
vis[y] = 1;
}
ans = tot;
rep(i, 1, tot)
{
if (pre[i] == i && !vis[i])
ans--;
}
printf("Case #%d: %d\n", cas++, ans);
}
return 0;
}
K Kabaleo Lite
题意：
有 道菜，第
道菜有
盘，每盘利润为
（利润可能为负）。遵循以下规则为每个顾客上菜：
● 每位顾客至少有一道菜。
● 每位顾客都得到从 开始的连续编号的菜，每道菜只吃一盘。
问能容纳的最大的顾客数，已经可赚取的最大利润。
因为所有人都必须吃第一盘菜，所有 就是最大顾客数量。
我们求利润 数组的前缀和为
AC代码：
const int N = 2e5 + 50;
const ll mod = 1e14;
ll a[N], b[N], sum[N];
int n;
ll ans, tmp;
int main()
{
int T, t, l, r, i, j, k;
sd(T);
int cas = 1;
while (T--)
{
mem(a, 0);
mem(b, 0);
mem(sum, 0);
sd(n);
rep(i, 0, n - 1)
sld(a[i]);
sld(b[0]);
rep(i, 1, n - 1)
{
sld(b[i]);
b[i] = min(b[i], b[i - 1]);
}
sum[0] = a[0];
rep(i, 1, n - 1)
sum[i] = sum[i - 1] + a[i];
l = r = ans = 0;
tmp = sum[l] * b[l];
while (r < n)
{
while (r < n && sum[r] <= sum[l])
r++;
if (r == n)
break;
tmp += b[r] * (sum[r] - sum[l]);
ans += tmp / mod;
tmp %= mod;
l = r;
}
printf("Case #%d: %lld ", cas++, b[0]);
if (ans)
printf("%lld%014lld\n", ans, tmp);
else
printf("%lld\n", tmp);
}
return 0;
}