Educational Codeforces Round 154 (Rated for Div. 2)

爱被打了一巴掌 2024-03-26 22:33 105阅读 0赞

###  ###

[Dashboard - Educational Codeforces Round 154 (Rated for Div. 2) - Codeforces![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://codeforces.com/contest/1861][Dashboard - Educational Codeforces Round 154 _Rated for Div. 2_ - Codeforces_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_codeforces.com_contest_1861]

### B. Two Binary Strings ###

fen![751293ddfa174b8ebdcba7a58c64cc29.png][]

#### 分析： ####

由于每一串数字只由0与1组成，且开头为0，结尾为1，所以一定可以将两个串变为逐渐由0变为1的串000...111（类似这样），故只要向下两串同一个位置为0，且下一个位置同为1则前半部分全变为0，后半部分全变为1

#### 代码： ####

#include<bits/stdc++.h>
    using namespace std;
    string s1, s2;
    int t;
    int main()
    {
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	cin >> t;
    	while(t --)
    	{
    		int flag = 0;
    		cin >> s1 >> s2;
    		int n = s1.size();
    		for(int i = 0; i < n - 1; i ++)
    		{
    			if(s1[i] == '0' && s1[i + 1] == '1' && s2[i] == '0' && s2[i + 1] == '1')
    			{
    				cout << "YES" << '\n';
    				flag = 1;
    				break;
    			}
    		}
    		if(!flag)cout << "NO" << '\n';
    	}	
    	return 0;
    }

### C. Queries for the Array ###

![ec45d53c16af45a2b6a7522526d5b3c8.png][]

#### 分析： ####

youxu:表示前youxu个数满足递增条件（取最大）（有序个数的最大长度）

wuxu:表示前wuxu个数不满足递增条件（取最小）（无序个数的最小长度）

**可以观察到只要有一个不符合递增后面全部都不递增，故找出最早的那一个不满足递增的**

非法情况：

1.当s\[i\] == '0'

当cnt < 2时，说明当前数组一定有序，如果此时s\[i\] == ’0‘，则非法

当s\[i\] == '0' 则说明此时这部分数为无序，如果有序的长度大于此时cnt这个(无序)的长度则不成立

2.当s\[i\] == '1'

当s\[i\] == '1' 则说明此时这部分为有序，如果无序的长度小于当前这部分有序的长度则不成立（因为前部分已为无序，正如黑体部分所说）

注：在s\[i\] == '-'时，如果cnt减到比无序的长度还小，因为无法确定无序的长度少一个数是否还为无序，故将其直接设置为未知的3e5

#### 代码： ####

#include<bits/stdc++.h>
    using namespace std;
    int t, cnt, youxu, wuxu;
    string s;
    void solve()
    {
    	cnt = 0;
    	youxu = 0;
    	wuxu = 3e5;
    	cin >> s;
    	for(int i = 0; i < s.size(); i ++)
    	{
    		if(s[i] == '+')cnt ++;
    		if(s[i] == '-')
    		{
    			cnt --;
    			youxu = min(cnt, youxu);
    			if(wuxu > cnt)wuxu = 3e5;//由于此时为'-'并不能确定无序数组减完之后任为无序，故直接将无序数组变为无穷 
    		} 
    		if(s[i] == '0')//无序 
    		{
    			if(youxu >= cnt || cnt < 2)
    			{
    				cout << "NO" << '\n';
    				return;
    			} 
    			wuxu = min(wuxu, cnt);
    		} 
    		if(s[i] == '1')
    		{
    			if(wuxu <= cnt)
    			{
    				cout << "NO" << '\n';
    				return;
    			}
    			youxu = max(youxu, cnt);
    		}
    	}
    	cout << "YES" << '\n';
    	return;
    }
    int main()
    {
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	cin >> t;
    	while(t --)
    	{
    		solve();
    	}
    	return 0;
    }

### D. Sorting By Multiplication ###

#### 分析： ####

一个为降序的序列无论这一段如何增大，这一段始终未降序，只能一个一个的去乘，但发现如果一次乘-1，就可以将其翻转这样就变成升序，此时再将其抬高到合适位置（如果需要抬高的话有‘+1’操作，符合就抬高）

b数组可以理解为如果不是升序排列需要一个值一个值翻转的最大操作步数，可以对其进行简化，由于a数组是从前往后进行循环的可以将b数组从后往前进行循环由此得知枚举a是b还需进行多少步得到答案，res记录整体向上的条数，由于不可以重复也不可以低，故if(a\[i\] >= shang)res ++;代码中+1为翻转操作。

![c27683248eb04dd6b880bc88f3dfa5ac.jpeg][]

#### 代码： ####

#include<bits/stdc++.h>
    using namespace std;
    const int N = 2e5 + 10; 
    int n, t, a[N], b[N];
    void solve()
    {
    	memset(b, 0, sizeof b);
    	cin >> n;
    	for(int i = 1; i <= n; i ++)
    	{
    		cin >> a[i];
    	}
    	for(int i = n - 1; i >= 1; i --)
    	{
    		if(a[i] >= a[i + 1])b[i] = b[i + 1] + 1;
    		else b[i] = b[i + 1];
    	}
    	int ans = b[1];
    	int res = 0, shang = 1e9 + 1;
    	for(int i = 1; i <= n; i ++)
    	{
    		if(a[i] >= shang)res ++;//此处实际上是需要翻转的，向上的，如果刚开始为升序其实也因为太大不会到ans; 
    		shang = a[i];
    		ans = min(ans, res + 1 + b[i + 1]);//1是整体反转，res为需要翻转时无法衔接（需要改变大小的递减数列、个数） 
    	}
    	cout << ans << '\n';
    }
    int main()
    {
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	cin >> t;
    	while(t --)
    	{
    		solve();
    	}
    	return 0;
    }

[icon-default.png_t_N7T8]: https://csdnimg.cn/release/blog_editor_html/release2.3.6/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N7T8
[Dashboard - Educational Codeforces Round 154 _Rated for Div. 2_ - Codeforces_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_codeforces.com_contest_1861]: https://codeforces.com/contest/1861
[751293ddfa174b8ebdcba7a58c64cc29.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/46b9bfeb44a24d8a946bc492148d98bc.png
[ec45d53c16af45a2b6a7522526d5b3c8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/7827f8414b2e4033882f17d8da8f5e87.png
[c27683248eb04dd6b880bc88f3dfa5ac.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/d73ac33044494643ad0cf3d076d49b0f.png