鸽子要跑路
Description
鸽子一开始位于平面直角坐标系上的整点 (a,b),每次可以上下左右走一个单位(保证坐标非负)。鸽子的家在 (c,d)。
鸽子的疲劳值初始值为 0。如果鸽子当前位置 (x,y) 满足 xandy>0,鸽子的疲劳值就要加 1,否则疲劳值不增加。and 是按位与。起点与终点的疲劳值不计入答案。
求鸽子回家的最小疲劳值。
第一行数据组数 T。
接下来 T 行,每行四个整数 a,b,c,d。
Output
T 行,每行一个整数表示答案。
Hint
T≤105,a,b,c,d≤1018。
Solution
打个表可以发现,xandy=0 的位置组成了一个谢尔宾斯基三角形,而且是四联通的,所以我们从 (a,b) 走到 (c,d) 就有两种方案:
- 先从 (a,b) 走到三角形上,再走到 (c,d)。
- 直接从 (a,b) 走到 (c,d)。
第二种走法很好算,第一种需要我们计算出每个点到谢尔宾斯基三角形的最近距离。
考虑谢尔宾斯基三角形是个分形,我们可以通过适当地缩放坐标来方便计算。
因为它是沿对角线对称的,所以不妨设当前坐标为 (x,y) 且 x≤y,观察规律可以发现每一级三角形的边长都是 2 的整次幂,所以我们找到第一个大于 y 的 2 的整次幂,设为 L,如果 x+y≥L 的,说明 (x,y) 已经在正方形的右下部分了,可以直接计算到边界的距离,否则可以使 y←y−L/2,重复以上步骤。
这样做每次可以使 y 坐标减小至少一半,所以单次询问是 O(logA) 的,其中 A 是坐标的值域。
#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; }
|
啊吧啊吧
Description
给你一个只包含字符 a
和 b
的字符串 s,你需要求出最多有多少不相交的子序列 abab
。
不相交的定义为:对于 s 种的每个字符,其最多处于一个子序列中。
第一行 T,代表数据组数。
接下来 T 行,每行一个字符串 s。
Output
共 T 行,表示每组数据的答案。
Hint
∣s∣≤107,1≤T≤5。
Solution
发现 abab
可以拆成两个 ab
,问题就变成了去除尽可能多的不相交的 ab
。
不能同时选的 ab
存在一个分界点 p∈[1,n],使得所有 a
的位置小于等于 p,所有 b 的位置大于等于 p。
设不能同时选的 ab
的最大值为 mx,共有 cnt 对 ab
,那么答案就是 min(⌊2cnt⌋,cnt−mx)。
这个 min 的式子含义是:如果 mx≤⌊2cnt⌋,那么就可以让所有的 ab
两两匹配,如果 mx>⌊2cnt⌋,那么有 cnt−mx 个 ab
是和这 mx 个 ab
不相交的,所以这 cnt−mx 个 ab
可以直接匹配这 mx 个相交的 ab
,可以得到 cnt−mx 个 abab
。
现在就需要使 mx 最小化,这个可以使每个 b 去匹配它前面最近的未被匹配的 a,这样可以使这一对 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
用 0 代表空树,如果一个节点没有左子树,那么认为它的左子树是空树(右子树同理)。对任意二叉树 A,0≤A 成立;对任意非空二叉树 A,A≤0 不成立。用 ls 代表左子树,rs 代表右子树,则对于非空二叉树 A,B,A≤B 当且仅当 ls(A)≤ls(B) 且 rs(B)≤rs(A)。
给定节点编号为 1∼n 的二叉树 A。 B 的初始形态为 A。对 B 重复进行以下操作:任选 B 中的一个儿子数量不超过 1 的节点,为这个节点增加一个儿子(使得 B 仍然是二叉树)。左右有区别。
问有多少不同的 B 满足 B 的节点数为 n+m 且 A≤B。
第一行两个整数 n,m。
接下来 n 行,给出二叉树 A。第 i+1 行有两个整数,第一个是 i 号节点的左儿子编号,第二个是右儿子编号(没有用 0 代替)。
Output
一个整数表示方案数,对 1914270647 (一个质数)取模。
Hint
n,m≤106。
Solution
如果 A≤B,那么 A 的每一个子树 A′ 和它对应的 B′ 都有大小关系的限制,要么是 $ A’ \le B’$ ,要么是 A′≥B′。我们可以在要求 A′≤B′ 的子树的根上标记状态为 1,在要求 A′≥B′ 的子树的根上标记状态为 0。左儿子状态与父亲相同,右儿子状态与父亲相反。
我们只能在 1 的地方添加节点。可以遍历一遍 A 找到所有能添加新节点的位置,我们只需要关系这些位置的数量,设为 c。问题转化为:
有 c 个互相独立的位置,放上 m 个节点,问最终形成的二叉树森林有几种。
设 f(c,m) 表示上述问题的答案。
分类讨论是否有节点挂在第 c 个位置。
-
如果有一个节点挂在第 c 个位置,节点数减少 1,互相独立的位置数反而增加了 1,状态转移为 f(c+1,m−1)。
-
如果没有节点挂在第 c 个位置,也就是再也不用位置 c,状态转移为 f(c−1,m)。
所以 f(c,m)=f(c+1,m−1)+f(c−1,m)。
这个式子可以转化为路径计数:
如果位置在 (x,y),下一步可以走到 (x−1,y+1) 或 (x+1,y),但始终保证 x>0,求从 (1,0) 走到 (c,m) 的路径条数。
把坐标变换为 (x+y,y),得到更熟悉的形式:
如果位置在 (x,y),下一步可以走到 (x,y+1) 或 (x+1,y),但始终保证 x>y,求从 (1,0) 走到 (c+m,m) 的路径条数。
这个很明显就是卡特兰数了,答案为 Cc+2m−1m−Cc+2m−1c。
#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; }
|