游记 - GDOI Junior 2022

由于防疫，初中组集体劝退提高组省选。呵呵。

DAY 1

早上起来，头是木的，人是麻的。

先扫一遍。

T1

入门题。

int main() {
  int N(0), val[3] = {0, 0, 0};
  cin >> N >> val[0] >> val[1] >> val[2];
  map<string, int> mp;
  int mxv(0);
  string ans;
  while (N--) {
    int tp(0);
    string name;
    cin >> name >> tp;
    --tp;
    if (mp.find(name) == mp.end()) mp[name] = 0;
    mp[name] += val[tp];
    if (mp[name] > mxv) ans = name, mxv = mp[name];
  }
  cout << ans << ' ' << mxv << endl;
  return 0;
}

T2

看到区间异或和，马上想到前缀和差分。

要求的数组没有任何一个区间异或和为 $0$，放到前缀异或和数组上，就是没有两个数相等。

而合并两个数，就是在前缀异或和数组上删掉一个数。

所以最后就是看这个数组上有多少种数，因为是前缀和差分所以 $-1$。

结果如果是 $0$，就是不存在，输出 $-1$。

一眼题。

int main() {
  int N(0);
  N = read();
  set<int> s;
  s.insert(0);
  for (int x(0), sum(0); N--; ) {
    x = read();
    sum ^= x;
    s.insert(sum);
  }
  write(s.size() == 1 ? -1 : s.size() - 1), putchar(10);
  
  return 0;
}

T3

这题居然把我卡住了，做的时候各种思考人生，最后发现答案如此简单。

我们考虑放一个数组，$a_i$ 表示最大值不超过 $i$ 时分成的模块数，结论是 $\min i\times a_i$。

考虑对于一个点 $x$，他的权值是 $w_x$，那么对于 $a_{w_x}$ 以下的情况，该节点必然分裂给所有儿子，DFS 递归处理。

此外的情况，整颗子树只有 $1$ 的贡献。

所以我们在 DFS 的过程中维护一个差分数组，每次遍历到一个点都用如上规则更新一遍，最后前缀和一下，完了。

至于值域太大的问题，用 map 维护就行。

void dfs(int x) {
  for (int i(head[x]); i; i = nxt[i], isleaf[x] = false) {
    dfs(to[i]);
    ++sons[x];
  }
  sum[tim[x]] += 1 - sons[x];
  if (!sons[x]) mxtm = max(mxtm, tim[x]);
}
int main() {
  N = read();
  for (int i(0); i != N; ++i) tim[i] = read();
  for (int i(1), f(0); i != N; ++i) addedge(read() - 1, i);
  dfs(0);
  map<int, int>::iterator i(sum.begin());
  map<int, int>::iterator j(i++);
  while (i != sum.end()) {
    i->second += j->second;
    if (i->first >= mxtm) ans = min(ans, i->first * 1LL * i->second);
    ++i, ++j;
  }
  cout << ans << endl;
  return 0;
}

T4

赛时摆烂。太困了，明明都想到枚举方差都没有往下想。

对于一个合法等差数列，考虑以 $i$ 为右端点的贡献：（暂不考虑左端点超过当前区间，可以随便处理）（暂不考虑公差，随便转化）

$$\sum_{j=i-R}^{i-L}{\prod_{k=j}^{i}{a_k}}$$

对于右边的乘积，我们可以前缀积去优化。

设前缀积所得数组为 $p$，原式化为：

$$\sum_{j=i-R}^{i-L}{p_i\times p_j^{-1}}$$

对于这个 $\sum{p_j^{-1}}$，我们再用前缀和优化。

令 $p$ 数组的逆元前缀和数组为 $v$，原式化为：

$$p_i\times(v_{i-L}-v_{i-R})$$

做完了。

赛后

$100+100+100+0=300$。

不出所料。

期待下一天翻盘。

---

DAY 2

T1

式子中合法的 $i$，必满足 $n\not\equiv 0\pmod{i}$，$n\not\equiv 1\pmod{i}$，$n\not\equiv 2\pmod{i}$。

不会（其实只是懒得推简单做法），整除分块乱搞。

怎么乱搞呢？令 $n=mi+p$（$0\le p<i$）。

有 $n=m(i+1)+(p-m)$，$n=m(i-1)+(p+m)$。

对于 $m$ 相同的一个块，只需要让右端点往左边慢慢移，看合不合法，反正移不了多少，顶多 $3$ 次，甚至不一定有。

int main() {
  int T(0);
  cin >> T;
  while (T--) {
    int N(0);
    cin >> N;
    int ans(0);
    for (int i(4); i < N; i = N / (N / i) + 1)  {
      int a(N % i), b(N / (N / i) - i + 1);
      while (~b && a - N / i * b <= 2) --b;
      ++b;
      ans += b;
    }
    cout << ans << endl;
  }
  
  return 0;
}

T2

赛时瞎打 DP，直接挂开。

首先有一点：选择返回永远不是唯一最优解。

如果返回，会有至少 $1$ 的代价；即使新开，也一定可以有至多 $1$ 的花费。

所以对于一个节点向下访问，就选择一个节点替代打开，其他的新标签页打开。

这样子下去，每个点有 $1$ 的进入代价，一个标签页只在叶子结点关闭。

令叶子结点有 $l$ 个，答案就是 $n+l$。

T3

模拟题。我图个方便，就弄了一个前缀和的 trick，变成是 0.1.1 00:00:00 至后一个时间点的花费，减去到前一个点的花费。

样例一次过，不知道为啥好像挂了。

T4

看到这种题，第一反应是搜索。

分几个阶段讲讲我的思路。

Stage 1: $O(T(nm|S|))$

DP。对于每一步，遍历每个点，看能不能走到。

Stage 2: $O(T(nm|S|))$ with an array

搜索，从原点出发搜索，每次往数组里面永久增加待走结点。这样子做，可以减少起点不可达的无用状态。

Stage 3: $O(T(nm|S|))$ with a list

做个小优化：把每个被墙和已访问结点围住的结点去掉，也就是去除无意义状态，用链表维护。这样子，其实应该已经可以过了。但是最坏也可以卡到 $O(T(nm|S|))$。

Stage 4: $O(T(nm+|S|))$ with four queues

上述在什么时候会被卡？

*RRR*RRR
*R*R*R*R
*R*R*R*R
*R*R*R*R
*R*R*R*R
*R*R*R*R
*R*R*R*R
*R*RRR*R

虽然几乎达不到，但是此时如果一直往左走，每个点都会一直被访问，但是此时的访问没有意义。

所以我们考虑维护四个队列，维护四个方向的可扩展点。

对于每个点，在每个队列里最多进一次出一次，这一部分的时间复杂度就是 $O(nm)$。

此时我们可以证明，时间复杂度是严格的 $O(T(nm+|S|))$。

typedef pair<int, int> pt;
const int DIRs = 4;
const char MTCH[] = "WSAD";
const int Xs[] = {-1, 1, 0, 0};
const int Ys[] = {0, 0, -1, 1};

inline pt gtnxt(pt p, int d) {
  return make_pair(p.first + Xs[d], p.second + Ys[d]);
}
inline bool isgoal(pt p) {
  return p.first < 0 || p.second < 0 || p.first >= N || p.second >= M;
}
inline bool judg(pt p) {
  return isgoal(p) || graph[p.first][p.second] == SPC;
}
void insert(pt x) {
  graph[x.first][x.second] = FPT;
  for (int i(0); i != DIRs; ++i) {
    pt nxt(gtnxt(x, i));
    if (judg(nxt)) ques[i].push_back(x);
  }
}
void clear() {
  for (int i(0); i != DIRs; ++i)
    ques[i].clear();
}
inline int trslt(char c) { return find(MTCH, MTCH + DIRs, c) - MTCH; }

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%s%d%d", opts, &N, &M);
    clear();
    for (int i(0); i != N; ++i)
      for (int j(0); j != M; ++j) {
        scanf(" %c", &graph[i][j]);
        if (graph[i][j] == FPT) insert(make_pair(i, j));
      }
    bool ans(false);
    for (char *i(opts); *i && !ans; ++i) {
      int t(trslt(*i));
      int sz(ques[t].size());
      while (sz-- && !ques[t].empty()) {
        pt nxt(gtnxt(ques[t].front(), t));
        ques[t].pop_front();
        if (judg(nxt)) {
          if (isgoal(nxt)) {
            ans = true;
            break;
          }
          insert(nxt);
        }
      }
    }
    puts(ans ? "YES" : "NO");
  }
  return 0;
}

std

最短路 $+$ DP。听不太懂，时间复杂度好像也没我的好，$O(T(nm\log(nm)+|S|))$。

不过好像可以优化 Dijkstra 算法，去掉 $\log$。

赛后

$100+30+40+100=270$。

在这种略微比 CSP-J 难的比赛，就只剩 $570$ in $800$。

太惨烈了。这次主要失利的就是 D1T4、D2T2、D2T3。

总结

可以发展的优点还有：

1. 能够很快且精准地使用搜索；
2. 能够在基础题上尽快地做过去，提高效率；
3. 能够运用前缀和与差分的技巧。

需要注意的缺陷还有：

1. 基础算法（模拟、贪心）掌握不熟练；
2. 太追求效率去做压轴，导致简单题来不及做；
3. 精神状态差。

应对问题的措施包括：

1. 更注重基础算法；
2. 在考试时合理安排节奏；
3. 在赛时，甚至是最近的一段精神、效率低谷期，要保持一个平稳的心态，不能太松懈，不能太急躁。