NC24065. [USACO 2019 Jan B]Shell Game
描述
游戏准备阶段，Bessie在桌子上放置三个倒置的坚果壳，并在其中一个坚果壳下面藏了一块小的鹅卵石（至少她希望这是一块鹅卵石——她在一块牧场的地上找到的）。随后Bessie会两两调换坚果壳，同时Elsie试着去猜鹅卵石的位置。
奶牛们在农业展览会上看到的这个游戏的标准形式是玩家可以看到鹅卵石初始的位置，然后要求玩家猜所有交换完成之后鹅卵石最终的位置。
然而，现在奶牛们想要去进行这样一种玩法，Elsie不知道鹅卵石的初始位置，同时她可以在每一次交换之后猜一下鹅卵石的位置。Bessie知道正确答案，在游戏结束后会给Elsie一个分数，等于她猜对的次数。
给定所有的交换和Elsie的猜测，但是不给出鹅卵石的初始位置，请求出Elsie最高可能获得的分数。
输入描述
输入的第一行包含一个整数N，为交换的次数（1≤N≤100）。以下N行每行描述了游戏的一个回合，包含三个整数a、b和g，表示Bessie交换了坚果壳a和b，然后Elsie猜的是坚果壳g。所有这三个数均为1、2、3之一，并且a≠b。
输出描述
输出Elsie可以得到的最高分数。
示例1
输入:
3 1 2 1 3 2 1 1 3 1
输出:
2
说明:
在这个例子中，Elsie最多可以获得2分。如果鹅卵石开始时位于坚果壳1下面，那么她猜中了一次（最后一次）。如果鹅卵石开始时位于坚果壳2下面，那么她猜中了两次（开始两次）。如果鹅卵石开始时位于坚果壳3下面，那么她没有猜对任何一次。pypy3(pypy3.6.1) 解法, 执行用时: 49ms, 内存消耗: 18800K, 提交时间: 2020-12-06 03:00:28
#!/usr/bin/env python3 # # Shell Game # import sys, os, math def read_int(): return int(input()) def read_ints(): return list(map(int, input().split())) n = read_int() t = [] for _ in range(n): t.append(read_ints()) ans = 0 for i in range(3): c = i + 1; sum = 0 for a, b, g in t: if c == a: c = b elif c == b: c = a if g == c: sum += 1 ans = max(ans, sum) print(ans)
C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 504K, 提交时间: 2020-09-02 22:40:26
#include<bits/stdc++.h>
using namespace std;
int cnt[4];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
swap(cnt[a],cnt[b]);
cnt[c]++;
}
printf("%d\n",max(max(cnt[1],cnt[2]),cnt[3]));
}