• 2022牛客多校（三）

    2022牛客多校（三）

    文章目录

    一、比赛小结

    比赛链接："蔚来杯"2022牛客暑期多校训练营3

    这场一堆神仙知识， 听都没听过 ，回头再补

    二、题目分析及解法（基础题）

    A、Ancestor

    题目链接：A-Ancestor_

    题意：

    给出两棵编号 1-n 的树A、B，A B树上每个节点均有一个权值，给出k个关键点的编号 x 1 , … , x n x_1,…,x_n x1​,…,xn​，问有多少种方案使得去掉恰好一个关键点使得剩余关键点在树A上LCA的权值大于树B上LCA的权值。

    题解：

    预处理出关键点序列的在树A B上的前缀LCA和后缀LCA，枚举去掉的关键节点并使用前后缀LCA算出剩余节点的LCA比较权值即可。

    代码：

    #include 
#include 
// #define int long long 会RE ？？？
using namespace std;
const int maxn = 2e5 + 5;
int n, k;
int pre1[maxn], deep1[maxn], num1[maxn], son1[maxn];  // 第一次dfs的变量
int dfn1[maxn], top1[maxn], rk1[maxn], id1;  // 第二次dfs的时候用到的变量
int val1[maxn], dfnval1[maxn];               // 建树时用dfn序下的val
int pre2[maxn], deep2[maxn], num2[maxn], son2[maxn];  // 第一次dfs的变量
int dfn2[maxn], top2[maxn], rk2[maxn], id2;  // 第二次dfs的时候用到的变量
int val2[maxn], dfnval2[maxn];               // 建树时用dfn序下的val
int head2[maxn], cnt2;
int x[maxn], a[maxn], b[maxn];
int anc1, anc2;

int preanc1[maxn], preanc2[maxn];
int last1[maxn], last2[maxn];
struct e {
  int to, next;
} edge1[maxn << 1], edge2[maxn << 1];
int head1[maxn], cnt1;
struct segtree {
  int l, r;
  int val, add;
} t1[maxn << 2];
void init() {
  cnt1 = 1, id1 = 0;
  memset(head1, -1, sizeof(head1));
  for (int i = 0; i < maxn; i++) edge1[i].next = -1;
  cnt2 = 1, id2 = 0;
  memset(head2, -1, sizeof(head2));
  for (int i = 0; i < maxn; i++) edge2[i].next = -1;
}
void addedge1(int u, int v) {
  edge1[cnt1] = e{v, head1[u]};
  head1[u] = cnt1++;
}
void addedge2(int u, int v) {
  edge2[cnt2] = e{v, head2[u]};
  head2[u] = cnt2++;
}
void predfs1(int u, int fa, int d) {
  deep1[u] = d, num1[u] = 1, pre1[u] = fa;
  for (int i = head1[u]; i != -1; i = edge1[i].next) {
    int v = edge1[i].to;
    if (v == fa) continue;
    predfs1(v, u, d + 1);
    num1[u] += num1[v];                        // 子树的节点数
    if (num1[son1[u]] < num1[v]) son1[u] = v;  // 重链子树的根节点
  }
}
void predfs2(int u, int fa, int d) {
  deep2[u] = d, num2[u] = 1, pre2[u] = fa;
  for (int i = head2[u]; i != -1; i = edge2[i].next) {
    int v = edge2[i].to;
    if (v == fa) continue;
    predfs2(v, u, d + 1);
    num2[u] += num2[v];                        // 子树的节点数
    if (num2[son2[u]] < num2[v]) son2[u] = v;  // 重链子树的根节点
  }
}
void dfs1(int u, int t) {
  dfn1[u] = ++id1, dfnval1[id1] = val1[u], top1[u] = t, rk1[id1] = u;
  if (!son1[u]) return;  // 按重链顺序进行dfs
  dfs1(son1[u], t);
  for (int i = head1[u]; i != -1; i = edge1[i].next) {
    int v = edge1[i].to;
    if (v == pre1[u] || v == son1[u]) continue;
    dfs1(v, v);  // 更新链首值top为v
  }
}
void dfs2(int u, int t) {
  dfn2[u] = ++id2, dfnval2[id2] = val2[u], top2[u] = t, rk2[id2] = u;
  if (!son2[u]) return;  // 按重链顺序进行dfs
  dfs2(son2[u], t);
  for (int i = head2[u]; i != -1; i = edge2[i].next) {
    int v = edge2[i].to;
    if (v == pre2[u] || v == son2[u]) continue;
    dfs2(v, v);  // 更新链首值top为v
  }
}
int lca1(int u, int v) {
  while (top1[u] != top1[v]) {
    if (deep1[top1[u]] > deep1[top1[v]])
      u = pre1[top1[u]];
    else
      v = pre1[top1[v]];
  }
  return deep1[u] > deep1[v] ? v : u;
}
int lca2(int u, int v) {
  while (top2[u] != top2[v]) {
    if (deep2[top2[u]] > deep2[top2[v]])
      u = pre2[top2[u]];
    else
      v = pre2[top2[v]];
  }
  return deep2[u] > deep2[v] ? v : u;
}
signed main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  init();
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= k; i++) scanf("%d", &x[i]);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i < n; i++) {
    int u;
    scanf("%d", &u);
    addedge1(u, i + 1);
    pre1[i + 1] = u;
  }
  for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
  for (int i = 1; i < n; i++) {
    int u;
    scanf("%d", &u);
    addedge2(u, i + 1);
    pre2[i + 1] = u;
  }
  predfs1(1, 0, 1);
  dfs1(1, 1);
  predfs2(1, 0, 1);
  dfs2(1, 1);
  preanc1[1] = x[1], preanc2[0] = x[0];
  for (int i = 2; i <= k; i++) {
    preanc1[i] = lca1(preanc1[i - 1], x[i]);
  }
  preanc2[1] = x[1], preanc2[0] = x[1];
  for (int i = 2; i <= k; i++) {
    preanc2[i] = lca2(preanc2[i - 1], x[i]);
  }
  last1[k] = x[k], last1[k + 1] = x[k];
  for (int i = k - 1; i >= 1; i--) {
    last1[i] = lca1(last1[i + 1], x[i]);
  }
  last2[k] = x[k], last2[k + 1] = x[k];
  for (int i = k - 1; i >= 1; i--) {
    last2[i] = lca2(last2[i + 1], x[i]);
  }
  int ans = 0;
  for (int i = 1; i <= k; i++) {
    int tmp1, tmp2;
    if (i == 1) {
      tmp1 = last1[i + 1];
      tmp2 = last2[i + 1];
    } else if (i == k) {
      tmp1 = preanc1[i - 1];
      tmp2 = preanc2[i - 1];
    } else {
      tmp1 = lca1(preanc1[i - 1], last1[i + 1]);
      tmp2 = lca2(preanc2[i - 1], last2[i + 1]);
    }
    // printf("%d %d\n", tmp1, tmp2);
    if (a[tmp1] > b[tmp2]) ans++;
  }
  printf("%d\n", ans);
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159

    C、Concatenation

    题目链接：C-Concatenation_

    题意：

    有若干个字符串，问如何拼接，可以使得所得到的总串字典序最小

    题解：

    这题真的很坑，挤牙膏般的优化，在进行 cmp 函数比较时，加上 const 和 & 可以节约不少时间

    还有一个点是 stable_sort 它可以保证在比较量相等时，要比较的两个元素相对位置不会改变，而 sort 则不能，前者是归并排序，后者是快排

    一般对于复杂的数据采用 stable_sort ，这样节省很多拷贝变量的时间

    代码：

    #include 
using namespace std;
const int maxn = 2e6 + 6;
bool cmp(const string &a, const string &b) { return a + b < b + a; }
string s[maxn];
int n;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> s[i];
  stable_sort(s, s + n, cmp);
  for (int i = 0; i < n; i++) cout << s[i];
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    H、Hacker

    题目链接：H-Hacker

    题意：

    给出一个文本串 A A A ， 和 k k k 个模式串，其长度为 m m m ，这些模式串不同位有不同的权值，现在要求你对这 m m m 个模式串求一个最大匹配值。其具体定义为：若某个模式串的 [ l , r ] [l,r] [l,r] 区间与 A A A 匹配，那么这个区间的值为 ∑ i = l r ω i \sum_{i=l}^{r}\omega_i ∑i=lr​ωi​ ，现在要求对于不同的模式串的最大的匹配值。

    题解：

    其实思路还是挺自然的，对这个 A A A 建立 SAM ，让这些模式串在 SAM 上匹配，假设对于模式串 B i B_i Bi​ 的第 j j j 个字符，它所匹配的 border 是 [ l , r ] [l,r] [l,r] ，那么就记录下 [ l , r ] [l,r] [l,r] 上权值的最大连续子段和。

    关于最大连续字段和，其实现原理是线段树，维护以下四个信息即可：区间最大前缀、区间最大后缀、区间总和、区间最大连续子段和即可。

    代码：

    #include 
#define ll long long
#define ls u << 1
#define rs u << 1 | 1
#define mm(x) memset(x, 0, sizeof(x))
using namespace std;
const int INF = 998244353;
const int P = 1e9 + 7;
const int N = 2e6 + 5;
int T;
int n, m, k;
char s[N];
char t[N];
int tot, las;
int ans;
int pos[N];
int len[N], fa[N], trip[N][26];
bool cmp(int a, int b) { return len[a] < len[b]; }
void extend(int u) {
  int p = las;
  int np = las = ++tot;
  // val[np]=1;
  len[np] = len[p] + 1;
  for (; p && !trip[p][u]; p = fa[p]) trip[p][u] = np;
  if (!p)
    fa[np] = 1;
  else {
    int q = trip[p][u];
    if (len[q] == len[p] + 1)
      fa[np] = q;
    else {
      int nq = ++tot;
      fa[nq] = fa[q];
      for (int i = 0; i < 26; ++i) trip[nq][i] = trip[q][i];
      len[nq] = len[p] + 1;
      fa[q] = fa[np] = nq;
      for (; p && trip[p][u] == q; p = fa[p]) trip[p][u] = nq;
    }
  }
}
ll val[N];
ll mn[N];
void build(int u, int l, int r) {
  if (l == r) {
    mn[u] = val[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(ls, l, mid);
  build(rs, mid + 1, r);
  mn[u] = min(mn[ls], mn[rs]);
}
ll query(int u, int l, int r, int L, int R) {
  if (L <= l && r <= R) return mn[u];
  int mid = (l + r) >> 1;
  ll res = 1e15;
  if (L <= mid) res = min(res, query(ls, l, mid, L, R));
  if (R > mid) res = min(res, query(rs, mid + 1, r, L, R));
  return res;
}
void solve() {
  scanf("%s", s + 1);
  ll res = 0;
  for (int i = 1, cur = 1, plen = 0; i <= m; ++i) {
    int ch = s[i] - 'a';
    while (cur && !trip[cur][ch]) cur = fa[cur], plen = len[cur];
    if (!cur)
      cur = 1;
    else {
      cur = trip[cur][ch];
      plen++;
    }
    ll tmp = query(1, 0, m, i - plen, i);
    res = max(res, val[i] - tmp);
  }
  printf("%lld\n", res);
}
int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  scanf("%d%d%d", &n, &m, &k);
  scanf("%s", s + 1);
  tot = las = 1;
  for (int i = 1; i <= n; ++i) extend(s[i] - 'a');
  // for (int i = 1; i <= n; ++i) pos[i] = tot + 1, extend(s[i] - 'a');
  for (int i = 1; i <= m; ++i) scanf("%lld", &val[i]);
  for (int i = 1; i <= m; ++i) val[i] += val[i - 1];
  build(1, 0, m);
  for (int i = 1; i <= k; ++i) solve();
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91

    J、Journey

    题目链接：J-Journey_

    题意：

    给出一张城市地图，求从起点走到终点的最短时间

    题解：

    建图，跑下 dijkstra 即可

    代码：

    #include 
#define pii pair<int, int>
using namespace std;
const int maxn = 5e5 + 5;
const int inf = 0x3f3f3f3f;
int n, s1, s2, t1, t2, dir1, dir2;
struct Node {
  int a[5];
} e[maxn];
int dis[5][maxn];
bool vis[5][maxn];
void bfs() {
  queue<pii> q;
  for (int i = 1; i <= 4; i++)
    if (e[s2].a[i] == s1) dir1 = i;
  for (int i = 1; i <= 4; i++)
    if (e[t2].a[i] == t1) dir2 = i;
  q.push(pii(dir1, s2));
  vis[dir1][s2] = 1;
  dis[dir1][s2] = 0;
  while (!q.empty()) {
    pii now = q.front();
    q.pop();
    int start = now.second, tdir = now.first;
    vis[tdir][start] = 0;
    for (int i = 1; i <= 4; i++) {
      int w = 1, v = e[start].a[i], vdir;
      if (v == 0) continue;
      if (i == tdir % 4 + 1) w = 0;
      for (int j = 1; j <= 4; j++)
        if (e[v].a[j] == start) vdir = j;
      if (dis[vdir][v] > dis[tdir][start] + w) {
        dis[vdir][v] = dis[tdir][start] + w;
        if (!vis[vdir][v]) q.push(pii(vdir, v)), vis[vdir][v] = 1;
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  memset(dis, 0x3f, sizeof dis);
  cin >> n;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= 4; j++) cin >> e[i].a[j];
  cin >> s1 >> s2 >> t1 >> t2;
  bfs();
  if (dis[dir2][t2] != inf)
    cout << dis[dir2][t2] << endl;
  else
    cout << -1 << endl;
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    三、题目分析及解法（进阶题）

    不会做X

    B、to-do

    D、to-do

    E、

    F、to-do

    G、

    I、

  • 相关阅读:
    浅析Betaflight中的OSD叠加程序【MAX7456&AT7456】
    十一、【吸取工具组】
    Linux防火的常用命令
    Vue3---uni-app--高德地图引用BUG
    JavaScript面试刷题指南
    “人间烟火”背后，长沙招商引资再出圈
    统计一个十进制数 的二进制中有多少个1
    Linux_day12_LVM
    计算机毕业设计（附源码）python在线课堂管理平台
    JavaScript 清空数组的方法大全
  • 原文地址：https://blog.csdn.net/m0_54646258/article/details/126799382