Topic Description
On the Tanabata Festival, Vani took cl's hand and walked happily through the bright lights and joyful atmosphere. At this time, there suddenly appeared a Taiguda machine platform in front of which sat the applepi that had just been rescued by members of the elite team, XLk, Poet_shy and lydrainbowcat. Seeing that the two people were interested in Taiguda, Apple Pi was decisive, so CL picked up the drum stick to prepare for the challenge. However, even under ordinary difficulties, the pedestrian nature of CL is fully exposed. At the end of the song, not only did it fail, but even the drum failed. Vani was so upset that he decided to help the staff fix drums.
The main component of the drum is M sensors in a circle. Each sensor has two working states of on and off, expressed in 1 and 0 respectively. Obviously, if K sensors are continuously checked clockwise from different positions, a series of 01 sensors with M lengths of K can be obtained. Vani knows that M 01 strings should be different from each other. And the drum design is very precise, M will get the maximum possible value. Now Vani knows the value of K. He wants you to find the value of M and give the sensor layout scheme with the smallest dictionary order.
Input format
An integer K.
Output format
An integer M and a binary string, separated by a space. Represents the maximum possible M, and the least lexicographic order arrangement scheme. Character 0 means off, and character 1 means open. The first word and the last word of the string you output are adjacent.
Example
sample input
3
sample output
8 00010111
Data Scope and Tips
The 8 01 strings were 000, 001, 010, 101, 011, 111, 110 and 100, respectively. Note that the front and back are adjacent. There are only eight binary strings with a length of 3, so M = 8 must be the maximum possible.
For all test points, 2 < K < 11.
This is a classical loop problem. The so-called longest string contains different substrings. We can consider from the substrings, for example, how can we get it?
It is true that I found a string in all binary strings of length 3 and added one that I could get at the end of the string. When I constructed the map, I found that a string returned to itself and ran the Eulerian circuit on this map. The minimum dictionary order was to start from zero.
Attach AC code
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; int main(){ int k; cin>>k; if(k==2) puts("4 0011"); if(k==3) puts("8 00010111"); if(k==4) puts("16 0000100110101111"); if(k==5) puts("32 00000100011001010011101011011111"); if(k==6) puts("64 0000001000011000101000111001001011001101001111010101110110111111"); if(k==7) puts("128 00000001000001100001010000111000100100010110001101000111100100110010101001011100110110011101001111101010110101111011011101111111"); if(k==8) puts("256 0000000010000001100000101000001110000100100001011000011010000111100010001001100010101000101110001100100011011000111010001111100100101001001110010101100101101001011110011001101010011011100111011001111010011111101010101110101101101011111011011110111011111111"); if(k==9) puts("512 00000000010000000110000001010000001110000010010000010110000011010000011110000100010000100110000101010000101110000110010000110110000111010000111110001000110001001010001001110001010010001010110001011010001011110001100110001101010001101110001110010001110110001111010001111110010010010110010011010010011110010100110010101010010101110010110110010111010010111110011001110011010110011011010011011110011101010011101110011110110011111010011111110101010110101011110101101110101110110101111110110110111110111011110111111111"); if(k==10) puts("1024 0000000000100000000110000000101000000011100000010010000001011000000110100000011110000010001000001001100000101010000010111000001100100000110110000011101000001111100001000010001100001001010000100111000010100100001010110000101101000010111100001100010000110011000011010100001101110000111001000011101100001111010000111111000100010100010001110001001001000100101100010011010001001111000101001100010101010001010111000101100100010110110001011101000101111100011000110010100011001110001101001000110101100011011010001101111000111001100011101010001110111000111100100011110110001111101000111111100100100110010010101001001011100100110110010011101001001111100101001010011100101010110010101101001010111100101100110010110101001011011100101110110010111101001011111100110011010011001111001101010100110101110011011011001101110100110111110011100111010110011101101001110111100111101010011110111001111101100111111010011111111010101010111010101101101010111110101101011011110101110111010111101101011111110110110111011011111101110111110111101111111111"); if(k==11) puts("2048 00000000000100000000011000000001010000000011100000001001000000010110000000110100000001111000000100010000001001100000010101000000101110000001100100000011011000000111010000001111100000100001000001000110000010010100000100111000001010010000010101100000101101000001011110000011000100000110011000001101010000011011100000111001000001110110000011110100000111111000010000110000100010100001000111000010010010000100101100001001101000010011110000101000100001010011000010101010000101011100001011001000010110110000101110100001011111000011000110000110010100001100111000011010010000110101100001101101000011011110000111000100001110011000011101010000111011100001111001000011110110000111110100001111111000100010010001000101100010001101000100011110001001001100010010101000100101110001001100100010011011000100111010001001111100010100011000101001010001010011100010101001000101010110001010110100010101111000101100110001011010100010110111000101110010001011101100010111101000101111110001100011100011001001000110010110001100110100011001111000110100110001101010100011010111000110110010001101101100011011101000110111110001110010100011100111000111010010001110101100011101101000111011110001111001100011110101000111101110001111100100011111011000111111010001111111100100100101001001001110010010101100100101101001001011110010011001100100110101001001101110010011101100100111101001001111110010100101100101001101001010011110010101001100101010101001010101110010101101100101011101001010111110010110011100101101011001011011010010110111100101110011001011101010010111011100101111011001011111010010111111100110011011001100111010011001111100110100111001101010110011010110100110101111001101101010011011011100110111011001101111010011011111100111001111001110101010011101011100111011011001110111010011101111100111101011001111011010011110111100111110101001111101110011111101100111111101001111111110101010101101010101111010101101110101011101101010111111010110101110101101101101011011111010111011110101111011101011111011010111111110110110111101101110111011011111110111011111101111011111011111111111"); }/* #include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; int k,b[2050],ch[2050][2050],mas,cnt; bool v[2050],t[2050]; int rd() { char cc=getchar(); int s=0,w=1; while(cc<'0'||cc>'9') {if(cc=='-') w=-1;cc=getchar();} while(cc>='0'&&cc<='9') s=(s<<3)+(s<<1)+cc-'0',cc=getchar(); return s*w; } void dfs(int x) { for(int i=0;i<=mas;i++) { if(ch[x][i]&&!v[i]) { ch[x][i]=0; v[i]=1; dfs(i); } } b[++cnt]=x; } int main() { freopen("2.cpp","w",stdout); printf("#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<vector>\n#include<algorithm>\nusing namespace std;\nint main(){\n"); printf("int k;\ncin>>k;\n"); for(k=2;k<=11;k++) { memset(t,0,sizeof(t)); memset(v,0,sizeof(v)); memset(ch,0,sizeof(ch)); memset(b,0,sizeof(b));cnt=0; printf("if(k==%d) puts(\"",k); mas=(1<<k)-1; //memset(ch,-1,sizeof(ch)); for(int i=0;i<=mas;i++) { int nt=(i<<1)&mas; t[nt|1]=1;t[nt]=0; // cout<<i<<" "<<(nt|1)<<" "<<nt<<endl; if((nt|1)!=i) ch[i][nt|1]=1; if(nt!=i) ch[i][nt]=1; } dfs(0); printf("%d ",cnt-1); for(int i=1;i<=k;i++) printf("0"); for(int i=cnt-1;i>k;i--) printf("%d",t[b[i]]); puts("\");"); } printf("}\n"); } */
Cough
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; int k,b[2050],ch[2050][2050],mas,cnt; bool v[2050],t[2050]; int rd() { char cc=getchar(); int s=0,w=1; while(cc<'0'||cc>'9') {if(cc=='-') w=-1;cc=getchar();} while(cc>='0'&&cc<='9') s=(s<<3)+(s<<1)+cc-'0',cc=getchar(); return s*w; } void dfs(int x) { for(int i=0;i<=mas;i++) { if(ch[x][i]&&!v[i]) { ch[x][i]=0; v[i]=1; dfs(i); } } b[++cnt]=x; } int main() { k=rd(); mas=(1<<k)-1; //memset(ch,-1,sizeof(ch)); for(int i=0;i<=mas;i++) { int nt=(i<<1)&mas; t[nt|1]=1;t[nt]=0; // cout<<i<<" "<<(nt|1)<<" "<<nt<<endl; if((nt|1)!=i) ch[i][nt|1]=1; if(nt!=i) ch[i][nt]=1; } dfs(0); printf("%d ",cnt-1); for(int i=1;i<=k;i++) printf("0"); for(int i=cnt-1;i>k;i--) printf("%d",t[b[i]]); puts(""); } /* g++ 1.cpp -o 1 ./1 4 */