Home

# 鸽子要跑路

# 题目描述

鸽子位于平面直角坐标系上的整点 (a,b)(a, b)，每次可以朝上下左右四个方向选一个走一个单位长度，走的时候需要保证横纵坐标非负，目的地是 (c,d)(c, d)。
鸽子的初始疲劳值为 00，如果当前位置 (x,y)(x, y) 满足 x&y > 0 ，那么疲劳值加 11，否则不变。起点与终点的疲劳值不计入答案。
一共 T(1≤T≤105)T(1 \le T \le 10^5) 组数据，对于每组数据求从 (a,b)(a, b) 到 (c,d)(c,d) 的最小疲劳值。(0≤a,b,c,d≤1018)(0 \le a,b,c,d \le 10^{18})。

# 解题思路

是一道找规律题，先打一手表：

发现是个 谢尔宾斯基三角形。
答案有两种情况，一种是直接走，每一步都算入疲劳值；另一种是先走到一个 00 上，再找个最近的位置走到目标点 (所有的 00 都是联通的)
对于一个正方形的左上部分，是一种递归结构，可递归求解。当落入某个正方形的右下时，计算与边界的距离。

# Code

#define Aniciry Meteorshower_Y
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
auto _find(ll x, ll y, ll len) -> ll;
int T; ll a, b, c, d;
inline auto work() -> void;
signed main()
{
    scanf("%d", &T);
    while (T--) work();
    return 0;
}
inline auto work() -> void
{
    ll part1, part2, len;
    scanf("%lld%lld", &a, &b);
    scanf("%lld%lld", &c, &d);
    ll ans = abs(a-c)+abs(b-d);
    if(a != c or b != d) ans -= 1;
    len = 1;
    while(len <= max(a, b)) len <<= 1;
    part1 = _find(a, b, len);
    len = 1;
    while(len <= max(c, d)) len <<= 1;
    part2 = _find(c, d, len);
    ans = min(ans, part1+part2);
    printf("%lld\n", ans);
}
inline auto _find(ll x, ll y, ll len) -> ll
{
    if(x+y >= len) return min({len-x-1, len-y-1, x+y-len});
    len >>= 1;
    if(x == len or y == len) return 0;
    if(x > len) x -= len;
    if(y > len) y -= len;
    return _find(x, y, len);
}

# abab

# 题目描述

给一个只包含 a 和 b 的字符串，问最多有多少不相交的子序列 abab 。
共 TT 组数据，每组数据包含一个字符串 ss。(1≤T≤5,1≤∣s∣≤107)(1 \le T \le 5, 1 \le |s| \le 10^7)

# 解题思路

abab 可以拆成两个 ab , 所以问题就转化为了找出尽量多的不相交的 ab 。
记字符串中， ab 相互交错的数量最多的为 mxmx，一共能找到 cntcnt 对 ab 。

  1. 当 mx>⌊cnt2⌋mx > \left\lfloor\frac{cnt}{2}\right\rfloor 时，会剩下相互交错的不能匹配的 ab ，答案为 cnt−mxcnt-mx；
  2. 当 mx≤⌊cnt2⌋mx \le \left\lfloor\frac{cnt}{2}\right\rfloor 时，所有的 ab 一定能找到一种方案全部匹配，答案为 ⌊cnt2⌋\left\lfloor\frac{cnt}{2}\right\rfloor

# Code

#define Aniciry Meteorshower_Y
#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
using namespace std;
namespace Aniciry
{
    const int READSIZE = 100000;
    char ibuf[READSIZE], *p1, *p2, ch;
    #define isseen(ch) (ch > 32)
    #define isspace(ch) (ch <= 32 and ch != EOF)
    #define isdigit(ch) (ch >= '0' and ch <= '9')
    #define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,READSIZE,stdin),p1==p2)?(EOF):(*p1++))
    template <class T>
    inline auto read(T &x) -> void
    {
        x = 0; ch = getchar();
        while(!isdigit(ch) and ch != EOF) ch = getchar();
        if(ch == EOF) return void();
        while(isdigit(ch)) x = x*10+(ch-'0'), ch = getchar();
    }
    inline auto read(char &x) -> void
    {
        x = getchar();
        while(isspace(x)) x = getchar();
    }
    inline auto read(char *s) -> void
    {
        ch = getchar();
        while(isspace(ch)) ch = getchar();
        while(isseen(ch)) *s = ch, ++s, ch = getchar();
        *s = '\000';
    }
    template <typename T, typename ...T1>
    inline auto read(T &a, T1 &...other) -> void{
        return read(a), read(other...);
    }
}
using namespace Aniciry;
const int N = 1e7+10;
int T, n, d[N]; char s[N];
auto work() -> void;
int main()
{
    read(T);
    while(T--) work();
    return 0;
}
auto work() -> void
{
    stack<int> st; int mx = 0, cnt = 0;
    read(s+1); n = strlen(s+1);
    for(int i = 1; i <= n; i += 1) 
    {
        d[i] = 0;
        if(s[i] == 'a') st.push(i);
        else if(!st.empty()) d[st.top()] += 1, st.pop(), d[i] -= 1, cnt += 1;
    }
    for(int i = 1, now = 0; i <= n; i += 1)
        if(now += d[i], now > mx) mx = now;
    printf("%d\n", min(cnt/2, cnt-mx));
}

# 二叉树比大小

# 题目描述

用 00 代表空树，如果一个节点没有左子树，那么就认为它的左子树是空树（右子树同理）。对于任意二叉树 AA，0≤A0 \le A 成立；对于任意非空二叉树 AA，A≤0A \le 0 不成立。
用 lsls 代表左子树，rsrs 代表右子树，对于所有非空二叉树 AA，BB，A≤BA \le B 当且仅当 ls(A)≤ls(B)ls(A) \le ls(B) 且 rs(B)≤rs(A)rs(B) \le rs(A)；A=BA = B 当且仅当 A≤BA \le B 且 B≤AB \le A，否则 A≠BA \not = B。
给定节点编号为 1∼n1 \sim n 的二叉树 AA。 BB 的初始形态为 AA。对 BB 重复进行以下操作：任选 BB 中的一个儿子数量不超过 11 的节点，为这个节点增加一个儿子（使得 BB 仍然是二叉树）。左右有区别。
问有多少不同的 BB 满足 BB 的节点数为 n+mn+m 且 A≤BA \le B。

# 解题思路

如果 A≤BA \le B ，那么 AA 的每一个子树 A′A' 和它对应的 B′B'，都有大小关系的限制。这个限制要么是 A′≤B′A' \le B'，要么是 A′≥B′A' \ge B'。我们可以在要求 A′≤B′A' \le B' 的子树的根节点上标记状态 11 ，在要求 A′≥B′A' \ge B' 的子树的根节点上标记状态 00 。左儿子的状态和父节点相同，右儿子的状态和父节点相反。
我可以且只可以在状态为 11 的地方添加节点。可以用一次 dfs 找到所有可以添加新节点的位置。我们只关心这些位置的数量，设为 cc。
问题转化成这样：

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

记 dp[c][m]dp[c][m] 为上述问题的答案。

分类讨论第 cc 个位置上是否挂了新的节点，如果挂了一个节点，那么还需要的节点数少了 11，一共需要挂的位置多了 11；如果不挂这个节点，后面就不考虑他了，一共要挂的位置就少了 11。
所以转移方程为 dp[c][m]=dp[c+1][m−1]+dp[c−1][m]dp[c][m] = dp[c+1][m-1]+dp[c-1][m]。
把他看成在二维平面上的行走问题，则每次可以从 (x,y)(x,y) 走到 (x+1,y−1)(x+1,y-1) 和 (x−1,y)(x-1,y) (需要保证 x≥0x \ge 0)，问题是从 (1,0)(1,0) 走到 (c+m,m)(c+m,m)
然后把坐标转化一下，将 (x,y)(x,y) 转化为 (x+y,y)(x+y,y)， 那么从 (x,y)(x,y) 往后走一步走到的点就是 (x+1,y)(x+1,y) 和 (x,y+1)(x,y+1)，同时上面的限制就变成了要保证 x≤yx \le y，而问题是从 (0,1)(0,1) 走到 (m,c+m)(m,c+m)。总方案是 (c+2m+1m)\binom{c+2m+1}{m}，枚举每第一次超出限制的点，就和 No.3 Count 那道题一样，得到最后的答案为 (c+2m−1m)−(c+2m−1c+m)\binom{c+2m-1}{m}-\binom{c+2m-1}{c+m}.

# Code

#define Aniciry Meteorshower_Y
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
const int mod = 1914270647;
namespace Aniciry
{
    const int READSIZE = 100000;
    char ibuf[READSIZE], *p1, *p2, ch;
    #define isseen(ch) (ch > 32)
    #define isspace(ch) (ch <= 32 and ch != EOF)
    #define isdigit(ch) (ch >= '0' and ch <= '9')
    #define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,READSIZE,stdin),p1==p2)?(EOF):(*p1++))
    template <class T>
    inline auto read(T &x) -> void
    {
        x = 0; ch = getchar();
        while(!isdigit(ch) and ch != EOF) ch = getchar();
        if(ch == EOF) return void();
        while(isdigit(ch)) x = x*10+(ch-'0'), ch = getchar();
    }
    inline auto read(char &x) -> void
    {
        x = getchar();
        while(isspace(x)) x = getchar();
    }
    inline auto read(char *s) -> void
    {
        ch = getchar();
        while(isspace(ch)) ch = getchar();
        while(isseen(ch)) *s = ch, ++s, ch = getchar();
        *s = '\000';
    }
    template <typename T, typename ...T1>
    inline auto read(T &a, T1 &...other) -> void{
        return read(a), read(other...);
    }
}
using namespace Aniciry;
 
int n, m, cnt;
int ls[N], rs[N], vis[N];
ll fact[N*3], finv[N*3], ans;
__int128_t base = ((__int128_t)1<<64)/mod;
 
inline auto C(int n, int m) -> ll;
inline auto ksm(ll a, int b) -> ll;
inline auto prework(int n) -> void;
inline auto dfs(int x, int tp) -> void;
inline auto modp(const ll x) -> ll{return x-mod*(base*x>>64);}
 
int main()
{
    read(n, m); prework(3e6);
    for(int i = 1; i <= n; i += 1)
    {
        read(ls[i], rs[i]);
        vis[ls[i]] = vis[rs[i]] = 1;
    }
    for(int i = 1; i <= n; i += 1)
        if(!vis[i]) dfs(i, 1);
    ans = C(cnt+2*m-1, m)-C(cnt+2*m-1, cnt+m);
    printf("%lld", modp(ans+mod));
    return 0;
}
 
inline auto dfs(int x, int tp) -> void
{
    if(!x) return (void)(cnt += tp);
    dfs(ls[x], tp);
    dfs(rs[x], tp^1);
}
 
inline auto prework(int n) -> void
{
    fact[0] = finv[0] = 1;
    for(int i = 1; i <= n; i += 1) 
        fact[i] = modp(fact[i-1]*i);
    finv[n] = ksm(fact[n], mod-2);
    for(int i = n-1; i >= 1; i -= 1)
        finv[i] = modp(finv[i+1]*(i+1));
}
 
inline auto C(int n, int m) -> ll
{
    if(n < m) return 0;
    return modp(modp(fact[n]*finv[m])*finv[n-m]);
}
 
inline auto ksm(ll a, int b) -> ll
{
    ll ans = 1;
    for(; b; a = modp(a*a), b >>= 1)
        if(b&1) ans = modp(ans*a);
    return ans;
}