冲刺省选4月5日第四十五场
冲刺省选4月5日第四十五场
好累
真的好累。
虚数之树
题目
题目描述
给定一棵树，初始你拥有一个为空的点集，你需要完成以下操作：
1 x：往点集中加入点 \(x\)，保证该点先前不存在于点集。2 x：从点集中删除点 \(x\)，保证该点先前存在于点集。3 l r x：询问编号属于 \([l, r]\) 且在点集中的点与 \(x\) 最短距离的最小值。定义最短距离为树上两点之间简单路径边数。如果不存在满足要求的点，输出 ?1 且本次答案视为不合法。
题目样例
第一行输入 \(4\) 个整数 \(n, q, testid, type\)。其中 \(n\) 表示树的节点数，\(q\) 表示操作次
数，\(testid\) 表示测试点编号，\(type\) 意义见下文。
接下来 \(n ? 1\) 行，每行两个整数 \(u, v\)，表示一条树边 \((u, v)\)。
接下来 \(q\) 行，每行先给出一个整数 \(opt\) 表示操作类型，接下来一个或三个整数
表示操作参数，格式见题目描述。
对于每个 \(x\)（同题目描述），你需要执行赋值语句 \(x = x\oplus (lastans \times type)\) 以
获得真实的参数，其中 \(\oplus\) 为按位异或操作，\(lastans\) 为最近一次合法答案，初始值为 \(0\)。
regression.in
6 5 0 0
1 2
1 3
2 4
2 5
5 6
1 2
1 6
3 1 6 4
2 2
3 1 6
regression.out
1
3
数据范围与约定
对于全部的数据，满足 \(1\le n\le 10^5,1\le l,r,x\le n\)
强制在线
AC代码
#include
using std::cin;
using std::cout;
using std::vector;
using std::copy;
using std::reverse;
using std::sort;
using std::get;
using std::unique;
using std::swap;
using std::array;
using std::cerr;
using std::function;
using std::map;
using std::set;
using std::pair;
using std::mt19937;
using std::make_pair;
using std::tuple;
using std::make_tuple;
using std::uniform_int_distribution;
using std::lower_bound;
using std::upper_bound;
using ll = long long;
namespace qwq {
mt19937 eng;
void init(int Seed) { return eng.seed(Seed); }
int rnd(int l = 1, int r = 1000000000) { return uniform_int_distribution (l, r)(eng); }
}
template
inline T min(const T &x, const T &y) { return x < y ? x : y; }
template
inline T max(const T &x, const T &y) { return x > y ? x : y; }
template
inline void read(T &x) {
x = 0;
bool f = 0;
char ch = getchar();
while (!isdigit(ch)) f = ch == '-', ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
if (f) x = -x;
}
template
inline void read(T &x, Arg &... y) {
read(x);
read(y...);
}
#define O(x) cerr << #x << " : " << x << '\n'
const double Pi = acos(-1);
const int MAXN = 262144, MOD = 998244353, inv2 = (MOD + 1) / 2, I32_INF = 0x3f3f3f3f;
const long long I64_INF = 0x3f3f3f3f3f3f3f3f;
auto Ksm = [] (int x, int y) -> int {
if (y < 0) {
y %= MOD - 1;
y += MOD - 1;
}
int ret = 1;
for (; y; y /= 2, x = (long long) x * x % MOD) if (y & 1) ret = (long long) ret * x % MOD;
return ret;
};
auto Mod = [] (int x) -> int {
if (x >= MOD) return x - MOD;
else if (x < 0) return x + MOD;
else return x;
};
inline int ls(int k) { return k << 1; }
inline int rs(int k) { return k << 1 | 1; }
int vis[MAXN], sz[MAXN], fa[MAXN];
vector tr[MAXN], id[MAXN], dep[MAXN], seg[MAXN];
void divide(int u, int nds, int vk) {
int rt, cnt = 0;
function findrt = [&] (int x, int lst) -> void {
int mx = 0;
++cnt;
sz[x] = 1;
for (auto &i: tr[x]) if (i != lst && !vis[i]) {
findrt(i, x);
sz[x] += sz[i];
mx = max(mx, sz[i]);
}
if (max(mx, nds - sz[x]) <= nds / 2) rt = x;
};
findrt(u, -1);
if (vk) fa[rt] = vk;
vis[rt] = 1;
function dfs = [&] (int x, int lst, int _) -> void {
dep[x].push_back(_);
id[rt].push_back(x);
for (auto &i: tr[x]) if (i != lst && !vis[i]) dfs(i, x, _ + 1);
};
dfs(rt, 0, 0);
sort(id[rt].begin(), id[rt].end());
seg[rt] = vector(id[rt].size() * 4, I32_INF);
for (auto &i: tr[rt]) if (!vis[i]) {
if (sz[i] > sz[rt]) divide(i, nds - sz[rt], rt);
else divide(i, sz[i], rt);
}
}
void mfy(vector &v, int pos, int x) {
int n = v.size() / 4;
function dfs = [&] (int nw, int l, int r) -> void {
if (l == r) {
v[nw] = x;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) dfs(ls(nw), l, mid);
else dfs(rs(nw), mid + 1, r);
v[nw] = min(v[ls(nw)], v[rs(nw)]);
};
return dfs(1, 0, n - 1);
}
int main() {
freopen("regression.in", "r", stdin);
freopen("regression.out", "w", stdout);
qwq::init(20050112);
int N, Q, testid, type;
read(N, Q, testid, type);
for (int i = 1, x, y; i < N; ++i) {
read(x, y);
tr[x].push_back(y);
tr[y].push_back(x);
}
divide(1, N, 0);
// O(1);
for (int i = 1, opt, l, r, x, lstans = 0; i <= Q; ++i) {
read(opt);
if (opt == 1) {
read(x);
x ^= type * lstans;
function ins = [&] (int nw) {
int t = nw, r = dep[nw].size() - 1;
while (t) {
int pos = lower_bound(id[t].begin(), id[t].end(), nw) - id[t].begin();
mfy(seg[t], pos, dep[nw][r--]);
t = fa[t];
}
};
ins(x);
}
else if (opt == 2) {
read(x);
x ^= type * lstans;
function del = [&] (int nw) {
int t = nw;
while (t) {
int pos = lower_bound(id[t].begin(), id[t].end(), nw) - id[t].begin();
mfy(seg[t], pos, I32_INF);
t = fa[t];
}
};
del(x);
}
else {
read(l, r, x);
int kl = lstans;
x ^= type * lstans;
function qry = [&] (int ql, int qr, int nw) {
lstans = I32_INF;
int t = nw, r = dep[nw].size() - 1;
while (t) {
int pol = std::lower_bound(id[t].begin(), id[t].end(), ql) - id[t].begin();
int por = std::upper_bound(id[t].begin(), id[t].end(), qr) - id[t].begin() - 1;
function&, int, int)> qry = [&] (vector &jk, int _l, int _r) {
int n = jk.size() / 4;
function dfs = [&] (int k, int L, int R) -> int {
if (_l <= L && R <= _r) return jk[k];
int mid = (L + R) / 2, ret = I32_INF;
if (_l <= mid) ret = min(ret, dfs(ls(k), L, mid));
if (mid < _r) ret = min(ret, dfs(rs(k), mid + 1, R));
return ret;
};
return dfs(1, 0, n - 1);
};
if (pol <= por) lstans = min(lstans, qry(seg[t], pol, por) + dep[nw][r]);
--r;
t = fa[t];
}
};
qry(l, r, x);
if (lstans == I32_INF) {
puts("-1");
lstans = kl;
}
else printf("%d\n", lstans);
}
}
// cout << (-3 / 2);
cerr << ((double) clock() / CLOCKS_PER_SEC) << '\n';
return (0-0);
}
我的感觉是，其实强制在线可能让这道题变得更简单了，因为离线的话，可能会想一些奇怪的分块吧。
就你考虑个暴力，每次对于 \(x\) 这个节点，然后暴力跳父亲，之后每次枚举父亲的其他子树的点，求合法最小值和这个点的距离即可。
然后考虑优化这个暴力，写个点分树，然后每个节点存一个当前分治区域这些节点（标号为下标）的线段树维护到当前分治中心的最短距离即可。
之后在点分树上暴力跳父亲即可，每次在线段树上进行查询，时间复杂度为 \(O(N\log N+Q \log ^ 2N)\)
速通
题目
题目描述
你正在打一款可爱的小游戏，一局游戏的流程可以抽象为一个以 1 为根的树。
具体而言：
树的一个点代表一个关卡。由于你的技术炉火纯青，你通过第 i 个点代表的关
卡时会花费 x 的时间，其中 \(x\) 为 \([l_i, r_i]\) 中 均匀随机的一个整数。( 均匀随机指对于 \([l, r]\) 范围内的任意一个整数，它们出现的概率相同，且它们的概率之和为 \(1\) )。
当你完成一个非叶结点关卡 \(u\) 后，你可以选择两种操作：
- 按一定概率随机走向 \(u\) 的一个儿子 \(v\)，继续本局游戏。( 对于点 \(u\)，走向它的一个儿子 \(v\) 的概率为 \(p_v\)，保证 \(\sum _{v\in son(u)} p_v = 1\)
- 按下 R 键重开，即跳回到 1 号点开始新一局游戏。
对于任意一局游戏，将在 \(1\) 号点开始该局游戏，当完成一个叶子节点代表的关卡时视为游戏胜利。
注意上述过程我们只关注完成关卡的时间之和。( 忽略进入下一关与重开的瞬时时间)。
作为一名速通玩家，你希望能在 \(lim\) 的时间内完成一局游戏，所以你会选择在恰当的时候重开 ( 比如说后面在最优情况下时间也已经不够用了，选择重开就更优)。假设你一共进行了 \(k\) 局游戏，记这 k 局游戏的用时分别为 \(t_1, t_2, t_3, \cdots. t_k\)，并
且第 \(k\) 局游戏已经胜利，且 \(t_k \le lim\)，那么总用时 \(T =\sum _{i= 1}^k t_i\)i 。
求 $E(T)_{\min}，即选用最优策略下总用时的期望。
此外，当期望总用时过大时，你会异常暴躁以至于砸碎电脑，因此如果 \(E(T)_{\min} \ge 10^9\) 时，输出 ”Remake” ( 不含引号)
题目样例
第一行两个正整数 \(n, lim\) 分别表示树的点数与时间限制。
接下来 \(n\) 行，第 \(i\) 行两个非负整数 \(l_i, r_i\)，意义见上文。
接下来 \(n ? 1\) 行，第 \(i\) 行输入两个数 \(f_{i+1}, p_{i+1}\)，分别表示 \(i + 1\) 的父亲，以及 $f_{i+1} 走向 \(i + 1\) 的概率。( 保证 \(f_{i+1} < i + 1\)，且 \(p_{i+1}\) 为一个两位小数，对于任意非叶子结点，所有儿子的 \(p\) 之和为 \(1\)
共一行，一个非负小数 T 表示答案或”Remake” ( 不含引号 )。精度不超过 \(1e-5\)
isaac.in
2 17
9 10
7 8
1 1.00
isaac.out
22.666666667
数据范围与约定
对于全部的数据，满足 \(1\le n\le 100, limit\le 1000\)。
AC代码
#include
using std::cin;
using std::cout;
using std::vector;
using std::copy;
using std::reverse;
using std::sort;
using std::get;
using std::unique;
using std::swap;
using std::array;
using std::cerr;
using std::function;
using std::map;
using std::set;
using std::pair;
using std::mt19937;
using std::make_pair;
using std::tuple;
using std::make_tuple;
using std::uniform_int_distribution;
using ll = long long;
namespace qwq {
mt19937 eng;
void init(int Seed) { return eng.seed(Seed); }
int rnd(int l = 1, int r = 1000000000) { return uniform_int_distribution (l, r)(eng); }
}
template
inline T min(const T &x, const T &y) { return x < y ? x : y; }
template
inline T max(const T &x, const T &y) { return x > y ? x : y; }
template
inline void read(T &x) {
x = 0;
bool f = 0;
char ch = getchar();
while (!isdigit(ch)) f = ch == '-', ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
if (f) x = -x;
}
template
inline void read(T &x, Arg &... y) {
read(x);
read(y...);
}
#define O(x) cerr << #x << " : " << x << '\n'
const double Pi = acos(-1);
const int MAXN = 105, MOD = 998244353, inv2 = (MOD + 1) / 2, I32_INF = 0x3f3f3f3f;
const long long I64_INF = 0x3f3f3f3f3f3f3f3f;
auto Ksm = [] (int x, int y) -> int {
if (y < 0) {
y %= MOD - 1;
y += MOD - 1;
}
int ret = 1;
for (; y; y /= 2, x = (long long) x * x % MOD) if (y & 1) ret = (long long) ret * x % MOD;
return ret;
};
auto Mod = [] (int x) -> int {
if (x >= MOD) return x - MOD;
else if (x < 0) return x + MOD;
else return x;
};
inline int ls(int k) { return k << 1; }
inline int rs(int k) { return k << 1 | 1; }
const double eps = 1e-9;
int N, limit, L[MAXN], R[MAXN];
double f[MAXN][1005], p[MAXN];
vector t[MAXN];
void dfs(int u, double w) {
for (int i = 0; i <= limit; ++i) f[u][i] = 0;
for (auto &i: t[u]) {
dfs(i, w);
for (int j = 0; j <= limit; ++j) f[u][j] += p[i] * f[i][j];
}
for (int i = 0; i <= limit; ++i) f[u][i] = min(f[u][i], w);
double cyc = 1.0 / (R[u] - L[u] + 1);
for (int i = limit; ~i; --i) {
if (L[u]) f[u][i] = 0;
else f[u][i] *= cyc;
for (int j = max(1, L[u]); j <= R[u]; ++j) {
if (i >= j) f[u][i] += cyc * (f[u][i - j] + j);
else f[u][i] += cyc * (w + j);
}
}
}
int main() {
freopen("isaac.in", "r", stdin);
freopen("isaac.out", "w", stdout);
std::ios::sync_with_stdio(0);
cout << std::fixed << std::setprecision(8);
cin.tie(0);
cout.tie(0);
qwq::init(20050112);
cin >> N >> limit;
for (int i = 1; i <= N; ++i) cin >> L[i] >> R[i];
for (int i = 2, x; i <= N; ++i) {
cin >> x >> p[i];
t[x].push_back(i);
}
double L = 0, R = 1e9;
while (R - L > eps) {
double mid = (L + R) / 2;
dfs(1, mid);
if (f[1][limit] > mid) L = mid;
else R = mid;
}
if (L >= 1e9 - eps) cout << "Remake\n";
else cout << L << '\n';
// cout << (-3 / 2);
cerr << ((double) clock() / CLOCKS_PER_SEC) << '\n';
return (0-0);
}
设 \(f[i][j]\) 表示 \(i\) 节点，剩余时间是 \(j\) 然后完成的期望时间，把转移方程写出来。应该是你考虑他的所有转移儿子比如，然后枚举当前节点的花费 \(x\)，然后转移即可。
需要考虑的是有一个一键回城的东西，这玩意我们就是考虑取 min 即可。
这状态后效性很明显，我们可以高斯消元！
但是复杂度太高。咋办捏，发现可以二分答案，然后按照我们的那个答案 dp 出来另外一个答案，然后根据差的多少二分即可。
叮叮车
题目
题目描述
给定一个第一层有 \(n\) 个方格，第二层的最后有 \(n ? 1\) 个方格，第三层的最后有 \(n ? 2\) 个方格……总共有 \(n\) 层的阶梯状图形，定义 \(f(n)\) 为用最少的矩形不重叠地覆盖这个图形的方案数
定义 \(v_p[x]\) 表示 \(x\) 分解质因数后 \(p\) 的次数。
求 \(\max_{i=l}^r v_7[(i+1)f(i)]\)
题目样例
第一行一个整数 \(l\)。
第二行一个整数 \(r\)。
仅一行，一个整数表示答案。
dingdingcar.in
3 3
dingdingcar.out
0
数据范围与约定
AC代码
#include
using std::cin;
using std::cout;
using std::vector;
using std::copy;
using std::reverse;
using std::sort;
using std::get;
using std::unique;
using std::swap;
using std::array;
using std::cerr;
using std::function;
using std::map;
using std::set;
using std::pair;
using std::mt19937;
using std::make_pair;
using std::tuple;
using std::make_tuple;
using std::uniform_int_distribution;
using ll = long long;
namespace qwq {
mt19937 eng;
void init(int Seed) { return eng.seed(Seed); }
int rnd(int l = 1, int r = 1000000000) { return uniform_int_distribution (l, r)(eng); }
}
template
inline T min(const T &x, const T &y) { return x < y ? x : y; }
template
inline T max(const T &x, const T &y) { return x > y ? x : y; }
template
inline void read(T &x) {
x = 0;
bool f = 0;
char ch = getchar();
while (!isdigit(ch)) f = ch == '-', ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
if (f) x = -x;
}
template
inline void read(T &x, Arg &... y) {
read(x);
read(y...);
}
#define O(x) cerr << #x << " : " << x << '\n'
const double Pi = acos(-1);
const int MAXN = 262144, MOD = 998244353, inv2 = (MOD + 1) / 2, I32_INF = 0x3f3f3f3f;
const long long I64_INF = 0x3f3f3f3f3f3f3f3f;
auto Ksm = [] (int x, int y) -> int {
if (y < 0) {
y %= MOD - 1;
y += MOD - 1;
}
int ret = 1;
for (; y; y /= 2, x = (long long) x * x % MOD) if (y & 1) ret = (long long) ret * x % MOD;
return ret;
};
auto Mod = [] (int x) -> int {
if (x >= MOD) return x - MOD;
else if (x < 0) return x + MOD;
else return x;
};
inline int ls(int k) { return k << 1; }
inline int rs(int k) { return k << 1 | 1; }
char s_l[MAXN], s_r[MAXN];
int A[MAXN], B[MAXN], L[MAXN * 2], R[MAXN * 2];
void solve(char *s, int *C) {
*C = 0;
*A = strlen(s + 1);
for (int i = 1; i <= *A; ++i) A[i] = s[i] - '0';
std::reverse(A + 1, A + *A + 1);
while (*A) {
int ret = 0;
for (int j = *A; j >= 1; --j) {
ret = 10 * ret + A[j];
B[j] = ret / 7;
ret %= 7;
}
C[++*C] = ret;
*B = *A;
while (*B && !B[*B]) --*B;
*A = *B;
for (int i = 1; i <= *A; ++i) A[i] = B[i];
}
return;
}
int main() {
freopen("dingdingcar.in", "r", stdin);
freopen("dingdingcar.out", "w", stdout);
scanf("%s%s", s_l + 1, s_r + 1);
solve(s_l, L);
solve(s_r, R);
int ans = 0, xzh_a_k = 0, xzh_niu_bi = 0, flag = 0;
for (int i = *R; i >= 1; --i) {
if (L[i] < R[i] || flag) {
if (R[i] < 4) ans = max(ans, i - 1 + xzh_niu_bi);
else ans = max(ans, i + xzh_niu_bi + xzh_a_k);
}
if (R[i] == 3) ++xzh_a_k;
else if (R[i] < 3) xzh_a_k = 0;
else xzh_niu_bi += xzh_a_k + 1, xzh_a_k = 0;
if (L[i] != R[i]) flag = 1;
}
ans = max(ans, xzh_niu_bi);
printf("%d\n", ans);
return 0;
}
首先可以看出来 \(f(i)\) 其实就是卡特兰数，因为我们考虑枚举包含左下角的矩形就可以转化为递推式，和卡特兰数的一样的。
然后就变成了 \(v_7{\binom{2n}{n}}\)，然后根据库莫尔定理，转化为在 \(7\) 进制下的加法进位次数，然后考虑转化为高精度，枚举位数直接贪心就好了。