1. Herdle
奶牛们发明了一种名为Herdle的新型解谜游戏，在牛界引起了轰动。
每天都会有一个新谜题发布供奶牛解决。游戏采用3x3方阵的形式表示农场的一块田地，田地的每个方格都由特定品种的奶牛占据。总共只有26种可能的品种，每一种由A到Z中的不同大写字母标识。玩家不会被告知田地中的奶牛品种排列方式——游戏目标是通过一系列猜测确定它们。
每次猜测，奶牛们输入一个3x3的大写字母方阵，表示该田地可以用奶牛填充的可能方式。猜测的某些方格可能是正确的。这些方格以绿色高亮显示，让奶牛们知道这些是正确的。猜测的另一些方格可能填入了品种正确但位置错误的奶牛。这些以黄色高亮显示。
黄色高亮显示的方格的数量可以帮助指示某个品种的奶牛数量。 例如，假设猜测方阵包含4头品种A的奶牛，而答案方阵包含2只品种A的奶牛，其中没有正确位置上的A（即，它们都不应该是绿色的）。 在这种情况下，猜测方阵中只有两个A应以黄色高亮显示。 更准确地说，如果猜测方阵中有x个特定品种的奶牛，并且 答案方阵中有\(y\lt x\)头该品种奶牛（不包括位置正确而得到绿色高亮显示的奶牛），那么猜测方阵的x头奶牛中只有y头奶牛应该以黄色高亮显示。
给定正确答案的方阵和一个表示对该答案的猜测的方阵，请计算绿色和黄色高亮显示的方格的数量。
输入格式（从终端 / 标准输入读入）：
输入的前3行给定了正确答案的方阵。以下3行表示对该答案的猜测。
输出格式（输出至终端 / 标准输出）：
输出两行。输出的第一行包含应当以绿色高亮显示的方格的数量。输出的第二行包含应当以黄色高亮显示的方格的数量。
输入样例：
COW
SAY
MOO
WIN
THE
IOI输出样例：
1
1在这个例子中，最后一行中间的O是正确的，所以这个方格以绿色高亮显示。字母W位于错误的位置，所以它以黄色高亮显示。
输入样例：
AAA
BBB
CCC
AYY
AAA
ZZZ输出样例：
1
2在这里，其中一个A位于正确的位置，所以它以绿色高亮显示。余下的A均不在正确位置上，由于答案方阵中有两个A，所以有两个A应当以黄色高亮显示。
分析
“绿色”（字母对，位置也对）是最好找的。
“黄色”（字母对，但位置不对）的找法是：我们先找到所有需要标颜色的格子（只要某个字母出现在答案和猜测中）然后减去上面求到的绿色格子即可。对于每个字母来说，它被标记的数量，是答案中的次数和猜测中的次数的较小的那个。
答案
思考
这道题的关键，是吃透题意，并最终分析出要被标记（不管是黄色还是绿色）的格子的数量是答案中的次数和猜测中的次数的较小的那个。
2. Non-Transitive Dice
为了消磨牛棚里的时光，奶牛们喜欢玩简单的骰子游戏。其中一种游戏使用两个骰子X和Y进行。两个骰子均被投掷，获胜的骰子是显示的数字较大的骰子。如果两者显示相同的数字，则重新投掷（只要持续打平，骰子可能会被重新投掷多次）。我们称骰子X击败骰子Y，如果骰子X比骰子Y更有可能赢得这局游戏。
考虑以下的 4 面骰子：
骰子 A 在各面上有数字 4，5，6 和 7。
骰子 B 在各面上有数字 2，4，5 和 10。
骰子 C 在各面上有数字 1，4，8 和 9。这些骰子满足一个相当奇妙的性质：A击败B，B击败C，并且C也击败A。特别地，三个骰子都不是“最佳的”，都不能击败其他两个。在这种情况下，当没有两个骰子打平，也没有一个骰子是最佳的，我们称这三个骰子的集合为“非传递的”。在非传递的三个骰子的集合中，每个骰子击败一个其他骰子，并输给另一个其他骰子。
给定两个4面骰子A和B各面上的数字，请帮助奶牛们求出是否有方法为第三个骰子C的各面分配数字，使得这个骰子的集合是非传递的。所有骰子面上的数字必须是1到10的整数。
输入格式（从终端 / 标准输入读入）：
每个测试用例包含多个独立的子测试用例，必须全部回答正确才能通过整个测试用例。输入的第一行包含
T（\(1\le T\le 10\)），为你需要求解的子测试用例的数量。以下
T行，每行描述了一个子测试用例，包含8个整数：骰子A的4面上的整数，以及骰子B的4面上的整数。所有的数均在1到10之间，不一定排序。可能同一个数会出现多次，即使在同一个骰子上也可能出现多个相同的数。
输出格式（输出至终端 / 标准输出）：
输出
T行。如果有可能为骰子C分配数字使得第k个测试用例成为一个非传递的骰子集合，则第k行输出yes，否则输出no。
输入样例：
3
4 5 6 7 2 4 5 10
2 2 2 2 1 1 1 1
1 1 1 1 2 2 2 2输出样例：
yes
no
no第一个子测试用例对应题目中的例子。在第二个子测试用例中，不存在骰子C可以使得这个骰子集合是非传递的。同理第三个子测试用例的答案也是no。
分析
一个骰子有4面，每一面可能有10个数值，所以总的点数可能性排列是\(10^4\)个，可以用暴力求解。
由于有三个骰子，我们在测试“非传递性”的时候，需要测试两个方向：A>B>C>A或者A<B<C<A。
最后，怎么判定A>B？方法也很简单：对于A和B上所有的点数对，如果A的点数大于B的点数，A赢的次数加1，否则B赢的次数加1。最后比较两者赢的次数，次数多的是胜出的骰子。
答案
思考
这是一道典型的“构造”类型的题目：根据题意，我们要构造出一个符合要求的答案。在本题的环境中，用了暴力搜索法来构造答案。
3. Drought
Farmer John的草地里的草在一场大旱中都干死了。经过数小时的绝望和沉思，Farmer John想到了一个绝妙的主意，购买玉米来喂养他宝贵的奶牛。
FJ的N头奶牛（\(1\le N\le 10^5\)）排成一行，队伍中的第i头奶牛的饥饿度为\(h_i\)（\(0\le h_i \le 10^9\)）。由于奶牛是社会性动物，她们坚持一起进食，FJ降低奶牛饥饿度的唯一方法是选择两头相邻的奶牛i和i+1并分别喂她们一袋玉米，令她们的饥饿度各减少1。
FJ想将他的奶牛喂至所有的奶牛都具有相同的非负饥饿度。请帮助FJ求出他喂奶牛达到上述状态所需的最少玉米袋数，或者如果不可能达到，输出−1。
输入格式（从终端 / 标准输入读入）：
每个测试用例包含多个独立的子测试用例，必须全部回答正确才能通过整个测试用例。输入的第一行包含
T（\(1\le T\le 100\)），为你需要求解的子测试用例的数量。以下是T个子测试用例，每个子测试用例包含两行。第一行包含N，第二行包含\(h_1, h_2, ... h_N\)
。输入保证所有子测试用例的N之和不超过\(10^5\)。每个子测试用例的N的值可能不同。
输出格式（输出至终端 / 标准输出）：
输出
T行，每个测试用例输出一行。
注意：这个问题涉及到的整数可能需要使用64位整数型（例如，C或 C++中的long long）。
输入样例：
5
3
8 10 5
6
4 6 4 4 6 4
3
0 1 0
2
1 2
3
10 9 9输出样例：
14
16
-1
-1
-1分析
我们可以观察到：每次喂食（记作(i, i+1)）会让两头牛的饥饿度减1。
一个直截了当的思路是：
对于每一对牛（\(h_i, h_{i+1}\)），我们不断地进行(i, i+1)的操作，直到其中某头牛的饥饿度达到某个f（也就是所有牛都相同的饥饿度）。然后重复上述的操作。
由于饥饿度不可以为负数，f最高就是\(min(h_i)\)。
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
const long long inf = 1e18;
ll cost(vector<int> h, int f)
{
int o = 0;
for (int i = 0; i < n - 1; i++)
{
if (h[i] > f)
{
int sub = min(h[i], h[i + 1]) - f;
h[i] -= sub, h[i + 1] -= sub;
o += sub * 2;
}
}
for (int i = 0; i < n - 1; i++)
{
if (h[i] != h[i + 1])
{
return inf;
}
}
return o;
}
ll exe()
{
cin >> n;
vector<int> h(n);
ll mn = inf, ans = inf;
for (int &i : h)
{
cin >> i;
mn = mn < i ? mn : i;
}
for (int f = 0; f <= mn; f++)
{
ll feeds = cost(h, f);
ans = ans < feeds ? ans : feeds;
}
return (ans == inf ? -1 : ans);
}
int main()
{
int t;
cin >> t;
while (t--)
{
cout << exe() << endl;
}
}按照答案的提示，这个方法只能得到一半的分。
我们还需要继续分析。
首先，我们进行一次\((i, i+1)\)的操作是将i和i+1的饥饿度减1。假定这样的操作要进行\(o_i\)次。\(o_1, o_2, \ldots, o_{N-1}\ge 0\)是明显的。当然，如果我们能调整到统一的饥饿度(f)，那么\(f>=0\)。
于是我们得到一系列式子：
\(\left\{\begin{array}{ll} f+o_1=h_1 \\f+o_1+o_2=h_2 \\f+o_1+o_2+o_3=h_3 \\... \\f+o_{N-2}+o_{N-1}=h_{N-1} \\f+o_{N-1}=h_{N} \end{array}\right.\)
将上述式子进行整理：
\(\left\{\begin{array}{ll} o_1=h_1-f\ge 0 \\ o_2=h_2-h_1\ge 0 \\ o_3=h_3-h_2+h_1-f\ge 0 \\ ... \\ o_{N-1}=h_{N-1}-h_{N-2}+h_{N-3}-...\ge 0 \\ h_N-h_{N-1}+h_{N-2}-h_{N-3}+...+h_2-h_1=0&\text{如果}N\text{为偶数} \\ h_N-h_{N-1}+h_{N-2}-h_{N-3}+...-h_2+h_1-f=0&\text{如果}N\text{为奇数} \end{array}\right.\)
注意到：如果N是奇数，最后的那个公式就可以计算出f。
如果N是偶数，在上面的公式中，我们会注意到：如果我们增加f的值，那么会影响\(o_1, o_3, ...o_{N-1}\)（所有的奇数项），而偶数项不变。所以最大的f只能是\(min(o_1, o_3, ..., o_{N-1})\)。
理解了上述思路后，代码的思路也就比较清楚了。
答案
思考
数学是编程的基础啊！从模拟到构造，是编程的一个大突破。