Educational Codeforces Round 65 (Rated for Div. 2)

手速场,前四题一个小时绝对够写,第五题差一点点,只要优化一个地方就可以过了


A. Telephone Number

time limit per test1 second memory limit per test256 megabytes

outputstandard output

A telephone number is a sequence of exactly 11 digits, where the first digit is 8. For example, the sequence 80011223388 is a telephone number, but the sequences 70011223388 and 80000011223388 are not.

You are given a string ?s of length ?n, consisting of digits.

In one operation you can delete any character from string ?s. For example, it is possible to obtain strings 112, 111 or 121 from string 1121.

You need to determine whether there is such a sequence of operations (possibly empty), after which the string ?s becomes a telephone number.Input

The first line contains one integer ?t (1≤?≤1001≤t≤100) — the number of test cases.

The first line of each test case contains one integer ?n (1≤?≤1001≤n≤100) — the length of string ?s.

The second line of each test case contains the string ?s (|?|=?|s|=n) consisting of digits.Output

For each test print one line.

If there is a sequence of operations, after which ?s becomes a telephone number, print YES.

Otherwise, print NO.
Exampleinput

2
13
7818005553535
11
31415926535

output

YES
NO

Note

In the first test case you need to delete the first and the third digits. Then the string 7818005553535 becomes 88005553535.

签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int main(){
	int T;cin>>T;
	while(T--){
		int n;cin>>n;
		string s;cin>>s;
		if(n<11) puts("NO");
		else{
			int flag=1;
			rep(i,0,n-11) if(s[i]=='8') flag=0;
			if(flag) puts("NO");
			else puts("YES");
		}
	}
}

 


B. Lost Numbers

time limit per test1 second memory limit per test256 megabytes

This is an interactive problem. Remember to flush your output while communicating with the testing program. You may use fflush(stdout) in C++, system.out.flush() in Java, stdout.flush() in Python or flush(output) in Pascal to flush the output. If you use some other programming language, consult its documentation. You may also refer to the guide on interactive problems: https://codeforces.com/blog/entry/45307.

The jury guessed some array ?a consisting of 66 integers. There are 66 special numbers — 44, 88, 1515, 1616, 2323, 4242 — and each of these numbers occurs in ?a exactly once (so, ?a is some permutation of these numbers).

You don't know anything about their order, but you are allowed to ask up to 44 queries. In each query, you may choose two indices ?i and ?j(1≤?,?≤61≤i,j≤6, ?i and ?j are not necessarily distinct), and you will get the value of ??⋅??ai⋅aj in return.

Can you guess the array ?a?

The array ?a is fixed beforehand in each test, the interaction program doesn't try to adapt to your queries.Interaction

Before submitting the answer, you may ask up to 44 queries. To ask a query, print one line in the following format: ?? ?i ?j, where ?i and ?jshould be two integers such that 1≤?,?≤61≤i,j≤6. The line should be ended with a line break character. After submitting a query, flush the output and read the answer to your query — one line containing one integer ??⋅??ai⋅aj. If you submit an incorrect query (or ask more than 44queries), the answer to it will be one string 0. After receiving such an answer, your program should terminate immediately — otherwise you may receive verdict "Runtime error", "Time limit exceeded" or some other verdict instead of "Wrong answer".

To give the answer, your program should print one line !! ?1a1 ?2a2 ?3a3 ?4a4 ?5a5 ?6a6 with a line break in the end. After that, it should flush the output and terminate gracefully.
Exampleinput

16
64
345
672

output

? 1 1
? 2 2
? 3 5
? 4 6
! 4 8 15 16 23 42

Note

If you want to submit a hack for this problem, your test should contain exactly six space-separated integers ?1a1, ?2a2, ..., ?6a6. Each of 66special numbers should occur exactly once in the test. The test should be ended with a line break character.

看起来是交互题但是实际上并不难,先三次询问问出(1,3),(2,4),(2,3),这样就可以确定四个数了,再一次询问问出一个数,现在还有一个数没确定,反正一共就四个数,扫一下就知道了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
#define F first
#define S second
typedef long long ll;
const int maxn=(int)2e5+100;
typedef pair<int,int> pii;
int a[10]={4,8,15,16,23,42};
map<int,pii> mp;
int query(int l,int r){
	printf("? %d %d\n",l,r);
	int ans; cin>>ans;
	return ans;
}
int main(){
	rep(i,0,5) rep(j,i+1,5) mp[a[i]*a[j]]={a[i],a[j]};
	int ans[10][2],flag[110]={0,};
	int q[10];
	q[1]=query(1,1); q[2]=query(2,4); q[3]=query(3,5); q[4]=query(3,4);
	ans[1][0]=sqrt(q[1]);
	rep(i,2,4) ans[i][0]=mp[q[i]].F,ans[i][1]=mp[q[i]].S;
	int aa[10]; aa[1]=ans[1][0];
	rep(i,0,1) rep(j,0,1) if(ans[2][i]==ans[4][j]){
		aa[4]=ans[2][i];
		aa[2]=ans[2][0]*ans[2][1]/aa[4];
		aa[3]=ans[4][0]*ans[4][1]/aa[4];
		aa[5]=ans[3][0]*ans[3][1]/aa[3];
	}
	rep(i,1,5) flag[aa[i]]=1;
	rep(i,0,5) if(!flag[a[i]]) aa[6]=a[i];
	printf("!");
	rep(i,1,6) printf(" %d",aa[i]);
}

 


C. News Distribution

time limit per test2 seconds memory limit per test256 megabytes

In some social network, there are ?n users communicating with each other in ?m groups of friends. Let's analyze the process of distributing some news between users.

Initially, some user ?x receives the news from some source. Then he or she sends the news to his or her friends (two users are friends if there is at least one group such that both of them belong to this group). Friends continue sending the news to their friends, and so on. The process ends when there is no pair of friends such that one of them knows the news, and another one doesn't know.

For each user ?x you have to determine what is the number of users that will know the news if initially only user ?x starts distributing it.Input

The first line contains two integers ?n and ?m (1≤?,?≤5⋅1051≤n,m≤5⋅105) — the number of users and the number of groups of friends, respectively.

Then ?m lines follow, each describing a group of friends. The ?i-th line begins with integer ??ki (0≤??≤?0≤ki≤n) — the number of users in the ?i-th group. Then ??ki distinct integers follow, denoting the users belonging to the ?i-th group.

It is guaranteed that ∑?=1???≤5⋅105∑i=1mki≤5⋅105.Output

Print ?n integers. The ?i-th integer should be equal to the number of users that will know the news if user ?i starts distributing it.
Exampleinput

7 5
3 2 5 4
0
2 1 2
1 1
2 6 7

output

4 4 1 4 4 2 2 

并查集裸题

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)5e5+100;
int pre[maxn],tot[maxn],n,m;
void init(){rep(i,0,n) pre[i]=i,tot[i]=1;}
int find(int x){return x==pre[x]?x:pre[x]=find(pre[x]);}
void join(int x,int y){
	x=find(x);y=find(y);
	if(x!=y){
		pre[x]=y;
		tot[y]+=tot[x];
	}
}
int main(){
	cin>>n>>m;
	init();
	while(m--){
		int num;cin>>num;
		int pre=0;
		while(num--){
			int x;scanf("%d",&x);
			if(!pre) pre=x;
			else join(pre,x);
		}
	}
	rep(i,1,n) printf("%d ",tot[find(i)]);
}

 


D. Bicolored RBS

time limit per test2 seconds memory limit per test256 megabytes

A string is called bracket sequence if it does not contain any characters other than "(" and ")". A bracket sequence is called regular(shortly, RBS) if it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, "", "(())" and "()()" are RBS and ")(" and "(()" are not.

We can see that each opening bracket in RBS is paired with some closing bracket, and, using this fact, we can define nesting depth of the RBS as maximum number of bracket pairs, such that the 22-nd pair lies inside the 11-st one, the 33-rd one — inside the 22-nd one and so on. For example, nesting depth of "" is 00, "()()()" is 11 and "()((())())" is 33.

Now, you are given RBS ?s of even length ?n. You should color each bracket of ?s into one of two colors: red or blue. Bracket sequence ?r, consisting only of red brackets, should be RBS, and bracket sequence, consisting only of blue brackets ?b, should be RBS. Any of them can be empty. You are not allowed to reorder characters in ?s, ?r or ?b. No brackets can be left uncolored.

Among all possible variants you should choose one that minimizes maximum of ?r's and ?b's nesting depth. If there are multiple solutions you can print any of them.Input

The first line contains an even integer ?n (2≤?≤2⋅1052≤n≤2⋅105) — the length of RBS ?s.

The second line contains regular bracket sequence ?s (|?|=?|s|=n, ??∈{si∈{"(", ")"}}).Output

Print single string ?t of length ?n consisting of "0"-s and "1"-s. If ??ti is equal to 0 then character ??si belongs to RBS ?r, otherwise ??si belongs to ?b.
Examplesinput

2
()

output

11

input

4
(())

output

0101

input

10
((()())())

output

0110001111

Note

In the first example one of optimal solutions is ?=s= "()()". ?r is empty and ?=b= "()()". The answer is max(0,1)=1max(0,1)=1.

In the second example it's optimal to make ?=s= "(())(())". ?=?=r=b= "()()" and the answer is 11.

In the third example we can make ?=s= "((()())())((()())())". ?=r= "()()()()" and ?=b= "(()())(()())" and the answer is 22.

贪心染色,最优策略一定是一边放一半的"(",而为了保证")"的数量匹配,每次遇到")"优先放数量多的那一边

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,ans=0;
string s;
int main(){
	cin>>n>>s;
	rep(i,0,n-1){
		if(s[i]=='(') ans++,printf("%d",ans%2);
		else printf("%d",ans%2),ans--;
	}
}

 


E. Range Deleting

time limit per test2 seconds memory limit per test256 megabytes

You are given an array consisting of ?n integers ?1,?2,…,??a1,a2,…,an and an integer ?x. It is guaranteed that for every ?i, 1≤??≤?1≤ai≤x.

Let's denote a function ?(?,?)f(l,r) which erases all values such that ?≤??≤?l≤ai≤r from the array ?a and returns the resulting array. For example, if ?=[4,1,1,4,5,2,4,3]a=[4,1,1,4,5,2,4,3], then ?(2,4)=[1,1,5]f(2,4)=[1,1,5].

Your task is to calculate the number of pairs (?,?)(l,r) such that 1≤?≤?≤?1≤l≤r≤x and ?(?,?)f(l,r) is sorted in non-descending order. Note that the empty array is also considered sorted.Input

The first line contains two integers ?n and ?x (1≤?,?≤1061≤n,x≤106) — the length of array ?a and the upper limit for its elements, respectively.

The second line contains ?n integers ?1,?2,…??a1,a2,…an (1≤??≤?1≤ai≤x).Output

Print the number of pairs 1≤?≤?≤?1≤l≤r≤x such that ?(?,?)f(l,r) is sorted in non-descending order.
Examplesinput

3 3
2 3 1

output

4

input

7 4
1 3 1 2 2 4 3

output

6

Note

In the first test case correct pairs are (1,1)(1,1), (1,2)(1,2), (1,3)(1,3) and (2,3)(2,3).

In the second test case correct pairs are (1,3)(1,3), (1,4)(1,4), (2,3)(2,3), (2,4)(2,4), (3,3)(3,3) and (3,4)(3,4).

双指针+预处理;
这道题的难点在于如何快速判断删除一段区间后的序列是否合法,也就是说:
[1,l-1]和[r+1,x]满足按权值排序后下标单调上升,并且l-1的下标小于r+1;
我们维护三个东西:
posmin[maxn] posmax[maxn]表示每个数下标的最小值和最大值
premax[maxn] sufmin[maxn]表示[1,i]/[i,x]范围内的数出现的下标值的最大值/最小值
precan[maxn] sufcan[maxn]表示[1,i]是否合法,[i,x]是否合法

那么一次预处理就可以在O(1)时间内判断[l,r]区间是否合法;
但是,一开始没想到双指针,n^2暴力判断了一下,果断Tle;

其实可以发现,若f(l,r)合法,则f(l,r+1),f(l,r+2),…,f(l,x)也都合法,那么我们每次确定l,移动r,找到一个合法的就加一次贡献,免去了大量的判断;

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int INF=0x7fffffff;
int n,x,a[maxn];
int posmin[maxn],posmax[maxn]; //每个数下标的最小值和最大值
int premax[maxn],sufmin[maxn]; //每个数从小到大/从大到小最后出现的下标
bool precan[maxn],sufcan[maxn]; //[1,i]是否合法,[i,x]是否合法
bool check(int l,int r){
	if(!precan[l-1]) return 0;
	if(!sufcan[r+1]) return 0;
	if(sufmin[r+1]<premax[l-1]) return 0;
	return 1;
}
int main(){
	cin>>n>>x;
	memset(posmin,0x3f,sizeof(posmin)); 
	sufmin[x+1]=INF; precan[0]=sufcan[x+1]=1;
	rep(i,1,n){
		scanf("%d",&a[i]);
		posmin[a[i]]=min(posmin[a[i]],i);
		posmax[a[i]]=max(posmax[a[i]],i);
	}
	rep(i,1,x) premax[i]=max(premax[i-1],posmax[i]);
	dep(i,x,1) sufmin[i]=min(sufmin[i+1],posmin[i]);
	rep(i,1,x) precan[i]=precan[i-1]&&(premax[i-1]<posmin[i]);
	dep(i,x,1) sufcan[i]=sufcan[i+1]&&(sufmin[i+1]>posmax[i]);
	ll ans=0;
	int l=1,r=1;
	for(;l<=x;++l){
		if(l>r) ++r;
		while(r<x&&!check(l,r)) ++r;
		if(check(l,r)) ans+=x-(r-1);
	}
	printf("%lld\n",ans);
}

 

Subscribe
提醒
0 评论
Inline Feedbacks
View all comments