Educational Codeforces Round 143 (Rated for Div. 2)

A. Two Towers

題目大意

有兩個(gè)有紅藍(lán)兩種顏色組成的塔，每次操作可以將其中一個(gè)塔頂?shù)纳珘K移動(dòng)到另一個(gè)塔頂上，問(wèn)能否使兩個(gè)塔沒(méi)有相同顏色相鄰的情況。

題目分析

可以將兩個(gè)塔頭頭銜接看成一座塔，只要相鄰色塊相同的情況出現(xiàn)兩次及以上則不能。

code

#include<bits/stdc++.h>using namespace std;int n, m, k, t;void solve()
{string s1, s2;cin >> n >> m;cin >> s1 >> s2;reverse(s2.begin(), s2.end());s1 = s1 + s2;int cnt = 0;for(int i = 1; i < n + m; i ++)if(s1[i] == s1[i - 1]) cnt ++;if(cnt > 1) puts("NO");else puts("YES");
}int main()
{cin >> t;while(t --) solve();return 0;
}

B. Ideal Point

題目大意

分別給出n個(gè)數(shù)段的最大值與最小值，每次操作可以刪除某個(gè)數(shù)段，問(wèn)能否通過(guò)刪除某些數(shù)段使得k點(diǎn)被覆蓋的次數(shù)最多。

題目分析

當(dāng)存在滿足k為最大值和k為最小值的數(shù)段都存在才可以通過(guò)刪除操作使得k點(diǎn)被覆蓋的次數(shù)最多，否則一定會(huì)有臨近k其他的數(shù)和k被覆蓋的次數(shù)相同。

code

#include<bits/stdc++.h>using namespace std;int n, m, k, t;void solve()
{int l, r;cin >> n >> k;int cnt1 = 0, cnt2 = 0;for(int i = 1; i <= n; i ++){cin >> l >> r;if(l == k) cnt1 ++;if(r == k) cnt2 ++;}if(cnt1 && cnt2)puts("YES");else puts("NO");
}int main()
{cin >> t;while(t --) solve();return 0;
}

C. Tea Tasting

題目大意

n種茶將被n個(gè)品茶人品嘗，a[i]表示某類(lèi)茶準(zhǔn)備了多少，b[i]表示某個(gè)人一次最多可以喝多少。品鑒將分步驟進(jìn)。在第一步中，第i個(gè)品茶員品嘗第i種茶。第i個(gè)品嘗者喝min(ai, bi),然后所有品茶者都轉(zhuǎn)向前一種茶，第一個(gè)人結(jié)束品嘗，以此類(lèi)推。求每人最少喝的茶量。

題目分析

題目中出現(xiàn)最少字眼，我們可以試著往二分的方向上思考。每個(gè)人每次喝茶情況為兩種，喝b[i]的茶或是a[i]剩下的茶，我們可以統(tǒng)計(jì)出喝b[i]的茶的次數(shù)l[i]和另一種情況喝的量r[i]，則此人的最終喝茶量為l[i]*b[i]+r[i]。

用前綴和維護(hù)每人都可以喝夠的情況下，到第幾個(gè)人需要多少茶量c[i]。進(jìn)而可以得到某兩個(gè)人之間需要耗費(fèi)掉多少茶。用二分的方法求出第i輪第一個(gè)需要喝剩茶的人u，則l[i]++，l[u]--。而i與u之間的也可喝掉相應(yīng)的茶，可以最后通過(guò)前綴和得到每人應(yīng)該的l[i]。

為了偷懶用了lower_bund函數(shù)代替了手寫(xiě)二分，對(duì)于其進(jìn)行簡(jiǎn)要介紹：lower_bound(first, las, value)返回的為在[first, last]這個(gè)區(qū)間內(nèi)第一個(gè)大于等于value的值

code

#include<bits/stdc++.h>
#define int long longusing namespace std;const int N = 2e5 + 10;int n, m, k, t;
int a[N], b[N];
int s[N], l[N], r[N];void solve()
{cin >> n;for(int i = 0; i <= n+ 1; i ++) l[i] = r[i] = 0;for(int i = 1; i <= n; i ++) cin >> a[i];for(int i = 1; i <= n; i ++) {cin >> b[i];s[i] = s[i - 1] + b[i];}for(int i = 1; i <= n; i ++){int u = lower_bound(s + 1, s + n + 1, a[i] + s[i - 1]) - s;l[i] ++, l[u] --;r[u] += a[i] - (s[u - 1] - s[i - 1]);}for(int i = 1; i <= n; i ++) l[i] += l[i - 1];for(int i = 1; i <= n; i ++) cout << b[i] * l[i] + r[i] << " ";puts("");
}signed main()
{cin >> t;while(t --) solve();return 0;
}