Codeforces Round #529 (Div. 3)

A. Repeating Cipher

time limit per test1 second memory limit per test256 megabytes

Polycarp loves ciphers. He has invented his own cipher called repeating.

Repeating cipher is used for strings. To encrypt the string 𝑠=𝑠1𝑠2…𝑠𝑚s=s1s2…sm (1≤𝑚≤101≤m≤10), Polycarp uses the following algorithm:

  • he writes down 𝑠1s1 ones,
  • he writes down 𝑠2s2 twice,
  • he writes down 𝑠3s3 three times,
  • he writes down 𝑠𝑚sm 𝑚m times.

For example, if 𝑠s=”bab” the process is: “b” →→ “baa” →→ “baabbb”. So the encrypted 𝑠s=”bab” is “baabbb”.

Given string 𝑡t — the result of encryption of some string 𝑠s. Your task is to decrypt it, i. e. find the string 𝑠s.Input

The first line contains integer 𝑛n (1≤𝑛≤551≤n≤55) — the length of the encrypted string. The second line of the input contains 𝑡t — the result of encryption of some string 𝑠s. It contains only lowercase Latin letters. The length of 𝑡t is exactly 𝑛n.

It is guaranteed that the answer to the test exists.Output

Print such string 𝑠s that after encryption it equals 𝑡t.
Examplesinput

6
baabbb

output

bab

input

10
ooopppssss

output

oops

input

1
z

output

z

签到

#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=(1<<16)+100;
const int INF=0x3f3f3f3f;
int main(){
	int n;cin>>n;
	string s;cin>>s;
	string ans="";
	int i=0,st=1;
	while(i<n){
		ans+=s[i];
		i+=st++;
	} cout<<ans;
}

 


B. Array Stabilization

time limit per test1 second memory limit per test256 megabytes

You are given an array 𝑎a consisting of 𝑛n integer numbers.

Let instability of the array be the following value: max𝑖=1𝑛𝑎𝑖−min𝑖=1𝑛𝑎𝑖maxi=1nai−mini=1nai.

You have to remove exactly one element from this array to minimize instability of the resulting (𝑛−1)(n−1)-elements array. Your task is to calculate the minimum possible instability.Input

The first line of the input contains one integer 𝑛n (2≤𝑛≤1052≤n≤105) — the number of elements in the array 𝑎a.

The second line of the input contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤1051≤ai≤105) — elements of the array 𝑎a.Output

Print one integer — the minimum possible instability of the array if you have to remove exactly one element from the array 𝑎a.
Examplesinput

4
1 3 3 7

output

2

input

2
1 100000

output

0

Note

In the first example you can remove 77 then instability of the remaining array will be 3−1=23−1=2.

In the second example you can remove either 11 or 100000100000 then instability of the remaining array will be 100000−100000=0100000−100000=0and 1−1=01−1=0 correspondingly.

sort一下就可以了

#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)1e5+100;
const int INF=0x3f3f3f3f;
int main(){
	int n;cin>>n;
	int a[maxn]={0,};
	rep(i,1,n) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	if(n==2) puts("0");
	else{
		int ans=min(a[n-1]-a[1],a[n]-a[2]);
		cout<<ans<<endl;
	}
}

 


C. Powers Of Two

time limit per test4 seconds memory limit per test256 megabytes

A positive integer 𝑥x is called a power of two if it can be represented as 𝑥=2𝑦x=2y, where 𝑦y is a non-negative integer. So, the powers of two are 1,2,4,8,16,…1,2,4,8,16,….

You are given two positive integers 𝑛n and 𝑘k. Your task is to represent 𝑛n as the sum of exactly 𝑘k powers of two.Input

The only line of the input contains two integers 𝑛n and 𝑘k (1≤𝑛≤1091≤n≤109, 1≤𝑘≤2⋅1051≤k≤2⋅105).Output

If it is impossible to represent 𝑛n as the sum of 𝑘k powers of two, print NO.

Otherwise, print YES, and then print 𝑘k positive integers 𝑏1,𝑏2,…,𝑏𝑘b1,b2,…,bk such that each of 𝑏𝑖bi is a power of two, and ∑𝑖=1𝑘𝑏𝑖=𝑛∑i=1kbi=n. If there are multiple answers, you may print any of them.
Examplesinput

9 4

output

YES
1 2 2 4 

input

8 1

output

YES
8 

input

5 1

output

NO

input

3 7

output

NO

位运算,每次高位向低位移一次,直到sum等于k

#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;
const int INF=0x3f3f3f3f;
int main(){
	int n,k;cin>>n>>k;
	if(k>n) {puts("NO");exit(0);}
	int a[110],pos=0,sum=0;
	int x=n;
	while(x){
		a[++pos]=x&1;
		x>>=1;
		if(a[pos]) sum++;
	}
	while(sum<k){
		if(pos==1) break;
		if(a[pos]){
			a[pos-1]+=2;
			a[pos]--;
		}
		if(!a[pos]) pos--;
		sum++;
	}
	if(sum!=k) {puts("NO");exit(0);}
	puts("YES");
	int t=1;
	rep(i,1,pos){
		rep(j,1,a[i]) printf("%d ",t);
		t<<=1;
	}
}

 


D. Circular Dance

time limit per test3 seconds memory limit per test256 megabytes

There are 𝑛n kids, numbered from 11 to 𝑛n, dancing in a circle around the Christmas tree. Let’s enumerate them in a clockwise direction as 𝑝1p1, 𝑝2p2, …, 𝑝𝑛pn (all these numbers are from 11 to 𝑛n and are distinct, so 𝑝p is a permutation). Let the next kid for a kid 𝑝𝑖pi be kid 𝑝𝑖+1pi+1 if 𝑖<𝑛i<n and 𝑝1p1 otherwise. After the dance, each kid remembered two kids: the next kid (let’s call him 𝑥x) and the next kid for 𝑥x. Each kid told you which kids he/she remembered: the kid 𝑖i remembered kids 𝑎𝑖,1ai,1 and 𝑎𝑖,2ai,2. However, the order of 𝑎𝑖,1ai,1 and 𝑎𝑖,2ai,2can differ from their order in the circle.

Example: 5 kids in a circle, 𝑝=[3,2,4,1,5]p=[3,2,4,1,5] (or any cyclic shift). The information kids remembered is: 𝑎1,1=3a1,1=3, 𝑎1,2=5a1,2=5; 𝑎2,1=1a2,1=1, 𝑎2,2=4a2,2=4; 𝑎3,1=2a3,1=2, 𝑎3,2=4a3,2=4; 𝑎4,1=1a4,1=1, 𝑎4,2=5a4,2=5; 𝑎5,1=2a5,1=2, 𝑎5,2=3a5,2=3.

You have to restore the order of the kids in the circle using this information. If there are several answers, you may print any. It is guaranteed that at least one solution exists.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.Input

The first line of the input contains one integer 𝑛n (3≤𝑛≤2⋅1053≤n≤2⋅105) — the number of the kids.

The next 𝑛n lines contain 22 integers each. The 𝑖i-th line contains two integers 𝑎𝑖,1ai,1 and 𝑎𝑖,2ai,2 (1≤𝑎𝑖,1,𝑎𝑖,2≤𝑛,𝑎𝑖,1≠𝑎𝑖,21≤ai,1,ai,2≤n,ai,1≠ai,2) — the kids the 𝑖i-th kid remembered, given in arbitrary order.Output

Print 𝑛n integers 𝑝1p1, 𝑝2p2, …, 𝑝𝑛pn — permutation of integers from 11 to 𝑛n, which corresponds to the order of kids in the circle. If there are several answers, you may print any (for example, it doesn’t matter which kid is the first in the circle). It is guaranteed that at least one solution exists.
Examplesinput

5
3 5
1 4
2 4
1 5
2 3

output

3 2 4 1 5 

input

3
2 3
3 1
1 2

output

3 1 2 

第一次从1开始选,之后有两种可能a和b,枚举两个可能;
在枚举过程中,已知当前点和上一个点时,可以推出下一个点,那么就可以得出整条链,遇到不能走下去的情况就是一开始选ab时选错了,换一个走就好了

#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;
const int INF=0x3f3f3f3f;
int a[maxn],b[maxn];
int ck(int now,int has){
	if(a[now]==has) return b[now];
	else if(b[now]==has) return a[now];
	else return -1;
}
int main(){
	int n;cin>>n;
	rep(i,1,n) scanf("%d%d",&a[i],&b[i]);
	int flag=0;
	vector<int> ans; ans.pb(1);
	int tem=a[1],pre=1;
	rep(i,1,n){
		ans.pb(tem);
		int pp=pre;
		pre=tem;
		tem=ck(pp,tem);
		if(tem==-1){flag=1;break;}
	}
	if(flag){
		ans.clear();ans.pb(1);
		int tem=b[1],pre=1;
		rep(i,1,n){
			ans.pb(tem);
			int pp=pre;
			pre=tem;
			tem=ck(pp,tem);
			if(tem==-1){flag=1;break;}
		}
	}
	for(int i=0;i<ans.size()-1;++i) printf("%d ",ans[i]);
}

 


E. Almost Regular Bracket Sequence

time limit per test3 seconds memory limit per test256 megabytes

You are given a bracket sequence 𝑠s consisting of 𝑛n opening ‘(‘ and closing ‘)’ brackets.

regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters ‘1’ and ‘+’ between the original characters of the sequence. For example, bracket sequences “()()”, “(())” are regular (the resulting expressions are: “(1)+(1)”, “((1+1)+1)”), and “)(” and “(” are not.

You can change the type of some bracket 𝑠𝑖si. It means that if 𝑠𝑖=si= ‘)’ then you can change it to ‘(‘ and vice versa.

Your task is to calculate the number of positions 𝑖i such that if you change the type of the 𝑖i-th bracket, then the resulting bracket sequence becomes regular.Input

The first line of the input contains one integer 𝑛n (1≤𝑛≤1061≤n≤106) — the length of the bracket sequence.

The second line of the input contains the string 𝑠s consisting of 𝑛n opening ‘(‘ and closing ‘)’ brackets.Output

Print one integer — the number of positions 𝑖i such that if you change the type of the 𝑖i-th bracket, then the resulting bracket sequence becomes regular.
Examplesinput

6
(((())

output

3

input

6
()()()

output

0

input

1
)

output

0

input

8
)))(((((

output

0

枚举每个位置,如果这个位置左边的‘(’和右边的‘)’相差1则有可能实现变化后合法

#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=0x3f3f3f3f;
int main(){
	int n;cin>>n;
	string s;cin>>s;
	s='@'+s+'@';
	int ans=0,tot=0;
	int l[maxn],r[maxn];
	l[0]=r[n+1]=0;
	rep(i,1,n){
		if(s[i]=='(') tot++;
		else tot--;
		if(tot<0||l[i-1]<0) l[i]=-1;
		else l[i]=tot;
	}
	tot=0;
	dep(i,n,1){
		if(s[i]==')') tot++;
		else tot--;
		if(tot<0||r[i+1]<0) r[i]=-1;
		else r[i]=tot;
	}
	rep(i,1,n){
		if(l[i-1]>=0&&r[i+1]>=0){
			int t=l[i-1]-r[i+1];
			if(t==1&&s[i]=='(')  ans++;
			if(t==-1&&s[i]==')') ans++;
		}
	}
	printf("%d\n",ans);
}

 


F. Make It Connected

time limit per test2 seconds memory limit per test256 megabytes

You are given an undirected graph consisting of 𝑛n vertices. A number is written on each vertex; the number on vertex 𝑖i is 𝑎𝑖ai. Initially there are no edges in the graph.

You may add some edges to this graph, but you have to pay for them. The cost of adding an edge between vertices 𝑥x and 𝑦y is 𝑎𝑥+𝑎𝑦ax+ay coins. There are also 𝑚m special offers, each of them is denoted by three numbers 𝑥x, 𝑦y and 𝑤w, and means that you can add an edge connecting vertices 𝑥x and 𝑦y and pay 𝑤w coins for it. You don’t have to use special offers: if there is a pair of vertices 𝑥xand 𝑦y that has a special offer associated with it, you still may connect these two vertices paying 𝑎𝑥+𝑎𝑦ax+ay coins for it.

What is the minimum number of coins you have to spend to make the graph connected? Recall that a graph is connected if it’s possible to get from any vertex to any other vertex using only the edges belonging to this graph.Input

The first line contains two integers 𝑛n and 𝑚m (1≤𝑛≤2⋅1051≤n≤2⋅105, 0≤𝑚≤2⋅1050≤m≤2⋅105) — the number of vertices in the graph and the number of special offers, respectively.

The second line contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤10121≤ai≤1012) — the numbers written on the vertices.

Then 𝑚m lines follow, each containing three integers 𝑥x, 𝑦y and 𝑤w (1≤𝑥,𝑦≤𝑛1≤x,y≤n, 1≤𝑤≤10121≤w≤1012, 𝑥≠𝑦x≠y) denoting a special offer: you may add an edge connecting vertex 𝑥x and vertex 𝑦y, and this edge will cost 𝑤w coins.Output

Print one integer — the minimum number of coins you have to pay to make the graph connected.
Examplesinput

3 2
1 3 3
2 3 5
2 1 1

output

5

input

4 0
1 3 3 7

output

16

input

5 4
1 2 3 4 5
1 2 8
1 3 10
1 4 7
1 5 15

output

18

Note

In the first example it is possible to connect 11 to 22 using special offer 22, and then 11 to 33 without using any offers.

In next two examples the optimal answer may be achieved without using special offers.

并查集裸题,注意开long long

#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;
const ll INF=(ll)1e15;
ll a[maxn],c[maxn],n,num=0;
ll ans=0;
struct node{
	ll u,v,w;
	bool operator <(const node& b) const{return w<b.w;}
}g[maxn<<1];
ll pre[maxn];
ll find(ll x){return x==pre[x]?x:pre[x]=find(pre[x]);}
void join(){
	rep(i,1,num){
		ll x=find(g[i].u);
		ll y=find(g[i].v);
		if(x!=y) pre[x]=y,ans+=g[i].w;
	}
}
int main(){
	int m;cin>>n>>m;
	ll minx=INF,id=0;
	rep(i,1,n){
		pre[i]=i;
		scanf("%lld",&a[i]);
		if(a[i]<minx) minx=a[i],id=i;
	}
	rep(i,1,m){
		ll u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
		w=min(w,a[u]+a[v]);
		g[++num].u=u; g[num].v=v; g[num].w=w;
	}
	rep(i,1,n){
		if(i==id) continue;
		g[++num].u=i; g[num].v=id; g[num].w=a[i]+a[id];
	}
	sort(g+1,g+1+num);
	join(); printf("%lld\n",ans);
}

 

发表评论,支持MarkDown语法