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);
}

 

发表评论,支持MarkDown语法