Educational Codeforces Round 166 (Rated for Div. 2)

A. Verify Password

题目描述

Monocarp is working on his new site, and the current challenge is to make the users pick strong passwords.

Monocarp decided that strong passwords should satisfy the following conditions:

• password should consist only of lowercase Latin letters and digits;
• there should be no digit that comes after a letter (so, after each letter, there is either another letter or the string ends);
• all digits should be sorted in the non-decreasing order;
• all letters should be sorted in the non-decreasing order.

Note that it’s allowed for the password to have only letters or only digits.

Monocarp managed to implement the first condition, but he struggles with the remaining ones. Can you help him to verify the passwords?

分析：

要求数字必须出现在字母的前面，且字母与数字分别要按照升序排列

代码：

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
	int tt;
	cin >> tt;
	while(tt--)
	{
		string a;
		int n;
		cin >> n;
		cin >> a;
		int flag=0,OK=0;
		char flag1='0',flag2='a';
		for(char q:a)
		{
			if(q>='0'&&q<='9') 
			{
				if(flag==1) //如果这个数字出现在字母之后
				{
					cout << "NO" << endl;
					OK=1;
					break;
				}
				if(q>=flag1) //判断是否按照升序排列
				{
					flag1=q;
				}
				else
				{
					cout << "NO" << endl;
					OK=1;
					break;
				}
			}
			else if(q>='a'&&q<='z')
			{
				flag=1;
				if(q>=flag2)
				{
					flag2=q;
				}
				else
				{
					cout << "NO" << endl;
					OK=1;
					break;
				}
			}
		}
		if(!OK) cout << "YES" << endl;
	}
	return 0;
 } 

B. Increase/Decrease/Copy

You are given two integer arrays: array a a a of length n n n and array b b b of length n + 1 n+1 n+1.

You can perform the following operations any number of times in any order:

• choose any element of the array a a a and increase it by 1 1 1;
• choose any element of the array a a a and decrease it by 1 1 1;
• choose any element of the array a a a, copy it and append the copy to the end of the array a a a.

Your task is to calculate the minimum number of aforementioned operations (possibly zero) required to transform the array a a a into the array b b b. It can be shown that under the constraints of the problem, it is always possible.

分析：

要把a数组转换为b数组，要在a中挑选出一个数字复制到末尾，要尽量使复制过去的数字与b[n]相差较小。因为可以按照任意次序进行操作，所以能从a数组中挑选出的数字包括a[i]-b[i]区间中的所有数字。最后操作数再加上a[i]-b[i]的绝对值。

例如：
4
4 2 1 2
2 1 5 2 3

用例3中,a[0]->b[0]，过程为4-1=3，3-1=2，在此过程中出现了数字3也就是b[n]，因此，我们可以直接将3复制到a数组的末尾。

代码：

#include<bits/stdc++.h>
using namespace std;
 
const int N =2*1e5+10;
long long int a[N],b[N];
 
int main()
{
	int tt;
	cin >> tt;
	while(tt--)
	{
		int n;
		cin >> n;
		for(int i=0;i<n;i++) cin >> a[i];
		for(int i=0;i<=n;i++)cin >> b[i];
		long long int ans=1e9;
		for(int i=0;i<n;i++) 
		{
	        ans=min(ans,abs(a[i]-b[n]));
	        ans=min(ans,abs(b[i]-b[n]));
	        if(min(a[i],b[i])<=b[n]&&b[n]<=max(a[i],b[i])) //判断区间中是否有b[n]
	        {
	            ans=0;
	        }
       }
	    for(int i=0;i<n;i++)
	    ans+=abs(a[i]-b[i]);
		cout << ans+1 << endl;
	}
	return 0;
 } 

24/5/31