20221126测试赛
Doc84. 孤独照片
时间限制：1.0s 内存限制：256.0MB
输入文件名：lonelyphoto.in 输出文件名：lonelyphoto.out
试题来源：USACO
问题描述
Farmer John 最近购入了 \(N\) 头新的奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。
奶牛目前排成一排，Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。 然而，他不想拍摄这样的照片，其中只有一头牛的品种是更赛牛，或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。 在为每个连续不少于三头奶牛的序列拍摄了一张照片后，他把所有「孤独的」照片，即其中只有一头更赛牛或荷斯坦奶牛的照片，都扔掉了。
给定奶牛的排列方式，请帮助 Farmer John 求出他会扔掉多少张孤独的照片。如果两张照片以不同的奶牛开始或结束，则认为它们是不同的。
输入格式
输入的第一行包含 N。
输入的第二行包含一个长为 N 的字符串。如果队伍中的第 i 头奶牛是更赛牛，则字符串的第 i 个字符为 G。否则，第 i 头奶牛是荷斯坦牛，该字符为 H。
输出格式
输出 Farmer John 会扔掉的孤独的照片数量。
输入样例
5
GHGHG
输出样例
3
样例说明
这个例子中的每一个长为 3 的子串均恰好包含一头更赛牛或荷斯坦牛——所以这些子串表示孤独的照片，并会被 Farmer John 扔掉。所有更长的子串（GHGH、HGHG 和 GHGHG）都可以被接受。
测试点性质
测试点 2-4 满足 \(N≤50\)。
测试点 5-10 满足 \(N≤5000\)。
为了增加一些挑战，测试点 \(11\) 没有额外限制。注意这个测试点的答案可能无法用标准的 \(32\) 位整数型存储，你可能需要使用更大的整数类型（例如，C++ 中 \(64\) 位的 "long long int" 类型）。
解题思路
用最朴素的想法，只要抓住一个点讨论，它后面共有多少的"孤独的照片"，并且这个区间是有限制的，只要H和G均大于等于二，就会导致这个范围及这个范围之后的所有照片都不会是孤独的，因此我们可以得出一个优化较好的\(O(N^2)\)的算法:
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
freopen("lonelyphoto.in" , "r" , stdin);
freopen("lonelyphoto.out" , "w" , stdout);
int n , cnt = 0;
string str;
cin >> n >> str;
for(int i = 0 ; i < n ; i ++)
{
int cntG = 0 , cntH = 0;
for(int j = i ; j < n ; j ++)
{
//cout << str[j] << endl;
if(str[j] == 'G')
cntG ++;
if(str[j] == 'H')
cntH ++;
if(j - i >= 2 &&(cntG == 1 || cntH == 1))
cnt ++;
if(cntH >= 2 && cntG >= 2)
break;
}
}
cout << cnt << endl;
return 0;
}
但是题目里还有一个额外的大数据点，会把这个\(O(n^2)\)的算法卡到90分。
于是让我们换一个思路:
每一个奶牛都可能会形成若干张"孤独"的照片，我们将其称为对答案的"贡献"
那么，我们是否有某种办法可以预处理出这个贡献值呢？
其实，由上面的思路分析可得，其实形成孤独的照片数量，就是这头牛前(后)与它不同种类连续的长度。
得出满分算法:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500010;
int n, m, i, j, k;
int l[N], r[N], ans;
string a;
signed main()
{
freopen("lonelyphoto.in" , "r" , stdin);
freopen("lonelyphoto.out" , "w" , stdout);
cin >> n >> a;
for (i = 0, k = 0; i < n; ++i)
if (a[i] == a[i - 1])
l[i] = 0, ++k;
else
l[i] = k, k = 1;
for (i = n - 1, k = 0; i >= 0; --i)
{
if (a[i] == a[i + 1])
r[i] = 0, ++k;
else
r[i] = k, k = 1;
}
for (i = 0; i < n; ++i)
{
if (l[i] && r[i])
ans += l[i] * r[i];
if (l[i] >= 2)
ans += l[i] - 1;
if (r[i] >= 2)
ans += r[i] - 1;
}
cout << ans << endl;
return 0;
}
D5k3c. 牧人游戏
时间限制：1.0s 内存限制：256.0MB
输入文件名：herdle.in 输出文件名：herdle.out
试题来源：UASCO
问题描述
奶牛们发明了一种名为 Herdle 的新型解谜游戏，在牛界引起了轰动。
每天都会有一个新谜题发布供奶牛解决。游戏采用 3x3 方阵的形式表示农场的一块田地，田地的每个方格都由特定品种的奶牛占据。总共只有 26 种可能的品种，每一种由 A 到 Z 中的不同大写字母标识。玩家不会被告知田地中的奶牛品种排列方式——游戏目标是通过一系列猜测确定它们。
每次猜测，奶牛们输入一个 3x3 的大写字母方阵，表示该田地可以用奶牛填充的可能方式。猜测的某些方格可能是正确的。这些方格以绿色高亮显示，让奶牛们知道这些是正确的。猜测的另一些方格可能填入了品种正确但位置错误的奶牛。这些以黄色高亮显示。
黄色高亮显示的方格的数量可以帮助指示某个品种的奶牛数量。 例如，假设猜测方阵包含 4 头品种 A 的奶牛，而答案方阵包含 2 只品种 A 的奶牛，其中没有正确位置上的 A （即，它们都不应该是绿色的）。 在这种情况下，猜测方阵中只有两个 A 应以黄色高亮显示。 更准确地说，如果猜测方阵中有 x 个特定品种的奶牛，并且 答案方阵中有 \(y<x\) 头该品种奶牛（不包括位置正确而得到绿色高亮显示的奶牛），那么猜测方阵的 x 头奶牛中只有 y 头奶牛应该以黄色高亮显示。
给定正确答案的方阵和一个表示对该答案的猜测的方阵，请计算绿色和黄色高亮显示的方格的数量。
输入格式
输入的前 3 行给定了正确答案的方阵。以下 3 行表示对该答案的猜测。
输出格式
输出两行。
输出的第一行包含应当以绿色高亮显示的方格的数量。
输出的第二行包含应当以黄色高亮显示的方格的数量。
输入样例1
COW
SAY
MOO
WIN
THE
IOI
输出样例1
1 1
样例说明1
在这个例子中，最后一行中间的 O 是正确的，所以这个方格以绿色高亮显示。字母 W 位于错误的位置，所以它以黄色高亮显示。
输入样例2
AAA
BBB
CCC
AYY
AAA
ZZZ
输出样例2
1 2
样例说明2
在这里，其中一个 A 位于正确的位置，所以它以绿色高亮显示。余下的 A 均不在正确位置上，由于答案方阵中有两个 A，所以有两个 A 应当以黄色高亮显示。
解题思路
对于正确的，我们只需要扫一遍对比即可。
位置错误的，可以采用哈希记录数量，最后比对即可。
一下是一种错误示范:
#include <bits/stdc++.h>
using namespace std;
char rht[3][3];
char guess[3][3];
int t[200] , m[200] , r[200];
int main()
{
freopen("herdle.in" , "r" , stdin);
freopen("herdle.out" , "w" , stdout);
int green = 0 , yellow = 0;
for(int i = 0 ; i < 3 ; i ++)
for(int j = 0 ; j < 3 ; j ++)
{
cin >> rht[i][j];
t[rht[i][j]] ++;
}
for(int i = 0 ; i < 3 ; i ++)
for(int j = 0 ; j < 3 ; j ++)
{
cin >> guess[i][j];
m[guess[i][j]]++;
}
for(int i = 0 ; i < 3 ; i ++)
for(int j = 0 ; j < 3 ; j ++)
{
if(rht[i][j] == guess[i][j])
{
green ++ , r[rht[i][j]] ++;
}
}
for(int i = 'A' ; i <= 'Z' ; i ++)
{
if(m[i] >= t[i] && m[i]!=0 && t[i]!=0)
yellow += t[i] - r[i];
}
cout << green << " " << yellow << endl;
return 0;
}
一个如此完美的零分。注意的是，这题的数据关系挺乱的，最好用有意义的单词来记录数据。
正解如下:
#include <bits/stdc++.h>
using namespace std;
char answer[10][10], check[10][10];
int sum1[27], sum2[27];
int main()
{
freopen("herdle.in", "r", stdin);
freopen("herdle.out", "w", stdout);
int i, j, green = 0, yellow = 0;
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
cin >> answer[i][j];
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
cin >> check[i][j];
for (i = 0; i < 3; ++i)
{
for (j = 0; j < 3; ++j)
{
if (answer[i][j] == check[i][j])
green++;
else
{
sum1[answer[i][j] - 'A']++;
sum2[check[i][j] - 'A']++;
}
}
}
for (int i = 0; i < 26; ++i)
yellow += min(sum1[i], sum2[i]);
cout << green << endl;
cout << yellow << endl;
return 0;
}
用answer矩阵记录正确答案，check记录猜测答案。sum1记录的是正确答案中该字符的数量，sum2则是猜测数组中的数量。最后讨论一下即可。
D8k2m. 温度调节
输入文件名：adjust.in 输出文件名：adjust.out
试题来源：USACO
问题描述
Farmer John 的 \(N\) 头奶牛对他们牛棚的室温非常挑剔。有些奶牛喜欢温度低一些，而有些奶牛则喜欢温度高一些。
Farmer John 的牛棚包含一排 \(N\) 个牛栏，编号为 \(1…N\)，每个牛栏里有一头牛。 第 \(i\) 头奶牛希望她的牛栏中的温度是 \(p_i\)，而现在她的牛栏中的温度是 \(t_i\)。为了确保每头奶牛都感到舒适，Farmer John 安装了一个新的空调系统。该系统进行控制的方式非常有趣，他可以向系统发送命令，告诉它将一组连续的牛栏内的温度升高或降低 1 个单位——例如「将牛栏 \(5…8\)的温度升高 1 个单位」。一组连续的牛栏最短可以仅包含一个牛栏。
请帮助 Farmer John 求出他需要向新的空调系统发送的命令的最小数量，使得每头奶牛的牛栏都处于其中的奶牛的理想温度。
输入格式
输入的第一行包含 N。下一行包含 N 个非负整数 \(p_1…p_N\)，用空格分隔。最后一行包含 N 个非负整数 \(t_1…t_N\)。
输出格式
输出一个整数，为 Farmer John 需要使用的最小指令数量。
输入样例
5
1 5 3 3 4
1 2 2 2 1
输出样例
5
样例说明
一组最优的 Farmer John 可以使用的指令如下：
初始温度 ：1 2 2 2 1
升高牛棚 2..5：1 3 3 3 2
升高牛棚 2..5：1 4 4 4 3
升高牛棚 2..5：1 5 5 5 4
降低牛棚 3..4：1 5 4 4 4
降低牛棚 3..4：1 5 3 3 4
测试点性质
测试点 2-5 满足 N≤100。
测试点 6-8 满足 N≤1000。
测试点 9-10 满足 N≤100,000。
测试点 1-6 和 9 中，温度值不超过 100。
测试点 7-8 和 10 中，温度值不超过 10,000。
解题思路
差分题.
从分段的思想考虑:
如果有一段牛的温度均低于理想温度，那么一定要对这一段都进行升温操作。反之亦然。
再这样考虑:
如果前一头牛的温度低于后一头牛(但都需要加温度)，我们只要考虑后一头牛，因为加后一头牛时可以同时加前一头牛。我们就可以划分出若干个"段"，即每一头牛需要在前一头牛身上再加多少.麻烦的是，有的牛需要降温.
抽象一下:
对于每一头牛，存在一个差异数组D,表示着现在温度和理想温度的差值，我们要选定一个范围，\(i-j\),使得\(p_1 - p_N\)最终等于0.
从刚才分段的思想，我们可以把正负差值统一成正数，分别计算。
得出如此思路:
- 若这项的差值大于前一项的差值，只需要计算这两个插值的和。(因为只需要调整后一头牛)
- 若不大于，就不需要处理。
代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100010;
int n, a[MAXN], b[MAXN], now[MAXN], want[MAXN];
signed main()
{
freopen("adjust.in" , "r" ,stdin);
freopen("adjust.out" , "w" , stdout);
int ans = 0;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> want[i];
for (int i = 1; i <= n; i++)
{
cin >> now[i];
int t = want[i] - now[i];
if (t >= 0)
a[i] = t;
else
b[i] = -t;
}
for (int i = 1; i <= n; i++)
if (a[i] > a[i - 1])
ans += a[i] - a[i - 1];
for (int i = 1; i <= n; i++)
if (b[i] > b[i - 1])
ans += b[i] - b[i - 1];
cout << ans << endl;
return 0;
}