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:
- + 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;
- ? 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();
}
}
