企业网站建设找智恒网络,个人简历模板免费可编辑,网络直播网站建设,网站搭建吧Educational Codeforces Round 143 (Rated for Div. 2) 文章目录A. Two Towers题目大意题目分析codeB. Ideal Point题目大意题目分析codeC. Tea Tasting题目大意题目分析codeA. Two Towers
题目大意
有两个有红蓝两种颜色组成的塔#xff0c;每次操作可以将其中一个塔顶的色…Educational Codeforces Round 143 (Rated for Div. 2)
文章目录A. Two Towers题目大意题目分析codeB. Ideal Point题目大意题目分析codeC. Tea Tasting题目大意题目分析codeA. Two Towers
题目大意
有两个有红蓝两种颜色组成的塔每次操作可以将其中一个塔顶的色块移动到另一个塔顶上问能否使两个塔没有相同颜色相邻的情况。
题目分析
可以将两个塔头头衔接看成一座塔只要相邻色块相同的情况出现两次及以上则不能。
code
#includebits/stdc.husing 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
#includebits/stdc.husing 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
#includebits/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;
}
