首页 > 代码库 > codeforces 288A:Polo the Penguin and Strings
codeforces 288A:Polo the Penguin and Strings
Description
Little penguin Polo adores strings. But most of all he adores strings of length n.
One day he wanted to find a string that meets the following conditions:
- The string consists of n lowercase English letters (that is, the string‘s length equals n), exactly k of these letters are distinct.
- No two neighbouring letters of a string coincide; that is, if we represent a string as s = s1s2... sn, then the following inequality holds, si ≠ si + 1(1 ≤ i < n).
- Among all strings that meet points 1 and 2, the required string is lexicographically smallest.
Help him find such string or state that such string doesn‘t exist.
String x = x1x2... xp is lexicographically less than string y = y1y2... yq, if either p < q and x1 = y1, x2 = y2, ... , xp = yp, or there is such number r (r < p, r < q), that x1 = y1, x2 = y2, ... , xr = yr and xr + 1 < yr + 1. The characters of the strings are compared by their ASCII codes.
A single line contains two positive integers n and k (1 ≤ n ≤ 106, 1 ≤ k ≤ 26) — the string‘s length and the number of distinct letters.
In a single line print the required string. If there isn‘t such string, print "-1" (without the quotes).
7 4
ababacd
4 7
-1
正解:贪心
解题报告:
直接每次贪心地让ab不断重复,注意特判一些细节,这题的数据好坑
1 //It is made by jump~ 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <ctime> 9 #include <vector>10 #include <queue>11 #include <map>12 #include <set>13 using namespace std;14 typedef long long LL;15 int n,k,cnt;16 17 inline int getint()18 {19 int w=0,q=0; char c=getchar();20 while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); 21 while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar(); return q ? -w : w;22 }23 24 inline void work(){25 n=getint(); k=getint();26 if(k>n || (k==1 && n>1)) { printf("-1"); return ; } 27 if(k==1 && n==1) { printf("a"); return ; }28 cnt=2; k-=2;29 for(int i=1;i<=n;i++) {30 if(n-i<k) printf("%c",(char)cnt+‘a‘),cnt++;31 else {32 if(i&1) printf("a"); else printf("b");33 }34 }35 }36 37 int main()38 {39 work();40 return 0;41 }
codeforces 288A:Polo the Penguin and Strings