题干：
给出v, k，请你找到最小的正整数n，满足：
n的二进制表示下存在一个长度为v的回文串，该回文串首尾都是1且n的二进制表示中至少有k个1。保证v,k均为偶数！
由于n可能很大，你只需要输出对取模的结果。
输入描述:
两个整数v, k。保证v,k均为偶数！
输出描述:
一个整数，表示n对取模的结果。
示例1
输入
6 4
输出
45
说明
样例的构造方法为：101101
示例2
输入
2 4
输出
15
说明
最优的构造方法为：1111
备注:
。
解题报告：
题目意思很清楚了，，不是长度为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 ;
}
总结：
想的时候还是思维不够缜密啊，，这种题光满足1A是不足够的，，需要写代码的时候一次就写对，情况全都考虑到，，而且不能debug的。。这种题必须最多5分钟搞定啊。
另：其实这题写代码的时候就没想这么多，本来直接填的回文串，然后第二个样例过不了，，然后发现还有可能k>v，，所以再加点判断就过了。。。其实这种构造方法还是需要证明的，，首先如果k<=v的话那没的说就是这么填（先两头有1，然后中间往两边填1）。k>v的时候，，首先我们需要n最小所以二进制越短越好，所以我们肯定是把已有的位置充分利用一下不然浪费着这些0也是浪费着。，所以回文串的v长度肯定要填满，，其次这个肯定剩下的k还是大于0的，所以我们还需要继续填1，要么从回文串前面填1，要么后面添1，，所以肯定后面添1更小嘛（其实一样大的，，因为反正这时候回文串也是全1串了，，也就是这时候答案一定是(2^k) -1 这样的一个全1二进制数，，所以其实直接qpow一下再-1就好了嘛）
（其实这题告诉你了k个v都是偶数，，万一是那种 如果不存在就输出-1 的 就要坑死一片了、、）
（训练过程中顺便给牛客的练习赛签个到2333）
京公网安备 11010502036488号