Educational Codeforces Round 97 (Rated for Div. 2)-部分题解

一场不算太难的 $\text{Edu}$。

---

A - Marketing Scheme

题目翻译

给出 $l , r$ ，判断是否存在一个数 $x$ 使得对于区间 $\lbrack l , r \rbrack$ 中的每一个整数有 $\frac{x}{2} \leq i \bmod x$。

---

分析

其实直接看样例手玩也能找出规律

考虑一下 $x$ 与区间 $\lbrack l , r \rbrack$ 的关系。

• $\frac{x}{2} \leq l$，否则的话 $\lbrack l , \frac{x}{2} \rbrack$ 不满足题意。
• $r < x$，否则的话 $\lbrack x , r \rbrack$ 不满足题意。

综上，若 $l \leq \frac{r}{2}$，则存在，否则不存在。

---

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
 
#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl
 
typedef long long ll;
typedef unsigned long long ull;
 
template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}
 
using namespace std;
 
const int N = 10000 + 5;
const int M = 100000 + 5;
const int HA = 998244353;
 
void solve(){
	ll l , r; 
	read(l) , read(r);
	if(l * 2 <= r) puts("NO");
	else puts("YES");
}
 
int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    int t; read(t);
    while(t --) solve();
 
    return 0;
}

---

B - Reverse Binary Strings

题目翻译

给定一个长度为偶数的 $01$ 串，每次可以选择一个连续子串并将其翻转。

要求最后翻转为一个交替 $01$ 串(即类似于 $010101……$ 或 $101010……$ 的串)，请求出最小的操作次数

---

分析

一次操作的有三种情况：让原本挨在一起的两个 $0$ 与两个 $1$ 不挨在一起，只让原本挨在一起的两个 $0$ 不挨在一起，只让原本挨在一起的两个 $1$ 不挨在一起。

因此答案就是最长的连续全 $0$ 串与连续全 $1$ 串的长度的最大值。

---

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 100000 + 5;
const int HA = 998244353;

char a[M] , b[M];

void solve(){
	int n; read(n);
	scanf("%s" , a + 1);
	int max0 = 0 , max1 = 0 , lst = a[1] , cnt = 0;
	rep(i , 1 , n){
		if(a[i] == '1' && a[i - 1] == '1') max1 ++;
		else if(a[i] == '0' && a[i - 1] == '0') max0 ++;
	}
	printf("%d\n" , max(max0 , max1));
}

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    int t; read(t);
    while(t --) solve();

    return 0;
}

---

C - Chef Monocarp

题目翻译

有一个厨师在 $0$ 时刻把 $n$ 道菜放到了烤箱里，每一个菜品都有一个烘烤时间 $t_i$。

在接下来的每一个时刻里，他可以从烤箱中拿出不超过一个菜品，设他在时间 $T$ 拿出了烘烤时间为 $t_i$ 的菜品，则该菜品的不美味度为 $|T - t_i|$。

厨师不想让所有菜品的不美味度之和太大，所以请你帮他求出所有菜品不美味度之和的最小值。

---

分析

先考虑烘烤时间短的菜品一定是更优的，因此我们先将菜品按照烘烤时间进行排序。

之后考虑 $\text{dp}$。

设 $f[i][j]$ 表示在时间 $i$ 拿出前 $j$ 个菜品的最小不美味度，则有：

$$f[i][j] = min(f[i][j] , f[i][j - 1] + |i - t[j]|)$$

发现 $i$ 这一维完全没什么用，删掉，就成了：

$$f[j] = min(f[j] , f[j - 1] + |i - t[j]|)$$

大力 $\text{dp}$ 即可。

时间复杂度 $O(n^2)$，可以通过本题。

---

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 100000 + 5;
const int HA = 998244353;

int n , a[M] , t[M];

int f[205];

void solve(){
	read(n);
	rep(i , 1 , n){
		read(a[i]);
	}
	clean(f , 0x3f3f3f3f);
	f[0] = 0;
	sort(a + 1 , a + 1 + n);
	rep(i , 1 , 2 * n){
		per(j , n , 1){
			f[j] = min(f[j] , f[j - 1] + abs(a[j] - i));
		}
	}
	printf("%d\n" , f[n]);
}

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    int t; read(t);
    while(t --) solve();

    return 0;
}

---

D - Minimal Height Tree

题意翻译

给你一棵树的 $\text{bfs}$ 序，规定这棵树以 $1$ 为根节点，$\text{bfs}$ 时会优先遍历编号较小的节点。

请求出这棵树的最小可能高度。

---

分析

不难发现，对于某个点后面出现的节点，如果它的编号比前面的节点小，那么就可以将其与前面的节点放在同一层上。

直接贪心即可。

---

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 300000 + 5;
const int HA = 998244353;

int n , a[M] , dep[M];

void bfs(){
	queue<int> q;
	clean(dep , 0);
	
	int cnt = 2;
	q.push(1);
	while(!q.empty()){
		int fro = q.front(); q.pop();
		int lst = cnt;
		if(cnt > n) break;
		while(a[cnt] < a[cnt + 1] && cnt < n){
			cnt ++;
		}
		rep(i , lst , cnt){
			dep[a[i]] = dep[fro] + 1;
			q.push(a[i]);
		}
		cnt ++;
	}
}

void solve(){
	read(n);
	rep(i , 1 , n) read(a[i]);
	int res = 0;
	bfs();
	rep(i , 1 , n) res = max(res , dep[i]);
	printf("%d\n" , res);	
}

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    int t; read(t);
    while(t --) solve();

    return 0;
}

---

E - Make It Increasing

题意翻译

给你一个数列 $a$ 与一个集合 $B$。

对于集合 $B$ 中的任意一个元素 $x$，$a_x$ 的值不可以被修改。除此之外，$a$ 中的元素均可以被修改。

请最小化将 $a$ 序列变为严格递增序列的修改次数，或者判断无解。

---

分析

先考虑什么情况无解：即存在任意一组 $i,j ∈ B , i < j$ 且 $a_i > a_j$。

转换一下，就成了 $i,j ∈ B , i < j , a_j - a_i < j - i$

之后考虑 $k = 0$ 时(即没有修改限制)的情况。若 $k = 0$，则原问题就变成了一个经典的 $\text{dp}$问题。

将原数列变形为 $a_i - i$，之后跑一遍最长不下降子序列，设其长度为 $len$，则最后的答案是 $n - len$，代码如下。

//a 为已知的数列，d[i]为长度为i的最长不下降子序列末尾元素的最小值

for(int i = 1; i <= n; i ++) a[i] -= i;

int cnt = 0;    //cnt 为长度

for(int i = 1; i <= n; i ++){
    if(cnt == 0 || a[i] >= d[cnt]){ 
        d[++ cnt] = a[i];
    }
    else{
        int j = upper_bound(d + 1 , d + 1 + cnt , a[i]) - d; //替换掉第一个比它大的元素
        d[j] = a[i];
    }
}

想想上面的代码在干什么？它会在遍历 $a$ 数组时尽量最小化一个假想的答案序列，以尽量容下一个新的值来增大答案。

在判掉不合法的情况之后，我们已经确保有解，但与之同时我们需要保证不修改不能修改的位置，故我们需要让他们处于这个假想的答案序列中，于是我们可以魔改一下上面的代码：

//lst 上一个维护的不能修改的值在假想答案序列中的位置
//cant[i]  a数组的第i位是否禁止修改

for(int i = 1; i <= n; i ++) a[i] -= i;

int cnt = 0;

for(int i = 1; i <= n; i ++){
    if(cnt == 0 || a[i] > d[cnt]){
        d[++ cnt] = a[i];
        if(cant[i] == 1) lst = cnt; //更新lst
    }
    else{
        int j = upper_bound(d + 1 , d + 1 + cnt , a[i]) - d;
        if(j <= lst) continue;  //如果我们要更改的位置在上一个不能修改的值之前，则不能修改，否则上一个不能修改的位置将不在答案序列中
        d[j] = a[i];
        if(cant[i]) lst = j , cnt = j;  
        //若这一位不能修改，则其答案序列后面的位置都不满足条件，因为它们不能大于这个不能修改的位置，因此对我们要的最长不下降子序列不能产生贡献。
    }
}

(建议配合代码进行理解)。

时间复杂度为 $O(n \log n)$，足以通过本题。

---

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 500000 + 5;
const int HA = 998244353;

int n , k , a[M] , b[M];

int d[M];
int cant[M];

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    read(n) , read(k);
    rep(i , 1 , n){
		read(a[i]);
	}
	rep(i , 1 , k){
		read(b[i]);
		cant[b[i]] = 1;
	}
	sort(b + 1 , b + k + 1);
	rep(i , 2 , k){
		if(a[b[i - 1]] - a[b[i]] > b[i - 1] - b[i]) return puts("-1") , 0;
	}
	rep(i , 1 , n) a[i] -= i;
	int cnt = 0 , lst = 0;
	rep(i , 1 , n){
		if(cnt == 0 || a[i] >= d[cnt]){
			d[++ cnt] = a[i];
			if(cant[i] == 1){
				lst = cnt;
			}
		}
		else{
			int j = upper_bound(d + 1 , d + 1 + cnt , a[i]) - d;
			if(j <= lst) continue;
			d[j] = a[i];
			if(cant[i]) lst = j , cnt = j;
		}
	}
	printf("%d\n" , n - cnt);

    return 0;
}

---

THE END