鸽子要跑路

Description

鸽子一开始位于平面直角坐标系上的整点 (a,b)(a, b),每次可以上下左右走一个单位(保证坐标非负)。鸽子的家在 (c,d)(c,d)

鸽子的疲劳值初始值为 00。如果鸽子当前位置 (x,y)(x,y) 满足 xandy>0x \, \operatorname{and} \, y > 0,鸽子的疲劳值就要加 11,否则疲劳值不增加。and\operatorname{and} 是按位与。起点与终点的疲劳值不计入答案。

求鸽子回家的最小疲劳值。

Input

第一行数据组数 TT

接下来 TT 行,每行四个整数 a,b,c,da, b, c, d

Output

TT 行,每行一个整数表示答案。

Hint

T105,a,b,c,d1018T \le 10^5, a,b,c,d \le 10^{18}

Solution

打个表可以发现,xandy=0x \operatorname{and} y = 0 的位置组成了一个谢尔宾斯基三角形,而且是四联通的,所以我们从 (a,b)(a,b) 走到 (c,d)(c,d) 就有两种方案:

  1. 先从 (a,b)(a,b) 走到三角形上,再走到 (c,d)(c,d)
  2. 直接从 (a,b)(a,b) 走到 (c,d)(c,d)

第二种走法很好算,第一种需要我们计算出每个点到谢尔宾斯基三角形的最近距离。

考虑谢尔宾斯基三角形是个分形,我们可以通过适当地缩放坐标来方便计算。

因为它是沿对角线对称的,所以不妨设当前坐标为 (x,y)(x,y)xyx \le y,观察规律可以发现每一级三角形的边长都是 22 的整次幂,所以我们找到第一个大于 yy22 的整次幂,设为 LL,如果 x+yLx+y \ge L 的,说明 (x,y)(x,y) 已经在正方形的右下部分了,可以直接计算到边界的距离,否则可以使 yyL/2y \leftarrow y-L/2,重复以上步骤。

这样做每次可以使 yy 坐标减小至少一半,所以单次询问是 O(logA)O(\log A) 的,其中 AA 是坐标的值域。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve();
ll get(ll x);
ll calc(ll x, ll y);

int main()
{
int t; read(t);
while(t --> 0) solve();
}

void solve()
{
ll a, b, c, d;
read(a, b, c, d);
if(a == c and b == d)
print("0\n");
else
{
ll x = calc(a, b);
ll y = calc(c, d);
print("{}\n", min({x+y, abs(a-c)+abs(b-d)-1}));
}
}
ll calc(ll x, ll y)
{
if((x&y) == 0) return 0;
ll l;
while(1)
{
if(x > y) swap(x, y);
l = get(y);
if(x+y >= l) break;
else y -= l/2;
}
return min({l-x-1, l-y-1, x+y-l});
}
ll get(ll x)
{
ll a = 1;
while(a <= x) a <<= 1;
return a;
}


/*
4
1 1 1 1
1 3 6 6
3 6 5 5
20191427 20190647 1242 803739

0
1
2
6827759
*/

啊吧啊吧

Description

给你一个只包含字符 ab 的字符串 ss,你需要求出最多有多少不相交的子序列 abab

不相交的定义为:对于 ss 种的每个字符,其最多处于一个子序列中。

Input

第一行 TT,代表数据组数。

接下来 TT 行,每行一个字符串 ss

Output

TT 行,表示每组数据的答案。

Hint

s107,1T5|s| \le 10^7, 1 \le T \le 5

Solution

发现 abab 可以拆成两个 ab,问题就变成了去除尽可能多的不相交的 ab

不能同时选的 ab 存在一个分界点 p[1,n]p \in [1,n],使得所有 a 的位置小于等于 pp,所有 bb 的位置大于等于 pp

设不能同时选的 ab 的最大值为 mxmx,共有 cntcntab,那么答案就是 min(cnt2,cntmx)\min(\lfloor \frac{cnt}{2} \rfloor, cnt-mx)

这个 min\min 的式子含义是:如果 mxcnt2mx \le \lfloor \frac{cnt}{2} \rfloor,那么就可以让所有的 ab 两两匹配,如果 mx>cnt2mx > \lfloor \frac{cnt}{2} \rfloor,那么有 cntmxcnt-mxab 是和这 mxmxab 不相交的,所以这 cntmxcnt-mxab 可以直接匹配这 mxmx 个相交的 ab,可以得到 cntmxcnt-mxabab

现在就需要使 mxmx 最小化,这个可以使每个 bb 去匹配它前面最近的未被匹配的 aa,这样可以使这一对 ab 包含的其他 ab 最少,所以用一个栈做一下括号匹配就行了。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e7+10;

int n, d[N];
char s[N];

void solve();

int main()
{
int t; read(t);
while(t --> 0) solve();
}

void solve()
{
memset(d, 0, sizeof(d));
read(s+1); n = strlen(s+1);
stack<int> st; int cnt = 0;
for(int i = 1; i <= n; i++)
{
if(s[i] == 'a') st.push(i);
else if(!st.empty())
{
d[st.top()]++, st.pop();
d[i]--, cnt++;
}
}

int sum = 0, mx = 0;
for(int i = 1; i <= n; i++)
sum += d[i], mx = max(mx, sum);

print("{}\n", min(cnt/2, cnt-mx));
}

二叉树比大小

Description

00 代表空树,如果一个节点没有左子树,那么认为它的左子树是空树(右子树同理)。对任意二叉树 AA0A0 \le A 成立;对任意非空二叉树 AAA0A \le 0 不成立。用 ls\operatorname{ls} 代表左子树,rs\operatorname{rs} 代表右子树,则对于非空二叉树 A,BA,BABA \le B 当且仅当 ls(A)ls(B)\operatorname{ls}(A) \le \operatorname{ls}(B)rs(B)rs(A)\operatorname{rs}(B) \le \operatorname{rs}(A)

给定节点编号为 1n1 \sim n 的二叉树 AABB 的初始形态为 AA。对 BB 重复进行以下操作:任选 BB 中的一个儿子数量不超过 11 的节点,为这个节点增加一个儿子(使得 BB 仍然是二叉树)。左右有区别。

问有多少不同BB 满足 BB 的节点数为 n+mn+mABA \le B

Input

第一行两个整数 n,mn, m

接下来 nn 行,给出二叉树 AA。第 i+1i+1 行有两个整数,第一个是 ii 号节点的左儿子编号,第二个是右儿子编号(没有用 00 代替)。

Output

一个整数表示方案数,对 19142706471914270647 (一个质数)取模。

Hint

n,m106n,m \le 10^6

Solution

如果 ABA \le B,那么 AA 的每一个子树 AA' 和它对应的 BB' 都有大小关系的限制,要么是 $ A’ \le B’$ ,要么是 ABA' \ge B'。我们可以在要求 ABA' \le B' 的子树的根上标记状态为 11,在要求 ABA' \ge B' 的子树的根上标记状态为 00。左儿子状态与父亲相同,右儿子状态与父亲相反。

我们只能在 11 的地方添加节点。可以遍历一遍 AA 找到所有能添加新节点的位置,我们只需要关系这些位置的数量,设为 cc。问题转化为:

cc 个互相独立的位置,放上 mm 个节点,问最终形成的二叉树森林有几种。

f(c,m)f(c,m) 表示上述问题的答案。

分类讨论是否有节点挂在第 cc 个位置。

  • 如果有一个节点挂在第 cc 个位置,节点数减少 11,互相独立的位置数反而增加了 11,状态转移为 f(c+1,m1)f(c+1,m-1)

  • 如果没有节点挂在第 cc 个位置,也就是再也不用位置 cc,状态转移为 f(c1,m)f(c-1,m)

所以 f(c,m)=f(c+1,m1)+f(c1,m)f(c,m) = f(c+1,m-1) + f(c-1, m)

这个式子可以转化为路径计数:

如果位置在 (x,y)(x,y),下一步可以走到 (x1,y+1)(x-1,y+1)(x+1,y)(x+1,y),但始终保证 x>0x > 0,求从 (1,0)(1,0) 走到 (c,m)(c,m) 的路径条数。

把坐标变换为 (x+y,y)(x+y, y),得到更熟悉的形式:

如果位置在 (x,y)(x,y),下一步可以走到 (x,y+1)(x,y+1)(x+1,y)(x+1,y),但始终保证 x>yx > y,求从 (1,0)(1,0) 走到 (c+m,m)(c+m,m) 的路径条数。

这个很明显就是卡特兰数了,答案为 Cc+2m1mCc+2m1cC_{c+2m-1}^{m} - C_{c+2m-1}^{c}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 3e6+10;
const ll P = 1914270647;

int n, m, c;
bool vis[N];
int ls[N], rs[N];
ll fact[N], finv[N];

ll C(int n, int m);
ll qpow(ll a, ll b);
void prework(int n);
void dfs(int x, bool t);

int main()
{
read(n, m);
for(int i = 1; i <= n; i++)
{
read(ls[i], rs[i]);
vis[ls[i]] = vis[rs[i]] = true;
}
for(int i = 1; i <= n; i++)
if(!vis[i]) dfs(i, 1);

prework(c+m*2-1);

ll ans = C(c+m*2-1, m) - C(c+m*2-1, c+m);

print("{}", (ans+P)%P);

}


void dfs(int x, bool t)
{
if(!x)
{
if(t) c++;
return void();
}
dfs(ls[x], t);
dfs(rs[x], t^1);
}
void prework(int n)
{
fact[0] = 1;
for(int i = 1; i <= n; i++)
fact[i] = fact[i-1]*i%P;
finv[n] = qpow(fact[n], P-2);
for(int i = n-1; i >= 0; i--)
finv[i] = finv[i+1]*(i+1)%P;
}
ll qpow(ll a, ll b)
{
ll ans = 1;
for(; b; b >>= 1, a = a*a%P)
if(b&1) ans = ans*a%P;
return ans;
}
ll C(int n, int m)
{
if(n < m or n < 0 or m < 0) return 0;
return fact[n] * finv[m]%P * finv[n-m]%P;
}
/*
4 2
2 0
3 0
0 4
0 0

6 3
0 0
0 3
6 4
0 1
2 0
0 0

1 1427
0 0
*/