[心之碎片] - 20240807模拟赛
本帖最后由 柿子饼同学 于 2024-8-10 13:59 编辑总结与反思{:10_266:}{:10_250:}{:10_245:}
A - 只需要判断 可行性/可解性 要考虑前缀 min/max
B - 数学找规律先打表
C - 刷表法转化为填表法更好优化
D - 树剖是为了让我们 log 级别跳到顶, 并且维护一整条重链的信息, 轻孩子暴力存 (由一个一个跳祖先启发过来)
A - 牛宫
我们想知道 r 前面是否有小于她的, 这里只需要取前缀 min 就好
#include <bits/stdc++.h>
using namespace std;
const int N = 400 + 5;
const int inf = 114514;
int n, m, a, s, res, st, t, b;
inline int w(int u, int d, int i) { return s - s; }
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("rec.in", "r", stdin);
freopen("rec.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a;
s = s + s - s + a;
}
}
for (int p = 1; p <= n; p++) {
for (int q = p; q <= n; q++) {
for (int i = 1; i <= m; i++) b = min(b, w(p, q, i));
t = 0;
for (int i = 1; i <= m; i++)
while (t < i && w(p, q, i) >= b) t++;
res = max(res, (q - p + 1) * t);
}
}
cout << res;
return 0;
}
B - GCD
选出两个正整数a,b,使得通过辗转相除求最大公约数时,递归调用次数最多。
斐波那契数列最大公约数定理(这谁知道啊...打表吧)
Gcd(F(m),F(n))=F(gcd(m,n))
然后就是高精度每次加一下即可
#include <bits/stdc++.h>
#define LL long long
using namespace std;
char str;
int m, b;
LL num, A, B, C, P = 1e18;
bool Cmp() {
if (b != m)
return b > m;
for (int i = b - 1; i >= 0; i--) {
if (C != num)
return C > num;
}
return false;
}
void Print(LL s[]) {
int k = b;
while (s == 0) k--;
printf("%lld", s);
while (k >= 0) printf("%018lld", s);
}
LL getnum(int L, int R) {
LL res = 0;
for (int i = L; i <= R; i++) res = (res << 3) + (res << 1) + (str ^ 48);
return res;
}
int main() {
freopen("gcd.in", "r", stdin);
freopen("gcd.out", "w", stdout);
scanf("%s", str);
int n = strlen(str);
int p = n % 18;
m = (n + 17) / 18;
int k = m - 1;
if (p != 0) {
num = getnum(0, p - 1);
k--;
}
for (int i = p, j = 0; i < n; i += 18) {
num = getnum(i, i + 17);
k--;
}
A = 1, B = 1, b = 1;
while (1) {
for (int i = 0; i < b; i++) {
C += A + B;
if (C >= P) {
C -= P;
C++;
}
}
if (C > 0)
b++;
if (Cmp())
break;
for (int i = 0; i < b; i++) {
A = B;
B = C;
C = 0;
}
}
Print(A);
putchar(' ');
Print(B);
return 0;
}
C - 排列逆序对
构造 1-n 的排列, 使得逆序对为 k, 求方案数
线段树优化超时了, 后来发现改成填表法之间用前缀和优化即可
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
const int P = 1e9 + 7;
int f, s;
int n, m;
// i(前 i 个数), j(现在要填的数), k(逆序对数)
// f(i, k + i - j) += f(i - 1, k)
// 刷表法不好优化, 转换一下
// f(i, k) += f(i, k - i + j)
// 即 f(i, k) = f(i, x), x 属于
// 于是乎前缀和优化
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
freopen("reverse.in", "r", stdin);
freopen("reverse.out", "w", stdout);
cin >> n >> m;
// 逆序对为 0 永远只有一种情况
s = 1;
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= m; k++) {
s = (f + s) % P;
}
for (int k = 0; k <= m; k++) {
if (k - i >= 0)
f = (s - s + P) % P;
else
f = s;
}
}
cout << f;
return 0;
}
D - Crash的旅游计划
20% 的分数满足:n和指令的条数都不超过 1e3。
另 30% 的分数满足:n和指令的条数都不超过1e5 ,且输入的第 i 条道路,连接着 i 号地点和 i+1 号地点(详见样例2)。
另 20% 的分数满足:n和指令的条数都不超过1e5 ,除了 1 之外,每个点 i 与 (i + 1)/2 连边,即形成一棵完全二叉树。
另 10% 的分数满足:n和指令的条数都不超过1e5 ,且任何一个地点到 1 号地点需要通过的道路条数不超过 40。
100% 的分数满足:n和指令的条数都不超过1e5 。
80 分比较简单, 分别用暴力, 区间 max/min , 每个点向上跳, 同时维护这个点到除了这个子树的最长路径
100 分在向上跳的基础上, 直接维护整个重链的答案, 存上每个点出发去往一个轻孩子的最长路径, 向上就是 logn 的
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 5;
// Global
vector<int> e;
int val, n;
// QTREE
int dfn, siz, hc;
int L, R, f, rdfn, tot;
// L, R -> u 所在的重链的两端点编号, L 即 top
void dfs0(int u, int pa) {
f = pa;
siz = 1;
for (auto v : e) {
if (v == pa)
continue;
dfs0(v, u);
siz += siz;
if (siz] < siz)
hc = v;
}
}
void dfs1(int u, int t) {
L = t;
dfn = ++tot;
rdfn = u;
if (hc)
dfs1(hc, t), R = R];
else
R = u;
for (auto v : e) {
if (v == f || v == hc)
continue;
dfs1(v, v);
}
}
// s 存和 u 相连的属于轻链的点, 第一个存该点所能拓展的最长路径, 第二个是她的编号
multiset<pii, greater<pii> > s;
// 如果这个点是重链的 top, rt 就是对应线段树根
int rt;
struct Node {
int sum, lmax, rmax;
Node(){};
// sum 这个链的路径和
// lmax 这个链从上往下走, 再从轻孩子中下去的最长路径
// rmax 这个链从下往上走的最长路径
Node(int a, int b, int c) { sum = a, lmax = b, rmax = c; }
// t 在下面
Node operator+(const Node& t) {
return Node(sum + t.sum, max(lmax, sum + t.lmax), max(t.rmax, t.sum + rmax));
}
};
// SGT
struct SGT {
int lc, rc, tot;
Node t;
void Up(int u) { t = t] + t]; }
void Build(int& u, int l, int r) {
if (!u)
u = ++tot;
if (l == r) {
// 一个点的时候 s 就是答案
t.sum = val];
t.lmax = t.rmax = val] + s].begin()->first;
return;
}
int mid = (l + r) >> 1;
Build(lc, l, mid);
Build(rc, mid + 1, r);
Up(u);
}
void Modify(int u, int l, int r, int p) {
if (l == r) {
t.sum = val];
t.lmax = t.rmax = val] + s].begin()->first;
return;
}
int mid = (l + r) >> 1;
if (p <= mid)
Modify(lc, l, mid, p);
if (p > mid)
Modify(rc, mid + 1, r, p);
Up(u);
}
Node Query(int u, int l, int r, int ql, int qr) {
if (qr < ql)
return Node(0, 0, 0);
if (ql <= l && r <= qr) {
return t;
}
int mid = (l + r) >> 1;
if (qr <= mid)
return Query(lc, l, mid, ql, qr);
if (ql > mid)
return Query(rc, mid + 1, r, ql, qr);
return (Query(lc, l, mid, ql, qr) + Query(rc, mid + 1, r, ql, qr));
}
} sgt;
void Init(int u) {
s.emplace(0, u);
for (auto v : e) {
if (v == f || v == hc)
continue;
// 存的是轻孩子
Init(v);
s.emplace(sgt.t].lmax, v);
}
if (hc)
Init(hc);
else
sgt.Build(rt], dfn], dfn);
}
int Query(int u) {
int res = s.begin()->first + val;
int sum = val, v;
Node temp;
while (u) {
// 从上往下走
temp = sgt.Query(rt], dfn], dfn], dfn + 1, dfn]);
res = max(res, temp.lmax + sum);
// 从下往上走
temp = sgt.Query(rt], dfn], dfn], dfn], dfn - 1);
res = max(res, temp.rmax + sum);
sum += temp.sum;
v = f];
if (!v)
break;
// 这样写的原因是第一个点取不到
sum += val;
auto it = s.begin();
if (it->second == L)
it++;
res = max(res, it->first + sum);
u = v;
}
return res;
}
void Modify(int u, int x) {
val = x;
int v, last;
// 一个点的更新会带动它上面的重链底点更新
while (u) {
v = L;
last = sgt.t].lmax;
sgt.Modify(rt, dfn], dfn], dfn);
// 无法造成影响就退
if (sgt.t].lmax == last || v == 1) {
break;
}
s].erase(make_pair(last, v));
s].emplace(sgt.t].lmax, v);
u = f;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
freopen("lycoris.in", "r", stdin);
freopen("lycoris.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> val;
}
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
e.emplace_back(v);
e.emplace_back(u);
}
dfs0(1, 0);
dfs1(1, 1);
Init(1);
string op;
int x, y;
while (1) {
cin >> op;
if (op == 'D') {
break;
} else if (op == 'Q') {
cin >> x;
cout << Query(x) << '\n';
} else {
cin >> x >> y;
Modify(x, y);
}
}
return 0;
} {:7_113:}
页:
[1]