Educational Codeforces Round 154 (Rated for Div. 2)

比赛链接
我都快忘了还有这一场比赛，今天打开cf看见这场比赛正好有时间就补了！！！
2023.9.3也许是出去玩了一下午脑子不够用了？？怎么现在读题都有一点读不懂了！！！
2023.9.4我靠这场我怎么感觉没什么思路呢？？？？

A题 Prime Deletion

题目链接
我们会给你一个1-9的一个序列，要求从中删除一部分数，使得最后的数是素数，最少是个两位数，不行就输出-1

A思路：

其实这个题也是猜测着过去的，数据量不是很大，因为最少是两位数，那么我们就直接按照顺序两两组合在一起在判断一下是不是素数就可以了，最后不行在输出-1.这样确实过了，但是我们证明哈哈哈

A代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool prime(int x){
	if(x==1||x==-0){
		return false;

	}
	if(x==2){
		return true;
	}
	for(int i=2;i<=x/i;i++){
		if(x%i==0){
			return false;
		}
	}
	return true;
}
void solve(){
	string s;
	cin>>s;
	int x=1;

	for(int i=1;i<s.size();i++){
		int y=s[i]-'0';
		x=0;
		x=x*10+y;
		for(int j=i+1;j<s.size();j++){
			int z=s[j]-'0';
			int c=x*10+z;
			if(prime(c)){
				cout<<c<<endl;
				return ;
			}
		}
	}
	cout<<-1<<endl;
	return ;
	
}
int main(){
	int t;
	cin>>t;

	while(t--){
		solve();

	}
	return 0;
}

B. Two Binary Strings

题目链接
给你两个长度相等的字符串a和b，它们都由字符 0 和/或 1 组成；两个字符串都以字符 0 开始，以字符 1 结束。
您可以执行任意次数（可能为零）的以下操作：
选择其中一个字符串和其中两个相等的字符；然后将它们之间的所有字符都变成这些字符。
形式上，您从这两个字符串中选择一个（让所选字符串为s），然后选取两个整数l和r，如1≤l<r≤|s|和sl=sr，然后用sl
替换每个字符si，l<i<r。
例如，如果选择的字符串是 010101，那么只需进行一次操作，就可以将其转换为以下字符串之一：
如果您选择l=1和r=3，则为 000101；如果您选择l=1和r=5，则为 000001；如果您选择l=3和r=5，则为 010001；如果您选择l=4和r=6，则为 010111；如果您选择l=2和r=6，则为 011111；如果您选择l=2和r=4，则为 011101。您必须确定是否有可能通过任意多次应用此操作使给定的字符串相等。
数据满足两个字符串的第一个字符均为 0，最后一个字符均为 1。

B思路：

其实我们怎么读懂题意，但是看了网上的介绍感觉是个dp动态规划问题，（网上也说是一个动规问题哈哈哈），那就好写了，不算是很难，看代码吧。

B代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
	string a,b;
	cin>>a>>b;
	int flag=0;
	int n=a.size();
	std::vector<bool> dp(n+1);
	
	dp[0]=true;
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			if(a[i]==b[i]&&a[j]==b[j]&&a[i]==a[j]&&dp[j]){
				dp[i+1]=true;
			}
		}
	}
	cout<<(dp[n]?"YES":"NO")<<endl;
	return ;

}
int main(){
	int t;
	cin>>t;

	while(t--){
		solve();

	}
	return 0;
}

C. Queries for the Array

题目链接
Monocarp 有一个由整数组成的数组 a。最初，这个数组是空的。
Monocarp 对这个数组进行了三种查询：
选择一个整数，并将其到数组的末尾。每当 Monocarp 执行一次这种类型的查询时，他都会写出个字符 +；
从数组中删除结尾的元素。每次 Monocarp 执行这种类型的查询时，他都会写出一个字符 -。Monocarp 从来没有在一个空数组上执行过这种查询；
检查数组是否以非降序排序，即 a1≤a2≤⋯≤ak，其中 k是当前数组中元素的个数。每个元素少于2
的数组都被认为是排序过的数组。如果在 Monocarp 执行该查询时数组已经排序，他就会写出字符 1。否则，他就写出一个字符 0。
给你一个由 0、1、+ 和 - 组成的 s个字符序列。这些都是 Monocarp 写出的字符，并按照他写出的顺序给出。
你必须检查这个顺序是否合法，即 Monocarp 有可能的某个查询，从而使他写出的字符串正好是 s。

C思路：

关于C题我没有理解什么意思，还望有大佬能帮我555
大佬的思路

C代码：

无，但我还会回来的！！！！

D. Sorting By Multiplication

题目链接
给你一个长度为 n的数组 a，由正整数组成。
你可以在这个数组上执行以下操作任意次数（可能为零）：选择三个整数l、r和x，使得1≤l≤r≤n，将每个ai乘以x，使得l≤i≤r乘以x。注意，你可以选择任何整数作为 x，它不一定是正数。
您必须计算出使数组 a按严格升序排序所需的最少操作次数（即必须满足条件 a1<a2<⋯<an）。

D思路：

因为x是任意的，即可能是正数也可能是负数，一种可能是全是正的，那么答案就是ai>=ai-1的位置的个数，方案就是从前往后没当ai>=ai-1时候都让ai-an乘以一个很大的数字。
但是数字是可以变成负数的，所以就有一种方案是某段前缀是递减的，然后乘上一个负数，这样就变成递增的了，然后剩下的后缀还得是递增的。这样其实也可以避免中间出现大小不一的问题。

D代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;

const int N=2e5+10;
int a[N],b[N],c[N];

void solve(){
	int n;
	cin>>n;
	
	// std::vector<int> v;
	bool flag=true;

	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(i){
			if(a[i]<=a[i-1]){
				flag=false;
			}
		}
	}
	if(flag){
		cout<<0<<endl;
		return ;
	}
	b[1]=0;

	for(int i=2;i<=n;i++){
		b[i]=b[i-1]+(a[i]>=a[i-1]);
	}
	c[n]=0;
	for(int i=n-1;i>=1;i--){
		c[i]=c[i+1]+(a[i]>=a[i+1]);
	}
	int ans=INF;
	// cout<<ans<<endl;
	
	for(int i=1;i<=n;i++){
		ans=min(ans,b[i-1]+c[i]+(i!=1));

	}
	cout<<ans<<endl;
	

}
int main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

E. Non-Intersecting Subpermutations

题目链接
给你两个整数 n和 k。
对于长度为 n的数组，让我们把它的代价定义为该数组的最大连续子数组数：
每个元素最多属于一个子数组；
每个子数组的长度正好是 k；
每个子数组恰好包含一次从 1到 k的整数。
例如，如果n=10、k=3
和数组是[1,2,1,3,2,3,2,3,1,3]，那么它的代价是2，原因如下、我们可以选择从第2个元素到第4个元素的子数组，以及从第7个元素到第9个元素的子数组，而且我们可以证明不可能选择超过2个子数组。
计算由 1到 k个整数组成的所有长度为 n的数组的代价总和，并打印出它的模数 998244353。
2≤k≤n≤4000

E思路：

考虑怎么求一个给定数组的代价。
显然就是贪心的策略，从前到后扫，每次如果找到了一个长度为 k的且满足条件的段就选择。
所以可以想到一个 dp就是设 f[i][j]表示前 i个极长的符合条件的后缀长度为 j的方案数，g[i][j]表示前 i个极长的符合条件的后缀长度为 j的代价之和。
转移的话就是考虑 f[i][j]的第 i+1个填的是什么。
可以填一个这 j个里都没有的数，也就是 f[i][j]×(k−j)→f[i+1][j]
或者可以填一个这 j个里面的数，让极长的符合条件的后缀变短，也就是 f[i][j]→f[i+1]p
对于 g的转移显然是同理的。
要注意的一点就是 f[i][k−1]的转移，显然没有必要转移到 f[i+1][k]可以直接转移到 f[i+1][0]比较方便后面的转移。
以及注意 g[i+1][0]的转移就是：f[i][k−1]+g[i][k−1]→g[i+1][0]。
来自大佬的思路

E代码：

#include <cstdio>
using namespace std;
const int N = 4001, p = 998244353;
 
int n, k, f[N][N], g[N][N];
 
int main(){
    scanf("%d%d", &n, &k);
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = k - 2; j >= 0; j--) {
            f[i - 1][j] = (f[i - 1][j] + f[i - 1][j + 1]) % p;
            g[i - 1][j] = (g[i - 1][j] + g[i - 1][j + 1]) % p;
        }
        for (int j = 1; j < k; j++) {
            f[i][j] = (f[i][j] + f[i - 1][j]) % p;
            g[i][j] = (g[i][j] + g[i - 1][j]) % p;
            f[i][j] = (f[i][j] + 1ll * (k - j + 1) * (f[i - 1][j - 1] - f[i - 1][j])) % p;
            g[i][j] = (g[i][j] + 1ll * (k - j + 1) * (g[i - 1][j - 1] - g[i - 1][j])) % p;
        }
        f[i][0] = f[i - 1][k - 1];
        g[i][0] = (g[i - 1][k - 1] + f[i - 1][k - 1]) % p;
    }
    int ans = 0;
    for (int i = 0; i < k; i++)
        ans = (ans + g[n][i]) % p;
    ans = (ans + p) % p;
    printf("%d", ans);
    return 0;
}

这场比赛补题补的我太难受了，总是犯困，看来有规律的作息了