【A. Diverse Strings】
A string is called diverse if it contains consecutive (adjacent) letters of the Latin alphabet and each letter occurs exactly once. For example, the following strings are diverse: "fced", "xyz", "r" and "dabcef". The following string are not diverse: "az", "aa", "bad" and "babc". Note that the letters 'a' and 'z' are not adjacent.Formally, consider positions of all letters in the string in the alphabet. These positions should form contiguous segment, i.e. they should come one by one without any gaps. And all letters in the string should be distinct (duplicates are not allowed).You are given a sequence of strings. For each string, if it is diverse, print "Yes". Otherwise, print "No".
【Input】
The first line contains integer n (1≤n≤100), denoting the number of strings to process. The following n lines contains strings, one string per line. Each string contains only lowercase Latin letters, its length is between 1 and 100, inclusive.
【Output】
Print n lines, one line per a string in the input. The line should contain "Yes" if the corresponding string is diverse and "No" if the corresponding string is not diverse. You can print each letter in any case (upper or lower). For example, "YeS", "no" and "yES" are all acceptable.
【题目大意】
一个字符串能称之为“Diverse”的是指其包含的字符在字母表中是连续的一段，比如fced是满足的字符串，因为包含的字符为 c,d,e,f 且在字母表中连续。但是aa,az,bad都不是“Diverse”的因为aa包含重读的字符串，a,z认为是不相邻的，bad在字母表中不是连续的一段（缺c），现在给出若干字符串，判断是否是“Diverse“.
int main(){
int n;cin>>n;
char s[1000];
while(n--){
cin>>s;
int use[27];int l=strlen(s);
memset(use,0,sizeof(use));
if(l>26)printf("No\n");
else{
int i;
for(i=0;i
use[s[i]-'a']++;
if(use[s[i]-'a']>1) { printf("No\n"); break;}
}
if(i==l){
int ni=0,nj=0;
for(int i=0;i<=25;i++){
if(use[i]>0 && use[i+1]>0 ) ni++;
if(use[i]>0 && use[i+1]==0) nj++;
}
if(ni==l-1&&nj==1) printf("Yes\n");
else printf("No\n");
}}}
return 0;
}
【B. Parity Alternated Deletions】
Polycarp has an array a consisting of n integers. He wants to play a game with this array. The game consists of several moves. On the first move he chooses any element and deletes it (after the first move the array contains n−1 elements). For each of the next moves he chooses any element with the only restriction: its parity should differ from the parity of the element deleted on the previous move. In other words, he alternates parities (even-odd-even-odd-... or odd-even-odd-even-...) of the removed elements. Polycarp stops if he can't make a move. Formally: If it is the first move, he chooses any element and deletes it; If it is the second or any next move: if the last deleted element was odd, Polycarp chooses any even element and deletes it; if the last deleted element was even, Polycarp chooses any odd element and deletes it. If after some move Polycarp cannot make a move, the game ends. Polycarp's goal is to minimize the sum of non-deleted elements of the array after end of the game. If Polycarp can delete the whole array, then the sum of non-deleted elements is zero. Help Polycarp find this value.
【Input】
The first line of the input contains one integer n (1≤n≤2000) — the number of elements of a. The second line of the input contains n integers a1,a2,…,an (0≤ai≤10^6)
【Output】
Print one integer — the minimum possible sum of non-deleted elements of the array after end of the game.
【题目大意】
Polycarp有包含n个整数的数组a，进行如下操作。第一步选取任意一个元素删除，这样数组a还剩n-1个元素。接下来的每一轮，Polycarp都会删除一个元素，且删除的元素和上一个删除的元素奇偶性不同。如果没有可删除的元素就停止。Polycarp的目标是最小化未被删除的元素和，输出这个答案。如果元素都被删除则输出为0。
【思路】
读入的数据按奇偶性分别保存到odd和even数组中，设分别有Lo和Le个元素。若abs（Lo-Le）≤1则必能全部删除完，答案是0。否则选取元素多的那个数组中统计最小的若干项的和即可。
int even[3000]={0},odd[3000]={0};
int main(){
int n,ans=0,tp;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&tp);
if(tp%2==1) odd[++odd[0]]=tp;
else even[++even[0]]=tp;
}
if(abs(even[0]-odd[0])<=1) cout<<0;
else{
if(odd[0]>even[0]){
sort(odd+1,odd+odd[0]+1);
for(int i=1;i<=odd[0]-even[0]-1;i++) ans+=odd[i];
cout<<ans;
}
else{
sort(even+1,even+even[0]+1);
for(int i=1;i<=even[0]-odd[0]-1;i++) ans+=even[i];
cout<<ans;
}
}
return 0;
}
【C. Two Shuffled Sequences】
Two integer sequences existed initially — one of them was strictly increasing, and the other one was strictly decreasing. Strictly increasing sequence is a sequence of integers [x1y2>>yl]. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing. They were merged into one sequence a. After that sequence a got shuffled. For example, some of the possible resulting sequences a for an increasing sequence [1,3,4] and a decreasing sequence [10,4,2] are sequences [1,2,3,4,4,10] or [4,2,1,10,4,3] This shuffled sequence a is given in the input. Your task is to find any two suitable initial sequences. One of them should be strictly increasing and the other one — strictly decreasing. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing. If there is a contradiction in the input and it is impossible to split the given sequence a to increasing and decreasing sequences, print "NO".
【Input】
The first line of the input contains one integer n (1≤n≤2⋅10^5) — the number of elements in a. The second line of the input contains n integers a1,a2,…,an (0≤ai≤2⋅10^5), where ai is the i-th element of a .
【Output】
If there is a contradiction in the input and it is impossible to split the given sequence a to increasing and decreasing sequences, print "NO" in the first line. Otherwise print "YES" in the first line and any two suitable sequences. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing. In the second line print ni — the number of elements in the strictly increasing sequence. Ni can be zero, in this case the increasing sequence is empty. In the third line print ni integers inc1,inc2,…,incni in the increasing order of its values (inc1— the number of elements in the strictly decreasing sequence. Nd can be zero, in this case the decreasing sequence is empty. In the fifth line print nd integers dec1,dec2,…,decnd in the decreasing order of its values (dec1>dec2>>decnd) — the strictly decreasing sequence itself. You can keep this line empty if nd=0 (or just print the empty line). Ni + nd should be equal to n and the union of printed sequences should be a permutation of the given sequence (in case of "YES" answer).
【题目大意】
两个序列，一个序列严格递增，另一个严格递减。认为空序列同时是严格递增 与 严格递减的。现在两个序列随机混合打乱，构成新序列。现在给出新序列，问能否拆成一个严格递增和一个严格递减序列？是输出方案，否输出NO。存在多解输出其中一个即可。
【思路】
由于严格递增递减，则同一个序列中不能出现相同元素，故如果新序列中某个元素出现超过2次则不可能还原，否则一定能还原。读入的数据先排序，由于只用输出一组解，故可以优先考虑放在递增序列中，如果元素相同的就放在递减序列中。由于一开始排序过了，序列添加完毕后也一定是有序的。输出即可。
int L[201000],R[200100];
int buk[201000];
int main(){
int n,tp,mini=2147483647,maxi=-1;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&tp); buk[tp]++;
maxi=max(tp,maxi); mini=min(mini,tp);
if(buk[tp]>2) {cout<<"NO";return 0;}
}
for(int i=mini;i<=maxi;i++){
if(buk[i]>0) L[++L[0]]=i;
if(buk[i]==2) R[++R[0]]=i;
}
cout<<"YES"<<endl;
printf("%d\n",L[0]); for(int i=1;i<=L[0];i++) printf("%d ",L[i]);
printf("\n%d\n",R[0]); for(int i=R[0];i>=1;i--) printf("%d ",R[i]);
return 0;
}
【D. Equalize Them All】
You are given an array a consisting of n integers. You can perform the following operations arbitrary number of times (possibly, zero): Choose a pair of indices (i, j) such that |I −j|=1 (indices i and j are adjacent) and set ai:=ai+|ai−aj| ; Choose a pair of indices (i, j) such that |i−j|=1 (indices i and j are adjacent) and set ai:=ai+|ai−aj| Your task is to find the minimum number of operations required to obtain the array of equal elements and print the order of operations to do it. It is guaranteed that you always can obtain the array of equal elements using such operations. Note that after each operation each element of the current array should not exceed 10^18 by absolute value.
【Input】
The first line of the input contains one integer n (1≤n≤2⋅10^5) — the number of elements in a. The second line of the input contains n integers a1, a2, … , an (0≤ai≤2⋅10^5), where ai is the i-th element of a .
【Output】
In the first line print one integer k — the minimum number of operations required to obtain the array of equal elements. In the next k lines print operations itself. The p-th operation should be printed as a triple of integers (tp,ip,jp), where tp is either 1 or 2 (1 means that you perform the operation of the first type, and 2 means that you perform the operation of the second type), and ip and jp are indices of adjacent elements of the array such that 1≤ip,jp≤n, |ip−jp|=1.
【题目大意】
N个整数的数组a，对于第i个元素，它可以有几种方法进行改变。设它相邻的为j，即abs(i-j）==1，可以做如下2种变化: ai:=ai+|ai−aj| 或ai:=ai+|ai−aj|.易证这种操作进行若干次后必可以使得所有元素都相等。现在求最小变化次数使得所有数都相等的方案，可能有多种答案，输出一个即可。
【分析】
所谓的变化，其实就是i位置的元素可以用相邻位置的元素进行覆盖。假设第i个元素想变成第k个元素，（如果i到k之间不存在和k相等的元素），则只要k-i步就可以使得从i到k都等于k。最少次数一定是每一步都能将一个不同于目标元素的元素变为相同的。由此看出贪心。先挑选出出现最多次数的元素，这些元素不用变化。紧接着是与这些元素相邻的元素（距离为1），进行变化。紧接着是据离为2的，一直到全部元素都相同。
先读入数据保存在ini[i]数组中，num[k]表示值为k的元素个数。值为Maxp的元素个数最多。L[i]表示在第i个元素左边 【距离i最近的且值为Maxp】的元素的距离。R[i]表示在第i个元素右边【距离i最近的且值为Maxp 】的元素的距离。定义一个元素的距离d=min(L[i],R[i]).dis[i]表示d==i的元素下标。序列肯定从靠近目标值的元素开始向两边扩散，故顺序是按照dis下标从小到大输出。
int num[201000],ini[201000];
vectordis[201000];
int main(){
int n;
scanf("%d",&n);int maxp=0;
for(int i=1;i<=n;i++){
scanf("%d",&ini[i]);
num[ini[i]]++;
if(num[ini[i]]>num[maxp]) maxp=ini[i];
}
int L[201000]={0},R[201000]={0};L[0]=R[n+1]=999999;
for(int i=1;i<=n;i++){ L[i]=L[i-1]+1; if(ini[i]==maxp) L[i]=0;}
for(int i=n;i>=1;i--){ R[i]=R[i+1]+1; if(ini[i]==maxp) R[i]=0;}
int ans=0;
for(int i=1;i<=n;i++) if(L[i]*R[i]!=0) {dis[min(L[i],R[i])].push_back(i); ans++;}
printf("%d\n",ans);
for(int i=1;i<=n;i++){
int l=dis[i].size();
for(int j=0;j
int id=dis[i][j];
if(ini[id]
if(L[id]==i) printf("%d %d\n",id,id-1);
else printf("%d %d\n",id,id+1);
}
}
return 0;
}
【E. Median String】
You are given two strings s and t, both consisting of exactly k lowercase Latin letters, s is lexicographically less than t. Let's consider list of all strings consisting of exactly k lowercase Latin letters, lexicographically not less than s and not greater than t (including s and t) in lexicographical order. For example, for k=2, s="az" and t= "bf" the list will be ["az", "ba", "bb", "bc", "bd", "be", "bf"]. Your task is to print the median (the middle element) of this list. For the example above this will be "bc". It is guaranteed that there is an odd number of strings lexicographically not less than s and not greater than t.
【Input】
The first line of the input contains one integer k (1≤k≤2⋅10^5) — the length of strings. The second line of the input contains one string s consisting of exactly k lowercase Latin letters. The third line of the input contains one string t consisting of exactly k lowercase Latin letters.
It is guaranteed that s is lexicographically less than t. It is guaranteed that there is an odd number of strings lexicographically not less than s and not greater than t.
【Output】
Print one string consisting exactly of k lowercase Latin letters — the median (the middle element) of list of strings of length k lexicographically not less than s and not greater than t.
【题目大意】
给定两个等长的字符串s，t且字典序s小于t，由字典序处于s和t之间且与二者等长的字符串构成了字符串序列，。输出此字符串序列中的中间的那个字符串。例如s=”az”,t=”bf”,则s,t所确定的字符串序列为["az","ba","bb","bc","bd", "be","bf"],处于中间的是”bc”.输入保证s和t所确定的字符串序列里有奇数个字符串。
【分析】
如果某个国家的字母表只有10个字母且写作0~9那么从 0913的确定的字典序的字符串序列是{09,10,11,12,13}，输出11.而11=（09+13）/2.同理，假设az表示0~26,每个字符串都是26进制数，那么（s+t）/2也就是我们的答案。
读入的字符串保存在s,t中，先将az转换成025，tp[i]表示第i位的最终结果。这样对于s[0…Ls-1]我们可以表示成S026^(Ls-1)+S126(Ls-2)+…+SLs-1*26(0),同理对于t也可写成类似26进制数的形式。那么(s+t)/2的每一位结果保存在tp[i]中，有 tp[i]=(s[i]+t[i])/2 如果出现了奇数，则保留整数部分，并将13加到下一位去(26进制下“13”就相当于十进制的“5”)。在从低位往高位进位，大于26的向前进1.题目保证是奇数，而且不会进位使得位数增加。最后在转化成字符就可以。
int main(){
int n;
char s1[210000],s2[210000];
cin>>n>>s1+1>>s2+1;
int tp[210000],j=0;
for(int i=n;i>=1;i--){
tp[i]=j+(s1[i]-'a')+(s2[i]-'a');
if(tp[i]%2!=0) tp[i+1]+=13;
tp[i]/=2;
}
for(int i=n;i>=1;i--)if(tp[i]>25){tp[i-1]++;tp[i]-=26;}
for(int i=1;i<=n;i++) printf("%c",'a'+tp[i]);
return 0;
}
【F. Graph Without Long Directed Paths】
You are given a connected undirected graph consisting of n vertices and m edges. There are no self-loops or multiple edges in the given graph. You have to direct its edges in such a way that the obtained directed graph does not contain any paths of length two or greater (where the length of path is denoted as the number of traversed edges).
【Input】
The first line contains two integer numbers n and m (2≤n≤2⋅105, n−1≤m≤2⋅10^5 ) — the number of vertices and edges, respectively. The following m lines contain edges: edge i is given as a pair of vertices ui, vi (1≤ui,vi≤n, ui≠vi). There are no multiple edges in the given graph, i. e. for each pair (ui,vi) there are no other pairs (ui,vi) and (vi,ui) in the list of edges. It is also guaranteed that the given graph is connected (there is a path between any pair of vertex in the given graph).
【Output】
If it is impossible to direct edges of the given graph in such a way that the obtained directed graph does not contain paths of length at least two, print "NO" in the first line. Otherwise print "YES" in the first line, and then print any suitable orientation of edges: a binary string (the string consisting only of '0' and '1') of length m. The i-th element of this string should be '0' if the i-th edge of the graph should be directed from ui to vi, and '1' otherwise. Edges are numbered in the order they are given in the input.
【题目大意】给一个无向连通图，n点m边且没有自环和重边。现在给每条边都给定方向，使得整个图变成有向图且最长路径不超过1.每条边的长度都为1.可能的话输出方案，按输入时边的顺序依次输出1或0表示不同的朝向,否则输出no
【分析】
最长不超过1，故如果某个点既有入边又有出边则能构成长度为2的路径，就已经违反条件。故连接某个点的所有边都必须全是入边或全是出边。那么，如果某些点的边构成一个环，则环的边数必为偶数。如果为奇数不可能满足全入全出。所以如果图中出现奇数环则为No。很明显的是，这变成了二分图。因为二分图的判断就是看有无奇数环。直接染色搜索判断即可。染色后每个点都被染成黑或白，如果染色结果为黑则都是入，白都是出。按边的顺序，如果边输入时是“黑 白”则为1，否则为0.
const int N = 200505;
int m,n;
int color[N];
int edu[N],edv[N];
vectornode[N];
bool dfs(int v,int c){
color[v]=c;
for(int i=0;i
if(color[node[v][i]]==c) return false;
if(color[node[v][i]]==0&&!dfs(node[v][i],-c))
return false;
}
return true;
}
bool solve(){
for(int i=0;i
printf("YES\n"); return true;
}
int main(){
int u,v;
scanf("%d %d",&n,&m);
for(int i = 0; i < m; i++){
scanf("%d %d",&edu[i],&edv[i]);
node[edu[i]].push_back(edv[i]);
node[edv[i]].push_back(edu[i]);
}
if(solve())for(int i=0;i < m;i++) if(color[edu[i]]==-1) printf("1"); else printf("0");
return 0;
}
return 0;
}
