写在前面
\(T1\) 签到题。
\(T2\) 本以为什么神仙题（正解确实很神仙），但简单的二分贪心就能过掉， \kk。
\(T3\) 想到正解不会写就很悲，打的暴力
\(T4\) 神仙博弈论
A 题么么
solution
考试时想到此题正解，语言功能出现障碍，但表示不会描述此题做法。
尽量说一下吧。
就是两条相邻的横线一定会贯穿所有纵线，开两个 map 一个记录横线相邻两个颜色成对出现的次数，一个记录纵线相邻两个颜色成对出现的次数，然后对于每次询问，两个一乘就是答案，对于只有 \(1\) 满足条件的特殊处理一下编号就好了。
复杂度 \(O(2n + k)\), \(map\) 可能还会带个 \(log\)
code
/*
work by:Ariel_
*/
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int n, m, k, col[MAXN], tmp[MAXN];
map<int, map<int, int> >mp_1, mp_2, id_1, id_2;
int main(){
n = read(), m = read(), k = read();
for (int i = 1; i <= n + 1; i++) {
col[i] = read();
if(i != 1) mp_1[col[i - 1]][col[i]]++;
}
for (int i = 1; i <= n + 1; i++) {
tmp[i] = read();
if(i != 1) {
mp_2[tmp[i - 1]][tmp[i]]++;
}
}
for (int i = 2; i <= n + 1; i++) {
if(mp_1[col[i - 1]][col[i]] == 1) id_1[col[i - 1]][col[i]] = i - 1;
if(mp_2[tmp[i - 1]][tmp[i]] == 1) id_2[tmp[i - 1]][tmp[i]] = i - 1;
}
for (int i = 1; i <= k; i++) {
int a = read(), b = read(), c = read(), d = read();
if(mp_1[a][b] == 1 && mp_2[c][d] == 1) {
cout<<id_1[a][b]<<" " << id_2[c][d]<<"\n";
continue;
}
printf("%d\n", mp_1[a][b] * mp_2[c][d]);
}
system("pause");
return 0;
}
B. 题迷迷
题目描述
给定正整数 \(M, k\) 和一个长度为 \(n\) 的单调不下降序列 \(\{a\}\)，你需要找到满足如下要求的序列 \(\{b\}\)：
-
\(b_1 \geq 0\)
-
\(b_n \leq M\)
-
对于任意的 \(1 \leq i < n, b_{i + 1} \geq b_i + 2k\)
最小化 \(\max\{|a_i - b_i|\}\)。 数据保证这样的 \(\{b\}\) 存在。可以证明这个最小值一定是 \(\frac{1}{2}\) 的整数倍，所以直接输出答案的 2 倍。
数据范围
\(1 \leq n \leq 10^5, 1 \leq k \leq M \leq 10^8, 0 \leq a_i \leq M\)
solution
正解好像很麻烦的样子。
直接二分枚举最小距离，然后判断合不合法就好了。
为了避免实数二分，因为答案一定是 \(\frac{1}{2}\) 的整数倍，直接将 \(a\)， \(b\) 序列乘以 \(2\) 就好了，注意 \(k\) 和 \(m\) 也要乘。
\(b[i] = \max\{b[i - 1] + 2k, a[i] - mid\}\)， 判断一下合不合法就好了。
特殊的 \(b[1] = \max{0, a[1] - v}\)
复杂度 \(O(nlog2m)\)
code
/*
work by:Ariel_
*/
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
#define int long long
using namespace std;
const double eps = 1e-6;
const int MAXN = 1e5 + 5;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int n, m, k, b[MAXN], a[MAXN], Ans;
bool check(int mid) {
b[1] = max(0ll, a[1] - mid);
for (int i = 2; i <= n; i++) {
b[i] = b[i - 1] + k;
if(b[i] < a[i] - mid) b[i] = a[i] - mid;
else if(b[i] > a[i] + mid) return false;
if(b[i] > m) return false;
}
return true;
}
signed main(){
n = read(), m = read() * 2, k = read() * 4;
for (int i = 1; i <= n; i++) a[i] = read() * 2;
int l = 0, r = m;
while(l <= r) {
int mid = (l + r) >> 1;
if(check(mid)) Ans = mid, r = mid - 1;
else l = mid + 1;
}
printf("%lld", Ans);
system("pause");
return 0;
}
T3
原题和这个题只是稍微改一下不等号的方向就好了。
solution
线段树合并维护dp
设 \(f_{u,i}\)表示 \(u\) 的子树中的方案最大值，保证这个方案中点权最小值为 \(i\)，当不选 \(u\) 时，依如下递推式单次将 \(u\) 的集合（指之前扫过的儿子和自己构成的集合）与 \(v\) 的子树的 \(dp\) 信息合并（不存在方案设为 \(0\infty\)）
\(f_{new} = \max_{j \geq i}\{f_{u, i} + \max{v, j}, f(v, i) + \max_{j \geq i} f(u, j)\}\)
当选 \(u\) 时，依递推式
\(f(u, a_u) \leftarrow 1 + \sum_v max_{j \geq a_u} f(v, j)\)
线段树合并，我们将不存在方案的 \(dp\) 在实现是设为 \(0\) （也就是这里没有节点），选 \(u\) 时是单点改比较正常，在线段树合并（将 \(o'\) 合并到 \(o\) 上）时需要维护后缀 \(max\)，如果 \(o=\text{null}\) 时，需要一个区间加操作，且一开始为 \(0\) 的位置不能被加。所以要存储一个节点的 \(dp\) 最大值和有 \(dp\) 值的位置个数。时间复杂度 \(O(n\log n)\)。
code
/*
work by:Ariel_
*/
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
const int MAXN = 200005;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int N, a[MAXN], id[MAXN], rk[MAXN];
bool cmp(int x, int y) {return a[x] < a[y];}
struct edge{int v, nxt;}e[MAXN << 1];
int E = 1, head[MAXN];
void add_edge(int u, int v) {
e[++E] = (edge){v, head[u]};
head[u] = E;
}
int rt[MAXN];
namespace Seg {
int ls[MAXN * 30], rs[MAXN * 30], mx[MAXN * 30], tag[MAXN * 30], Tlen;
#define mid ((l + r) >> 1)
void pushUp(int o) { mx[o] = max(mx[ls[o]], mx[rs[o]]); }
void add(int o, int k) { if (mx[o]) mx[o] += k, tag[o] += k; }
void pushDown(int o) { if (tag[o]) add(ls[o], tag[o]), add(rs[o], tag[o]), tag[o] = 0; }
int query(int& o, int l, int r, int L, int R) {
if (!o) return 0;
if (l == L && r == R) return mx[o];
else {
pushDown(o);
if (R <= mid) return query(ls[o], l, mid, L, R);
else if (L > mid) return query(rs[o], mid + 1, r, L, R);
else return max(query(ls[o], l, mid, L, mid), query(rs[o], mid + 1, r, mid + 1, R));
}
}
void insert(int& o, int l, int r, int pos, int k) {
if (!o) o = ++Tlen;
if (l == r) {
mx[o] = max(mx[o], k);
}
else {
pushDown(o);
if (pos <= mid) insert(ls[o], l, mid, pos, k);
else insert(rs[o], mid + 1, r, pos, k);
pushUp(o);
}
}
void merge(int& o, int l, int r, int old, int mx1, int mx2) {
if (!o) o = old, add(o, mx1);
else if (!old) add(o, mx2);
else if (l == r) {
int val = max(mx[o] + mx[old], max (mx[o] + mx2, mx[old] + mx1));
mx[o] = val;
}
else {
pushDown(o), pushDown(old);
merge(ls[o], l, mid, ls[old], max(mx1, mx[rs[o]]), max(mx2, mx[rs[old]]));
merge(rs[o], mid + 1, r, rs[old], mx1, mx2);
pushUp(o);
}
}
}
using namespace Seg;
void dfs(int u, int ff) {
int qaq = 1;
for (int i = head[u]; i; i = e[i].nxt) if (e[i].v != ff) dfs(e[i].v, u), qaq += query(rt[e[i].v], 1, N, rk[u], N);
bool flag = 1;
for (int i = head[u]; i; i = e[i].nxt) if (e[i].v != ff) {
if (flag) rt[u] = rt[e[i].v], flag = 0;
else merge(rt[u], 1, N, rt[e[i].v], 0, 0);
}
insert(rt[u], 1, N, rk[u], qaq);
}
int ans;
int main() {
scanf("%d", &N);
for (int i = 1; i <= N; ++i) scanf("%d", &a[i]), id[i] = i;
sort(id + 1, id + N + 1, cmp);
for (int i = 1; i <= N; ++i) rk[id[i]] = rk[id[i - 1]] + (a[id[i - 1]] != a[id[i]]);
for (int i = 2, x; i <= N; ++i) scanf("%d", &x), add_edge(x, i);
dfs(1, 0);
printf("%d\n", query(rt[1], 1, N, 1, N));
system("pause");
return 0;
}
T4
题面描述
是一个麻将大师，你正在学博弈论。
博弈的规则是这样的：有 \(k\) 种不同的牌，每种有四张，其中有一些已经放在了桌子上。两个人轮流操作，任选一张牌放到桌子上（注意不能让桌子上的一种牌超过四张）。如果某个人操作后使桌子上的牌“和了”，则这个人输，另一个人胜。
关于“和了”的定义，分为两种情况：如果采用规则“无七对子”，“和了”需要保证有一种牌至少 \(2\) 张，另外不同的四种牌每种至少 \(3\) 张。如果采用规则“有七对子”，“和了”需要满足上一条的定义，或者有七种不同的牌每种至少 \(2\) 张。
双方都采用最优策略。给定开始时桌子上牌的状态，你需要求出在这一状态下，先手应该如何操作才能必胜。
数据范围
\(T\leq 10^4, 5 \leq k \leq 10^9, p \in \{0, 1\}\)
挖大坑 /kk