专栏文章

I3

TTTpandaS
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min987qv
此快照首次捕获于
2025/12/01 22:38
3 个月前
此快照最后确认于
2025/12/01 22:38
3 个月前
查看原文

命题

若整数 x,y,kx,y,k 满足：
⌈xk⌉+⌈yk⌉<⌈x+y+1k⌉\left\lceil \dfrac{x}{k} \right\rceil+\left\lceil \dfrac{y}{k} \right\rceil < \left\lceil \dfrac{x+y+1}{k} \right\rceil
当且仅当
k∣x,k∣yk \mid x, k \mid y

证明

定义

定义 r1,r2r_1,r_2 表示 x,yx,y 除以 kk 的余数，即：
x≡r1(modk)x \equiv r_1 \pmod {k}
y≡r2(modk)y \equiv r_2 \pmod {k}
可以得到
x+y+1≡r1+r2+1(modk)x + y + 1 \equiv r_1+r_2+1 \pmod {k}
原定理等价于：
⌈r1k⌉+⌈r2k⌉<⌈r1+r2+1k⌉\left\lceil \dfrac{r_1}{k} \right\rceil+\left\lceil \dfrac{r_2}{k} \right\rceil < \left\lceil \dfrac{r1+r2+1}{k} \right\rceil
由定义可得
r1,r2∈[0,k)r_1,r_2 \in [0,k)
r1+r2+1∈[1,2k)r_1+r_2+1 \in [1,2k)
因此
1≤⌈r1+r2+1k⌉≤21 \leq \left\lceil \dfrac{r1+r2+1}{k} \right\rceil \leq 2
分两种情况讨论。
  1. ⌈r1+r2+1k⌉=1 \left\lceil \dfrac{r1+r2+1}{k} \right\rceil =1
此时若 ⌈r1k⌉+⌈r2k⌉<⌈r1+r2+1k⌉\left\lceil \dfrac{r_1}{k} \right\rceil+\left\lceil \dfrac{r_2}{k} \right\rceil < \left\lceil \dfrac{r1+r2+1}{k} \right\rceil，当且仅当 ⌈r1k⌉=⌈r2k⌉=0\left\lceil \dfrac{r_1}{k} \right\rceil = \left\lceil \dfrac{r_2}{k} \right\rceil = 0，即 r1=r2=0r_1 = r_2 = 0，即
k∣x,k∣yk \mid x, k \mid y
  1. ⌈r1+r2+1k⌉=2 \left\lceil \dfrac{r1+r2+1}{k} \right\rceil = 2
此时若 ⌈r1k⌉+⌈r2k⌉<⌈r1+r2+1k⌉\left\lceil \dfrac{r_1}{k} \right\rceil+\left\lceil \dfrac{r_2}{k} \right\rceil < \left\lceil \dfrac{r1+r2+1}{k} \right\rceil，即 ⌈r1k⌉+⌈r2k⌉≤1\left\lceil \dfrac{r_1}{k} \right\rceil + \left\lceil \dfrac{r_2}{k} \right\rceil \leq 1，则总是满足 r1=0r_1=0 或 r2=0r_2=0。不失一般性的，设 r1=0r_1=0，则 r1+r2+1=r2+1∈[1,k]≤kr_1+r_2+1=r_2+1 \in [1,k] \leq k，因此 ⌈r1+r2+1k⌉=1 \left\lceil \dfrac{r1+r2+1}{k} \right\rceil = 1，与条件不符，因此此情况不可能发生。
总上，原定理成立。

应用

CF1237G Balanced Distribution *3500

1 分析

定义 1.1

定义一个函数 Sum(l,r,a)(l≤r,l,r∈[1,n])\text{Sum}(l,r,a) (l \leq r,l,r \in [1,n])，满足：
Sum(l,r,a)=∑i=lrai\text{Sum}(l,r,a)=\sum_{i=l}^{r}a_i

定义 1.2

定义每个位置的目标状态为 ss，满足：
s=Sum(1,n,a)ns=\dfrac{\text{Sum}(1,n,a)}{n}

定理 1.1

对于区间 [l,r][l,r]，若满足 Sum(l,r,a)=(r−l+1)×s \text{Sum}(l,r,a)=(r-l+1)\times s，则至多 ⌈r−lk−1⌉\left\lceil \dfrac{r-l}{k-1} \right\rceil 次分配操作使得 ∀i∈[l,r],ai=s\forall i \in [l,r],a_i=s 且其余数值不变。

证明 1.1

进行操作：
对于 ∀i∈[1,n],ai→ai−s\forall i \in [1,n] , a_i \to a_i-s。
此时原定理等价于：
对于区间 [l,r][l,r]，若满足 Sum(l,r,a)=0 \text{Sum}(l,r,a)=0，则至多 ⌈r−lk−1⌉\left\lceil \dfrac{r-l}{k-1} \right\rceil 次分配操作使得 ∀i∈[l,r],ai=0\forall i \in [l,r],a_i=0 且其余数值不变。

定义 1.1.1

定义一个函数 f(l,r,x,a,t)f(l,r,x,a,t) 表示是否满足至多 tt 次操作使得 al=x,∀i∈[l+1,r],ai=0a_l=x,\forall i \in [l+1,r],a_i=0 且其余数值不变。
特殊的，f(l,l,x,a,0)=[al=x]f(l,l,x,a,0)=[a_l=x]。
定理成立等价于若满足 f(l,r,0,a,⌈r−lk−1⌉)=1f(l,r,0,a,\left\lceil \dfrac{r-l}{k-1} \right\rceil)=1。
考虑任意情况下的 f(l,r,x,a,t)f(l,r,x,a,t)。
  1. r−l+1≤kr-l+1 \leq k
f(l,r,x,a,t)=[x=Sum(l,r,a)][t≥1]f(l,r,x,a,t)=[x=\text{Sum}(l,r,a)][t \geq 1]
具体的，若满足 x=Sum(l,r,a)x=\text{Sum}(l,r,a)，则对 [l,l+k−1][l,l+k-1] 进行一次分配操作。
分配后的数值满足：
al=xa_l=x
∀i∈[l+1,r],ai=0\forall i \in [l+1,r],a_i=0
区间 [r+1,l+k−1][r+1,l+k-1] 中的数不变。
  1. Sum(l,l+k−1,a)≥x\text{Sum}(l,l+k-1,a) \geq x

定义 1.1.2

定义一个数组 bb，满足
bl=xb_l=x
∀i∈[l+1,l+k−1),bi=0\forall i \in [l+1,l+k-1),b_i=0
bl+k−1=Sum(l,l+k−1,a)−xb_{l+k-1}=\text{Sum}(l,l+k-1,a)-x
∀i∈[1,l)∧(l+k−1,n],bi=ai\forall i \in [1,l)\wedge(l+k-1,n] ,b_i=a_i
f(l,r,x,a,t)=f(l+k−1,r,0,b,t−1)f(l,r,x,a,t)=f(l+k-1,r,0,b,t-1)
具体的，先对 [l,l+k−1][l,l+k-1] 进行一次分配操作。
分配后的数值满足：
al=xa_l=x
∀i∈[l+1,l+k−1),ai=0\forall i \in [l+1,l+k-1),a_i=0
al+k−1=Sum(l,l+k−1,a)−xa_{l+k-1}=\text{Sum}(l,l+k-1,a)-x
分配后的 aa 数组即变成 bb 数组。
此时再对后面的部分进行操作，等价于 f(l+k−1,r,0,b)f(l+k-1,r,0,b)。
  1. Sum(l,l+k−1,a)<x\text{Sum}(l,l+k-1,a) < x
f(l,r,x,a,t)=f(l+k−1,r,al+k−1+x−Sum(l,l+k−1,a),a,t−1)f(l,r,x,a,t)=f(l+k-1,r,a_{l+k-1}+x-\text{Sum}(l,l+k-1,a),a,t-1)
具体的，先对 [l+k−1,r][l+k-1,r] 进行分配操作。
分配后的数值满足：
al+k−1=al+k−1+x−Sum(l,l+k−1,a)a_{l+k-1}=a_{l+k-1}+x-\text{Sum}(l,l+k-1,a)
∀i∈(l+k−1,r],ai=0\forall i \in (l+k-1,r] , a_i=0
能否完成等价于 f(l+k−1,r,al+k−1+x−Sum(l,l+k−1,a),a,t−1)f(l+k-1,r,a_{l+k-1}+x-\text{Sum}(l,l+k-1,a),a,t-1)。
此时对 [l,l+k−1][l,l+k-1] 进行一次分配操作。
分配后的数值满足：
al=xa_{l}=x
∀i∈(l,l+k−1],ai=0\forall i \in (l,l+k-1] , a_i=0
考虑待证命题 f(l,r,0,a,⌈r−lk−1⌉)=1f(l,r,0,a,\left\lceil \dfrac{r-l}{k-1} \right\rceil)=1。
通过上述 33 种情况对原问题进行归纳。

性质 1.1.1

对于情况 2,32,3 将 f(l,r,x,a,t)f(l,r,x,a,t) 归纳为 f(l′,r′,x′,a′,t′)f(l',r',x',a',t') 时，满足 r′−l′=r−l−(k−1)r'-l'=r-l-(k-1)。

性质 1.1.2

对于情况 2,32,3 将 f(l,r,x,a,t)f(l,r,x,a,t) 归纳为 f(l′,r′,x′,a′,t′)f(l',r',x',a',t') 时，满足 Sum(l′,r′,a′)=Sum(l′,r′,a)\text{Sum}(l',r',a')=\text{Sum}(l',r',a)。

性质 1.1.3

对于情况 2,32,3 将 f(l,r,x,a,t)f(l,r,x,a,t) 归纳为 f(l′,r′,x′,a′,t′)f(l',r',x',a',t') 时，满足 x′+Sum(l,r,a)−Sum(l′,r′,a)=xx'+\text{Sum}(l,r,a)-\text{Sum}(l',r',a)=x。
由性质 1.1.1 可得，在变成情况 1 前归纳次数不超过 ⌈r−lk−1⌉−1\left\lceil \dfrac{r-l}{k-1} \right\rceil-1，因此在得到情况 1 时 [t≥1][t \geq 1] 总是满足。
由性质 1.1.2，1.1.3 可得，由于初始状态 Sum(l,r,a)=x=0\text{Sum}(l,r,a)=x=0，每次归纳后得到的 f(l′,r′,x′,a′,t′)f(l',r',x',a',t') 总是满足 Sum(l′,r′,a′)=Sum(l′,r′,a)=x′+Sum(l,r,a)−x=x′\text{Sum}(l',r',a')=\text{Sum}(l',r',a)=x'+\text{Sum}(l,r,a)-x=x'，因此在得到情况 1 时 [x=Sum(l,r,a)][x=\text{Sum}(l,r,a)] 总是满足。
总上，f(l,r,0,a,⌈r−lk−1⌉)=1f(l,r,0,a,\left\lceil \dfrac{r-l}{k-1} \right\rceil)=1，原命题得证。

定理 1.2

对于相邻的两个区间 [l1,r1],[l2,r2](1≤l1≤r1≤1n,1≤l2≤r2≤n,l2=r1+1)[l_1,r_1],[l_2,r_2] (1\leq l_1 \leq r_1 \le1 n,1 \leq l_2 \leq r_2 \leq n,l_2=r_1+1)，满足
Sum(l1,r1,a)=(r1−l1+1)×s \text{Sum}(l_1,r_1,a)=(r_1-l_1+1)\times s
Sum(l2,r2,a)=(r2−l2+1)×s \text{Sum}(l_2,r_2,a)=(r_2-l_2+1)\times s
，若分别操作的次数小于将两个区间合并为一个区间操作的次数，当且仅当两个区间的 len−1\text{len}-1 为 k−1k-1 的倍数。
形式化的，若满足
⌈len1−1k−1⌉+⌈len2−1k−1⌉<⌈len1+len2−1k−1⌉\left\lceil \dfrac{\text{len}_1-1}{k-1} \right\rceil+\left\lceil \dfrac{\text{len}_2-1}{k-1} \right\rceil < \left\lceil \dfrac{\text{len}_1+\text{len}_2-1}{k-1} \right\rceil
当且仅当
len1−1≡0(modk−1)\text{len}_1-1 \equiv 0 \pmod {k-1}
len2−1≡0(modk−1)\text{len}_2-1 \equiv 0 \pmod {k-1}
可以发现等价于本文所提的命题。

对原问题的分析

将原数组分为若干个区间 [li,ri][l_i,r_i]，满足
Sum(li,ri,a)=(ri−li+1)×s \text{Sum}(l_i,r_i,a)=(r_i-l_i+1)\times s
答案为
∑i⌈ri−lik−1⌉\sum_{i} \left\lceil \dfrac{r_i-l_i}{k-1} \right\rceil
由定理 1.2 可得，可以一直合并区间直到满足
len−1≡0(modk−1)\text{len}-1 \equiv 0 \pmod {k-1}
此时答案为
∑iri−lik−1=nk−1−∑i1k−1\sum_{i} \dfrac{r_i-l_i}{k-1} = \dfrac{n}{k-1} - \sum_{i} \dfrac{1}{k-1}
因此答案与区间数量成负相关，贪心地尽可能多的划分区间即可。
具体的，对于 ii，找到最大的 jj 满足
j≤ij \leq i
Sum(j,i,a)=(i−j+1)×s\text{Sum}(j,i,a)=(i-j+1)\times s
i−j≡0(modk−1)i-j \equiv 0 \pmod {k-1}
则划分出区间 [i,j][i,j]。

证明 1.3

考虑反证。
设存在 pp，满足
p<j≤ip < j \leq i
Sum(p,i,a)=(i−p+1)×s\text{Sum}(p,i,a)=(i-p+1)\times s
i−p≡0(modk−1)i-p \equiv 0 \pmod {k-1}
使得划分 [p,i][p,i] 更优。
则
Sum(p,j−1,a)=(j−1−p+1)×s\text{Sum}(p,j-1,a)=(j-1-p+1)\times s
j−1−p≡0(modk−1)j-1-p \equiv 0 \pmod {k-1}
此时可以划分出区间 [p,j−1][p,j-1]。
因此原方案中对于 [1,p−1][1,p-1] 和 [i+1,n][i+1,n] 部分采用与现方案相同的划分方式，而原方案中 [p,i][p,i] 可以划分为两个区间，现方案中只划分为了一个区间。与现方案比原方案更优的假设不符。
因此划分区间 [i,j][i,j] 最优。

2 实现

考虑如何实现上述贪心过程找到每个 ii 匹配的端点 jj。
进行操作：
对于 ∀i∈[1,n],ai→ai−s\forall i \in [1,n] , a_i \to a_i-s。
此时对于 ii，满足条件的 jj 可以刻画为
Sum(j,i,a)=0\text{Sum}(j,i,a)=0
i≡j(modk−1)i \equiv j \pmod {k-1}
条件一可以重新刻画为
Sum(1,j−1,a)=Sum(1,i,a)\text{Sum}(1,j-1,a)=\text{Sum}(1,i,a)
因此维护二元组 (Sum(1,i,a),i mod k−1)(\text{Sum}(1,i,a),i \bmod k-1)，jj 即为最大的下标，满足
j≤ij \leq i
(Sum(1,j−1,a),j mod k−1)=(Sum(1,i,a),i mod k−1)(\text{Sum}(1,j-1,a),j \bmod k-1)=(\text{Sum}(1,i,a),i \bmod k-1)
使用 map 记录每个二元组最近一次出现的位置即可，时间复杂度 O(nlog⁡n)O(n \log n)。
由于原题中数组成环，最后枚举起点，可以实现 O(n2)O(n^2) 的算法。
考虑倍增加速，计算 fi,jf_{i,j} 表示以 ii 为起点划分 2j2^j 个区间的端点，可以将原算法改进为 O(nlog⁡n)O(n \log n)。
输出方案参照证明 1.1 中将问题化归的方式递归即可，时间复杂度 O(n)O(n)。
总时间复杂度 O(nlog⁡n)O(n \log n)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...