Educational Codeforces Round 143 (Rated for Div. 2) A — C

Educational Codeforces Round 143 (Rated for Div. 2)

A. Two Towers

题目大意

有两个有红蓝两种颜色组成的塔，每次操作可以将其中一个塔顶的色块移动到另一个塔顶上，问能否使两个塔没有相同颜色相邻的情况。

题目分析

可以将两个塔头头衔接看成一座塔，只要相邻色块相同的情况出现两次及以上则不能。

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个数段的最大值与最小值，每次操作可以删除某个数段，问能否通过删除某些数段使得k点被覆盖的次数最多。

题目分析

当存在满足k为最大值和k为最小值的数段都存在才可以通过删除操作使得k点被覆盖的次数最多，否则一定会有临近k其他的数和k被覆盖的次数相同。

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个品茶人品尝，a[i]表示某类茶准备了多少，b[i]表示某个人一次最多可以喝多少。品鉴将分步骤进。在第一步中，第i个品茶员品尝第i种茶。第i个品尝者喝min(ai, bi),然后所有品茶者都转向前一种茶，第一个人结束品尝，以此类推。求每人最少喝的茶量。

题目分析

题目中出现最少字眼，我们可以试着往二分的方向上思考。每个人每次喝茶情况为两种，喝b[i]的茶或是a[i]剩下的茶，我们可以统计出喝b[i]的茶的次数l[i]和另一种情况喝的量r[i]，则此人的最终喝茶量为l[i]*b[i]+r[i]。

用前缀和维护每人都可以喝够的情况下，到第几个人需要多少茶量c[i]。进而可以得到某两个人之间需要耗费掉多少茶。用二分的方法求出第i轮第一个需要喝剩茶的人u，则l[i]++，l[u]--。而i与u之间的也可喝掉相应的茶，可以最后通过前缀和得到每人应该的l[i]。

为了偷懒用了lower_bund函数代替了手写二分，对于其进行简要介绍：lower_bound(first, las, value)返回的为在[first, last]这个区间内第一个大于等于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;
}