526互联

[Educational Codeforces Round 147 (Rated for Div. 2)](https://codeforc.es/contest/1821)题解A~D

发布时间 2023-04-21 16:49:26作者: 橘赴亦梦人ω

A:

思路：

首字母如果是0，直接输出0。
如果首字母是?,提供九种方案，之后每一个？提供10种方案。

void solve(){
	string s;
	cin>>s;
	if(s[0]=='0'){
		cout<<"0"<<endl;
		return ;
	}
	int ans=1;
	for(int i=0;i<s.size();i++){
		if(s[i]=='?'){
			if(i==0) ans*=9;
			else ans*=10;
		}
	}
	cout<<ans<<endl;
}

B：

题目：给出两个数组，a和a‘，a'是a中一段子区间进行了排序之后的结果，需要输出这段区间的开始，结束位置，并且，最后输出的位置的包含的区间的长度要尽可能的长。
思路：遍历找到第一个不相等的位置和最后一个不相等的位置，现在的区间一定是答案里面包含的区间，但是可能是可以扩展的，比如在区间左边的数，如果本来就是区间里面的mina小的话，加到区间里面也不影响结果。
同理，区间最右边也是这样。因此判断两下即可。
代码：

void solve(){
	int n; cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	int q,h; 
	q=-1,h=-1;
	for(int i=1;i<=n;i++){
		if(a[i]!=b[i]){
			h=i;
			if(q==-1) q=i;
		}
	}
	while(q>0){
		if(b[q-1]<=b[q]) q--;
		else break;
	}
	if(q==0) q=1;
	while(h<n){
		if(b[h+1]>=b[h]) h++; 
		else break;
	}
	cout<<q<<" "<<h<<"\n";
}

C:

题目：给一个字符串，每次的操作：可以随便删除字母，但是必须保证删除的位置不是相邻的。问最后使得这个字符串里面的字母都相同的最少操作次数。
思路：
做过CF字符串的题目之后，会发现CF里面的经常可以暴力枚举26种情况，而且最后还保证了必须留下来一种字母，那么就只有26种情况。对于每一种情况，需要知道要删除的区间长度，因为字母是随机分布的，所以可能会得到很多个区间长度，只需要记录最大的长度就可以，最大的都可以全部删除的话，其他的当然也是可以的。
枚举26种字母上述的处理之后的答案，记录所有答案的mina输出。

void solve(){
	string s,k;s="a";cin>>k;int n=k.size();s+=k;
	for(int i=1;i<=26;i++){v[i].clear();v[i].push_back(0);}
	for(int i=1;i<=n;i++){
		int num=s[i]-'a'+1;
		v[num].push_back(i);
	}
	for(int i=1;i<=26;i++),v[i].push_back(n+1);
	int mina=0x3f3f3f3f;
	for(int i=1;i<=26;i++){
		int maxa=0;
		int sh=0;
		for(int j=1;j<v[i].size();j++){
			maxa=max(v[i][j]-sh-1,maxa);
			sh=v[i][j];
		}
		mina=min(mina,maxa);
	}
	while(mina>0){
		mina/=2;
		num++;
	}
	cout<<num<<endl;
}

D:

当时写挂了，感觉上个月的后悔贪心白学了。。。。。

题目：
在一个直线上最开始在-0的位置，每一时刻，可以进行三种操作中的一个：往右走一个，按下标记按钮，松开标记按钮。会给定我们可以打标记的区间，问最早在第几秒的时候，标记完k个格子。如果不能标记k个，就输出-1.
思路：
从左往右，用sum记录如果路过的所有格子都打上标记的时候sum是几，如果遍历的时候如果当前sum>k的情况。先以此更新一下答案。

/关于以此的解释：
比如现在在第5个区间，把第五个区间的所有数都打上标记是一定可以满足要求的，这个时候为了找到最小值，也就是为了优化答案，应该找到在哪里的时候可以刚刚好满足要求，找到这个位置之后加上优先队列的个数，也是打过标记的区间的个数的两倍，就可以当做一次答案。/

如果当前的sum后面还有空余，且空余要比经过的区间的最小值还要大，就让sum减去这个最小值，这个区间从优先队列里面弹出。这样可以优化答案。其实并不一定每一次都是可以让答案最小的，只不过如果有更加优化的答案，就一定是这样的。

但是这里有一个优化：如果前面的一段区间长度大于2，这一段区间是完全没有必要在之后被弹出的，因为如果对于一段长度为3的区间我们没有用到，只会少了两部操作，但是后面为了加上这个至少为3的区间，就要多走至少3步。因此，只需要把<=2的区间长度能弹出的弹出即可。

每一次在弹出之前，弹出之后，如果可以更新答案，都要更新一下。这样可以保证一定可以记录到最优的答案。

void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>l[i];
	for(int i=1;i<=n;i++)cin>>r[i];}
	int sum=0;int anss=2e9;
	priority_queue<int,vector<int>,greater<int>>q;
	for(int i=1;i<=n;i++){
		sum+=r[i]-l[i]+1;
		q.push(r[i]-l[i]+1);
		if(sum>=k ){
			while(sum>=k){
				int p=r[i]-(sum-k);
				p+=q.size()*2;
				anss=min(anss,p);
				if(q.top()==1 || q.top()==2){
				sum-=q.top();
				q.pop();
			}
			else break;
			}
		}
	} 
	if(anss==2e9) cout<<"-1"<<endl;
	else cout<<anss<<endl;
}

其实看懂题目之后，很容易就想到了，前面的区间长度为1的区间是有可能优化答案的，长度为2的也是有可能的。本来想着贪心实现，但是因为情况复杂，且代码功底不够深厚，写挂了。

插一嘴，D题，多半是根据JLY的代码写出来的....
int p=r[i]-(sum-k); 蒋老师这一句代码 实在是非常的妙啊。
[希望明天天梯赛可以赢~~~]