The 3rd Universal Cup 做题记录

2024-09-25 21:38 由 yhddd 发表于 #其他

https://www.cnblogs.com/yhddd/p/18415768

The 3rd Universal Cup. Stage 0: Trial Contest

G. Manhattan Walk

每个位置独立。设 \(dp_{i,j}\) 为 \((i,j)\) 去到终点的期望，\(dp_{i+1,j},dp_{i,j+1}\) 分别为 \(a,b\)，\(a<b\)。如果 \(a+p\le b\) 一定走 \(a\)，否则按等待时间划分走 \(a\) 还是 \(b\)。

I. Not Another Constructive!

在 A 处计算前缀 N 和后缀 C 的乘积。设 \(dp_{i,j,k,num}\) 为前 \(i\) 个，前缀有 \(j\) 个，后缀有 \(k\) 个，能否有 \(num\) 个子序列。bitset 优化。

M. Training, Round 2

记录前 \(i\) 个题能否达到 \((j,k)\)。每个 \((j,k)\) 只会更新一次。set 维护。

The 3rd Universal Cup. Stage 1: St. Petersburg

A. Element-Wise Comparison

bitset 维护 \(f_{i,j}=a_i<a_j\)。每 \(m\) 个点划一个段，统计跨过段的答案，维护一段的后缀 or。

D. Dwarfs' Bedtime

在 \(0\) 先每个问一次，然后每隔 \(49,48,\dotsb ,1\) 问一次，问到状态翻转就挂到 \(12\) 小时后连续的问。

G. Unusual Case

随机一个点开始找，当前找到 \(a_1,\dotsb,a_k\)，如果找不到新的出边，那么 \(a_k\) 连向 \(a_p\)，将路径改为 \(a_1\to\dotsb\to a_{p-1}\to a_p\to a_k\to a_{k-1}\dotsb\to a_{p+1}\)。据题解说是 \(O(n)\) 的，删掉一条路径之和图仍随机。

J. First Billion

对 \(a_i\bmod B\) 做 bitset 背包，还原方案时如果既可以选也可以不选，就随一个。取 \(B=2.5\times 10^6\)。

也可以分为若干块，块内折半，块间选绝对值前 \(k\) 小合并。

N. (Un)labeled graphs

\(\log n\) 个点维护每个点的编号，把 \(\log n\) 个点连成一条链。剩下 \(3\) 个点。取 \(a\) 为度数最大的点，\(b\) 标记所有的 \(n\) 个点，\(c\) 是唯一不连 \(a\) 的点，标记 \(b\) 和 \(\log n\) 个点的链头。

The 3rd Universal Cup. Stage 4: Hongō

B. Black or White 2

令 \(k=\min(k,nm-k)\)，\(n>m\)。第 \(1\) 行隔一个填一个，之后插空一次填 \((i,j)\) 和 \((i-1,j)\)。多出来的填 \((n,m)\)。

C. Contour Multiplication

\(dp_{i,s}\) 为与 \(popcount(s\oplus t)=i\) 的所有 \(t\) 的共同系数。依次枚举 \(j\) 将 \(dp_{i,s}\to dp_{i-1}{s\oplus 2^j}\)。

D. DRD String

设 \(dp_i\) 为长为 \(i\) 且不存在 \(s[1,j]=s[i-j+1,i],j<i-j+1\) 的方案数。

E. Equally Dividing

只要 \(sum\bmod n=0\) 就有解。若 \(m\) 为偶，每列交替升序降序；否则 \(n\) 为奇，可以构造前 \(3\) 列填 \([1,3n]\)。

升序排序，二分答案 \(x\)。对于每个 \(i\) 可以 \(O(n)\) 计算 \((i,j,k)\) 的答案。设阈值 \(B\)，前 \(B\) 个的贡献 \(O(nB)\) 计算。如果没超过 \(k\)，\(B\) 的 \((B,j,k)\) 贡献 \(\le \frac{k}{B}\)。后边只需要前 \(\frac{k}{B}\) 小的 \((j,k)\) 对，\(O(\frac{k}{B}\log n)\) 预处理。

L. Largest Triangle

取相邻的 \(a_i,a_{i+1},a_{i+2}\) 海伦公式计算。

N. Number of Abbreviations

对于 \(l<r\) 要求 \(s_l\neq s_r\)。

Q. Quotient Sum

形如降序 a 挖去包括 \(n\) 在内的一些位置最后上升的排列。设 \(f_i\) 为前 \(i\) 个且选了 \(i\)，有决策单调性。

The 3rd Universal Cup. Stage 5: Moscow

A. Counting Permutations

模 \(m1\) 和 \(m2\) 相等的可以排列。

B. Bookshelf Tracking

在最后一次 R 操作前维护属于前半边还是后半边。

E. Building a Fence

分类讨论先做哪些，剩下的部分填到哪里。所有方式取 min。

F. Teleports

设 \(dp_{l,r}\) 为区间 \([l,r]\) 的答案，枚举 \(k\) 翻转，每次要么拆成更小的两个区间要么从相等长度的区间转移而来。先做第一种转移，在最短路第二种转移。

F. Teleports

\(e^x=\sum_{n=0}^{\infty}\frac{x^n}{n!}\)。每个 \(n\) 要两次，\(\mid x\mid\) 增大精度下降。计算 \(e^{\frac{x}{2^B}}\) 后平方 \(B\) 次。取 \(n=7,B=10\)。

I. Marks Sum

在后 \(2000\) 位一定存在前缀和 \(\bmod 2000=0/1\)。可以写为 \(2000x+y\)，\(x\le 1000\)，传 \(2x+y\) 即可。

K. Train Depot

区间加，求区间 max。线段树合并。注意到修改的特殊性，合并时如果存在 \(tree_x=tag_x\) 就一定不优，返回 \(v\)，极大减小常数。否则需要递归到 \(tree_u=tag_u\) 且 \(tree_v=tag_v\) 再比较 \(tree_u\) 和 \(tree_v\)，理论复杂度依然正确但是常数极大。

M. Uniting Amoebas

答案为 \(\sum a_i-\max a_i\)。

The 3rd Universal Cup. Stage 7: Warsaw

A. Bus Analysis

代价 \(2\to 1,6\to 3\)。dp 套 dp。内层 dp，设 \(dp_{i,j}\) 为前 \(i\) 个点，代价为 \(j\) 最长向后多远。只有 \(mn,mn+1,mn+2\) 的 dp 值有用。外层 dp 设 \(f_{i,x,y,z}\) 为前 \(i\) 个点，\(mn,mn+1,mn+2\) 的 dp 值分别在 \(x,y,z\)。当 mn 增加时增加答案。除了最开始只有 \(a+20\le b,b+20\le c\) 的三元组有用。

B. Missing Boundaries

有不确定的端点先当成 \([p,p]\)。按左端点排序，记录最多最少能放多少 \((-1,-1)\)。

E. Express Eviction

将横纵坐标都小于等于 \(2\) 的障碍连边，等价于不存在左下边界到右上边界的路径。最小割。

G. Game of Geniuses

答案为最大的行的最小值。

K. Routing K-Codes

设 \(f_u\) 为 \(u\) 为根的和，\(sum_u=\sum_{v\in subtree(u)} 2^{dep_v}\)，\(mxdep_u\) 为最大深度。换根 dp。

L. Random Numbers

\(a_i\) 期望为 \(\frac{n}{2}\)。所以检查长度为 \([1,B]\) 和 \([\frac{n}{2}-B,\frac{n}{2}+B]\) 的区间。

The 3rd Universal Cup. Stage 8: Cangqian

C. Challenge NPC

构造二分图，\(1,4\) 为左，\(2,3\) 为右，\(1\to 2,4\to 3\)。然后奇数为左向之前的右连边，偶数为右向除了 \(2\times i-1\) 之前的左连边。

D. Puzzle: Easy as Scrabble

一个格子如果有两个方向的要求则为矛盾格子，最后为空。队列维护矛盾格子向后推。

E. Team Arrangement

注意到划分数不多，搜出来每组大小后贪心检查。按组的大小从小往大，在一个人的左端点处将他的右端点加入优先队列，对每个组优先取队列中最小的。

H. Permutation

二分，时刻维护当前区间次大值位置。如果次大值和最大值在同一边则用一次，否则两次。每次将 \(len\) 变为 \(d\times len\) 用 \(1\) 次，\((1-d)\times len\) 用 \(2\) 次，取 \(d=0.6\)。

I. Piggy Sort

按位置之和排序，可以知道每张照片的先后顺序。\(m>n\) 所以必然有一只猪出现在相邻照片的同一位置。枚举这个位置，检查是否存在这样一条直线经过 \(m\) 个点。每只猪只可能出现在一条直线上。

J. Even or Odd Spanning Tree

找到最小生成树，只替换一条边，维护奇偶边权的路径最大值。

The 3rd Universal Cup. Stage 9: Xi'an

A. An Easy Geometry Problem

差分，哈希 \(a_i\) 和反过来的 \(k-a_i\)。线段树维护哈希值。二分答案。

E. Dominating Point

出度最大的点 \(u\) 为支配点。设 \(u\) 连向 \(S\)，\(T\) 连向 \(u\)。如果存在 \(x\) 使得 \(dis(u,x)>2\)，那么 \(x\) 连向所有 \(S\) 和 \(u\)，\(d_x>d_u\)，矛盾。如果 \(T\) 为空，无解。否则 \(T\) 组成的子图的支配点 \(uu\) 也符合条件。如果 \(uu\) 不是指向 \(T\) 所有点，递归下去得到 \(uuu\)。否则指向 \(uu\) 且属于 \(S\) 的部分的支配点符合条件。

F. An Easy Counting Problem

lucas 定理，等价于拆成 \(p\) 进制数下每一位的组合数之积。设 \(dp_{i,j}\) 为填到前 \(i\) 位，组合数之积为 \(j\)，\(cnt_k\) 为一位时的答案。\(dp_{i,j}=\sum_{kl\mod p=j} dp_{i,k}\times cnt_l\)。满足结合律，快速幂优化。\(p\) 为质数有原根，下标 \(i\) 改为 \(g^x\bmod=i\) 的 \(x\)，加法卷积。

H. Elimination Series Once More

从小到大加入，每次更新 \(n\) 个点。

I. Max GCD

质因数分解，枚举答案。可能贡献的 \((i,j,k)\) 满足 \(i,j\) 是相邻的 \(v\) 的倍数，双指针最近的 \(k\)。共 \(O(n\sqrt n)\) 组。把 \((k,v)\) 挂在 \(i\) 上，二位数点，做 \(O(1)\) 插入 \(O(\sqrt n)\) 查询的分治。

J. Graph Changing

\(>3\) 一次后无解，分讨 \(n\) 和 \(t\)。