门门
如果限制条件只有 1,2,4，是个人基本都会做。
问题在3，不妨考虑 x>y的情况(方便去掉绝对值)，显然另一种情况 y>x是对称的，我们只需要考虑现在的这种情况即可。
因为涉及到减法，有一些退位的问题就很烦，比赛的时候过的人也少，队里就没人做这题了。
我们把 k 给二进制展开成 (kt…k1)2
我们从高位向低位 dfs，每次枚举两个数的第 u位，分别为 i,j，记 nku=i–j(表示 nk的第 u位二进制数)，显然 nku可能是 −1,0,1其中的一个，我们的目标是让 nk≤k。
我们会发现，如果做到第 u位的时候，若前面的数 nk–k≥2的话，我们就算把 nk剩下的位数全部置为 −1，最多只能使前面的数 −1，所以这样的情况对答案是没有贡献的。
因此我们只要记录前面的数的 nk–k是多少 (代码里这个值为 limk)，然后分类讨论转移即可 (具体看代码)。
自己不会做最大的问题是没想到每一位 nk−k≤1必定成立的性质，长脑子了。
还有一个小小的 trick 是可以每次都把 dp数组置 −1(前提是数组比较小)，这样可以记录更多状态，减少无用搜索数量
#include<bits/stdc++.h>
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define eps 1e-4
#define mod 10086
#define lowbit(x) (x & -x)
#define N 505
#define M 2005
#define clr(arr) memset(arr, 0, sizeof arr)
#define bset std::bitset<N>
#define pi std::pair<int, int>
#define ls t[u].l
#define rs t[u].r
#define pls t[pu].l
#define prs t[pu].r
ll read ()
{
Re char ch = getchar();
Re ll ret = 0;
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) {ret = ret * 10 + ch - '0'; ch = getchar();}
return ret;
}
char s[N];
int tb[35], ta[35], tk[35], tw[35], pa[35], pb[35];
ll dp[35][2][2][2][3][2];
ll dfs (int u, bool lima, bool limb, int limk, bool limw, bool ab)
{
if (!u)
{
if (limk <= 0 && !ab)
{
return 1;
}
return 0;
}
if (dp[u][lima][limb][limw][limk + 1][ab] != -1)
return dp[u][lima][limb][limw][limk + 1][ab];
int upi = lima ? ta[u] : 1;
int upj = limb ? tb[u] : 1;
ll ret = 0;
fo (i, 0, upi)
fo (j, 0, upj)
{
if (ab && i < j) continue;
int k = i ^ j;
if (limw && k > tw[u]) continue;
k = i - j;
int nk;
if (limk == -1)
{
nk = -1;
}
else
if (!limk)
{
if (k > tk[u]) nk = 1;
if (k == tk[u]) nk = 0;
if (k < tk[u]) nk = -1;
}
else
{
nk = k + 2 - tk[u];
if (nk >= 2) continue;
}
ret += dfs(u - 1, lima && i == ta[u], limb && j == tb[u], nk, limw && ((i ^ j) == tw[u]), ab && i == j);
}
dp[u][lima][limb][limw][limk + 1][ab] = ret;
return ret;
}
ll solve (int a, int b, int k, int w)
{
memset(dp, -1, sizeof dp);
fo (i, 1, 30)
{
ta[i] = (a >> i - 1) & 1;
tb[i] = (b >> i - 1) & 1;
tk[i] = (k >> i - 1) & 1;
tw[i] = (w >> i - 1) & 1;
}
return dfs(30, 1, 1, 0, 1, 1);
}
int a, b, k, w;
int main ()
{
int T = read();
while (T--)
{
a = read(); b = read(); k = read(); w = read();
printf("%lld\n", solve(a, b, k, w) + solve(b, a, k, w) + std::min(a, b) + 1);
}
return 0;
}
0 条评论