BZOJ 3780 数字统计

Link

Solution

从低位到高位DP。。现在感觉这种边DP边卡的做法很舒服啊。。 \(f[i][0/1][0/1]\)表示第\(i\)位,是否卡到了上界(卡上界的情况需要包含超上界的情况,因为是从低到高DP的),删之后剩下了\(0/1\)的方案数目。转移的时候和从高到低的判断条件不太一样,不要手滑写错。 # Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include "lucida"
using std::reverse;
using std::max;
const int MAXB=200+11;
IO::Ost &operator <<(IO::Ost &,struct BinNum &);
struct BinNum {
short a[MAXB];int n;
short &operator [](int x) {
return a[x];
}
BinNum(int x=0) {
memset(a,0,sizeof(a));
for(n=0;x;x>>=1)
a[++n]=x&1;
}
friend BinNum operator +(BinNum a,BinNum b) {
int &n=a.n=max(a.n,b.n);
for(int i=1;i<=n;++i) {
a[i]+=b[i];
}
for(int i=1;i<=n;++i) {
a[i+1]+=a[i]>>1;
a[i]&=1;
if(a[i+1])
chkmx(n,i+1);
}
return a;
}
friend BinNum operator -(BinNum a,BinNum b) {
int &n=a.n=max(a.n,b.n);
for(int i=1;i<=n;++i)
a[i]-=b[i];
for(int i=1;i<=n;++i)
if(a[i]<0) {
a[i]+=2;
a[i+1]--;
}
while(n && !a[n]) --n;//n..
return a;
}
#define template template <class T>
template BinNum &operator +=(T a) {
return *this=*this+a;
}
template BinNum &operator -=(T a) {
return *this=*this-a;
}
#undef template
};
IO::Ist &operator >>(IO::Ist &is,BinNum &x) {
int &n=x.n=0;
char ch;
while(ch=getchar(),(ch!='0' && ch!='1'));
do x[++n]=ch-'0';
while(ch=getchar(),(ch=='0' || ch=='1'));
reverse(x.a+1,x.a+1+n);
return is;
}
IO::Ost &operator <<(IO::Ost &os,BinNum &x) {
int p=x.n;
while(p && !x[p]) p--;
if(p) do
putchar(x[p--]+'0');
while(p);
else putchar('0');
return os;
}
BinNum f[MAXB][2][2];//定义成了int64????2333..
BinNum Calc(BinNum x,int Y) {
#define merge(x,y) ((x)==0 && (y)==0)
memset(f,0,sizeof(f));
//f[i][(f)0/1][(s)0/1] 表示后i位,</>= x,删出来的结果为0/1
//答案就是f[len][0][Y]
for(int i=0;i<2;++i)
f[1][i>=x[1]][i]=1;
for(int i=2;i<=x.n;++i) {
for(int dt=0;dt<2;++dt)
for(int ff=0;ff<2;++ff)
for(int fs=0;fs<2;++fs) {
f[i][dt>x[i] || (dt==x[i] && ff)][merge(dt,fs)]+=f[i-1][ff][fs];
}
}
return f[x.n][0][Y];
}
void Work() {
int M,Y;is>>M>>Y;
BinNum l,r;is>>l>>r;
BinNum Ans=Calc(r+1,Y)-Calc(l,Y);
os<<Ans<<'\n';
}
int main() {
// freopen("input","r",stdin);
int T;is>>T;
while(T--)
Work();
return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利