Codeworks round 481 (Div. 3) [done]

2022.3.1
Title address :https://codeforces.com/contest/978

A. Remove Duplicates【 simulation 】

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],st[N],n;
set<int>s; 
vector<int>ve;
int main(void)
{
    
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i],s.insert(a[i]);
	cout<<s.size()<<endl;
	for(int i=n-1;i>=0;i--)
	{
    
		if(st[a[i]]) continue;
		ve.push_back(a[i]);
		st[a[i]]++;
	}
	for(int i=ve.size()-1;i>=0;i--) cout<<ve[i]<<" ";
	return 0;
}

B. File Name【 greedy / Double pointer 】

Work out paragraph by paragraph xxx…, Calculate the minimum number of deletions for each segment , Add it up .

#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int main(void)
{
    
	cin>>n>>s;
	if(s.find("xxx")==-1) puts("0");
	else
	{
    
		int cnt=0;
		for(int i=0;i<s.size();i++)
		{
    
			if(s[i]=='x')
			{
    
				int j=i;
				while(j+1<s.size()&&s[j+1]=='x') j++;
				int len=j-i+1;
				if(len>=3) cnt+=len-2;
				i=j;
			}
		}
		cout<<cnt;
	}
	return 0;
}

C. Letters【 The prefix and + Two points 】

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N=1e5*2+10;
LL a[N],b[N],s[N],n,m;
int main(void)
{
    
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];
	for(int i=1;i<=m;i++) 
	{
    
		cin>>b[i];
		int index=lower_bound(s+1,s+n+1,b[i])-s;
		cout<<index<<" "<<b[i]-s[index-1]<<endl;
	}
	return 0;
}

D. Almost Arithmetic Progression【 Violence enumeration 】

Not difficult, but there are many details , Enumerate the first two , The tolerance can be determined .
Then judge , Note that the maximum difference between the original data and the data of the arithmetic sequence is 1.

#include<bits/stdc++.h>
using namespace std;
const int N=1e5*2+10;
typedef long long int LL; 
int dx[3]={
    0,-1,1};
int a[N],n,ans=1e9;
void solve(int x,int sum,int d)
{
    
	int b[N]={
    0};
	b[1]=x;
	for(int i=2;i<n;i++) b[i]=b[i-1]+d;// Construct an array based on prime tolerance 
	for(int i=2;i<n;i++) 
	{
    
		int len=abs(b[i]-a[i]);
		if(len>1) return;// Tolerance greater than 1
		sum+=len;
	} 
	if(sum<=n) ans=min(ans,sum);// The number of steps is less than or equal to n
}
int main(void)
{
    
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	if(n==1){
     puts("0");return 0;}
	for(int i=0;i<3;i++)
	{
    
		for(int j=0;j<3;j++) 
		{
    
			int tempx=a[0]+dx[i];
			int tempy=a[1]+dx[j];
			int d=tempy-tempx;// tolerance 
			solve(tempy,abs(dx[i])+abs(dx[j]),d);//a[1]  They count   tolerance 
		}
	}
	if(ans<=n) cout<<ans;
	else cout<<-1;
	return 0;
}

E. Bus Video System【 thinking greedy 】

Read the same question many times and you will find , The prefix sum is the number of people corresponding to each station .
Let's save ,minv and maxv Obviously, the problem is to shift the graph upward . How many steps can you pan at most to make minv>=0 And maxv<=m.

It is divided into 4 In this case :

• minv>=0,maxv>=0
• minv>=0,maxv<=0( direct pass)
• minv<=0,maxv>=0
• minv<=0,maxv<=0

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],n,m;
int main(void)
{
    
	cin>>n>>m;
	int minv=1e9,maxv=-1e9,sum=0;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<n;i++)
	{
    
		sum+=a[i];
		maxv=max(maxv,sum);
		minv=min(minv,sum);
	}
	if(minv<-m||maxv>m) 
	{
    
		puts("0");
		return 0;
	}
	if(minv>=0&&maxv>=0) cout<<m-maxv+1;
	else if(minv<=0&&maxv>=0)
	{
    
		maxv+=abs(minv);
		if(maxv>m) puts("0");
		else cout<<min(m-abs(minv)+1,m-maxv+1);
	}
	else if(minv<=0&&maxv<=0)
	{
    
		maxv+=abs(minv);
		if(maxv>m) puts("0");
		else cout<<min(m-abs(minv)+1,m-maxv+1);
	}
	return 0;
}

F. Mentors【 Two points 】

#include<bits/stdc++.h>
using namespace std;
const int N=1e5*2+10;
int a[N],b[N],cnt[N],n,m;
int main(void)
{
    
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);
	while(m--)
	{
    
		int s1,s2; cin>>s1>>s2;
		if(a[s1]>a[s2]) cnt[s1]--;// Subtract... From the number of conflicts 
		if(a[s1]<a[s2]) cnt[s2]--;// Subtract... From the number of conflicts 
	}
	for(int i=1;i<=n;i++)
	{
    
		int l=lower_bound(b+1,b+n+1,a[i])-b;// Find greater than or equal to a[i] The subscript 
		if(b[l]>=a[i]) l--;// subtract 
		cnt[i]+=l;
		cout<<cnt[i]<<" ";
	}
	return 0;
}

G. Petya’s Exams【 greedy 】

Sort by end first , In order of starting first .
Then enumerate the number of days , Greedy simulation can .
One thing to note is that the implied message of the title is , It is also common sense that every subject must be examined on the examination day .

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int a[N],n,m,cnt,ans[N];
struct node{
    int st,ed,c,k,id;}Node[N];
bool cmp(node a,node b)
{
    
    if(a.ed==b.ed) return a.st<b.st;
    return a.ed<b.ed;
}
int main(void)
{
    
	cin>>n>>m;
	for(int i=0;i<m;i++) 
	{
    
	    cin>>Node[i].st>>Node[i].ed>>Node[i].c,Node[i].id=i+1;
	}
	sort(Node,Node+m,cmp);
	for(int i=1;i<=n;i++)
	{
    
		for(int j=0;j<m;j++)
		{
    
		    if((Node[j].c==Node[j].k)&&(i==Node[j].ed)) // Enough days to prepare , And it's exam day 
		    {
    
		        ans[i]=m+1,cnt++;
		        break;
		    }
		    if(Node[j].k==Node[j].c) continue;// There are enough days to prepare, but it is not an exam day .
			if(Node[j].st<=i&&i<Node[j].ed)// In the interval 
			{
    
				ans[i]=Node[j].id;
				Node[j].k++;
				break;
			}
		}
	}
	if(cnt==m)// The test is over m door 
	{
    
		for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	}else puts("-1");
	return 0;
}