2018-2019 ACM-ICPC, Asia Jiaozuo Regional Contest gym102028

(Updated: )
(10 mins to read)

前五题不难（银），第六题（B or H）都不会

A

真签到

D

初中题，有点烦有两种情况，懒得写了

E

很容易打表找到规律

F

很直白的bfs，需要对给出的图进行一些转化（我的转化方法不太好，导致有点难写）

I

横轴上有n个点，让你选择k个点，最大化他们两两之间距离的和k从1~n都回答一遍两个点一定是取最左和最右，三个点随便再取一个，四个点一定是取最左两个和最右两个，那么结论就很显然了

H

给定n个数，定义一个子区间的值为该区间的最大值，让你求所有本质不同的子区间的值的和没有本质不同那就很模板了，单调栈或者笛卡尔树即可但是本质不同就很棘手，想了想后缀自动机感觉做不了，又想了想单调栈和笛卡尔树感觉也不行，哈希也没法搞。看到题解的后缀数组后就知道了。忘了本质不同还可以后缀数组了。先想一下后缀数组是怎么求本质不同的串的，就是求出$height_i$​，那么对于从位置i开始的后缀，他会多统计$height_{rk_i}$​​个前缀，即从i开始，以$i$ ~ $i+height_{rk_i}-1$结束的这些区间的值重复算了，减掉即可令$r_i = i+height_{rk_i}-1$先建出笛卡尔树，对于当前点u，当前范围为[L,R],则左子树内所有$r_i$​大于等于u的，都要减掉$a_u$​的贡献即要求出左子树(包括u)内$\sum_{i=L}^u max(r_i-u+1,0) -\sum_{i=L}^u max(r_i-R,0)$可以用线段树合并来维护

这题发现了我sa板子的一个问题，在求height数组的时候要注意i+k和j+k的范围，否则在多组数据+数组是int的时候会挂掉

1
while(i+k<=n&&j+k<=n&&a[i+k]==a[j+k]) k++;

B

有两种怪物，血量攻击力分别为$HP_A,ATK_A,HP_B,ATK_B$第i回合你会先受到活着的怪物的攻击，然后你可以选择一只怪物造成i的伤害，让你最小化自己所受的伤害的同时最小化攻击序列的字典序（尽可能优先打A）先考虑怎么最小化自己受到的伤害定义f(t)表示最小的x，使得$\sum_{i=1}^x \geq t$一定是在$f(HP_A+HP_B)$回合以内，先优先打死A，或者先优先打死B考虑先打死A，如果前$f(HP_A)$回合都用来打A，剩余回合打B也能把B打死那这就是最优的，否则假设缺了x点伤害，打A富余了y点伤害，必然有关系$y\geqx$，为了让B尽可能靠后，只要在第y回合改成打B即可考虑先打死B，先在前$f(HP_B)$回合都打B，后面打A，如果打B富余了x点伤害，我们让前$f(x+1)-1$个回合改成打A即可，如果A还缺了x的伤害，那就让前面最后一下打A延迟x回合

C

一个$n \times n$的棋盘，每一列上都一个棋子（且都不同行），现在有四种操作和两种询问

  • L K：所有棋子同时向左移动k步，如果碰到边界就不动
  • R K：所有棋子同时向右移动k步，如果碰到边界就不动
  • U K：所有棋子同时向上移动k步，如果碰到边界就不动
  • D K：所有棋子同时向下移动k步，如果碰到边界就不动
  • 询问初始第i个棋子现在的位置
  • 询问有多少对棋子现在在同一个位置上

$n \leq 3\times 10^5$这种二维问题，一个想法就是行列分离做，这边显然也可以行列分离转成一维去思考就考虑所有棋子在一条横轴上，可以同时左右移动k步对于碰到过左边界的棋子，以后就永远在一起了，右边界也是这样第一步左移k，那么1~k的棋子之后就相同了另一个套路是n个棋子一起动不好维护，那么我们去维护边界，左移k，我们让左边界右移k就行了，这样$\leq$左边界的棋子都相当于是在左边界上，这样一来相当于是左右边界不断在向中间靠拢，因为不断移动下去合并的棋子就越来越多了。但是我们维护的并不是真实的左边界坐标，所以还需要维护一个变量d。左移就让d+k，右移就让d-k，则l-k和r-k就是真实的边界了，当然还需要保证真实边界在1~n范围内，因为碰到边界就不动了这样横轴纵轴分别维护就可以解决第一个询问了，对于第二个询问，我们相当于是LRDU四个边界在不断的往中间压缩，由于初始行列均不同，要位于同一个格子，必须同在LR轴中的一个，UD轴的一个，用四个变量LD，LU，RD，RU分别维护一下，注意特判L=R，D=U的情况。具体维护的话，因为lrud这四个轴都是单调变化的，那么每次移动的时候判断一下当前碰到边界的点即可，注意不要重复统计。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e5 + 5;
int n, m, ul, ur, dl, dr;
bool vis[N];
ll C[N];
void check(int id);
struct Bound
{
  int l, r, d;
  int p[N], id[N];
  void init(int n) { l = 1, r = n, d = 0; }
  void set(int x, int y) { p[x] = y, id[y] = x; }
  void movel(int k)
  {
    while(l<r && l+d-k<1) check(id[++l]);
    if(l+d-k>=1) d -= k;
    else d = 1 - l;
  }
  void mover(int k)
  {
    while(l<r && r+d+k>n) check(id[--r]);
    if(r+d+k<=n) d += k;
    else d = n - r;
  }
  int get(int k)
  {
    if(p[k]<=l) return l + d;
    else if(p[k]>=r) return r + d;
    return p[k] + d;
  }
}lr, ud;
void check(int id)
{
  if(vis[id]) return;
  if(lr.p[id]<=lr.l && ud.p[id]<=ud.l) ul++, vis[id] = 1;
  else if(lr.p[id]<=lr.l && ud.p[id]>=ud.r) dl++, vis[id] = 1;
  else if(lr.p[id]>=lr.r && ud.p[id]<=ud.l) ur++, vis[id] = 1;
  else if(lr.p[id]>=lr.r && ud.p[id]>=ud.r) dr++, vis[id] = 1;
}
ll ask()
{
  if(lr.l==lr.r && ud.l==ud.r) return C[ul+dl+ur+dr];
  else if(lr.l==lr.r) return C[ul+ur] + C[dl+dr];
  else if(ud.l==ud.r) return C[ul+dl] + C[ur+dr];
  else return C[ul] + C[ur] + C[dl] + C[dr];
}
void solve()
{
  ul = ur = dl = dr = 0;
  scanf("%d%d", &n, &m);
  for(int i=1; i<=n; i++) vis[i] = 0;
  lr.init(n), ud.init(n);
  for(int i=1; i<=n; i++)
  {
    int x, y; scanf("%d%d", &x, &y);
    lr.set(i, y); ud.set(i, x);
  }
  check(lr.id[1]), check(lr.id[n]);
  for(int i=1; i<=m; i++)
  {
    static char op[2];
    scanf("%s", op);
    if(op[0]=='?')
    {
      int k; scanf("%d", &k);
      printf("%d %d\n", ud.get(k), lr.get(k));
    }
    else if(op[0]=='!') printf("%lld\n", ask());
    else
    {
      int k; scanf("%d", &k);
      if(op[0]=='L') lr.movel(k);
      else if(op[0]=='R') lr.mover(k);
      else if(op[0]=='U') ud.movel(k);
      else ud.mover(k);
    }
  }
}
int main()
{
  for(int i=1; i<N; i++) C[i] = 1ll*i*(i-1)/2;
  int _; scanf("%d", &_);
  while(_--) solve();
  return 0;
}