前言
首先祝贺本次喜闻乐见的 COCR Cup 2025 比赛圆满结束！竞赛题目具体内容如下：
题目编号 题目名称 题目类型 主要考点 题目难度 预计通过率
A Easy 语法题 初中几何
入门
入门
50
%
50%
B Word 算法题 模拟法
普及
/
提高
−
普及/提高−
15
%
15%
C Force 数学题 高中物理、三角函数
普及
+
/
提高
普及+/提高
5
%
5%
D Stone 数学题 Nim 博弈、位运算
普及
+
/
提高
普及+/提高
5
%
5%
E Farm 数据结构题 K-D Tree、平衡树
省选
/
𝑁
𝑂
𝐼
−
省选/NOI−
0.1
%
0.1%
F Run 数学题 扩展 Lucas 定理
省选
/
𝑁
𝑂
𝐼
−
省选/NOI−
0.1
%
0.1%
G Zombie 数学题 数位 DP、倍增
𝑁
𝑂
𝐼
/
𝑁
𝑂
𝐼
+
/
𝐶
𝑇
𝑆
𝐶
NOI/NOI+/CTSC
<
0.1
%
<0.1%
H Square 数据结构题 树状数组、线段树、离散化
𝑁
𝑂
𝐼
/
𝑁
𝑂
𝐼
+
/
𝐶
𝑇
𝑆
𝐶
NOI/NOI+/CTSC
<
0.1
%
<0.1%
难度分布为：入门题
2
2 道（
𝐴
/
𝐵
A/B），中档题
2
2 道（
𝐶
/
𝐷
C/D），难题
4
4 道（
𝐸
/
𝐹
/
𝐺
/
𝐻
E/F/G/H）。
A. EASY
SUBTASK 100 PT
根据简单计算可得，
∠
𝐶
3
0
∘
∠C=30
∘
，
3
0
∘
30
∘
角所对的边是斜边的一半，可得：
𝐴
𝐶
2
𝐴
𝐵
𝑁
×
2
AC=2AB=N×2
AC Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
double n; cin >> n;
printf("%.2lf",n * 2.00);
return 0;
}
时间复杂度：
𝑂
(
1
)
O(1)
B. Word
Subtask 100 pt
根据题意模拟即可。本题难点在于字符串函数的使用，以下是本题需用到的函数：
size()：得到字符串的长度
erase()：删除字符串的指定区域
insert()：在字符串指定区域插入内容
empty()：判断字符串是否为空
substr()：截取字符串的指定区域
AC Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int n; cin >> n;
string wd = "",jtb = "";
int gb = 0,xz_l = -1,xz_r = -1;
for(int _ = 1; _ <= n;_++){
string op; cin >> op;
if(op == "I"){
string s; cin >> s;
if(xz_l != -1 && xz_l <= xz_r && xz_r < (int)wd.size()){
wd.erase(xz_l,xz_r - xz_l + 1);
wd.insert(xz_l,s);
gb = xz_l + s.size();
}else{
wd.insert(gb,s);
gb += s.size();
}
xz_l = xz_r = -1;
}else if(op == "A"){
if(wd.empty()) xz_l = xz_r = -1;
else{
xz_l = 0;
xz_r = (int)wd.size() - 1;
}
gb = wd.size();
}else if(op == "C"){
if(xz_l != -1 && xz_l <= xz_r && xz_r < (int)wd.size()) jtb = wd.substr(xz_l,xz_r - xz_l + 1);
xz_l = xz_r = -1;
}else if(op == "V"){
if(xz_l != -1 && xz_l <= xz_r && xz_r < (int)wd.size()){
wd.erase(xz_l,xz_r - xz_l + 1);
wd.insert(xz_l,jtb);
gb = xz_l + jtb.size();
}else{
wd.insert(gb,jtb);
gb += jtb.size();
}
xz_l = xz_r = -1;
}else if(op == "P"){
int i; cin >> i;
gb = min(i,(int)wd.size());
xz_l = xz_r = -1;
}else if(op == "TP"){
int i; cin >> i;
if(wd.empty()){
xz_l = xz_r = -1;
gb = 0;
}else{
i = max(1LL,min(i,(int)wd.size()));
xz_l = xz_r = i - 1;
gb = i;
}
}
}
cout << wd;
return 0;
}
时间复杂度：
𝑂
(
𝑛
)
O(n)
C. Force
Subtask 100 pt
引入三角形法则：当两个向量首尾相接时，从第一个向量的起点指向第二个向量终点的向量，即为这两个向量的和向量。
解决问题的过程如下：
先将每个力分解为水平（
𝑥
x 轴）和垂直（
𝑦
y 轴）分量：
水平分量：
𝐹
𝑥
𝑖
𝑓
𝑖
×
cos
(
𝑥
𝑖
×
𝜋
180
)
F
x
i
=F
I
×COS(X
I
×
180
Π
)
垂直分量：
𝐹
𝑦
𝑖
𝑓
𝑖
×
sin
(
𝑥
𝑖
×
𝜋
180
)
F
y
i
=F
I
×SIN(X
I
×
180
Π
)
合力计算：将所有水平分量相加得到总水平分量
𝐹
𝑥
F
X
，所有垂直分量相加得到总垂直分量
𝐹
𝑦
F
Y
。合力大小
𝐹
𝐹
𝑥
2
+
𝐹
𝑦
2
F=
F
x
2
+F
y
2
。
方向计算：使用
𝜃
arctan
2
(
𝐹
𝑦
,
𝐹
𝑥
)
θ=arctan2(F
y
,F
x
) 计算合力方向（弧度），然后转换为角度。如果结果为负，加
360
°
360° 使其在
[
0
,
360
)
[0,360) 区间内。
AC Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const double PI = acos(-1.0L);
signed main(){
int n; cin >> n;
double xx = 0.0;
double yy = 0.0;
for(int i = 1;i <= n;i++){
double x,f; cin >> x >> f;
double k = x * PI / 180.0;
xx += f * cos(k);
yy += f * sin(k);
}
if(fabs(xx) < 1e-12 && fabs(yy) < 1e-12){
cout << 0 << " " << 0;
return 0;
}
double mag = sqrt(xx * xx + yy * yy);
double t = atan2(yy,xx) * 180.0 / PI;
if(t < 0) t += 360.0;
cout << (int)floor(mag) << " " << (int)floor(t);
return 0;
}
时间复杂度：
𝑂
(
𝑛
)
O(n)
D. Stone
Subtask 100 pt
学过的同学一眼看出：这是Nim博弈。没错，这是一道很模板的 Nim 游戏。但是如果 FM 处于必败态时，第
𝑎
𝑁
+
1
a
N+1
堆石子数量应该是多少呢？
众所周知：
0
⊕
1
1
0⊕1=1，处于必败态的 FM Nim 和为
0
0，那么下一堆石子只需要
1
1 即可。
拓展：Nim 游戏的博弈图和状态。
如果将每个状态视为一个节点，再从每个状态向它的后继状态连边，我们就可以得到一个博弈状态图。
例如，如果节点
𝑖
,
𝑗
,
𝑘
i,j,k 表示局面为
𝑖
,
𝑗
,
𝑘
i,j,k 时的状态，则我们可以画出下面的博弈图（由于篇幅有限，故仅显示部分状态节点和部分边)：
定义必胜状态为先手必胜的状态，必败状态为先手必败的状态。
通过推理，我们可以得出下面三条定理：
定理 1：没有后继状态的状态是必败状态。
定理 2：一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。
定理 3：一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。
对于定理 1，如果游戏进行不下去了，那么这个玩家就输掉了游戏。
对于定理 2，如果该状态至少有一个后继状态为必败状态，那么玩家可以通过操作到该必败状态；此时对手的状态为必败状态——对手必定是失败的，而相反地，自己就获得了胜利。
对于定理 3，如果不存在一个后继状态为必败状态，那么无论如何，玩家只能操作到必胜状态；此时对手的状态为必胜状态——对手必定是胜利的，自己就输掉了游戏。
如果博弈图是一个有向无环图，则通过这三个定理，我们可以在绘出博弈图的情况下用
𝑂
(
𝑁
+
𝑀
)
O(N+M) 的时间（其中
𝑁
N 为状态种数，
𝑀
M 为边数)得出每个状态是必胜状态还是必败状态。
AC Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int T; cin >> T;
while(T--){
int n; cin >> n;
int ans = 0;
for(int i = 1;i <= n;i++){
int t; cin >> t;
ans ^= t;
}
if(ans) cout << "Yes\n";
else cout << "No 1\n";
}
return 0;
}
时间复杂度：
𝑂
(
𝑇
×
𝑁
)
O(T×N)
E. Farm
substask 20 pt
可以发现直接暴力时间复杂度为
𝑂
(
𝑁
×
𝑀
×
𝑄
)
O(N×M×Q)，TLE，剪枝（或记忆化搜索）即可。
Subtask 45 pt
考虑使用
𝑣
𝑒
𝑐
𝑡
𝑜
𝑟
vector，每次查询时查找之前每次操作
1
1 播下的种子即可。
45 pt Code
#include <iostream>
#include <vector>
using namespace std;
struct Seed {
int x, y;
int t; // 成熟时间 = 播种时间 + k
bool picked; // 是否已被采摘
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
时间复杂度：
𝑂
(
𝑄
2
)
O(Q
2
)
备注：由于一些原因，对于特殊性质 B 依旧可以通过，因此应当正常得分 30 pt。
Subtask 10 pt（特殊性质 B 正解）
可以发现每次操作
1
1 中的
𝑘
k 为
1
1，因此可以直接在每次查询时直接查询每个
1
1 操作并删除。
Subtask 100 pt
由于存在二维数区间点数问题，我们考虑 K-D Tree 或平衡树。以下为 K-D Tree 解法：
分析
2
2 种操作的处理：
播种操作：将种子信息（坐标
(
𝑥
,
𝑦
)
(x,y) 的成熟时间
𝑡
t 为当前时间加
𝑘
k）插入到 K-D Tree 中。
采摘操作：查询矩形区域内所有成熟时间
≤
≤ 当前时间的蔬菜，并标记为已采摘。
但是这样的时间复杂度极限下可能达到
𝑂
(
𝑄
2
)
O(Q
2
)，我们考虑剪枝。
每个节点存储子树的最小或最大
(
𝑥
,
𝑦
)
(x,y) 坐标和时间信息，用于快速剪枝。
使用 lazy tag 表示蔬菜是否已被采摘。
在查询时，根据这些信息可以快速跳过不满足条件的子树。
这样我们的时间复杂度为
𝑂
(
𝑁
𝑁
)
O(N
N
)，大约为
8
×
1
0
7
8×10
7
。
AC Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct pt{
int x,y,t;
};
struct node{
int x,y,t,minx,maxx,miny,maxy,mint,maxt,sz;
bool vis;
node *l,*r;
node(pt p){
x = p.x;
y = p.y;
t = p.t;
minx = maxx = x;
miny = maxy = y;
mint = maxt = t;
sz = 1;
vis = 0;
l = r = NULL;
}
void change(){
if(vis){
minx = miny = mint = 0x3f3f3f3f;
maxx = maxy = maxt = -0x3f3f3f3f;
sz = 0;
}else{
minx = maxx = x;
miny = maxy = y;
mint = maxt = t;
sz = 1;
}
if(l && l -> sz > 0){
minx = min(minx,l -> minx);
maxx = max(maxx,l -> maxx);
miny = min(miny,l -> miny);
maxy = max(maxy,l -> maxy);
mint = min(mint,l -> mint);
maxt = max(maxt,l -> maxt);
sz += l -> sz;
}
if(r && r -> sz > 0){
minx = min(minx,r -> minx);
maxx = max(maxx,r -> maxx);
miny = min(miny,r -> miny);
maxy = max(maxy,r -> maxy);
mint = min(mint,r -> mint);
maxt = max(maxt,r -> maxt);
sz += r -> sz;
}
}
};
node *upd(node *nd,pt p,int dep = 0){
if(nd == NULL) return new node(p);
if(dep % 2 == 0){
if(p.x < nd -> x) nd -> l = upd(nd -> l,p,dep + 1);
else nd -> r = upd(nd -> r,p,dep + 1);
}else{
if(p.y < nd -> y) nd -> l = upd(nd -> l,p,dep + 1);
else nd -> r = upd(nd -> r,p,dep + 1);
}
nd -> change();
return nd;
}
int query(node *nd,int x1,int x2,int y1,int y2,int cur){
if(nd == NULL || nd -> sz == 0) return 0;
if(nd -> maxx < x1 || nd -> minx > x2 || nd -> maxy < y1 || nd -> miny > y2) return 0;
if(nd -> mint > cur) return 0;
int cnt = 0;
if(!nd -> vis){
if(nd -> x >= x1 && nd -> x <= x2 && nd -> y >= y1 && nd -> y <= y2 && nd -> t <= cur){
cnt++;
nd -> vis = 1;
}
}
cnt += query(nd -> l,x1,x2,y1,y2,cur);
cnt += query(nd -> r,x1,x2,y1,y2,cur);
nd -> change();
return cnt;
}
signed main(){
int n,m,q; cin >> n >> m >> q;
node *root = NULL;
for(int i = 1;i <= q;i++){
int op; cin >> op;
if(op == 1){
int x,y,k; cin >> x >> y >> k;
root = upd(root,{x,y,i + k});
}else{
int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
cout << query(root,x1,x2,y1,y2,i) << "\n";
}
}
return 0;
}
时间复杂度：
𝑂
(
𝑁
𝑁
)
O(N
N
)
F. Run
Subtask 10 pt
对于
10
%
10% 的数据
𝑛
≤
5
×
1
0
3
n≤5×10
3
，直接代入公式暴力递推、枚举即可。
Subtask 40 pt
首先化简公式，引入杨辉三角（当然使用 Catalan 数亦可）：
1
1
1
1
2
1
1
3
3
1
…
1
1 1
1 2 1
1 3 3 1
…
杨辉三角的实质是二项式系数的几何排列。若一个人从第一个
1
1 处走，只能向下或右下，走到该地的方案数。其组合数表示为：
𝐶
𝑛
𝑘
𝑛
!
𝑘
!
×
(
𝑛
−
𝑘
)
!
C
N
K
k!×(n−k)!
n!
容易将公式转换为：
∑
𝑘
0
𝑛
(
𝑘
𝑛
)
2
mod
𝑝
k=0
∑
n
(
k
n
)
2
modp
根据范德蒙德公式化简：
∑
𝑘
0
𝑛
(
𝑘
𝑛
)
2
MOD
𝑝
∑
𝑘
0
𝑛
(
𝑛
−
𝑘
𝑛
)
(
𝑘
𝑛
)
MOD
𝑝
K=0
∑
N
(
K
N
)
2
MODP
k=0
∑
n
(
n−k
n
)(
k
n
)modp
再根据二项式定理化简：
∑
𝑘
0
𝑛
(
𝑛
−
𝑘
𝑛
)
(
𝑘
𝑛
)
MOD
𝑝
(
𝑛
2
𝑛
)
mod
𝑝
k=0
∑
n
(
n−k
n
)(
k
n
)modp
=(
n
2n
)modp
拓展：实际上存在 Vandermonde 恒等式可直接得到：
∑
𝑘
0
𝑛
(
𝑘
𝑛
)
2
(
𝑛
2
𝑛
)
k=0
∑
n
(
k
n
)
2
=(
n
2n
)
两边同时
mod
𝑝
modp，得：
∑
𝑘
0
𝑛
(
𝑘
𝑛
)
2
MOD
𝑝
(
𝑛
2
𝑛
)
mod
𝑝
k=0
∑
n
(
k
n
)
2
modp=(
n
2n
)modp
由于
𝑝
∈
Prime
p∈Prime，考虑使用 Lucas 定理：
(
𝑛
𝑘
)
≡
(
⌊
𝑘
/
𝑝
⌋
⌊
𝑛
/
𝑝
⌋
)
(
𝑘
mod
𝑝
𝑛
mod
𝑝
)
(
m
o
d
𝑝
)
(
n
k
)≡(
⌊k/p⌋
⌊n/p⌋
)(
kmodp
nmodp
)(modp)
其中，当
𝑛
<
𝑘
n<k 时，二项式系数
(
𝑛
𝑘
)
(
n
k
) 规定为
0
0 。
递归求解即可。
40 pt Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int fp(int a,int b,int p){
int ans = 1;
while(b){
if(b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
int ans[10000005];
int C(int n,int m,int p){
ans[0] = 1;
for(int i = 1;i <= m;i++){
ans[i] = 0;
ans[i] = ans[i - 1] * (n - i + 1) % p * fp(i,p - 2,p) % p;
}
return ans[m];
}
int lucas(int n,int m,int p){
if(m == 0) return 1;
return lucas(n / p,m / p,p) * C(n % p,m % p,p) % p;
}
signed main(){
int n,p; cin >> n >> p;
cout << lucas(n * 2,n,p);
return 0;
}
时间复杂度：
𝑂
(
𝑝
+
log
𝑝
𝑛
)
O(p+log
p
n)
Subtask 100 pt
请先阅读 40 pt 做法。
由于 Lucas 定理只能在
𝑝
p 为质数的情况下使用，对于
100
%
100% 的数据我们考虑扩展 Lucas 定理。
对于
𝑝
p 是一般的合数的情形，只需要首先对它做素因数分解：
𝑝
𝑚
1
𝑎
1
𝑚
2
𝑎
2
…
𝑚
𝑠
𝑎
𝑠
p=m
1
a
1
m
2
a
2
…m
s
a
s
然后，分别计算出模
𝑚
𝑖
𝑎
𝑖
m
i
a
i
下组合数
(
𝑘
𝑛
)
(
k
n
) 的余数，就得到
𝑠
s 个同余方程：
{
(
𝑘
𝑛
)
≡
𝑟
1
(
m
o
d
𝑝
1
𝑎
1
)
(
𝑘
𝑛
)
≡
𝑟
2
(
m
o
d
𝑝
2
𝑎
2
)
…
(
𝑘
𝑛
)
≡
𝑟
𝑠
(
m
o
d
𝑝
𝑠
𝑎
𝑠
)
⎩
⎨
⎧
(
k
n
)≡r
1
(modp
1
a
1
)
(
k
n
)≡r
2
(modp
2
a
2
)
…
(
k
n
)≡r
s
(modp
s
a
s
)
引入中国剩余定理（CRT）：
{
𝑥
≡
𝑎
1
(
m
o
d
𝑛
1
)
𝑥
≡
𝑎
2
(
m
o
d
𝑛
2
)
…
𝑥
≡
𝑎
𝑘
(
m
o
d
𝑛
𝑘
)
⎩
⎨
⎧
x≡a
1
(modn
1
)
x≡a
2
(modn
2
)
…
x≡a
k
(modn
k
)
利用中国剩余定理（CRT）即可求出模
𝑝
p 的余数。
AC Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#ifndef Fading
inline char gc(){
static char now[1<<16],S,T;
if (TS){T=(S=now)+fread(now,1,1<<16,stdin);if (TS) return EOF;}
return S++;
}
#endif
#ifdef Fading
#define gc getchar
#endif
void exgcd(ll a,ll b,ll &x,ll &y){
if (!b) return (void)(x=1,y=0);
exgcd(b,a%b,x,y);
ll tmp=x;x=y;y=tmp-a/by;
}
ll gcd(ll a,ll b){
if (b==0) return a;
return gcd(b,a%b);
}
inline ll INV(ll a,ll p){
ll x,y;
exgcd(a,p,x,y);
return (x+p)%p;
}
inline ll lcm(ll a,ll b){
return a/gcd(a,b)b;
}
inline ll mabs(ll x){
return (x>0?x:-x);
}
inline ll fast_mul(ll a,ll b,ll p){
ll t=0;a%=p;b%=p;
while (b){
if (b&1LL) t=(t+a)%p;
b>>=1LL;a=(a+a)%p;
}
return t;
}
inline ll fast_pow(ll a,ll b,ll p){
ll t=1;a%=p;
while (b){
if (b&1LL) t=(ta)%p;
b>>=1LL;a=(aa)%p;
}
return t;
}
inline ll read(){
ll x=0,f=1;char ch=gc();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();}
while (isdigit(ch)) x=x10+ch-'0',ch=gc();
return xf;
}
inline ll F(ll n,ll P,ll PK){
if (n==0) return 1;
ll rou=1;
ll rem=1;
for (ll i=1;i<=PK;i++){
if (i%P) rou=roui%PK;
}
rou=fast_pow(rou,n/PK,PK);
for (ll i=PK*(n/PK);i<=n;i++){
if (i%P) rem=rem*(i%PK)%PK;
}
return F(n/P,P,PK)rou%PKrem%PK;
}
inline ll G(ll n,ll P){
if (n<P) return 0;
return G(n/P,P)+(n/P);
}
inline ll C_PK(ll n,ll m,ll P,ll PK){
ll fz=F(n,P,PK),fm1=INV(F(m,P,PK),PK),fm2=INV(F(n-m,P,PK),PK);
ll mi=fast_pow(P,G(n,P)-G(m,P)-G(n-m,P),PK);
return fzfm1%PKfm2%PKmi%PK;
}
ll A[1001],B[1001];
//x=B(mod A)
inline ll exLucas(ll n,ll m,ll P){
ll ljc=P,tot=0;
for (ll tmp=2;tmptmp<=P;tmp++){
if (!(ljc%tmp)){
ll PK=1;
while (!(ljc%tmp)){
PK*=tmp;ljc/=tmp;
}
A[++tot]=PK;B[tot]=C_PK(n,m,tmp,PK);
}
}
if (ljc!=1){
A[tot]=ljc;B[tot]=C_PK(n,m,ljc,ljc);
}
ll ans=0;
for (ll i=1;i<=tot;i){
ll M=P/A[i],T=INV(M,A[i]);
ans=(ans+B[i]M%PT%P)%P;
}
return ans;
}
signed main(){
int n,p; cin >> n >> p;
cout << exLucas(n * 2,n,p);
}
时间复杂度：
𝑂
(
log
𝑛
)
O(logn)
G. Zombie
Subtask 6 pt
数据范围较小，直接枚举即可。
6 pt Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int _; cin >> ;
while(--){
int a,m,n; cin >> a >> m >> n;
a %= m;
for(int i = 1;i < n;i++){
int t = a,maxx = 0;
while(t){
maxx = max(maxx,t % 10);
t /= 10;
}
a = (a + maxx) % m + 1;
}
cout << a << "\n";
}
return 0;
}
时间复杂度：
𝑂
(
𝑇
×
𝑁
)
O(T×N)
Subtask 100 pt
采用倍增上数位 DP 的方法。
我们先看式子：
𝑝
𝑜
𝑠
𝑛
𝑒
𝑤
(
(
𝑝
𝑜
𝑠
+
𝑓
(
𝑝
𝑜
𝑠
)
)
mod
𝑝
)
+
1
pos
new
=((pos+f(pos))modp)+1
省略
+
1
+1，得：
𝑝
𝑜
𝑠
𝑛
𝑒
𝑤
(
𝑝
𝑜
𝑠
+
𝑓
(
𝑝
𝑜
𝑠
)
)
mod
𝑝
pos
new
=(pos+f(pos))modp
我们发现每次增量不会超过
9
9，因此如果不看个位前面每次的增量不会超过
1
1。也就是说对于除个位之外的每一位我们都是一点点变化的，每次循环每个阶段我们都会经历。于是我们发现个位是特殊的，考虑单独处理。既然其他位置每个阶段都会经历，那我们不妨找到最特殊的阶段——全
0
0（尽管不会出现）。而前面的阶段位数对后面剩下的影响只需要记录最大数码即可。
于是我们考虑定义
𝑑
𝑝
1
𝑖
,
𝑗
,
𝑘
,
𝑑
𝑝
2
𝑖
,
𝑗
,
𝑘
dp1
i,j,k
,dp2
i,j,k
分别表示
2
∼
𝑖
2∼i 位均为
0
0，
𝑗
j 是
𝑖
+
1
i+1 位及以上的最大数码，个位现在是
𝑘
k 的状态下，我们想要给
𝑖
+
1
i+1 位加
1
1，并且第一次回到
2
∼
𝑖
2∼i 位均为
0
0 的状态后个位的值，和需要的步数。
我们发现
𝑑
𝑝
1
𝑖
,
𝑗
,
𝑘
,
𝑑
𝑝
2
𝑖
,
𝑗
,
𝑘
dp1
i,j,k
,dp2
i,j,k
只需要由
𝑑
𝑝
1
𝑖
−
1
,
𝑑
𝑝
2
𝑖
−
1
dp1
i−1
,dp2
i−1
开始然后枚举
𝑖
−
1
i−1 开始由
0
→
9
0→9 的变化即可转移。
接下来我们有
3
3 步。
对于
mod
𝑚
modm 的操作，我们先尝试将
𝐴
A 变为
0
∼
9
0∼9。先变到要跨过
𝑚
m 之前，我们先用
𝑑
𝑝
1
𝑖
,
𝑗
,
𝑘
,
𝑑
𝑝
2
𝑖
,
𝑗
,
𝑘
dp1
i,j,k
,dp2
i,j,k
从低位开始一步步加到
0
0 然后加到不能再加后，再从高位一步步向下加到不能再加。
然后因为我们反复跨过
𝑚
m 的次数可能很多，于是我们通过
𝑑
𝑝
1
𝑖
,
𝑗
,
𝑘
,
𝑑
𝑝
2
𝑖
,
𝑗
,
𝑘
dp1
i,j,k
,dp2
i,j,k
预处理数组
𝑓
𝑟
𝑖
,
𝑗
,
𝑘
,
𝑡
𝑜
𝑖
,
𝑗
,
𝑘
fr
i,j,k
,to
i,j,k
表示
0
∼
9
0∼9 中的数
𝑗
j 跨过
𝑚
2
𝑖
m2
i
次后变成的
0
→
9
0→9 中的哪一个，用多少步，然后我们就可以快速处理跨过
𝑚
m 了。
接下来我们不会再走一次超过
𝑚
m 的了，于是我们又按
𝑆
𝑡
𝑒
𝑝
1
Step1 中的方法，从低位开始一步步加到
0
0 然后加到不能再加后，再从高位一步步向下加到不能再加。
最后
+
1
+1 即可。
AC Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp1[20][10][10],dp2[20][10][10],pw[20];
int fr[70][25],to[70][25],num[20],maxx[20];
int solve(int x){
int maxx = 0;
while(x){
maxx = max(maxx,x % 10);
x /= 10;
}
return maxx;
}
signed main(){
int _; cin >> ;
while(--){
int a,m,rem; cin >> a >> m >> rem;
int mm = m;
rem--;
for(int i = 1;i <= 19;i++){
num[i] = mm % 10;
mm /= 10;
}
pw[0] = 1;
for(int i = 1;i <= 19;i++) pw[i] = pw[i - 1] * 10;
for(int a = 0;a < 10;a++){
for(int b = 0;b < 10;b++){
if(!a && !b){
dp2[1][a][b]=LLONG_MAX;
continue;
}
dp1[1][a][b] = b;
dp2[1][a][b] = 0;
while(dp1[1][a][b] <= 9){
dp1[1][a][b] += max(a,dp1[1][a][b]);
dp2[1][a][b];
}
dp1[1][a][b] -= 10;
}
}
for(int k = 2;k <= 19;k){
for(int a = 0;a < 10;a++){
for(int b = 0;b < 10;b++){
if(!a && !b){
dp2[k][a][b] = LLONG_MAX;
continue;
}
int ft = b,gt = 0,t;
for(int i = 0;i <= 9;i++){
t = ft;
ft = dp1[k - 1][max(a,i)][t];
gt = min(gt + dp2[k - 1][max(a,i)][t],LLONG_MAX);
}
dp1[k][a][b] = ft;
dp2[k][a][b] = gt;
}
}
}
for(int s = 0;s < 10;s++){
if(!s){
fr[0][s] = 0;
to[0][s] = 1;
continue;
}
int ff = s,gg = 0,maxx = 0,t,b = 0;
for(int i = 19;i >= 2;i--){
for(int j = 0;j <= num[i] - 1;j++){
t = ff;
ff = dp1[i - 1][max(maxx,j)][t];
gg = min(gg + dp2[i - 1][max(maxx,j)][t],LLONG_MAX);
}
b = b * 10 + num[i];
maxx = max(maxx,num[i]);
}
ff = b * 10 + ff;
while(ff < m){
ff += solve(ff);
gg++;
}
fr[0][s] = ff % m;
to[0][s] = gg;
}
for(int i = 1;i <= 69;i++){
for(int s = 0;s < 10;s++){
int t = fr[i - 1][s];
fr[i][s] = fr[i - 1][t];
to[i][s] = min(to[i - 1][s] + to[i - 1][t],LLONG_MAX);
}
}
while(rem >= 100){
if(a <= 9 && to[0][a] <= rem){
int k = 0;
while(k <= 63 && to[k + 1][a] <= rem) k++;
rem -= to[k][a];
a = fr[k][a];
continue;
}
if(m - a <= 100){
a = (a + solve(a)) % m;
rem--;
continue;
}
mm = a;
for(int i = 1;i <= 19;i++){
num[i] = mm % 10;
mm /= 10;
}
for(int i = 19;i >= 1;i--){
if(i != 19) maxx[i] = maxx[i + 1];
else maxx[i] = 0;
maxx[i] = max(maxx[i],num[i]);
}
int k = 1;
int t = a % 10;
while(!num[k + 1] && (a / pw[k + 1] + 1) * pw[k + 1] + dp1[k + 1][maxx[k + 2]][t] < m && rem >= dp2[k + 1][maxx[k + 2]][t]) k++;
rem -= dp2[k][maxx[k + 1]][t];
num[1] = dp1[k][maxx[k + 1]][t];
num[k + 1]++;
a = 0;
for(int i = 19;i >= 1;i--) a = a * 10 + num[i];
}
while(rem--) a = (a + solve(a)) % m + 1;
cout << a << "\n";
}
return 0;
}
时间复杂度：
𝑂
(
𝑇
×
log
𝑁
)
O(T×logN)
H. Square
Subtask 20 pt
不断枚举
3
3 个不同颜色的点，时间复杂度
𝑂
(
𝑁
3
)
O(N
3
)。
Subtask 60 pt
按
𝑥
x 递增枚举前两个点，那么第三个点的情况被这两个点的
𝑦
y 坐标分为三部分，分别记录
𝑥
x 的后缀这三部分的
𝑥
,
(
𝑥
+
𝑦
)
,
(
𝑥
−
𝑦
)
x,(x+y),(x−y) 最大值即可快速计算，离散化使支持区间查询，这里因为
𝑁
N 比较小可以暴力更新，时间复杂度
𝑂
(
𝑁
2
)
O(N
2
)。在实现时考虑对颜色进行置换，复杂度为
𝑂
(
𝑁
2
×
6
)
O(N
2
×6)。
Subtask 100 pt
采用扫描线、二位数点。
由于
𝑁
N 较大，暴力更新会超时，采用树状数组或线段树的解法更新。
经过分析可以发现三个点的位置可能是：
两个点在矩形的邻边上且相对，一个点在矩形内部。（共存在
6
6 组置换，两个边上的点控制了四边的缩小）
两个点在矩形的边上且相边相邻，一个点在矩形邻边上。（共存在
4
4 组置换，三个点控制了四边的缩小）
首先对于颜色进行排列置换，并对坐标进行四个象限的变换。这样我们可以从左到右钦定颜色加入的顺序。
经过前面的变换，我们按照
𝑥
x 坐标升序，我们发现本质不同的三个点形态只有
𝑦
y 递增，或者先增再减。
第一种可以直接开两个树状数组，把第一个点的
−
𝑥
−
𝑦
−x−y 扔进第一个树状数组，然后由第二点查询传递到第二颗树状数组（这里是为了保证有这样一个点处在中间）。
第二种情况我们可以按顺序加入前两个点，并用扫描线采用二位数点找出第三个点，在线段树上直接赋值（一个对后缀赋值，一个对前缀赋值，那么他们中间的点一定可以两个信息都接受到，并且合并这两个信息得到答案），最终在第三个点的
𝑦
y 坐标处进行单点查询，需要把
𝑥
x 的差加上，线段树里存的是
𝑦
y 的差值和第一个点的 $。。
AC Code
#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll N=2e5+10,inf=1e9+10;
ll n,tx,ty;
ll rrx[N],rry[N],rrc[N];
ll x[N],y[N],rc[N],c[N];
ll mxx=0,mxy=0;
ll dx[N],dy[N],rx[N],ry[N],px[N],py[N];
ll d[4]={0,1,2,3};
#define lowbit(i) (i&(-i))
struct szmin{
ll c[N];
inline void clear(){for(int i=1;i<=ty;i++)c[i]=inf;return ;}
inline void add(ll x,ll y){
for(int i=x;i<=ty;i+=lowbit(i))c[i]=min(c[i],y);
return ;
}inline ll ask(ll x){ll an=inf;for(int i=x;i;i-=lowbit(i))an=min(an,c[i]);return an;}
}o,p;
inline bool cmpx(ll px,ll py){if(x[px]!=x[py])return x[px]<x[py];return y[px]<y[py];}
ll ans=inf;
inline void s1(){
o.clear();p.clear();
for(int t=1;t<=n;t++){
ll i=px[t];if(c[i]==0){
o.add(dy[i],-x[i]-y[i]);
}if(c[i]1){
p.add(dy[i],o.ask(dy[i]));
}if(c[i]2){
ans=min(ans,x[i]+y[i]+p.ask(dy[i]));
}
}return ;
}
ll val[N<<2],t1[N<<2],t2[N<<2];
inline void build(ll o,ll l,ll r){
val[o]=t1[o]=t2[o]=inf;if(lr)return ;
ll mid=(l+r)>>1;build(o<<1,l,mid);build(o<<1|1,mid+1,r);
return ;
}
inline void push1(ll o,ll x){
t1[o]=min(t1[o],x);return ;
}inline void push2(ll o,ll x){
val[o]=min(val[o],t1[o]+x);t2[o]=min(t2[o],x);return ;
}
inline void pushdown(ll o){
if(t2[o]*2<inf)push2(o<<1,t2[o]),push2(o<<1|1,t2[o]),t2[o]=inf;if(t1[o]*2<inf)push1(o<<1,t1[o]),push1(o<<1|1,t1[o]),t1[o]=inf;
return ;
}
inline ll ask(ll o,ll l,ll r,ll x){
if(lr)return val[o];
ll mid=(l+r)>>1;pushdown(o);
if(mid>=x)return min(val[o],ask(o<<1,l,mid,x));
return min(val[o],ask(o<<1|1,mid+1,r,x));
}
inline void upd1(ll o,ll l,ll r,ll x,ll y,ll z){
if(x<=l&&r<=y){push1(o,z);return ;}
ll mid=(l+r)>>1;pushdown(o);
if(mid>=x)upd1(o<<1,l,mid,x,y,z);
if(mid<y)upd1(o<<1|1,mid+1,r,x,y,z);
return ;
}
inline void upd2(ll o,ll l,ll r,ll x,ll y,ll z){
if(x<=l&&r<=y){push2(o,z);return ;}
ll mid=(l+r)>>1;pushdown(o);
if(mid>=x)upd2(o<<1,l,mid,x,y,z);
if(mid<y)upd2(o<<1|1,mid+1,r,x,y,z);
return ;
}
inline void s2(){
build(1,1,ty);
for(int t=1;t<=n;t++){
ll i=px[t];if(c[i]==0){
upd1(1,1,ty,dy[i],ty,-x[i]-y[i]);
}if(c[i]1){
upd2(1,1,ty,1,dy[i],y[i]);
}if(c[i]2){
ans=min(ans,ask(1,1,ty,dy[i])+x[i]);
}
}return ;
}
inline void solve(){
s1();s2();
return ;
}
inline void ss(ll tpx,ll tpy){
for(int i=1;i<=n;i++){
if(tpx1)x[i]=rrx[i];else x[i]=mxx-rrx[i]+1;if(tpy1)y[i]=rry[i];else y[i]=mxy-rry[i]+1;
rc[i]=rrc[i];rx[i]=x[i];ry[i]=y[i];px[i]=i;
}sort(rx+1,rx+n+1);sort(ry+1,ry+n+1);tx=unique(rx+1,rx+n+1)-rx-1,ty=unique(ry+1,ry+n+1)-ry-1;
for(int i=1;i<=n;i++)dx[i]=lower_bound(rx+1,rx+n+1,x[i])-rx;for(int i=1;i<=n;i++)dy[i]=lower_bound(ry+1,ry+n+1,y[i])-ry;
sort(px+1,px+n+1,cmpx);for(int i=0;i<3;i++)d[i]=i;
while(1){
for(int i=1;i<=n;i++)c[i]=d[rc[i]];
solve();if(!next_permutation(d,d+3))break;
}return ;
}
int main(){
cin>>n;for(int i=1;i<=n;i++)cin>>rrx[i]>>rry[i]>>rrc[i],mxx=max(mxx,rrx[i]),mxy=max(mxy,rry[i]);
ss(1,1);
ss(1,0);
ss(0,1);
ss(0,0);
cout<<ans*2;return 0;
}
