立志用更少的代碼做更高效的表達
Recently, doge starts to get interested in a strange problem: whether there exists a string A following all the rules below:
1.The length of the string A is N .
2.The string A contains only lowercase English alphabet letters.
3.Each substring of A with length equal to or larger than 4 can appear in the string exactly once.
Doge cannot solve the problem, so he turns to his brother Yuege for help. However, Yuege is busy setting problems. Would you please help doge solve this problem?
Input
There are several test cases, please process till EOF.
For each test case, there will be one line containing one integer N (1 ≤ N ≤ 500000).
Sum of all N will not exceed 5000000.
Output
For each case, please output one line consisting a valid string if such a string exists, or “Impossible” (without quotes) otherwise. You can output any string if there are multiple valid ones.
Sample Input
5
3
11
10
6
17
8
Sample Output
pwned
wow
suchproblem
manystring
soeasy
muchlinearalgebra
abcdabch
題意
給你一個整數n，讓你輸出一個字串，必須滿足以下條件：
1.字串的長度為n，
2.這個字串只包含小寫字母，
3.字串中長度大于等于4的子串最多只能出現一次，
如果無解輸出Impossible，
解題思路
因為大于等于4的子串只能出現一次，所以不會重復的串最長只會達到4^26+3 = 456979的長度，
因此， 我們可以預先打一個不會重復的字符表出來
若n>456979 ，則輸出Impossible，
否則輸出表的前n項，
打表的方式用回圈即可，
代碼決議
#include<iostream>
using namespace std;
int vis[26][26][26][26];
int s[5000005];
int main() {
ios::sync_with_stdio;
for(int i = 0; i < 26; i++)
s[i*4] = s[i*4+1] = s[i*4+2] = s[i*4+3] = i;
for(int i = 3; i < 26*4; i++)
vis[s[i-3]][s[i-2]][s[i-1]][s[i]]=1;
for(int i=26*4; i < 456979; i++) //xx
for(int j = 25; j >= 0; j--)
if(vis[s[i-3]][s[i-2]][s[i-1]][j]==0) {
vis[s[i-3]][s[i-2]][s[i-1]][j]=1;
s[i] = j;
break;
}
int n; while(cin>>n) {
if(n > 456979) { cout << "Impossible" << '\n'; }
else {
for(int i = 0; i < n; i++) putchar(s[i]+97);
putchar('\n');
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/210056.html
標籤：java
上一篇：關于融云的單聊通訊那點事