「题解」USACO 2022 January Bronze 比赛

T1 Herdle（牧群）

在这题中，我们可以直接将两个 二维字符数组 $answer$ 和 $guess$ 进行校对。

一旦字母位置相同，就将变量 $green$ 加 $1$；

否则，

我们就统计字母的 出现次数。

举个栗子，

字母 $X$ 在 $guess$ 数组中出现了 $a$ 次，其中，被标记为 $green$ 的部分有 $b$ 个，

则字母 $X$ 在 $guess$ 数组中，被标记为 $yellow$ 的部分就有 $a-b\space (a\ge b)$ 个。

于是，完整代码水落石出。

Code:

#include
using namespace std;
int green=0,yellow=0,cntans[30],cntguess[30];
string ans[4],guess[4];
int main()
{
    for(int i=0;i<3;i++)
        cin>>ans[i];
    for(int i=0;i<3;i++)
        cin>>guess[i];
    //输入
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            if(ans[i][j]==guess[i][j])
                ++green; //位置相同，字母相同
            ++cntans[ans[i][j]-'A'];
            ++cntguess[guess[i][j]-'A'];
        }
    }
    for(int j=0;j<26;j++)
        yellow+=min(cntans[j],cntguess[j]); //比较出现次数
    yellow-=green; //减去被计算的绿色标记数量
    printf("%d\n%d",green,yellow);
    return 0;
}

T2 Non-Transitive Dice (非传递骰子)
众所周知，每一次打开题目，我们都要注意 数据范围。

emmm……

$1\le T\le 10$

并且，我们要枚举的这个骰子是一个 四面骰子，而每一面上的数字 仅仅是 $1\sim 10$。

考虑深搜。

每次从 $1\sim 10$ 里选一个数字，如此执行 $4$ 次，时间复杂度为 $O(10^4\times T)$，完全可以通过。

再来分析一下 判定函数：
举个栗子，
$A=\{4,5,6,7\}$
$B=\{2,4,5,10\}$

其中，有：
$A_1>B_1,A_2>B_1,A_3>B_1\dots$

合起来，
序列 $A$ 中的数字大于 $B$ 的有 $9$ 次；
序列 $B$ 中的数字大于 $A$ 的则有 $5$ 次！

因此，我们就说 $A$ 能战胜 $B$！

由此，可得出以下程序：

bool check(int x[],int y[]) //计算x能否赢y
{
    int cntx=0,cnty=0;
    for(int i=1;i<5;i++)
    {
        for(int j=1;j<5;j++)
        {
            if(x[i]>y[j])
                ++cntx;
            else if(x[i]<y[j])
                ++cnty;
        }
    }
    return cntx>cnty;
}

至此，这题完全结束。
下面给出 完整代码。
Code:

#include
#define isdight(c) (c>='0'&&c<='9')
using namespace std;
int t,a[5],b[5],c[5],flag=0;
inline int read() //快读
{
    int x=0,f=1;
    char c=getchar();
    while(!isdight(c))
        f=(c^'-'?1:-1),c=getchar();
    while(isdight(c))
        x=(x<<1)+(x<<3)+(c-'0'),c=getchar();
    return x*f;
}
bool check(int x[],int y[]) //计算x能否赢y
{
    int cntx=0,cnty=0;
    for(int i=1;i<5;i++)
    {
        for(int j=1;j<5;j++)
        {
            if(x[i]>y[j])
                ++cntx;
            else if(x[i]<y[j])
                ++cnty;
        }
    }
    return cntx>cnty;
}
void dfs(int dep) //核心部分
{
    if(dep>4)
    {
        if((check(a,b)&&check(b,c)&&check(c,a))||(check(b,a)&&check(a,c)&&check(c,b))) //满足非传递性
            flag=1;
        return;
    }
    if(flag)
        return;
    for(int i=1;i<11;i++) //递归
    {
        c[dep]=i;
        dfs(dep+1);
    }
}
int main()
{
    t=read();
    while(t--)
    {
        flag=0;
        for(int i=1;i<5;i++)
            a[i]=read();
        for(int i=1;i<5;i++)
            b[i]=read();
        sort(a+1,a+5);
        sort(b+1,b+5);
        //排序，预处理
        dfs(1);
        if(flag)
            puts("yes");
        else
            puts("no");
    }
    return 0;
}

T3 Drought（干旱）

为了获得更快的解决方案，

我们首先要在数组 $h$ 上 从左向右移动，

对 $(h_i,h_{i+1})$ 操作，使得 $h_i=h_{i-1}$，

完成这些操作以后，

我们发现了一条性质：

对于所有 $1\le i\le N$，执行操作前满足 $h_i>h_{i-1}$。

遍历数组后，
要么，$h_N>h_{N-1}$（在这种情况下无解）；
要么，对于所有 $2\le i\le N，h_i\le h_{i-1}$，$h_i$ 将不增加。

在后一种情况下，让我们反转数组 $h$。

再按照上述过程执行操作之后，$h_1\sim h_{N-1}$，都将相等，如果 $h_N>h_{N-1}$，则无解；
否则，$h$ 的所有元素是否相等，还需要验证这些元素是否为 非负数。

该解决方案需要 $O(N)$ 级别的时间复杂度。

上代码！
Code:

#include
#define int long long
#define isdight(c) (c>='0'&&c<='9')
#define swap(a,b) a^=b^=a^=b
using namespace std;
int t,n,h[100005];
inline int read() //快读
{
    int x=0,f=1;
    char c=getchar();
    while(!isdight(c))
        f=(c^'-'?1:-1),c=getchar();
    while(isdight(c))
        x=(x<<1)+(x<<3)+c-'0',c=getchar();
    return x*f;
}
int solve()
{
    int ans=0;
    if(n<2)
        return 0; //无需改变
    for(int j=1;j<3;j++) //正序变化与倒序变化
    {
        for(int i=2;i)
        {
            if(h[i]>h[i-1])
            {
                int differ=h[i]-h[i-1];
                ans+=differ<<1; //每次喂两袋
                h[i+1]-=differ;
                h[i]=h[i-1]; //同时变化
            }
        }
        if(h[n]>h[n-1])
            return -1; //无解
        reverse(h+1,h+1+n); //反转
    }
    return h[1]<0?-1:ans;
}
signed main()
{
    t=read();
    while(t--)
    {
        n=read();
        for(int i=1;i<=n;i++)
            h[i]=read();
        printf("%lld\n",solve());
    }
    return 0;
}