CF Edu178 ABCDE
CF Edu178 ABCDE
題目經(jīng)過(guò)dpsk小姐翻譯
過(guò)了5題還只能排2000+,無(wú)語(yǔ)了
目錄
A
題目名稱：三堆卡牌游戲
喵喵~Monocarp在桌子上放了3堆卡牌喵！第一堆有a張牌，第二堆有b張牌，第三堆有c張牌，而且滿足a < b < c這個(gè)條件喵~
現(xiàn)在Monocarp想從第三堆牌中拿走一些牌（至少要拿1張，最多可以拿c張），然后把這些牌分給前兩堆喵！每張拿走的牌都要分到第一堆或者第二堆里去喵當(dāng)然也可以把所有拿的牌都分到同一堆里喵
你的任務(wù)是判斷Monocarp能不能通過(guò)這樣的操作，讓三堆牌的數(shù)量變得一樣多喵！
喵~簡(jiǎn)單來(lái)說(shuō)就是：
- 從最多的第三堆拿牌
- 把拿的牌分給前兩堆
- 看看能不能讓三堆牌數(shù)變得相同
要特別注意a < b < c這個(gè)條件喵！
已知:
則得到：
故
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol()
{
ll a, b, c;
cin >> a >> b >> c;
if ((c + a - 2 * b) % 3 != 0)
{
cout << "NO" << endl;
return;
}
if ((c + a - 2 * b) < 0)
{
cout << "NO" << endl;
return;
}
cout << "YES\n";
}
int main()
{
int t;
cin >> t;
while (t--)
sol();
return 0;
}
B
給定一個(gè)由n個(gè)整數(shù)組成的數(shù)組a。
對(duì)于從1到n的每一個(gè)整數(shù)k，你需要執(zhí)行以下操作：
- 任意選擇數(shù)組a中的一個(gè)元素，將它移動(dòng)到數(shù)組的最右端（如果選擇最后一個(gè)元素，數(shù)組不會(huì)發(fā)生變化）；
- 輸出數(shù)組a最后k個(gè)元素的和；
- 將第一步移動(dòng)的元素放回它原來(lái)的位置（恢復(fù)原始數(shù)組a）。
對(duì)于每一個(gè)k，你需要選擇移動(dòng)的元素，使得輸出的值盡可能大。
請(qǐng)計(jì)算并輸出每一個(gè)k對(duì)應(yīng)的最大值。
喵~簡(jiǎn)單來(lái)說(shuō)就是：
每次可以選一個(gè)數(shù)放到最后，計(jì)算最后k個(gè)數(shù)的和（要盡可能大），然后把這個(gè)數(shù)放回原位。需要為每個(gè)k=1到n都算出這個(gè)最大和哦！(?′ω`?)
n輪相互獨(dú)立， 所以每輪單獨(dú)考慮
對(duì)于每一輪：
- 換
- 在后綴和前面選一個(gè)最大的數(shù)放到最后，擠掉了第k個(gè)數(shù)
- 不換
- 直接后綴和
兩種情況取最大值即可
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol()
{
ll n;
cin >> n;
vector<ll> a(n + 2, 0), maxx(n + 2, 0), pre(n + 2, 0);
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
{
maxx[i] = max(maxx[i - 1], a[i]);
pre[i] = pre[i - 1] + a[i];
}
for (int i = 1; i <= n; ++i)
{
ll pref = pre[n] - pre[n - i];
ll modify=max(0ll,maxx[n - i] - a[n - i + 1]);
cout << pref + modify<< ' ';
}
cout << endl;
}
int main()
{
int t;
cin >> t;
while (t--)
sol();
return 0;
}
C
愛(ài)麗絲和鮑勃正在玩一個(gè)游戲喵~他們有一堆編號(hào)從1到n的卡牌。游戲開(kāi)始時(shí)，這些卡牌會(huì)分別發(fā)給愛(ài)麗絲和鮑勃。
【卡牌勝負(fù)規(guī)則】
- 通常來(lái)說(shuō)，數(shù)字大的牌能打敗數(shù)字小的牌喵~(i > j)
- 但是有個(gè)特例喵！1號(hào)牌可以打敗n號(hào)牌哦！(｀?ω?′)
【游戲流程】
- 每回合開(kāi)始時(shí)，雙方必須至少有一張牌才能繼續(xù)游戲喵~
- 愛(ài)麗絲先出牌，從她的牌堆中選一張放到桌上
- 鮑勃看到愛(ài)麗絲出的牌后，也選一張自己的牌放到桌上
- 比較勝負(fù)：
- 如果愛(ài)麗絲的牌贏了，兩張牌都?xì)w愛(ài)麗絲所有喵~
- 否則兩張牌都?xì)w鮑勃所有
- 贏得的牌可以在之后的回合中使用哦！
【游戲結(jié)束】
當(dāng)某一方在回合開(kāi)始時(shí)沒(méi)有牌了，就輸?shù)粲螒蚶瞺
題目要求：在雙方都采取最優(yōu)策略的情況下，判斷誰(shuí)會(huì)獲勝喵！
1 號(hào)牌只能打敗n號(hào)牌
因此我們可以考慮分類討論1，n號(hào)牌給了誰(shuí)
先特判一張牌的情況
之后只用考慮兩個(gè)人都至少有兩張牌的情況
-
\(1 , n\) 在同一個(gè)人手上
- 顯然這個(gè)人只需要不停出n就贏了
-
\(1 , n\) 在不同人手上
- Alice 有 \(1\)
- Alice 無(wú)論如何先手不能出1
- Bob出n就贏了
- Alice 有 \(n\)
- Alice 先手不能出\(n\)，他會(huì)出剩余的最大值
- Bob必須要比這個(gè)值大才能贏
- 所以看誰(shuí)有\(n-1\)就行
- Alice 有 \(1\)
代碼寫得有點(diǎn)丑
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using namespace std;
void sol()
{
int n;
cin >> n;
vector<int> AAA, BBB;
string s;
cin >> s;
int cnt = 1;
for (auto i : s)
{
if (i == 'A')
AAA.push_back(cnt);
else
BBB.push_back(cnt);
++cnt;
}
if (AAA.size() == 1 and BBB.size() == 1)
{
if (AAA[0] < BBB[0])
cout << "Alice" << endl;
else
cout << "Bob" << endl;
return;
}
if (AAA.size() == 1)
{
cout << "Bob" << endl;
return;
}
if (BBB.size() == 1)
{
cout << "Alice" << endl;
return;
}
if (AAA[0] == 1 and AAA[AAA.size() - 1] == n)
{
cout << "Alice" << endl;
return;
}
if (BBB[0] == 1 and BBB[BBB.size() - 1] == n)
{
cout << "Bob" << endl;
return;
}
if (AAA[0] == 1)
{
cout << "Bob" << endl;
return;
}
else
{
if (AAA[AAA.size() - 2] > BBB[BBB.size() - 1])
{
cout << "Alice" << endl;
return;
}
else
{
cout << "Bob" << endl;
return;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
sol();
return 0;
}
D
喵嗚~讓我來(lái)幫你翻譯這道算法題目吧！(≧▽≦)
題目名稱：打造完美數(shù)組喵~
題目描述： 給你一個(gè)大小為n的整數(shù)數(shù)組a喵~
你可以進(jìn)行以下操作任意次數(shù)(包括零次)：
花費(fèi)1枚硬幣，將數(shù)組中任意一個(gè)元素增加1(執(zhí)行此操作時(shí)至少要有1枚硬幣喵~)
獲得1枚硬幣，將數(shù)組中任意一個(gè)元素減少1
我們稱一個(gè)數(shù)組是"完美數(shù)組"當(dāng)且僅當(dāng)滿足以下兩個(gè)條件：
- 數(shù)組中的每個(gè)元素都至少為2喵~
- 對(duì)于數(shù)組中任意兩個(gè)不同的元素a_i和a_j，它們的最大公約數(shù)(GCD)等于1。如果數(shù)組中元素少于2個(gè)，這個(gè)條件自動(dòng)滿足喵~
我們稱一個(gè)數(shù)組是"美麗數(shù)組"如果可以通過(guò)上述操作(初始硬幣數(shù)為0)將其變成完美數(shù)組。如果數(shù)組已經(jīng)是完美數(shù)組，那它也是美麗數(shù)組喵~
給定的數(shù)組不一定是美麗或完美的。你可以從中刪除任意數(shù)量的元素(可以全部刪除或者一個(gè)都不刪)。你的任務(wù)是計(jì)算最少需要?jiǎng)h除多少個(gè)元素(可以是零個(gè))才能使數(shù)組變得美麗喵~
最少需要?jiǎng)h除多少個(gè)元素
轉(zhuǎn)化為
最多可以保留多少個(gè)元素
這樣可以貪心地做了
\(+/-\)操作可以任意次，\(-\)操作 \(\geq\) \(+\)操作
所以我們可以把所有的數(shù)變成任意樣子，只要總和 \(\leq sum_{原}\) 就行
又因?yàn)橐笕我鈨蓴?shù) \(gcd=1\)，且 大于 \(1\)
可以構(gòu)造$2,3,5,7,11, ... $ 這樣全是素?cái)?shù)的序列，都求前綴和然后遍歷找就行，也可以二分（
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using namespace std;
const ll MAX_PRIME_COUNT = 400005;
const ll SIEVE_LIMIT = 6500005;
vector<bool> primesss(SIEVE_LIMIT + 1, 1);// 素?cái)?shù)篩
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// ------預(yù)處理素?cái)?shù)-----------------
primesss[0] = primesss[1] = false;
for (int i = 2; i * i <= SIEVE_LIMIT; i++)
if (primesss[i])
for (int j = i * i; j <= SIEVE_LIMIT; j += i)
primesss[j] = false;
vector<ll> primes;//存儲(chǔ)素?cái)?shù)
primes.reserve(MAX_PRIME_COUNT);
for (int i = 2; i <= SIEVE_LIMIT && (int)primes.size() < MAX_PRIME_COUNT; i++)
{
if (primesss[i])
primes.push_back(i);
}
vector<ll> f(primes.size() + 1, 0ll);//素?cái)?shù)前綴和
for (size_t i = 0; i < primes.size(); i++)
f[i + 1] = f[i] + primes[i];
// ----------------------------------
ll t;
cin >> t;
while (t--)
{
ll n;
cin >> n;
ll mmx = 0;
vector<ll> arr(n), pref(n + 1, 0ll);
for (int i = 0; i < n; i++)
cin >> arr[i];
sort(arr.begin(), arr.end(), greater<ll>());
for (int i = 0; i < n; i++)
pref[i + 1] = pref[i] + arr[i];
for (int m = 1; m <= n; m++)
{
if (pref[m] >= f[m])
mmx = m;
}
cout << (n - mmx) << endl;
}
return 0;
}
E
題目描述：
我們把一個(gè)字母稱為"允許字母"，如果它是小寫字母并且是拉丁字母表前k個(gè)字母中的一個(gè)喵~
現(xiàn)在給你一個(gè)長(zhǎng)度為n的字符串s，它只由"允許字母"組成喵~
如果一個(gè)字符串t是s的子序列，我們就稱t是"可愛(ài)的"字符串喵~
接下來(lái)會(huì)給出q個(gè)字符串t?, t?, ..., tq，它們也都只由"允許字母"組成喵對(duì)于每個(gè)字符串ti，你需要計(jì)算出最少需要在它的右邊添加多少個(gè)"允許字母"，才能讓它變得"不可愛(ài)"（即不再是s的子序列）喵
補(bǔ)充說(shuō)明：
字符串t是字符串s的子序列，是指可以通過(guò)從s中刪除零個(gè)或多個(gè)字符（可以從任意位置刪除）得到t喵~
一看q個(gè)字符串，
就想到要預(yù)處理一下s了，剛好看到過(guò)字符串自動(dòng)機(jī)
有時(shí)間更新一下
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using namespace std;
void sol()
{
int n, k;
cin >> n >> k;
string s;
cin >> s;
const ll INFFER = 1145141919;
vector<array<ll, 26>> f(n + 1);//狀態(tài)機(jī)
/*
預(yù)處理 s，讓 f[i][c] 表示：從 s 中位置 i（0‐索引）開(kāi)始，遇到字母 c 的第一個(gè)位置。如果沒(méi)有出現(xiàn)，則無(wú)窮大
*/
for (int c = 0; c < 26; c++)
f[n][c] = INFFER;
for (int i = n - 1; i >= 0; i--)
{
f[i] = f[i + 1];
int lc = s[i] - 'a';
f[i][lc] = i;
}
vector<int> dp(n + 1, 0);
dp[n] = 1;
for (int i = n - 1; i >= 0; i--)
{
int best = INT_MAX;
for (int c = 0; c < k; c++)
{
int nxt = f[i][c];
int maybe;
if (nxt == INFFER)
maybe = 1;
else
maybe = 1 + dp[nxt + 1];
best = min(best, maybe);
}
dp[i] = best;
}
int q;
cin >> q;
while (q--)
{
string t;
cin >> t;
int cur = 0;
bool notok = 0;
for (char ch : t)
{
int lc = ch - 'a';
int nxt = f[cur][lc];
if (nxt == INFFER)
{
notok = true;
break;
}
else
{
cur = nxt + 1;
if (cur > n)
cur = n;
}
}
if (notok)
cout << 0 << endl;
else
cout << dp[cur] << endl;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
sol();
return 0;
}
浙公網(wǎng)安備 33010602011771號(hào)