【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.
【題目大意】
一個(gè)字符串能稱(chēng)之為“Diverse”的是指其包含的字符在字母表中是連續(xù)的一段橱乱，比如fced是滿足的字符串，因?yàn)榘淖址麨?c,d,e,f 且在字母表中連續(xù)装哆。但是aa,az,bad都不是“Diverse”的因?yàn)閍a包含重讀的字符串帘瞭，a,z認(rèn)為是不相鄰的看彼，bad在字母表中不是連續(xù)的一段（缺c）椒惨，現(xiàn)在給出若干字符串拣度，判斷是否是“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個(gè)整數(shù)的數(shù)組a俊性，進(jìn)行如下操作搪桂。第一步選取任意一個(gè)元素刪除透敌，這樣數(shù)組a還剩n-1個(gè)元素。接下來(lái)的每一輪踢械，Polycarp都會(huì)刪除一個(gè)元素酗电，且刪除的元素和上一個(gè)刪除的元素奇偶性不同。如果沒(méi)有可刪除的元素就停止内列。Polycarp的目標(biāo)是最小化未被刪除的元素和撵术，輸出這個(gè)答案。如果元素都被刪除則輸出為0话瞧。
【思路】
讀入的數(shù)據(jù)按奇偶性分別保存到odd和even數(shù)組中嫩与，設(shè)分別有Lo和Le個(gè)元素。若abs（Lo-Le）≤1則必能全部刪除完交排，答案是0划滋。否則選取元素多的那個(gè)數(shù)組中統(tǒng)計(jì)最小的若干項(xiàng)的和即可。
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).
【題目大意】
兩個(gè)序列埃篓，一個(gè)序列嚴(yán)格遞增处坪，另一個(gè)嚴(yán)格遞減。認(rèn)為空序列同時(shí)是嚴(yán)格遞增 與 嚴(yán)格遞減的〖茏ǎ現(xiàn)在兩個(gè)序列隨機(jī)混合打亂同窘，構(gòu)成新序列。現(xiàn)在給出新序列胶征，問(wèn)能否拆成一個(gè)嚴(yán)格遞增和一個(gè)嚴(yán)格遞減序列？是輸出方案桨仿，否輸出NO睛低。存在多解輸出其中一個(gè)即可。
【思路】
由于嚴(yán)格遞增遞減服傍，則同一個(gè)序列中不能出現(xiàn)相同元素钱雷，故如果新序列中某個(gè)元素出現(xiàn)超過(guò)2次則不可能還原，否則一定能還原吹零。讀入的數(shù)據(jù)先排序罩抗，由于只用輸出一組解，故可以?xún)?yōu)先考慮放在遞增序列中灿椅，如果元素相同的就放在遞減序列中套蒂。由于一開(kāi)始排序過(guò)了钞支，序列添加完畢后也一定是有序的。輸出即可操刀。
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個(gè)整數(shù)的數(shù)組a烁挟，對(duì)于第i個(gè)元素，它可以有幾種方法進(jìn)行改變骨坑。設(shè)它相鄰的為j撼嗓，即abs(i-j）==1，可以做如下2種變化: ai:=ai+|ai?aj| 或ai:=ai+|ai?aj|.易證這種操作進(jìn)行若干次后必可以使得所有元素都相等』锻伲現(xiàn)在求最小變化次數(shù)使得所有數(shù)都相等的方案且警，可能有多種答案，輸出一個(gè)即可礁遣。
【分析】
所謂的變化斑芜，其實(shí)就是i位置的元素可以用相鄰位置的元素進(jìn)行覆蓋。假設(shè)第i個(gè)元素想變成第k個(gè)元素亡脸，（如果i到k之間不存在和k相等的元素）押搪，則只要k-i步就可以使得從i到k都等于k。最少次數(shù)一定是每一步都能將一個(gè)不同于目標(biāo)元素的元素變?yōu)橄嗤那衬搿Ｓ纱丝闯鲐澬拇笾荨Ｏ忍暨x出出現(xiàn)最多次數(shù)的元素，這些元素不用變化垂谢。緊接著是與這些元素相鄰的元素（距離為1）厦画，進(jìn)行變化。緊接著是據(jù)離為2的滥朱，一直到全部元素都相同根暑。
先讀入數(shù)據(jù)保存在ini[i]數(shù)組中，num[k]表示值為k的元素個(gè)數(shù)徙邻。值為Maxp的元素個(gè)數(shù)最多排嫌。L[i]表示在第i個(gè)元素左邊 【距離i最近的且值為Maxp】的元素的距離。R[i]表示在第i個(gè)元素右邊【距離i最近的且值為Maxp 】的元素的距離缰犁。定義一個(gè)元素的距離d=min(L[i],R[i]).dis[i]表示d==i的元素下標(biāo)淳地。序列肯定從靠近目標(biāo)值的元素開(kāi)始向兩邊擴(kuò)散，故順序是按照dis下標(biāo)從小到大輸出帅容。
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.
【題目大意】
給定兩個(gè)等長(zhǎng)的字符串s颇象，t且字典序s小于t，由字典序處于s和t之間且與二者等長(zhǎng)的字符串構(gòu)成了字符串序列并徘，遣钳。輸出此字符串序列中的中間的那個(gè)字符串。例如s=”az”,t=”bf”,則s,t所確定的字符串序列為["az","ba","bb","bc","bd", "be","bf"],處于中間的是”bc”.輸入保證s和t所確定的字符串序列里有奇數(shù)個(gè)字符串麦乞。
【分析】
如果某個(gè)國(guó)家的字母表只有10個(gè)字母且寫(xiě)作0~9那么從 0913的確定的字典序的字符串序列是{09,10,11,12,13}蕴茴，輸出11.而11=（09+13）/2.同理劝评，假設(shè)az表示0~26,每個(gè)字符串都是26進(jìn)制數(shù)，那么（s+t）/2也就是我們的答案荐开。
讀入的字符串保存在s,t中付翁，先將az轉(zhuǎn)換成025，tp[i]表示第i位的最終結(jié)果晃听。這樣對(duì)于s[0…Ls-1]我們可以表示成S026^(Ls-1)+S126(Ls-2)+…+SLs-1*26(0),同理對(duì)于t也可寫(xiě)成類(lèi)似26進(jìn)制數(shù)的形式百侧。那么(s+t)/2的每一位結(jié)果保存在tp[i]中，有 tp[i]=(s[i]+t[i])/2 如果出現(xiàn)了奇數(shù)能扒，則保留整數(shù)部分佣渴，并將13加到下一位去(26進(jìn)制下“13”就相當(dāng)于十進(jìn)制的“5”)。在從低位往高位進(jìn)位初斑，大于26的向前進(jìn)1.題目保證是奇數(shù)辛润，而且不會(huì)進(jìn)位使得位數(shù)增加。最后在轉(zhuǎn)化成字符就可以见秤。
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.
【題目大意】給一個(gè)無(wú)向連通圖砂竖，n點(diǎn)m邊且沒(méi)有自環(huán)和重邊。現(xiàn)在給每條邊都給定方向鹃答，使得整個(gè)圖變成有向圖且最長(zhǎng)路徑不超過(guò)1.每條邊的長(zhǎng)度都為1.可能的話輸出方案乎澄，按輸入時(shí)邊的順序依次輸出1或0表示不同的朝向,否則輸出no
【分析】
最長(zhǎng)不超過(guò)1，故如果某個(gè)點(diǎn)既有入邊又有出邊則能構(gòu)成長(zhǎng)度為2的路徑测摔，就已經(jīng)違反條件置济。故連接某個(gè)點(diǎn)的所有邊都必須全是入邊或全是出邊。那么锋八，如果某些點(diǎn)的邊構(gòu)成一個(gè)環(huán)浙于，則環(huán)的邊數(shù)必為偶數(shù)。如果為奇數(shù)不可能滿足全入全出挟纱。所以如果圖中出現(xiàn)奇數(shù)環(huán)則為No羞酗。很明顯的是，這變成了二分圖紊服。因?yàn)槎謭D的判斷就是看有無(wú)奇數(shù)環(huán)檀轨。直接染色搜索判斷即可。染色后每個(gè)點(diǎn)都被染成黑或白围苫，如果染色結(jié)果為黑則都是入裤园，白都是出撤师。按邊的順序剂府，如果邊輸入時(shí)是“黑 白”則為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;
}
