鸽子要跑路

Description

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

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

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

Input

第一行数据组数 TT。

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

Output

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

Hint

T≤105,a,b,c,d≤1018T \le 10^5, a,b,c,d \le 10^{18}。

Solution

打个表可以发现，xand⁡y=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) 且 x≤yx \le y，观察规律可以发现每一级三角形的边长都是 22 的整次幂，所以我们找到第一个大于 yy 的 22 的整次幂，设为 LL，如果 x+y≥Lx+y \ge L 的，说明 (x,y)(x,y) 已经在正方形的右下部分了，可以直接计算到边界的距离，否则可以使 y←y−L/2y \leftarrow y-L/2，重复以上步骤。

这样做每次可以使 yy 坐标减小至少一半，所以单次询问是 O(log⁡A)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

给你一个只包含字符 a 和 b 的字符串 ss，你需要求出最多有多少不相交的子序列 abab。

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

Input

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

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

Output

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

Hint

∣s∣≤107,1≤T≤5|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，共有 cntcnt 对 ab，那么答案就是 min⁡(⌊cnt2⌋,cnt−mx)\min(\lfloor \frac{cnt}{2} \rfloor, cnt-mx)。

这个 min⁡\min 的式子含义是：如果 mx≤⌊cnt2⌋mx \le \lfloor \frac{cnt}{2} \rfloor，那么就可以让所有的 ab 两两匹配，如果 mx>⌊cnt2⌋mx > \lfloor \frac{cnt}{2} \rfloor，那么有 cnt−mxcnt-mx 个 ab 是和这 mxmx 个 ab 不相交的，所以这 cnt−mxcnt-mx 个 ab 可以直接匹配这 mxmx 个相交的 ab，可以得到 cnt−mxcnt-mx 个 abab。

现在就需要使 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 代表空树，如果一个节点没有左子树，那么认为它的左子树是空树(右子树同理)。对任意二叉树 AA，0≤A0 \le A 成立；对任意非空二叉树 AA，A≤0A \le 0 不成立。用 ls⁡\operatorname{ls} 代表左子树，rs⁡\operatorname{rs} 代表右子树，则对于非空二叉树 A,BA,B，A≤BA \le B 当且仅当 ls⁡(A)≤ls⁡(B)\operatorname{ls}(A) \le \operatorname{ls}(B) 且 rs⁡(B)≤rs⁡(A)\operatorname{rs}(B) \le \operatorname{rs}(A)。

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

问有多少不同的 BB 满足 BB 的节点数为 n+mn+m 且 A≤BA \le B。

Input

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

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

Output

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

Hint

n,m≤106n,m \le 10^6。

Solution

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

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

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

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

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

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

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

所以 f(c,m)=f(c+1,m−1)+f(c−1,m)f(c,m) = f(c+1,m-1) + f(c-1, m)。

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

如果位置在 (x,y)(x,y)，下一步可以走到 (x−1,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+2m−1m−Cc+2m−1cC_{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
*/