首页 > 其他分享 >Educational Codeforces Round 154 (Rated for Div. 2) A-D

Educational Codeforces Round 154 (Rated for Div. 2) A-D

时间:2023-09-20 11:45:36浏览次数:37  
标签:Educational Rated 154 int 负数 -- solve maxn 变成

传送门:edu154/div2

A. Prime Deletion

  • 题意:给定一个0-9的排列,要求一个长度>=2的子序列,使得该子序列是质数

  • 做法:考虑31或者13即可。不过当时没有立刻想到,感觉1000以内的质数必有答案,打了暴力。用时就多了点。

Code
#include<bits/stdc++.h>
using namespace std;
int pri[1005],pos[11],cnt;
void solve(){
	string s;
	cin>>s;
	int len=s.length();
	memset(pos,0,sizeof pos);
	for(int i=0;i<len;i++){
		int x=s[i]-'0';
		pos[x]=i;
	}
	for(int i=1;i<=cnt;i++){
		int l=0,x=pri[i];
		if(x<=10) continue;
		int num[11];
		while(x){
			l++;
			num[l]=x%10;
			x/=10;
		}
		reverse(num+1,num+1+l);
		int ok=1;
		for(int i=2;i<=l;i++){
			if(pos[num[i]]>pos[num[i-1]]) continue;
			ok=0;
		}
		if(ok){
			cout<<pri[i]<<endl;
			return;
		}
	}
}
void init(){
	for(int i=2;i<1000;i++){
		int flag=1;
		for(int j=2;j<i;j++)
			if(i%j==0) flag=0;
		if(flag==1){
			cnt++;
			pri[cnt]=i;
		}
	}
}
int main(){
//	freopen("lys.in","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	init();
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

B.Two Binary Strings

  • 题意:给定01串,第一位必然是0,最后一位是1,可以做的操作是每次把两个字符相同(就是都1或者都是0)之间的所有字符都变成一样,问能否使ab串相等

  • 做法:有一个观察:所有可以变成相同的串最后必然会变成00001111串的形式,所以考虑能否变成这样。符合情况当且仅当存在i,使得a[i]=b[i]='1',a[i-1]=b[i-1]='0'

Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int a[maxn],l[maxn],r[maxn];
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],l[i]=r[i]=0;
	
	l[0]=l[n+1]=r[0]=r[n+1]=0;
	for(int i=2;i<=n;i++){
		l[i]=l[i-1]+(a[i]>=a[i-1]);
	}
	
	for(int i=n-1;i>=1;i--){
		r[i]=r[i+1]+(a[i]>=a[i+1]);
	}
	
	int ans=n+1;
	for(int i=1;i<=n;i++){
		ans=min(ans,l[i]+1+r[i+1]);
	}
	ans=min(ans,l[n]+1);
	ans=min(ans,r[1]);
	cout<<ans<<endl;
}
int main(){
	//freopen("lys.in","r",stdin);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

C.Queries for the Array

  • 题意:给定一个固定的操作序列,+表示在数列末尾加一个任意值,-表示删去当前末尾的数,1表示当前的序列是有序的,0表示无须,问是否可能。

  • 做法:最开始的想法是维护一个最近的有序长度,然后详细讨论从状态1变成状态0,从状态0变成状态1可不可行等等,但是想法有些难落地。从维护有序长度出发,考虑干脆维护一个区间好了,那最终思路就出来了。具体的细节看代码

Code
#include<bits/stdc++.h>
using namespace std;
void solve(){
	string s;
	cin>>s;
	int len=s.length();
	int arr_l=0,l=0,r=0;
	for(int i=0;i<len;i++){
		if(s[i]=='+'){
			if(r==arr_l) r++;
			arr_l++;
		    if(!l) l++;
		}
		else if(s[i]=='-'){
			if(arr_l==r){
				r--;
			}
			if(arr_l==l){
				l--;
			}
			arr_l--;
		}
		else if(s[i]=='1'){
			if(arr_l!=r&&arr_l!=1){
			//	cout<<i<<" "<<l<<" "<<r<<" "<<arr_l<<endl;
				cout<<"NO"<<endl;
				return;
			}
			l=r;
		}
		else if(s[i]=='0'){
			if(l>=arr_l) {
			//	cout<<i<<" "<<l<<" "<<r<<" "<<arr_l<<endl;
				cout<<"NO"<<endl;
				return;
			}
			r=min(r,arr_l-1);
			l=min(l,r);
		}
	}
	cout<<"YES"<<endl;
}
int main(){
	//freopen("lys.in","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

D.Sorting By Multiplication

  • 题意:每次可以选择一个区间对区间内每一个数乘上一个整数(可以为负),要求使得数组最后变成严格递增的最少次数

  • 做法:首先考虑如果只用正数去乘的话就很显然。再考虑乘以一个负数。
    这里有几个观察:

    • 1 是负数段一定是连续的,设想如果不连续,中间有一截正数,那最后还是要把中间的正数变成负数,或者把负数再变回去(显然这没有意义),基于这种思想我们就可以把负数段合并了。

    • 2 负数段一定是在前面的部分,也就是说,它是一个前缀。如果不是前缀的话,前面肯定有正数,那么同理,要么把正数变成负数,要么再把负数段变成正数(你干啥子咧)。

    • 3 所以最终的思路是枚举分段点,计算前面的一段变成严格递减的代价,后面一段,然后前后合并,记得+1(把递减的前缀乘以一个负数)

Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int a[maxn],l[maxn],r[maxn];
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],l[i]=r[i]=0;
	
	l[0]=l[n+1]=r[0]=r[n+1]=0;
	for(int i=2;i<=n;i++){
		l[i]=l[i-1]+(a[i]>=a[i-1]);
	}
	
	for(int i=n-1;i>=1;i--){
		r[i]=r[i+1]+(a[i]>=a[i+1]);
	}
	
	int ans=n+1;
	for(int i=1;i<=n;i++){
		ans=min(ans,l[i]+1+r[i+1]);
	}
	ans=min(ans,l[n]+1);
	ans=min(ans,r[1]);
	cout<<ans<<endl;
}
int main(){
	//freopen("lys.in","r",stdin);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}
我想说,在很多时候,要走很多错误的路才能通往正确的那一条。所以现在还在茫然和没有答案,我跟自己说不要害怕。

标签:Educational,Rated,154,int,负数,--,solve,maxn,变成
From: https://www.cnblogs.com/liyishui2003/p/17716945.html

相关文章

  • Educational Codeforces Round 143
    A.TwoTowers#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#definempmake_pairusingpii=pair<int,int>;usingvi=vector<int>;constexprintinf=1e18;voidsolve(){intn,m,cnt=0;stringa,......
  • CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)(A-D)
    CodeTONRound6(Div.1+Div.2,Rated,Prizes!)A.让你找mex为k的n个数,这n个数从0-x,问n个数的和最大值是多少先判断不行的。然后行的肯定有0-k-1,剩下还有就选x就行。查看代码#include<iostream>usingnamespacestd;typedeflonglongll;voidsolve(){ intn,k,x;......
  • Educational Codeforces Round 107
    依然是四题,但是感觉太久没打,好像变得迟钝了。B题大概就是令\[c={10}^k,a=c*3^k,b=c*2^k\]C的话直接暴力维护每种颜色的第一个位置就行,反正只有50个D的话刚开始没什么想法,构造题什么的真的不会啊打表之后发现,对于k,在cost为0的情况下,最多能造出长度为\(k^2+1\)的串,也就是能够......
  • (数据科学学习手札154)geopandas 0.14版本新特性一览
    本文示例代码已上传至我的Github仓库https://github.com/CNFeffery/DataScienceStudyNotes1简介大家好我是费老师,就在前两天,Python生态中的GIS运算神器geopandas发布了其0.14.0新版本,在这次新版本更新中,不仅是新增了许多矢量计算API,还开始为日后正式发布1.0版本做准备,对......
  • CF1542E1 Abnormal Permutation Pairs (easy version) 题解
    CF1542E1AbnormalPermutationPairs(easyversion)题解不会Hardversion对于第一个限制字典序,我们可以考虑枚举前\(i\)位相同,然后考虑后\(n-i\)位。我们只需要保证\(p_{i+1}<q_{i+1}\)即可。我们设\(len=n-i\)。由于前\(i\)位完全相同,所以前\(i\)位内部......
  • Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2) A. Divide
    有一个长为\(n\)的数组,可以执行以下整份操作任意次:选择任意两个数\(a_i,a_j\),满足\(2\mida_i\)\(a_i=\frac{a_i}{2}\)\(a_j=2\cdota_j\)请找到经过任意此操作后的最大\(\sum_{i=1}^{n}a_i\)。在唯一分解定理下讨论两个数\(a_i=2^{\alpha_i}\cdotx,a......
  • Educational Codeforces Round 100
    B.FindTheArray对于条件二来说,1是万金油的存在,所以我们只需要把奇数位置或偶数位置全部变成1即可。因为要求差值小于\(\fracs2\),所以我可以求出奇偶位的和修改较小值即可。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongusingpii=pair<in......
  • mysql错误记录 - 关键字generated
    今天想直接操作flowable的表ACT_GE_BYTEARRAY表字段如下字段名字段含义ID表示唯一标识符的字符串,用于标识每个字节数组。REV_表示字节数组的版本号。NAME_表示字节数组的名称。DEPLOYMENT_ID_表示字节数组所属的部署ID。BYTES_表示存储在数据库中的字......
  • 【题解】Educational Codeforces Round 141(CF1783)
    评价:educationalA.MakeitBeautiful题目描述:如果一个数组中存在一个数恰好等于该数前面所有数之和,那么这个数组就是丑的。如果一个数组不是丑的,就是美的。比如说:数组$[6,3,9,6]$是丑的,因为\(9=6+3\);数组$[5,5,7]$是丑的,因为第二个\(5=5\)。数组$......
  • COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
    Preface这场比赛本来想着周日晚上带着队友打一下的,但当天下午已经VP练了一场了晚上就休息了后面有时间大概花了5~6天的空闲时间才陆陆续续把这场补了,感觉题目还是不错的A.AmbitiousKid签到题,找一个数把它变成\(0\)即可#include<cstdio>#include<iostream>#include<utili......