Fork me on GitHub

Codeforces776G

Codeforces776G题解

题意:

  • 设$x$的16进制表示为$x_{n-1} \cdots x_1x_0$,那么设$h(x)=2^{x_{n-1}}|2^{x_{n-2}}| \cdots 2^{x_1}|2^{x_0}$,求区间$[l,r]$中满足$x\ xor\ h(x)< x$的数的个数。

题解:

  • 显然只跟最后几位有关,就是一个16进制的数位dp。
  • 用记忆化搜索的方式,$dfs(x,y,z,flag)$表示目前到第$x$位,各位的最大值为$y$,最后16位的和到现在的值为$z$,$flag$表示是否贴紧上限。

代码:

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
#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define N 16
using namespace std;
int a[N];
ll dp[N][N][1<<N];
ll dfs(int x,int y,int z,int flag)
{
if (x==0) return z>>y&1;
if (!flag&&dp[x][y][z]!=-1) return dp[x][y][z];
ll ret=0;
int lim=(flag?a[x]:15);
for (int i=0;i<=lim;i++)
ret+=dfs(x-1,max(y,i),(x<=4)?(z|(i<<((x-1)<<2))):z,flag&&(i==lim));
if (!flag) dp[x][y][z]=ret;
return ret;
}
ll solve(ll now)
{
if (now<0) return 0;
int n=0;
while (now)
{
a[++n]=now%16;
now>>=4;
}
return dfs(n,0,0,1);
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int q;
memset(dp,-1,sizeof(dp));
cin>>q;
while (q--)
{
ll l,r;
cin>>hex>>l>>hex>>r;
cout<<solve(r)-solve(l-1)<<endl;
}
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Codeforces776G

文章作者:wzf2000

发布时间:2017年12月25日 - 12:12

最后更新:2017年12月26日 - 05:12

原始链接:https://wzf2000.github.io/2017/12/25/Codeforces776G/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。