526互联

Educational Codeforces Round 147(A~E)(补提记录)

发布时间 2023-04-25 20:00:02作者: laniser

Educational Codeforces Round 147(Rated for Div. 2)

A:

题意：

每个问号都能被替换成0~9，求替换每个问号后所能的到的数的数量
注：所得到的序列不能有前导0

思路：先判断第一位是什么，作为特判，为0，则不能得到任何数输出0，为？则答案×9再依次枚举之后的每一个数，若为问号答案*10

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int t;
char s[6];

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>t;
	while(t--)
	{
		int cnt=1;                  //答案初始为1,若无问号和前导0答案即为1

		cin>>s;
		int len=strlen(s);
		if(s[0]=='0') cnt=0;
		else
		{
			for(int i=0;i<len;i++)
				if(s[i]=='?')
					if(i==0) cnt*=9;
					else cnt*=10;
		}

		cout<<cnt<<endl;
	}
	return 0;
}

B：

题意：

当时比赛第一时间想的是DP,想了一会还是想出来力
给你两个序列，第一个是原序列，第二个是操作后的序列，对第一个序列进行操作:选择一段连续的子序列进行升序排列是其成为序列二，求这个选择的最长子序列的区间

思路:枚举两个序列，找到第一个不相同的值，以此为分界线，分别向前和向后判断是否满足为连续不下降序列,求出两端点

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
 
const int N=2e5+10;
int t;
int a[N],s[N];
int f[N];                       //比赛时的数组都没删干净hh
 
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
 
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++) cin>>s[i];
 
		bool flag=true;
		for(int i=1;i<=n;i++)
		{
			if(s[i]!=a[i])
			{
				flag=false;
				int j=i;
				while(j<n&&s[j+1]>=s[j]) j++;
				int k=i;
				while(k>1&&s[k-1]<=s[k]) k--;
				cout<<k<<" "<<j<<endl;
				break;
			}
		}
		if(flag) cout<<"1"<<" "<<n<<endl;
		
	}
 
	return 0;
}

太弱力，后面都是补的题

C

题意:

给定一段由小写字母组成的字串，每次进行一些操作，删除其中的一些字母:不能删除相邻的两个字母。要求操作次数最少的情况下让序列全为同一种字母。

思路:

拿样例模拟后不难发现每次操作最多可以使序列/2,那么可以得知把一段序列全部删除的次数为log2向上取整,不妨
枚举每个字母为删除n次后剩下的字母，我们可以选择不对该字母进行操作，枚举一遍每两个当前字母之间的子序列，并
求出最长的子序列长度，计算要多少次操作，最后所有字母取个min即可
在这里插入图片描述

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
 
const int N=2e5+10;
char s[N];
int t;
 
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
 
	cin>>t;
	while(t--)
	{
		cin>>s;
		int len=strlen(s);
 
		int ans=1e9;
		for(char i='a';i<='z';i++)
		{
			int maxv=0,pre=0;
			bool flag=true;
			for(int j=0;j<len;j++)
				if(s[j]==i)
				{
					flag=false;
					int k=j+1;
					while(s[k]!=s[j]&&k<len) k++;
					k--;
					maxv=max(k-j,maxv);
					j=k;
				}
				else if(flag) pre++;
			maxv=max(pre,maxv);
 
			if(!flag)
			{
				int cnt=0;
				while(maxv)
				{
					maxv>>=1;
					cnt++;
				}
				ans=min(ans,cnt);
			}
		}
		cout<<ans<<endl;
	}
 
	return 0;
}

D:

题意:语文不好描述不清捏(

思路:

先统计一下所有区间是否能满足答案，不能直接输出-1，可以再继续判断
不难发现，当一个区间长度为1时我们要获取这个1就要额外花出两点代价，
若除去该区间的点任然满足条件的话，那可以舍去该点得到更小的操作步数
在这里插入图片描述

一直枚举每个区间，并记录之前所有能涂黑的点的数量和所有区间为1的数量
在这里插入图片描述


#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
 
const int N=2e5+10;
int t,n,k;
 
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
 
	cin>>t;
	while(t--)
	{
		cin>>n>>k;
		int l[N],r[N],len[N];
		for(int i=1;i<=n;i++) cin>>l[i];
		
		int sum=0;
		for(int i=1;i<=n;i++)
		{
			cin>>r[i];
			len[i]=r[i]-l[i]+1;
			sum+=len[i];
		}
 
		if(sum<k)
		{
			cout<<"-1"<<endl;
			continue;
		} 
 
		sum=0;
		int res=0x3f3f3f3f,step=0,one=0;
		for(int i=1;i<=n;i++)
		{
			int need=k-sum;
			if(need<=0) break;
			if(need<=len[i]+one)
			{
				if(need<=len[i]) res=min(res,step+2+need-1+l[i]);
				else res=min(res,step+2+(need-len[i])*2+r[i]);
			}
 
			if(len[i]!=1) step+=2,sum+=len[i];
			else one++;
		}
		cout<<res<<endl; 
	}
 
	return 0;
}

E:

题意:

给定一个括号序列，每次你能删除相邻的一对括号，代价是右括号所有右边的括号数，你可以操作一段连续的括号将他放在任意位置(但要满足常括号序列)，一共操作k次后，你要消除所有的括号使代价最小

思路:

不难发现每个大括号与大括号之间是相互独立的
在这里插入图片描述

存储每个括号我们用栈实现，用堆来维护每次取出的最大值

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
 
const int N=2e5+10;
int t,k;
string s;
int stk[N];
priority_queue<int> q;
 
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
 
	cin>>t;
	while(t--)
	{
		cin>>k>>s;
		int n=s.size(),len=0;
		long long ans=0;
		for(int i=0;i<n;i++)
			if(s[i]=='(')
				stk[++len]=i;
			else
			{
				int pre=stk[len--];
				q.push((i-pre)/2);
				ans+=(i-pre)/2;
			}
		while(q.size()&&k--)
		{
			ans-=q.top();
			q.pop();
		}
		while(q.size()) q.pop();
		cout<<ans<<endl;
	}
 
	return 0;
}