Codeforces Round #561 (Div. 2)

A. Silent Classroom

time limit per test1 second memory limit per test256 megabytes

There are nn students in the first grade of Nlogonia high school. The principal wishes to split the students into two classrooms (each student must be in exactly one of the classrooms). Two distinct students whose name starts with the same letter will be chatty if they are put in the same classroom (because they must have a lot in common). Let xx be the number of such pairs of students in a split. Pairs (a,b)(a,b) and (b,a)(b,a) are the same and counted only once.

For example, if there are 66 students: “olivia”, “jacob”, “tanya”, “jack”, “oliver” and “jessica”, then:

  • splitting into two classrooms (“jack”, “jacob”, “jessica”, “tanya”) and (“olivia”, “oliver”) will give x=4x=4 (33 chatting pairs in the first classroom, 11 chatting pair in the second classroom),
  • splitting into two classrooms (“jack”, “tanya”, “olivia”) and (“jessica”, “oliver”, “jacob”) will give x=1x=1 (00 chatting pairs in the first classroom, 11 chatting pair in the second classroom).

You are given the list of the nn names. What is the minimum xx we can obtain by splitting the students into classrooms?

Note that it is valid to place all of the students in one of the classrooms, leaving the other one empty.Input

The first line contains a single integer nn (1≤n≤1001≤n≤100) — the number of students.

After this nn lines follow.

The ii-th line contains the name of the ii-th student.

It is guaranteed each name is a string of lowercase English letters of length at most 2020. Note that multiple students may share the same name.Output

The output must consist of a single integer xx — the minimum possible number of chatty pairs.
Examplesinput

4
jorge
jose
oscar
jerry

output

1

input

7
kambei
gorobei
shichiroji
kyuzo
heihachi
katsushiro
kikuchiyo

output

2

input

5
mike
mike
mike
mike
mike

output

4

Note

In the first sample the minimum number of pairs is 11. This can be achieved, for example, by putting everyone except jose in one classroom, and jose in the other, so jorge and jerry form the only chatty pair.

In the second sample the minimum number of pairs is 22. This can be achieved, for example, by putting kambei, gorobei, shichiroji and kyuzo in one room and putting heihachi, katsushiro and kikuchiyo in the other room. In this case the two pairs are kambei and kyuzo, and katsushiro and kikuchiyo.

In the third sample the minimum number of pairs is 44. This can be achieved by placing three of the students named mike in one classroom and the other two students in another classroom. Thus there will be three chatty pairs in one classroom and one chatty pair in the other classroom.

对每个字母算一次贡献

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
const ll INF=0x7fffffff;
int n;
map<char,int> mp;
int main(){
	cin>>n;
	rep(i,1,n){
		string s; cin>>s;
		mp[s[0]]++;
	}
	ll ans=0;
	for(char c='a';c<='z';++c) if(mp[c]){
		int t=mp[c]/2;
		int tt=mp[c]-t;
		ans+=(t-1)*t/2+(tt-1)*tt/2;
	}
	cout<<ans<<endl;
}


B. All the Vowels Please

time limit per test1 second memory limit per test256 megabytes

Tom loves vowels, and he likes long words with many vowels. His favorite words are vowelly words. We say a word of length kk is vowelly if there are positive integers nn and mm such that n⋅m=kn⋅m=k and when the word is written by using nn rows and mm columns (the first row is filled first, then the second and so on, with each row filled from left to right), every vowel of the English alphabet appears at least once in every row and every column.

You are given an integer kk and you must either print a vowelly word of length kk or print −1−1 if no such word exists.

In this problem the vowels of the English alphabet are ‘a’, ‘e’, ‘i’, ‘o’ ,’u’.Input

Input consists of a single line containing the integer kk (1≤k≤1041≤k≤104) — the required length.Output

The output must consist of a single line, consisting of a vowelly word of length kk consisting of lowercase English letters if it exists or −1−1 if it does not.

If there are multiple possible words, you may output any of them.
Examplesinput

7

output

-1

input

36

output

agoeuioaeiruuimaeoieauoweouoiaouimae

Note

In the second example, the word “agoeuioaeiruuimaeoieauoweouoiaouimae” can be arranged into the following 6×66×6 grid:

It is easy to verify that every row and every column contain all the vowels.

判断情况然后构造一下就好了

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
const ll INF=0x7fffffff;
int k;
char c[5]={'a','e','i','o','u'};
int main(){
	cin>>k;
	if(k<25) return puts("-1"),0;
	rep(i,5,k/5) if(k%i==0){
		int w=i,h=k/i;
		rep(j,0,h-1){
			rep(k,0,w-1) printf("%c",c[(j+k)%5]);
		}
		exit(0);
	}
	return puts("-1"),0;
}


C. A Tale of Two Lands

time limit per test1 second memory limit per test256 megabytes

The legend of the foundation of Vectorland talks of two integers 𝑥x and 𝑦y. Centuries ago, the array king placed two markers at points |𝑥||x|and |𝑦||y| on the number line and conquered all the land in between (including the endpoints), which he declared to be Arrayland. Many years later, the vector king placed markers at points |𝑥−𝑦||x−y| and |𝑥+𝑦||x+y| and conquered all the land in between (including the endpoints), which he declared to be Vectorland. He did so in such a way that the land of Arrayland was completely inside (including the endpoints) the land of Vectorland.

Here |𝑧||z| denotes the absolute value of 𝑧z.

Now, Jose is stuck on a question of his history exam: “What are the values of 𝑥x and 𝑦y?” Jose doesn’t know the answer, but he believes he has narrowed the possible answers down to 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an. Now, he wants to know the number of unordered pairs formed by two different elements from these 𝑛n integers such that the legend could be true if 𝑥x and 𝑦y were equal to these two values. Note that it is possible that Jose is wrong, and that no pairs could possibly make the legend true.Input

The first line contains a single integer 𝑛n (2≤𝑛≤2⋅1052≤n≤2⋅105)  — the number of choices.

The second line contains 𝑛n pairwise distinct integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (−109≤𝑎𝑖≤109−109≤ai≤109) — the choices Jose is considering.Output

Print a single integer number — the number of unordered pairs {𝑥,𝑦}{x,y} formed by different numbers from Jose’s choices that could make the legend true.
Examplesinput

3
2 5 -3

output

2

input

2
3 6

output

1

Note

Consider the first sample. For the pair {2,5}{2,5}, the situation looks as follows, with the Arrayland markers at |2|=2|2|=2 and |5|=5|5|=5, while the Vectorland markers are located at |2−5|=3|2−5|=3 and |2+5|=7|2+5|=7:

The legend is not true in this case, because the interval [2,3][2,3] is not conquered by Vectorland. For the pair {5,−3}{5,−3} the situation looks as follows, with Arrayland consisting of the interval [3,5][3,5] and Vectorland consisting of the interval [2,8][2,8]:

As Vectorland completely contains Arrayland, the legend is true. It can also be shown that the legend is true for the pair {2,−3}{2,−3}, for a total of two pairs.

In the second sample, the only pair is {3,6}{3,6}, and the situation looks as follows:

Note that even though Arrayland and Vectorland share 33 as endpoint, we still consider Arrayland to be completely inside of Vectorland.

显然每对数的正负对于答案无影响,所以可以先abs一下
再考虑对于0<=x<=y的情况,显然符合条件的x,y要满足y<=2*x
对于一对符合条件的x,y,它对答案对贡献就是num[x]*num[y]

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
const ll INF=0x7fffffff;
int n,a[maxn],num[maxn],pos[maxn];
vector<int> v;
map<int,int> mp;
int main(){
	cin>>n;
	rep(i,1,n){
		int x;scanf("%d",&x);x=abs(x);mp[x]++; v.pb(x);
	}
	sort(v.begin(),v.end()); auto end=unique(v.begin(),v.end());
	v.erase(end,v.end());
	for(auto i=v.begin();i!=v.end();i++){
		int x=*i,pos=i-v.begin();num[pos+1]=num[pos]+mp[x];
	}
	ll ans=0;
	for(auto i=v.begin();i!=v.end();i++){
		int x=*i,cur_pos=i-v.begin()+1;
		if(mp[x]) ans+=mp[x]*(mp[x]-1)/2;
		int pos=upper_bound(v.begin(),v.end(),2*x)-v.begin();
		ans+=(num[pos]-num[cur_pos])*mp[x];
	}
	printf("%lld\n",ans);
	return 0;
}


D. Cute Sequences

time limit per test1 second memory limit per test256 megabytes

Given a positive integer 𝑚m, we say that a sequence 𝑥1,𝑥2,…,𝑥𝑛x1,x2,…,xn of positive integers is 𝑚m-cute if for every index 𝑖i such that 2≤𝑖≤𝑛2≤i≤n it holds that 𝑥𝑖=𝑥𝑖−1+𝑥𝑖−2+⋯+𝑥1+𝑟𝑖xi=xi−1+xi−2+⋯+x1+ri for some positive integer 𝑟𝑖ri satisfying 1≤𝑟𝑖≤𝑚1≤ri≤m.

You will be given 𝑞q queries consisting of three positive integers 𝑎a, 𝑏b and 𝑚m. For each query you must determine whether or not there exists an 𝑚m-cute sequence whose first term is 𝑎a and whose last term is 𝑏b. If such a sequence exists, you must additionally find an example of it.Input

The first line contains an integer number 𝑞q (1≤𝑞≤1031≤q≤103) — the number of queries.

Each of the following 𝑞q lines contains three integers 𝑎a, 𝑏b, and 𝑚m (1≤𝑎,𝑏,𝑚≤10141≤a,b,m≤1014, 𝑎≤𝑏a≤b), describing a single query.Output

For each query, if no 𝑚m-cute sequence whose first term is 𝑎a and whose last term is 𝑏b exists, print −1−1.

Otherwise print an integer 𝑘k (1≤𝑘≤501≤k≤50), followed by 𝑘k integers 𝑥1,𝑥2,…,𝑥𝑘x1,x2,…,xk (1≤𝑥𝑖≤10141≤xi≤1014). These integers must satisfy 𝑥1=𝑎x1=a, 𝑥𝑘=𝑏xk=b, and that the sequence 𝑥1,𝑥2,…,𝑥𝑘x1,x2,…,xk is 𝑚m-cute.

It can be shown that under the problem constraints, for each query either no 𝑚m-cute sequence exists, or there exists one with at most 5050terms.

If there are multiple possible sequences, you may print any of them.
Exampleinput

2
5 26 2
3 9 1

output

4 5 6 13 26
-1

Note

Consider the sample. In the first query, the sequence 5,6,13,265,6,13,26 is valid since 6=5+16=5+1, 13=6+5+213=6+5+2 and 26=13+6+5+226=13+6+5+2have the bold values all between 11 and 22, so the sequence is 22-cute. Other valid sequences, such as 5,7,13,265,7,13,26 are also accepted.

In the second query, the only possible 11-cute sequence starting at 33 is 3,4,8,16,…3,4,8,16,…, which does not contain 99.

首先,假设序列长度为n,那么显然b要满足 2^(n-2)*(a+1)<=b<=2^(n-2)*(a+m)
那么如果我们能找到这样一个n使得上面对式子成立,则说明有解;
接下来要计算每一个ri
我们把xi中的xi−2+⋯+x1替换成xi−1−ri−1,即xi=2*xi−1+ri−ri−1。
然后我们贪心地想ri最大可以放多少
由于xi-1和ri-1我们之前已经求出,所以现在只要考虑ri确定了之后,如果之后的r全都放1,那么最后一项会不会超过b

那么当ri+1,ri+2⋯rn都取1时,可以得到:
xi+1=2xi-ri+1
xi+2=2xi+1-ri+1+1=2xi+1
xi+3=2xi+2-ri+2+1=2xi+2=4xi+1

xn=2^(n-i-1)*(2xi-ri+1)=2^(n-i-1)*(4xi-1+ri-2ri-1+1)<=b;
所以 ri<=[b/2^(n-i-1)]-4xi-1+2ri-1-1;

所以每次的ri只要取 min(fun(i),m) 就好了
然后考虑到要用到多次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=110;
ll _pow[63],ans[maxn];
ll a,b,m,pre_r;
int len;
int calc_length(){
	for(int i=2;;++i){
		if(_pow[i-2]*(a+1)<=b&&_pow[i-2]*(a+m)>=b) return i;
		if(_pow[i-2]*(a+1)>b) return -1;
	}
	return -1;
}
ll fun(int pos){
	return b/_pow[len-pos-1]-4*ans[pos-1]+2*pre_r-1;
}
int main(){
	int T;cin>>T;
	rep(i,0,60) _pow[i]=pow(2,i);
	while(T--){
		scanf("%lld%lld%lld",&a,&b,&m);
		if(a==b) {printf("1 %lld\n",a);continue;}
		if((len=calc_length())==-1) {puts("-1");continue;}
		printf("%d %lld",len,a);
		ans[1]=a; ans[len]=b; pre_r=a;
		rep(i,2,len-1){
			pre_r=min(fun(i),m);
			ans[i]=a+pre_r;
			a+=ans[i];
			printf(" %lld",ans[i]);
		}
		printf(" %lld\n",b);
	}
}


E. The LCMs Must be Large

time limit per test1 second memory limit per test256 megabytes

Dora the explorer has decided to use her money after several years of juicy royalties to go shopping. What better place to shop than Nlogonia?

There are 𝑛n stores numbered from 11 to 𝑛n in Nlogonia. The 𝑖i-th of these stores offers a positive integer 𝑎𝑖ai.

Each day among the last 𝑚m days Dora bought a single integer from some of the stores. The same day, Swiper the fox bought a single integer from all the stores that Dora did not buy an integer from on that day.

Dora considers Swiper to be her rival, and she considers that she beat Swiper on day 𝑖i if and only if the least common multiple of the numbers she bought on day 𝑖i is strictly greater than the least common multiple of the numbers that Swiper bought on day 𝑖i.

The least common multiple (LCM) of a collection of integers is the smallest positive integer that is divisible by all the integers in the collection.

However, Dora forgot the values of 𝑎𝑖ai. Help Dora find out if there are positive integer values of 𝑎𝑖ai such that she beat Swiper on every day. You don’t need to find what are the possible values of 𝑎𝑖ai though.

Note that it is possible for some values of 𝑎𝑖ai to coincide in a solution.Input

The first line contains integers 𝑚m and 𝑛n (1≤𝑚≤501≤m≤50, 1≤𝑛≤1041≤n≤104) — the number of days and the number of stores.

After this 𝑚m lines follow, the 𝑖i-th line starts with an integer 𝑠𝑖si (1≤𝑠𝑖≤𝑛−11≤si≤n−1), the number of integers Dora bought on day 𝑖i, followed by 𝑠𝑖si distinct integers, the indices of the stores where Dora bought an integer on the 𝑖i-th day. The indices are between 11 and 𝑛n.Output

Output must consist of a single line containing “possible” if there exist positive integers 𝑎𝑖ai such that for each day the least common multiple of the integers bought by Dora is strictly greater than the least common multiple of the integers bought by Swiper on that day. Otherwise, print “impossible”.

Note that you don’t have to restore the integers themselves.
Examplesinput

2 5
3 1 2 3
3 3 4 5

output

possible

input

10 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

output

impossible

Note

In the first sample, a possible choice for the values of the 𝑎𝑖ai is 3,4,3,5,23,4,3,5,2. On the first day, Dora buys the integers 3,43,4 and 33, whose LCM is 1212, while Swiper buys integers 55 and 22, whose LCM is 1010. On the second day, Dora buys 3,53,5 and 22, whose LCM is 3030, and Swiper buys integers 33 and 44, whose LCM is 1212.

读懂题意之后还是挺好做的;

有 n 种石头,每个石头有一个未知的权值,有 m 天,每天一个整数 k 代表这一天拿了 k 个石头,接下来是 k 个整数,代表石头的下标。
问是否存在一种分配权值的方案,使得每一天拿的所有石头权值的 LCM 都严格大于补集中所有石头权值的 LCM 。

反证法,假设某一天拿的集合为Di,补集为Si,另一天的集合为Dj,补集为Sj,且Si严格等于Dj。假设题设成立,那么有:
LCM(Di)>LCM(Si)=LCM(Dj)>LCM(Sj)=LCM(Di)
显然矛盾

所以任意两天所拿的石头都必须有交集。

考虑到m只有50,所以可以暴力做

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
const int maxn=(int)1e4+100;
const int mod=(int)1e9+7;
const ll INF=0x7fffffff;
int vis[55][maxn]={0,};
int main(){
	int n,m; cin>>m>>n;
	rep(i,1,m){
		int num;scanf("%d",&num);
		while(num--){
			int x;scanf("%d",&x);vis[i][x]=1;
		}
	}
	rep(i,1,m) rep(j,1,m){
		int flag=0;
		rep(k,1,n) if(vis[i][k]&&vis[j][k]) {flag=1;break;}
		if(!flag) return puts("impossible"),0;
	}
	return puts("possible"),0;
}


F. Vicky’s Delivery Service

time limit per test4 seconds memory limit per test256 megabytes

In a magical land there are nn cities conveniently numbered 1,2,…,n1,2,…,n. Some pairs of these cities are connected by magical colored roads. Magic is unstable, so at any time, new roads may appear between two cities.

Vicky the witch has been tasked with performing deliveries between some pairs of cities. However, Vicky is a beginner, so she can only complete a delivery if she can move from her starting city to her destination city through a double rainbow. A double rainbow is a sequence of cities c1,c2,…,ckc1,c2,…,ck satisfying the following properties:

  • For each ii with 1≤i≤k−11≤i≤k−1, the cities cici and ci+1ci+1 are connected by a road.
  • For each ii with 1≤i≤k−121≤i≤k−12, the roads connecting c2ic2i with c2i−1c2i−1 and c2i+1c2i+1 have the same color.

For example if k=5k=5, the road between c1c1 and c2c2 must be the same color as the road between c2c2 and c3c3, and the road between c3c3 and c4c4must be the same color as the road between c4c4 and c5c5.

Vicky has a list of events in chronological order, where each event is either a delivery she must perform, or appearance of a new road. Help her determine which of her deliveries she will be able to complete.Input

The first line contains four integers nn, mm, cc, and qq (2≤n≤1052≤n≤105, 1≤m,c,q≤1051≤m,c,q≤105), denoting respectively the number of cities, the number of roads initially present, the number of different colors the roads can take, and the number of events.

Each of the following mm lines contains three integers xx, yy, and zz (1≤x,y≤n1≤x,y≤n, 1≤z≤c1≤z≤c), describing that there initially exists a bidirectional road with color zz between cities xx and yy.

Then qq lines follow, describing the events. Each event is one of the following two types:

  1. + x y z (1≤x,y≤n1≤x,y≤n, 1≤z≤c1≤z≤c), meaning a road with color zz appears between cities xx and yy;
  2. ? x y (1≤x,y≤n1≤x,y≤n), meaning you should determine whether Vicky can make a delivery starting at city xx and ending at city yy. It is guaranteed that x≠yx≠y.

It is guaranteed that at any moment, there is at most one road connecting any pair of cities, and that no road connects a city to itself. It is guaranteed that the input contains at least one event of the second type.Output

For each event of the second type, print a single line containing “Yes” (without quotes) if the delivery can be made, or a single line containing “No” (without quotes) otherwise.
Exampleinput

4 3 2 4
1 2 1
2 3 1
3 4 2
? 1 4
? 4 1
+ 3 1 2
? 4 1

output

Yes
No
Yes

Note

The following picture corresponds to the sample.

For her first delivery, Vicky can use the sequence 1, 2, 3, 4 which is a double rainbow. However, she cannot complete the second delivery, as she can only reach city 33. After adding the road between cities 11 and 33, she can now complete a delivery from city 44 to city 11by using the double rainbow 4, 3, 1.

首先考虑存边,这里我用了 map<int,vector<int>> 存,其实 map<int,int> 完全可以
接下来我们考虑可以把偶数步可以到达的点用并查集合并起来,比如1-2-3中的边颜色都相同,就把1和3合并;

询问时如果可达,那么显然只有两种情况:经过偶数条边或奇数条边;
偶数的话就是判断 find(x)==find(y) 是否成立;
奇数由于最后一条边是什么颜色无所谓,只要求之前的k-1条边满足条件就可以了,所以我们可以再对每个连通块维护一个set,里面存的是当前连通块中的点经过一步可以走到的所有点;那么判断时就看 s[find(x)].count(y)

合并时用到了启发式合并的思想

#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;
int pre[maxn],n,m,c,q,tot[maxn];
map<int,vector<int>> mp[maxn];
set<int> s[maxn];
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){
		if(s[x].size()<s[y].size()) swap(x,y); 
		for(auto u:s[y]) s[x].insert(u);
		pre[y]=x;
	}
}
void add(){
	int x,y,col; scanf("%d%d%d",&x,&y,&col);
	s[find(y)].insert(x); s[find(x)].insert(y);
	mp[x][col].pb(y); join(y,mp[x][col][0]);
	mp[y][col].pb(x); join(x,mp[y][col][0]);
}
int main(){
	scanf("%d%d%d%d",&n,&m,&c,&q);
	init();
	while(m--) add();
	while(q--){
		char op[2]; scanf("%s",op);
		if(op[0]=='?'){
			int x,y;scanf("%d%d",&x,&y);
			printf(find(x)==find(y)||s[find(x)].count(y)?"Yes\n":"No\n");
		}
		else add();
	}
}

发表评论,支持MarkDown语法