Codeforces Round #700 (Div. 2)ABCD1D2
A - Yet Another String Game
題意
給定一個由小寫字母組成的字元串，每次選擇一個尚未被選取過的字元進行修改（範圍：小寫字母a~z）——必須修改成除目前字母以外的小寫字母，直至沒有字元可以選取。A的目标是使它字典序越小越好，B的目标是使它字典序越大越好，A先開始修改，兩個人都選擇最佳政策進行遊戲。問最終這個串會變成什麼樣？
思路
選過就不能再選，是以一定是選剩下的裡面最靠前的修改，無論是改大還是改小。遇到a、z，就改成b、y。
代碼
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 1e3 + 19;
const ll mod = 1e9 + 7;
char str[N];
int main()
{
int T;
cin >> T;
while(T--)
{
cin >> str;
int n = strlen(str);
for(int i = 0; i < n; i++)
{
if(i % 2)
{
str[i] = str[i] == 'z' ? 'y' : 'z';
}
else
{
str[i] = str[i] == 'a' ? 'b' : 'a';
}
cout << str[i];
}
cout << endl;
}
return 0;
}
B - The Great Hero
題意
英雄有 A A A 點傷害， B B B 點生命； n n n 隻怪獸的傷害值和初始生命值分别為 a 1 , a 2 , … , a n a_1, a_2, … , a_n a1,a2,…,an 和 b 1 , b 2 , … , b n b_1, b_2, … , b_n b1,b2,…,bn ，英雄和怪獸每次交戰，英雄掉 a i a_i ai 點血，怪獸掉 B B B 點血。英雄可以和怪獸多次交戰。問英雄能否殺死所有怪獸？
思路
這題最需要注意的點在樣例中已經指出了：如果最後一個怪獸和英雄交戰時，英雄死了，怪獸也死了，那麼英雄雖死猶榮，他還是算殺死了所有的怪獸。我最開始WA的三發都是在這裡。假設有一個傷害極高的怪獸，和一群幾乎沒傷害的怪獸，我們應該先殺死沒傷害的怪獸，把傷害越高的怪獸放在越後面，不然英雄在第一輪就被gank了，把傷害高的放在後面，那麼英雄雖然仍然會死亡，但是能殺死所有怪獸。
其他點都挺簡單的。
代碼
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 1e6 + 19;
const ll mod = 1e9 + 7;
struct node
{
ll a, b;
bool operator < (const node& x)
{
return a < x.a;
}
} c[N];
int main()
{
int T;
cin >> T;
while(T--)
{
ll A, B, n;
bool flag = 0;
cin >> A >> B >> n;
for(int i = 0; i < n; i++)
{
cin >> c[i].a;
}
for(int i = 0; i < n; i++)
{
cin >> c[i].b;
}
sort(c, c + n);
for(int i = 0; i < n; i++)
{
ll time = min((B + c[i].a - 1) / c[i].a , (c[i].b + A - 1) / A);
B -= time * c[i].a;
if(B <= 0)
{
if(i < n - 1)
flag = 1;
else if(c[i].b > time * A)
flag = 1;
break;
}
}
if(flag)
{
cout << "NO" << endl;
}
else
{
cout << "YES" << endl;
}
}
return 0;
}
C - Searching Local Minimum
題意
給定一個從1到n的排列 p p p ，每次可以詢問一個位置的數字，要求你在100次詢問内，找到一個位置 i i i ，有 a i − 1 > a i , a i < a i + 1 a_{i - 1} \gt a_i,a_i \lt a_{i + 1} ai−1>ai,ai<ai+1 。
思路
參考：(4條消息) 1480 C. Searching Local Minimum(新穎的二分查找)
挺有意思的題目，賽場上是真的想不出
代碼
（其實和參考寫的挺像的，可以直接去參考看思路和代碼）
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 1e6 + 19;
const ll mod = 1e9 + 7;
int a[N];
int n;
void query(int x)
{
if(x > n || x < 1 || a[x])
return ;
cout << "? " << x << endl;
cout.flush();
cin >> a[x];
}
int main()
{
cin >> n;
int l = 1, r = n;
a[0] = INF, a[n + 1] = INF;
while(l < r)
{
int mid = (l + r) >> 1;
query(mid);
query(mid + 1);
if(a[mid] > a[mid + 1])
{
l = mid + 1;
}
else
{
r = mid;
}
}
cout << "! " << l << endl;
return 0;
}
D1 - Painting the Array I
題意
給你一個數組，把他不打亂順序的分成兩半，并合并這分開的兩個數組中所有的連續重複元素。問兩個數組最終長度和最大是多少？
思路
其實是很簡單的一道題，賽場上的思路也很完美，就是細節太多，死得很慘。思路如下：
- 把原數組中的數字拆分存儲成 { \{ { 1 1 1 個 2 2 2， 3 3 3 個 1 , … , k 1,…,k 1,…,k 個 n } n\} n} 的形式，即合并連續相同的數字，之後以這樣的形式從頭到尾周遊；
- 我們很容易看出，其實情況完全可以歸為兩種：
- 數字個數為 1 1 1 ；
- 數字個數大于 1 1 1 。
為什麼直接把其他情況都合并到2呢？因為不管多少個最後肯定都是分成兩堆。是以多少個到最後最多都是合并成兩個。
第一種情況，肯定能給答案增加1的貢獻1；第二種情況則需要特判目前分出來的兩個隊列末尾的字元，會有兩種情況，第一種是有一個隊列的末尾和目前數字相同，第二個情況是兩個隊列的末尾都不和目前數字相同2。第一種情況隻能提供1的貢獻，第二種情況提供2的貢獻。
實作方法很多，就不詳細講實作了（代碼應該還是容易看懂的qwq）。
代碼
//這題如果很難了解可以畫圖看看，就能明白了
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 1e6 + 19;
const ll mod = 1e9 + 7;
queue<P> que;
int main()
{
int n;
cin >> n;
int cur;
int cnt = 1;
cin >> cur;
for(int i = 1; i < n; i++)
{
int x;
cin >> x;
if(x != cur)
{
que.push(P(cur, cnt));//轉化成數字cur有cnt個的形式
cur = x;
cnt = 1;
}
else
{
cnt++;
}
}
que.push(P(cur, cnt));
ll ans = 0;
int flag = 0;
int tmp;
while(!que.empty())
{
P p = que.front();
if(flag)//flag > 0标志着如果我要把現在手上這堆數字分成兩半，有可能出現貢獻隻有1的情況
{
if(p.second > 1)//目前這堆個數超過1
{
if(p.first == tmp)
ans++;
else
ans += 2;
flag = 2;
tmp = p.first;
}
else//為什麼目前這堆個數不超過1也要判斷？因為也會影響到flag的值，這就是我賽場上錯的地方
{
if(p.first != tmp)
{
flag--;
}
else
{
flag = 2;
}
ans++;
}
}
else
{
if(p.second > 1)
{
ans += 2;
flag = 2;
tmp = p.first;
}
else
{
ans += 1;
}
}
que.pop();
}
cout << ans << endl;
return 0;
}
D2 - Painting the Array II
題意
和D1的差別僅在于，D1求最大長度，D2求最短長度。
思路
參考：Submission #107024651 - Codeforces
看了很多人的部落格，做法從貪心到堆優化dp、線段樹dp都有，貪心的實作很多使用的是記錄下一個該數字出現的位置 next[i]
主要思路：（下面将0 1區分開後的兩個數組稱為兩個隊伍）
- 把所有的多個數字都合并成一個（這點應該不用我多說），使得變化後的數組中沒有連續相同的數字；
- 從頭到尾周遊，用set來記錄可能是兩個隊伍末尾的數字。這樣說可能很難了解，那麼我們先分類讨論set如何變化：
- 如果目前數字不能在set中，則加入set；
- 如果目前數字在set中，清空set，将目前位置與目前位置的前一個位置的兩個數組加入set。
顯然，set維護的其實是一連串不同的數字，通過不同的劃分方案，這些數字都有可能成為兩條隊伍的末尾。
周遊過程中一旦出現一個數字，它在set中已經有了對應元素，那麼這兩個相同的數字一定能通過一個劃分方案位置相鄰，完成我們縮短隊伍長度的目的。
在相鄰之後，隊伍末尾就确定下來了，一定是目前數字和上一個數字（可以了解為，把兩個相同數字中間夾着的數字全部移動到另一個隊伍裡去了，那麼最末尾的數字肯定是這個數的上一個數了）。
代碼
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 1e6 + 19;
const ll mod = 1e9 + 7;
int a[N];
vector<int> vec;
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
if(a[i] != a[i - 1])
vec.push_back(a[i]);
}
if(vec.back() != a[n])
vec.push_back(a[n]);
set<int> st;
ll ans = 0;
for(int i = 0; i < vec.size(); i++)
{
if(st.find(vec[i]) != st.end())
{
st.clear();
st.insert(vec[i]);
st.insert(vec[i - 1]);
}
else
{
st.insert(vec[i]);
ans++;
}
}
cout << ans << endl;
return 0;
}
總結
還是心态問題+身體問題，導緻繼續掉分。B卡了之後沒有重新思考是不是從方法上有問題，而是一意孤行認為是資料範圍的問題；D1思路完全正确，卻因為細節敗的很慘。做題的時候就安心做題，是否放棄比賽應該在賽前想好，出錯了應該冷靜思考，而不是一邊想着放棄一邊因為掉分急得無法思考。以後的現場賽更考驗心态呀！要加油了
多多包涵，共同進步
- 因為經過第一步的轉換後，這個單獨的數字一定和它前後都是不同的 ↩︎
- 為什麼不會有都相同的情況？和這段開頭的注釋1一樣 ↩︎
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)