20221126測(cè)試賽
20221126測(cè)試賽
Doc84. 孤獨(dú)照片
時(shí)間限制：1.0s 內(nèi)存限制：256.0MB
輸入文件名：lonelyphoto.in 輸出文件名：lonelyphoto.out
試題來(lái)源：USACO
問(wèn)題描述
Farmer John 最近購(gòu)入了 \(N\) 頭新的奶牛，每頭奶牛的品種是更賽牛（Guernsey）或荷斯坦牛（Holstein）之一。
奶牛目前排成一排，F(xiàn)armer John 想要為每個(gè)連續(xù)不少于三頭奶牛的序列拍攝一張照片。 然而，他不想拍攝這樣的照片，其中只有一頭牛的品種是更賽牛，或者只有一頭牛的品種是荷斯坦牛——他認(rèn)為這頭奇特的牛會(huì)感到孤立和不自然。 在為每個(gè)連續(xù)不少于三頭奶牛的序列拍攝了一張照片后，他把所有「孤獨(dú)的」照片，即其中只有一頭更賽牛或荷斯坦奶牛的照片，都扔掉了。
給定奶牛的排列方式，請(qǐng)幫助 Farmer John 求出他會(huì)扔掉多少?gòu)埞陋?dú)的照片。如果兩張照片以不同的奶牛開(kāi)始或結(jié)束，則認(rèn)為它們是不同的。
輸入格式
輸入的第一行包含 N。
輸入的第二行包含一個(gè)長(zhǎng)為 N 的字符串。如果隊(duì)伍中的第 i 頭奶牛是更賽牛，則字符串的第 i 個(gè)字符為 G。否則，第 i 頭奶牛是荷斯坦牛，該字符為 H。
輸出格式
輸出 Farmer John 會(huì)扔掉的孤獨(dú)的照片數(shù)量。
輸入樣例
5
GHGHG
輸出樣例
3
樣例說(shuō)明
這個(gè)例子中的每一個(gè)長(zhǎng)為 3 的子串均恰好包含一頭更賽牛或荷斯坦牛——所以這些子串表示孤獨(dú)的照片，并會(huì)被 Farmer John 扔掉。所有更長(zhǎng)的子串（GHGH、HGHG 和 GHGHG）都可以被接受。
測(cè)試點(diǎn)性質(zhì)
測(cè)試點(diǎn) 2-4 滿足 \(N≤50\)。
測(cè)試點(diǎn) 5-10 滿足 \(N≤5000\)。
為了增加一些挑戰(zhàn)，測(cè)試點(diǎn) \(11\) 沒(méi)有額外限制。注意這個(gè)測(cè)試點(diǎn)的答案可能無(wú)法用標(biāo)準(zhǔn)的 \(32\) 位整數(shù)型存儲(chǔ)，你可能需要使用更大的整數(shù)類(lèi)型（例如，C++ 中 \(64\) 位的 "long long int" 類(lèi)型）。
解題思路
用最樸素的想法，只要抓住一個(gè)點(diǎn)討論，它后面共有多少的"孤獨(dú)的照片"，并且這個(gè)區(qū)間是有限制的，只要H和G均大于等于二，就會(huì)導(dǎo)致這個(gè)范圍及這個(gè)范圍之后的所有照片都不會(huì)是孤獨(dú)的，因此我們可以得出一個(gè)優(yōu)化較好的\(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;
}
但是題目里還有一個(gè)額外的大數(shù)據(jù)點(diǎn)，會(huì)把這個(gè)\(O(n^2)\)的算法卡到90分。
于是讓我們換一個(gè)思路:
每一個(gè)奶牛都可能會(huì)形成若干張"孤獨(dú)"的照片，我們將其稱(chēng)為對(duì)答案的"貢獻(xiàn)"
那么，我們是否有某種辦法可以預(yù)處理出這個(gè)貢獻(xiàn)值呢？
其實(shí)，由上面的思路分析可得，其實(shí)形成孤獨(dú)的照片數(shù)量，就是這頭牛前(后)與它不同種類(lèi)連續(xù)的長(zhǎng)度。
得出滿分算法:
#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. 牧人游戲
時(shí)間限制：1.0s 內(nèi)存限制：256.0MB
輸入文件名：herdle.in 輸出文件名：herdle.out
試題來(lái)源：UASCO
問(wèn)題描述
奶牛們發(fā)明了一種名為 Herdle 的新型解謎游戲，在牛界引起了轟動(dòng)。
每天都會(huì)有一個(gè)新謎題發(fā)布供奶牛解決。游戲采用 3x3 方陣的形式表示農(nóng)場(chǎng)的一塊田地，田地的每個(gè)方格都由特定品種的奶牛占據(jù)。總共只有 26 種可能的品種，每一種由 A 到 Z 中的不同大寫(xiě)字母標(biāo)識(shí)。玩家不會(huì)被告知田地中的奶牛品種排列方式——游戲目標(biāo)是通過(guò)一系列猜測(cè)確定它們。
每次猜測(cè)，奶牛們輸入一個(gè) 3x3 的大寫(xiě)字母方陣，表示該田地可以用奶牛填充的可能方式。猜測(cè)的某些方格可能是正確的。這些方格以綠色高亮顯示，讓奶牛們知道這些是正確的。猜測(cè)的另一些方格可能填入了品種正確但位置錯(cuò)誤的奶牛。這些以黃色高亮顯示。
黃色高亮顯示的方格的數(shù)量可以幫助指示某個(gè)品種的奶牛數(shù)量。 例如，假設(shè)猜測(cè)方陣包含 4 頭品種 A 的奶牛，而答案方陣包含 2 只品種 A 的奶牛，其中沒(méi)有正確位置上的 A （即，它們都不應(yīng)該是綠色的）。 在這種情況下，猜測(cè)方陣中只有兩個(gè) A 應(yīng)以黃色高亮顯示。 更準(zhǔn)確地說(shuō)，如果猜測(cè)方陣中有 x 個(gè)特定品種的奶牛，并且 答案方陣中有 \(y<x\) 頭該品種奶牛（不包括位置正確而得到綠色高亮顯示的奶牛），那么猜測(cè)方陣的 x 頭奶牛中只有 y 頭奶牛應(yīng)該以黃色高亮顯示。
給定正確答案的方陣和一個(gè)表示對(duì)該答案的猜測(cè)的方陣，請(qǐng)計(jì)算綠色和黃色高亮顯示的方格的數(shù)量。
輸入格式
輸入的前 3 行給定了正確答案的方陣。以下 3 行表示對(duì)該答案的猜測(cè)。
輸出格式
輸出兩行。
輸出的第一行包含應(yīng)當(dāng)以綠色高亮顯示的方格的數(shù)量。
輸出的第二行包含應(yīng)當(dāng)以黃色高亮顯示的方格的數(shù)量。
輸入樣例1
COW
SAY
MOO
WIN
THE
IOI
輸出樣例1
1 1
樣例說(shuō)明1
在這個(gè)例子中，最后一行中間的 O 是正確的，所以這個(gè)方格以綠色高亮顯示。字母 W 位于錯(cuò)誤的位置，所以它以黃色高亮顯示。
輸入樣例2
AAA
BBB
CCC
AYY
AAA
ZZZ
輸出樣例2
1 2
樣例說(shuō)明2
在這里，其中一個(gè) A 位于正確的位置，所以它以綠色高亮顯示。余下的 A 均不在正確位置上，由于答案方陣中有兩個(gè) A，所以有兩個(gè) A 應(yīng)當(dāng)以黃色高亮顯示。
解題思路
對(duì)于正確的，我們只需要掃一遍對(duì)比即可。
位置錯(cuò)誤的，可以采用哈希記錄數(shù)量，最后比對(duì)即可。
一下是一種錯(cuò)誤示范:
#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;
}
一個(gè)如此完美的零分。注意的是，這題的數(shù)據(jù)關(guān)系挺亂的，最好用有意義的單詞來(lái)記錄數(shù)據(jù)。
正解如下:
#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記錄猜測(cè)答案。sum1記錄的是正確答案中該字符的數(shù)量，sum2則是猜測(cè)數(shù)組中的數(shù)量。最后討論一下即可。
D8k2m. 溫度調(diào)節(jié)
輸入文件名：adjust.in 輸出文件名：adjust.out
試題來(lái)源：USACO
問(wèn)題描述
Farmer John 的 \(N\) 頭奶牛對(duì)他們牛棚的室溫非常挑剔。有些奶牛喜歡溫度低一些，而有些奶牛則喜歡溫度高一些。
Farmer John 的牛棚包含一排 \(N\) 個(gè)牛欄，編號(hào)為 \(1…N\)，每個(gè)牛欄里有一頭牛。 第 \(i\) 頭奶牛希望她的牛欄中的溫度是 \(p_i\)，而現(xiàn)在她的牛欄中的溫度是 \(t_i\)。為了確保每頭奶牛都感到舒適，F(xiàn)armer John 安裝了一個(gè)新的空調(diào)系統(tǒng)。該系統(tǒng)進(jìn)行控制的方式非常有趣，他可以向系統(tǒng)發(fā)送命令，告訴它將一組連續(xù)的牛欄內(nèi)的溫度升高或降低 1 個(gè)單位——例如「將牛欄 \(5…8\)的溫度升高 1 個(gè)單位」。一組連續(xù)的牛欄最短可以僅包含一個(gè)牛欄。
請(qǐng)幫助 Farmer John 求出他需要向新的空調(diào)系統(tǒng)發(fā)送的命令的最小數(shù)量，使得每頭奶牛的牛欄都處于其中的奶牛的理想溫度。
輸入格式
輸入的第一行包含 N。下一行包含 N 個(gè)非負(fù)整數(shù) \(p_1…p_N\)，用空格分隔。最后一行包含 N 個(gè)非負(fù)整數(shù) \(t_1…t_N\)。
輸出格式
輸出一個(gè)整數(shù)，為 Farmer John 需要使用的最小指令數(shù)量。
輸入樣例
5
1 5 3 3 4
1 2 2 2 1
輸出樣例
5
樣例說(shuō)明
一組最優(yōu)的 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
測(cè)試點(diǎn)性質(zhì)
測(cè)試點(diǎn) 2-5 滿足 N≤100。
測(cè)試點(diǎn) 6-8 滿足 N≤1000。
測(cè)試點(diǎn) 9-10 滿足 N≤100,000。
測(cè)試點(diǎn) 1-6 和 9 中，溫度值不超過(guò) 100。
測(cè)試點(diǎn) 7-8 和 10 中，溫度值不超過(guò) 10,000。
解題思路
差分題.
從分段的思想考慮:
如果有一段牛的溫度均低于理想溫度，那么一定要對(duì)這一段都進(jìn)行升溫操作。反之亦然。
再這樣考慮:
如果前一頭牛的溫度低于后一頭牛(但都需要加溫度)，我們只要考慮后一頭牛，因?yàn)榧雍笠活^牛時(shí)可以同時(shí)加前一頭牛。我們就可以劃分出若干個(gè)"段"，即每一頭牛需要在前一頭牛身上再加多少.麻煩的是，有的牛需要降溫.
抽象一下:
對(duì)于每一頭牛，存在一個(gè)差異數(shù)組D,表示著現(xiàn)在溫度和理想溫度的差值，我們要選定一個(gè)范圍，\(i-j\),使得\(p_1 - p_N\)最終等于0.
從剛才分段的思想，我們可以把正負(fù)差值統(tǒng)一成正數(shù)，分別計(jì)算。
得出如此思路:
- 若這項(xiàng)的差值大于前一項(xiàng)的差值，只需要計(jì)算這兩個(gè)插值的和。(因?yàn)橹恍枰{(diào)整后一頭牛)
- 若不大于，就不需要處理。
代碼:
#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;
}
浙公網(wǎng)安備 33010602011771號(hào)