EducationalCodeforcesRound97(RatedforDiv.2)ABCD

A. Marketing Scheme 

题意：是否存在一个整数a，对于[l, r]中的所有数 i 都有 i % a >= a / 2

思路：只要使得 l % a >= a / 2 即可，最优的情况就是取a = r + 1，这样可以使得 l % a 尽量大

#include
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 7;
int main() {
int t, l, r;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &l, &r);
if(l % (r + 1) >= (r + 2) / 2) printf("YES\n");
else printf("NO\n");
}
return 0;
}


B. Reverse Binary Strings

 题意：给一个01串，一次操作可以将一段连续的字符串（左右）反转，问至少操作几次将原串变为01交替的字符串（010101……或101010……

思路：目标答案是01交替的字符串，现在从原串中寻找有多少连续的01交替子串，两个子串的之间需要进行一次反转操作，由于反转的时候左右两边对称，所以左右两边的不同子串间隔一起反转

#include
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 7;
int main() {
int t, n;
scanf("%d", &t);
string s;
while(t--) {
scanf("%d", &n);
cin >> s;
s[n] = s[0];
int cnt = 0;
for(int i = 1; i <= n; ++i)
if(s[i] == s[i - 1]) cnt++;
printf("%d\n", cnt / 2);
}
return 0;
}


C. Chef Monocarp

 题意：

现在锅里有 n 个菜，给出每个菜的最优出锅的时间 t[i]，如果一个菜从时刻 a 出锅，那么会花费 |a - t[i]|，问把 n 个菜全都拿出来的最小花费

思路：

由于t[i] <= n，2n分钟内一定可以拿完

 题意：给出一颗树的bfs序，已知父节点相同的结点在bfs序中升序排列，问这个树的最小高度

思路：找连续上升子序列，每次把一个连续上升的子序列全都连当前最底层的一个点，样例解释：

5 1 2 5 4 3答案是2，长这样：

#include
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 7;
int a[N];
int main() {
int t, n;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int ans = 0, pre = 1, cnt = 0, now = 0;
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
if(i == 1) continue;
if(a[i] > a[i - 1]) cnt++;
else {
now++;
if(now == pre) {
ans++;
pre = cnt;
now = 0;
}
}
}
printf("%d\n", ans + 1);
}
return 0;
}