題意

定義一個(gè)01串若其奇數(shù)位為回文或者其偶數(shù)位為回文則是個(gè)好串，問(wèn)長(zhǎng)度為n字典序第K小的好串是什么。

題解

比較套路的暴力找第k大問(wèn)題，每次從高位枚舉是0還是1，之后統(tǒng)計(jì)填0時(shí)候方案可行的方案數(shù)（使用容斥）若方案數(shù)<k說(shuō)明該為是1則將k減去求的的然后，否則該位是0繼續(xù)枚舉。

代碼

/*** author: TelmaZzzz* create: 2019-10-05-11.07.16 **/ #include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <ctime> #include <string> #include <vector> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> //#include <random> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef double db; void _R(int &x) { scanf("%d", &x); } void _R(ll &x) { scanf("%lld", &x); } void _R(db &x) { scanf("%lf", &x); } void _R(char &x) { scanf(" %c", &x); } void _R(char *x) { scanf("%s", x); } void R() {} template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); } void _W(const int &x) { printf("%d", x); } void _W(const ll &x) { printf("%lld", x); } void _W(const db &x) { printf("%.16f", x); } void _W(const char &x) { putchar(x); } void _W(const char *x) { printf("%s", x); } template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); } void W() {} template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); } #define rep(x,y,z) for(int x=y;x<=z;x++) #define erp(x,y,z) for(int x=y;x>=z;x--) #define PB push_back #define MP make_pair #define INF 1073741824 #define inf 1152921504606846976 #define pi 3.14159265358979323846 #define Fi first #define Se second //#pragma comment(linker,"/STACK:10240000,10240000") //mt19937 rand_(time(0)); const int N=3e5+7,M=2e6; const long long mod=1e9+7; inline int read(){int ret=0;char ch=getchar();bool f=1;for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');for(;isdigit(ch);ch=getchar()) ret=(ret<<1)+(ret<<3)+ch-48;return f?ret:-ret;} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll ksm(ll a,ll b,ll mod){int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;} ll inv2(ll a,ll mod){return ksm(a,mod-2,mod);}//逆元 //int head[N],NEXT[M],ver[M],tot;void link(int u,int v){ver[++tot]=v;NEXT[tot]=head[u];head[u]=tot;} void TelmaZzzz(){ #ifndef ONLINE_JUDGEfreopen("1.txt","r",stdin); #endif }int n; int pos_odd; int pos_even; int pos_odd_last; int pos_even_last; int ans[N]; bool flag1,flag0; ll Pow(int x){x=min(x,61);ll res=1;ll p=2;while(x){if(x%2==0) {p*=p;x/=2;}else {res*=p;x--;}}return res; } ll cal(int x){int ra0=(n/2-x/2);int ra1=((n+1)/2-(x+1)/2);int rmi0=max(0,(n/2+1)/2-x/2);int rmi1=max(0,((n+1)/2+1)/2-(x+1)/2);//cout<<x<<' '<<ra0<<' '<<ra1<<' '<<rmi0<<' '<<rmi1<<' '<<flag0<<' '<<flag1<<' '<<k<<endl;ll tmp0,tmp1,tmp2;if(flag0){tmp0=Pow(ra1+rmi0);}else tmp0=0;if(flag1){tmp1=Pow(ra0+rmi1);}else tmp1=0;if(flag1&&flag0){tmp2=Pow(rmi1+rmi0);}else tmp2=0;//cout<<tmp1<<' '<<tmp0<<' '<<tmp2<<endl;return tmp1+tmp0-tmp2; } void update(int x){int mi0,mi1;if(n%2==0){mi0=n/2+1;mi1=n/2;}else {mi0=n/2+1;mi1=n/2+1;}if(x%2==0){if(x>mi0){if(ans[mi0*2-x]!=ans[x]) flag0=false;}}else {if(x>mi1){if(ans[mi1*2-x]!=ans[x]) flag1=false;}} } int main(){TelmaZzzz();//ios::sync_with_stdio(false);int t;R(t);ll k;int ti=0;while(t--){R(n,k);flag1=flag0=true;for(int i=1;i<=n;i++){ans[i]=0;bool tm1=flag1,tm0=flag0;update(i);ll tmp=cal(i);//cout<<tmp<<endl;if(k>tmp){k-=tmp;flag1=tm1;flag0=tm0;ans[i]=1;update(i);}}//cout<<k<<endl;if(k>1){printf("Case #%d: NOT FOUND!\n",++ti);}else {printf("Case #%d: ",++ti);for(int i=1;i<=n;i++){printf("%d",ans[i]);}puts("");}}//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的gym 101194 B Hemi Palindrome的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。