題干：

給出v, k，請你找到最小的正整數(shù)n，滿足：
n的二進(jìn)制表示下存在一個(gè)長度為v的回文串，該回文串首尾都是1且n的二進(jìn)制表示中至少有k個(gè)1。保證v,k均為偶數(shù)！
由于n可能很大，你只需要輸出對取模的結(jié)果。

輸入描述:

兩個(gè)整數(shù)v, k。保證v,k均為偶數(shù)！

輸出描述:

一個(gè)整數(shù)，表示n對取模的結(jié)果。

示例1

輸入

復(fù)制

6 4

輸出

復(fù)制

45

說明

樣例的構(gòu)造方法為：101101

示例2

輸入

復(fù)制

2 4

輸出

復(fù)制

15

說明

最優(yōu)的構(gòu)造方法為：1111

備注:

。

解題報(bào)告：

? ?題目意思很清楚了，，不是長度為v的字符串，而是存在長度為v的子串。。。所以就直接先長度對半分，先填k，，看能不能都填上，長度為v的回文串都填滿了的話那就再后面填1就行了、、、

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; const ll mod = 1e9 + 7; int v,k; int qq[MAX]; ll qpow(ll a,ll k) {ll res = 1;while(k) {if(k&1) res = (res*a)%mod;k>>=1;a= (a*a)%mod;}return res; } int main() {cin>>v>>k;v>>=1;k>>=1;k--;qq[1]=1;for(int i = v; i>=2; i--) {if(k>0) qq[i]=1,k--;}for(int i = v+1; i<=(v<<1); i++) qq[i] = qq[v-(i-v)+1]; // for(int i = 1; i<=(v<<1); i++) printf("%d",qq[i]);if(k>0) {k<<=1;for(int i = (v<<1)+1; i<=k+(v<<1); i++) {qq[i] = 1;}}ll ans = 0;int up = k+(v<<1); // printf("up = %d\n",up);for(int i = up; i>=1; i--) {if(qq[i] == 1) ans = (ans + qpow(2,up-i))%mod;}printf("%lld\n",ans);return 0 ;}

總結(jié)：

想的時(shí)候還是思維不夠縝密啊，，這種題光滿足1A是不足夠的，，需要寫代碼的時(shí)候一次就寫對，情況全都考慮到，，而且不能debug的。。這種題必須最多5分鐘搞定啊。

另：其實(shí)這題寫代碼的時(shí)候就沒想這么多，本來直接填的回文串，然后第二個(gè)樣例過不了，，然后發(fā)現(xiàn)還有可能k>v，，所以再加點(diǎn)判斷就過了。。。其實(shí)這種構(gòu)造方法還是需要證明的，，首先如果k<=v的話那沒的說就是這么填（先兩頭有1，然后中間往兩邊填1）。k>v的時(shí)候，，首先我們需要n最小所以二進(jìn)制越短越好，所以我們肯定是把已有的位置充分利用一下不然浪費(fèi)著這些0也是浪費(fèi)著。，所以回文串的v長度肯定要填滿，，其次這個(gè)肯定剩下的k還是大于0的，所以我們還需要繼續(xù)填1，要么從回文串前面填1，要么后面添1，，所以肯定后面添1更小嘛（其實(shí)一樣大的，，因?yàn)榉凑@時(shí)候回文串也是全1串了，，也就是這時(shí)候答案一定是(2^k)? -1 這樣的一個(gè)全1二進(jìn)制數(shù)，，所以其實(shí)直接qpow一下再-1就好了嘛）

（其實(shí)這題告訴你了k個(gè)v都是偶數(shù)，，萬一是那種? 如果不存在就輸出-1? ?的? 就要坑死一片了、、）

（訓(xùn)練過程中順便給牛客的練習(xí)賽簽個(gè)到2333）

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 272A】Phrase String（构造，水题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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