Codeforces Round 920 (Div. 3) (A,B,C,D,E,F,G)
比赛链接
这把前ABC比较简单，中间两道DE很有难度，很有意思。上把刚掉分（打了两题就跑了，没想到掉了那么多），这把状态比较好，大概八十分钟写完前五个，润了。
赛后看了一下FG题解，发现可做，顺手给补掉了。
C是个简单的贪心。D需要证明一些结论，之后暴力枚举。E是博弈论，把局面分类讨论即可。F是个根号分治，准备两种暴力手段，一个带权前缀和，一个直接暴力模拟。G也是个前缀和，难点在于坐标的计算和动态开辟空间。
A. Square
题意：
在二维坐标轴上有一个正方形，它的边与坐标轴平行，给你一个正方形的四个顶点坐标，问面积是多少
思路：
因为边与坐标轴平行，所以两个点如果在同一条边上，要么x值相等，这时y值之差就是边长，要么y值相等，这时x值之差就是边长。因为四个点都给了，所以假设我们只看x值，肯定两个点是一个x值，另外两个点是另一个x值。两个不同的x值之差就是边长。答案就是边长的平方，数据范围很小甚至longlong都不用开
code：
#include
#include
using namespace std;
int T;
int main(){
cin>>T;
while(T--){
int a,b;
for(int i=1,x,y;i<=4;i++){
cin>>x>>y;
if(i==1)a=x;
else if(a!=x)b=x;
}
cout<<(a-b)*(a-b)<<endl;
}
return 0;
}
B. Arranging Cats
题意：
有n个盒子，上面要么有猫要么没猫，用一个长为n的01串
b
b
b 描述盒子的状态，即：对第i个位置，
b
i
b_i
bi为1则表示有猫，为0则表示没猫。
可以执行三种操作：
- 给一个没猫的位置放一只猫
- 把一个有猫的位置上的猫移除
- 把一个有猫的位置上的猫移动到一个没猫的位置
给你一个长为n的目标状态的01串
f
f
f，问你要得到这个目标状态最少要执行多少次操作。
思路：
很容易想到，一个位置上的状态如果没变就不需要管了，不要碰了。如果一个位置 没猫->有猫，就需要通过操作1添加或者从其他位置移动过来，如果一个位置 有猫->没猫，就需要通过操作2删除或者从其他位置移动走。正好 有->没 的猫可以放到 没->有 的位置上，如果猫不够就用操作1补，猫多了就移除，总的操作数就是max( 有->没 位置的个数 ， 没->有 位置的个数 ) 。
code：
#include
#include
using namespace std;
const int maxn=1e5+5;
int T,n;
bool vis[maxn];
int main(){
cin>>T;
while(T--){
cin>>n;
int n1=0,n2=0;//有->没 没->有
for(int i=1,t;i<=n;i++){
scanf("%1d",&t);
if(t==1){
n1++;
vis[i]=true;
}
else vis[i]=false;
}
for(int i=1,t;i<=n;i++){
scanf("%1d",&t);
if(t==1){
if(vis[i])n1--;
else n2++;
}
}
cout<<max(n1,n2)<<endl;
}
return 0;
}
C. Sending Messages
题意：
Stepan有n条消息要发，分别要在
m
1
,
m
2
,
…
m
n
m_1, m_2, \dots m_n
m1,m2,…mn
(
m
i
<
m
i
+
1
)
(m_i < m_{i + 1})
(mi<mi+1)时刻发送。一开始手机有
f
f
f 格电量，某个时刻如果电量为 0 ，那么就不能再发送信息了。
每待机1个时刻消耗
a
a
a 格电。或者可以直接关机，之后再开机，每执行这样一个过程会消耗
b
b
b 格电，中间就不会消耗电量了。不考虑开关机消耗的时间。
问Stepan能否发送完所有信息。
思路：
贪心即可，从上一个消息发送的时刻到下一个信息发送的时刻会经过一段时间，比较一下待机这段时间和开关机度过这段时间哪个消耗电量更少，选择少的执行即可，这样手机消耗电量一定是最慢的。如果发送最后一条消息的时候电量
≤
\le
≤ 0（等于零时还没来得及发消息就关机了，发不出去），就说明不能发送完，记得开longlong，不然会吃WA。
code：
#include
#include
using namespace std;
const int maxn=2e5+5;
typedef long long ll;
int T;
int n,a,b;
ll f;
int main(){
cin>>T;
while(T--){
cin>>n>>f>>a>>b;
for(int i=1,t,lst=0;i<=n;i++){
cin>>t;
if(1ll*(t-lst)*a>b)f-=b;
else f-=1ll*(t-lst)*a;
lst=t;
}
puts((f<=0)?"NO":"YES");
}
return 0;
}
D. Very Different Array
题意
Petya有一个有
n
n
n 个正整数的数组
a
a
a，他兄弟Vasya眼红，想要制作一个他自己的有
n
n
n 个正整数的数组。
Vasya先找到
m
m
m 个数
b
i
b_i
bi
(
m
≥
n
)
(m\ge n)
(m≥n)，从中选择n个数并按一定的顺序放到数组
c
c
c 中。
为了避免与他兄弟的数组相似，Vasya希望他的数组与Petya的尽可能不同。具体来说，他希望总差异值
D
=
∑
i
=
1
n
∣
a
i
−
c
i
∣
D = \sum_{i=1}^{n} |a_i – c_i|
D=∑i=1n∣ai−ci∣ 尽可能大。问最大值是多少。
思路：
先不看选了什么数，假设没得选，c数组是固定的，看看c数组元素怎么放才能差异值最大化。
一个简单粗暴的想法就是a数组最大值对c数组最小值，a次大对c次小，类推。反证法证明正确性：
如果a中有两数n和m
(
n
<
m
)
(n<m)
(n<m)，c中有两数x和y
(
x
<
y
)
(x<y)
(x<y)，上面的想法是让n对应y，m对应x。如果这种想法是错的，那么应当n对x，m对y会使得答案更大。如果上面的暴力想法是错的，至少会存在这样一对n m和x y不符合条件。
枚举一下n m x y的大小情况，检验每种情况下是否有反例。
可以发现n m x y的大小情况一共有
C
4
2
=
6
C_{4}^{2} = 6
C42=6 种，而且n m与x y角色互换的话情况还是一样的，所以不同的状态只有3个，直接暴力手玩就可以了，证明如上图。可以发现方式1一定更优。所以这种暴力思想是对的。
另外还有一种证明思路：
把a数组的n个数和c数组的n个数摆在一起排序，把前n个数变负，2n个元素之和就是最大的差异值，而这种暴力想法一定可以得到这个差异值，因此这个暴力想法一定是正确的。
为什么呢？前n个数假设里面有x个a数组的数，那么就有n-x个c数组的数，后面有n-x个a数组的数和x个c数组的数 ，暴力想法一定可以保证前x个a数组的数和后面x个c数组的数配对，前n-x个c数组的数和后面n-x个a数组的数配对，这时差异值就是后n个数减去前n个数。
好的，现在知道了c数组的n个数确定时的答案，那么如何去从m个数里挑n个数出来，使得一定包含最大答案？一个简单的想法就是全都选比较“极端”的数，这样可以尽量和a数组的数拉开差距，答案就大了。具体来说，就是对m个数排序，只取两端的数，中间的不取。接下来反证法证明：
分别对a数组进行降序排列，对b数组进行升序排列，这样在b中取出n个数后得到c数组，因为已经是有序的了，
a
i
c
i
a_i c_i
aici直接按顺序一一对应即可。
如果答案的选取状态是两端各选一部分，中间选一部分，中间的部分和两端的部分不相接，看能否优化为更优的状态：
容易想到，应该存在一个分界线 i，
a
i
>
b
k
a_i > b_k
ai>bk 而
a
i
+
1
≤
b
s
a_{i+1} \le b_s
ai+1≤bs （
a
i
a_i
ai 对应
b
k
b_k
bk，
a
i
+
1
a_{i+1}
ai+1 对应
b
s
b_s
bs），这时
b
k
b_k
bk肯定越小越好，拿
b
k
b_k
bk不如拿一个最靠前的数，而且对前 i 个对应关系中的所有b都是如此，同理，
b
s
b_s
bs肯定越大越好，而且对后 n-i 个对应关系中的所有b都是如此。所以不应当存在中间部分，只要存在就会找到一个更优的情况，这个情况一定不是最大的。
因此我们只要暴力枚举b开头选几个，算出末尾选几个，然后计算出此时最大的分配方式下得到的答案，所有答案中的最大值就是所求。由于开头选 n-i 个，末尾选 i 个的状态到开头选 n-i-1 个，末尾选 i+1 个的状态相当于分配时把
a
n
−
i
−
b
n
−
i
a_{n-i}-b_{n-i}
an−i−bn−i 组换成了
a
n
−
i
−
b
m
−
i
a_{n-i}-b_{m-i}
an−i−bm−i组，上一个状态结果减去
a
n
−
i
−
b
n
−
i
a_{n-i}-b_{n-i}
an−i−bn−i 组的贡献加上
a
n
−
i
−
b
m
−
i
a_{n-i}-b_{m-i}
an−i−bm−i组的贡献就是下一个状态的结果了。所以算出开头选n个，末尾选0个的状态的答案，然后递推即可算出所有情况了。时间复杂度
O
(
m
l
o
g
m
)
O(mlogm)
O(mlogm)。
code：
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int T,n,m;
int a[maxn],b[maxn];
int main(){
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i>a[i];
for(int i=1;i>b[i];
sort(a+1,a+n+1,greater());
sort(b+1,b+m+1);
ll ans=0,tmp=0;
for(int i=1;i<=n;i++)
tmp+=abs(a[i]-b[i]);
ans=tmp;
//这里枚举末尾选取的个数
for(int i=0;i<n;i++){//a[n-i] -> b[m-i]
tmp+=-abs(a[n-i]-b[n-i])+abs(a[n-i]-b[m-i]);
ans=max(tmp,ans);
}
cout<
E. Eat the Chip
题意：
Alice 和 Bob在一个棋盘上下棋，棋盘有 h h h 行 w w w 列，两人各有一个棋子，Ailce的棋子初始在坐标 ( x a , y a ) (x_a, y_a) (xa,ya) 上，Bob的棋子初始在坐标 ( x b , y b ) (x_b, y_b) (xb,yb) 上，保证两人棋子的初始坐标不在一个位置上。Alice先手。
轮到Alice时，她可以将自己的棋子向下，左下或右下移动一格。轮到Bob时，他可以将自己的棋子向上，左上或右上移动一格。移动不允许超出棋盘。
谁先吃到对方的棋子谁赢，当一方走到底的时候（对Alice来说就是走到第h行，对Bob来说就是走到第1行），就达成平局。
给你 h h h， w w w， x a x_a xa， y a y_a ya， x b x_b xb， y b y_b yb，如果双方都不失误，问结果是什么？
思路：
非常明显的博弈论。发现俩人不管怎么移动他们的棋子一定会向前走一格，如果两人的棋子在同一列，移动的时候不左右乱动，那么棋子相遇的时候，谁动来吃对方一定是确定的。假如两个棋子之间隔了len行（ l e n < 0 len\lt 0 len<0 肯定平局不考虑，只看 l e n ≥ 0 len\ge 0 len≥0 的情况），可以看出：当len为偶数的时候，Alice和Bob各走了 l e n 2 \frac {len} 2 2len步，Alice可能获胜，Bob必不可能获胜；当len为奇数的时候，Alice走了 ⌊ l e n 2 ⌋ + 1 \left\lfloor \frac {len} 2 \right\rfloor +1 ⌊2len⌋+1 步，Bob走了 ⌊ l e n 2 ⌋ \left\lfloor\frac {len} 2\right\rfloor ⌊2len⌋步，Bob可能获胜，Alice必不可能获胜。
发现如果一开始两个棋子在同一列上，败者移动一步，胜者就能同样移动一步使得两个棋子一直保持在同一列上，这时胜者必胜。
如果两个棋子不在同一列上，但是Alice是可能的胜者并且两个棋子列数就差1，那么Alice可以选择移动到和Bob同一列的位置上，之后和上面一样，这时Alice必胜。反之如果Alice是可能的败者并且两个棋子列数就差1，那么Alice一定会想办法“逃离”Bob棋子所在列，即向远离Bob棋子所在列的方向移动，如果到墙（地图边界）的距离足够远，那么Alice可以一直耗到两个棋子间隔为0，这时候Bob吃不到Alice，之后就永远吃不到了，达成平局。否则胜者获胜。
如果两个棋子的列差的更远了，那么可能的败者一定会尽力逃离可能的胜者所在列，和上面一样，如果到墙（地图边界）的距离足够远，那么败者可以一直耗到两个棋子间隔为0，这时候胜者吃不到败者，之后就永远吃不到了，达成平局。否则胜者获胜。
看看怎么才算 到墙足够远，因为败者不可能回头，这样胜者也不可能回头，所以走一步就到墙距离-1，一直到胜者走到 到墙距离为1的时候，败者就无路可逃了，也就是说，到墙的距离-胜者的操作数<=1 时，这时胜者获胜。
code：
#include
#include
using namespace std;
int T,h,w,x1,y1,x2,y2;
int main(){
cin>>T;
while(T--){
cin>>h>>w>>x1>>y1>>x2>>y2;
//如果距离为偶数，alice可能胜，否则bob可能胜利
int len=x2-x1-1;
if(len<0)puts("Draw");
else if(abs(y2-y1)==0 || ((len&1)==0 && abs(y2-y1)==1))puts((len&1)?"Bob":"Alice");
else {
//看看败方能否逃脱追捕
if(len&1){
//胜者到墙的距离
int dis=(y2>y1)?y2-1:w-y2;
//步数大于等于到墙的距离-1，产生胜者
puts((len/2>=dis-1)?"Bob":"Draw");
}
else {
int dis=(y1>y2)?y1-1:w-y1;
puts((len/2>=dis-1)?"Alice":"Draw");
}
}
}
return 0;
}
FG题的讲解可以去B站看，这场不知道为什么讲的很多，听着有人说话可能比较容易理解，指路。
F. Sum of Progression
题意：
给你一个有
n
n
n 个数的数组
a
a
a，有
q
q
q 组询问，每次询问给出三个数
s
s
s
d
d
d
k
k
k。
对每组询问，计算
a
s
+
a
s
+
d
⋅
2
+
⋯
+
a
s
+
d
⋅
(
k
−
1
)
⋅
k
a_s + a_{s+d} \cdot 2 + \dots + a_{s + d \cdot (k - 1)} \cdot k
as+as+d⋅2+⋯+as+d⋅(k−1)⋅k 的值。
思路：
如果暴力来算，当步长
d
d
d 很大的时候计算量很小，但是如果
d
d
d 很小
k
k
k 很大的时候就会超时，最坏是
O
(
q
n
)
O(qn)
O(qn) 的。换种思路，每次都是一个“区间”（步长
d
d
d 确定时，原序列可以分成
d
d
d 个子序列，第一个序列是
a
1
,
a
d
+
1
,
a
2
∗
d
+
1
,
…
,
a
x
∗
d
+
1
a_1,a_{d+1},a_{2*d+1},\dots,a_{x*d+1}
a1,ad+1,a2∗d+1,…,ax∗d+1，另外几个序列类推，相当于找到对应的子序列，在子序列上求区间和）的求和，所以试试前缀和，假设把
a
t
+
i
⋅
(
j
−
1
)
⋅
j
a_{ t + i \cdot (j - 1)} \cdot j
at+i⋅(j−1)⋅j 看作一个元素，可以预处理出前缀和来。但是要存下标和步长两维，
n
,
q
≤
1
0
5
n,q\le 10^5
n,q≤105肯定会爆空间，而且光预处理的时间复杂度就很高了。
考虑到
d
d
d 很大的时候
k
k
k 肯定会比较小，这时候直接暴力就很快了，而这时前缀和费事预处理出来每次就查询两三个数的求和肯定不划算。所以考虑
d
d
d 很大的时候直接交给暴力来做，
d
d
d 比较小的时候再前缀和。那么怎么认定d比较大还是比较小，从而分情况使用不同的做法呢？假设
d
≤
x
d\le x
d≤x 时给前缀和，
d
>
x
d\gt x
d>x 时给暴力，前缀和最差时间复杂度就是预处理的时间复杂度，也就是
O
(
n
x
)
O(nx)
O(nx)，暴力的最差时间复杂度是
O
(
q
∗
k
=
q
∗
⌊
n
d
⌋
=
q
∗
⌊
n
x
⌋
≈
⌊
q
∗
n
x
⌋
)
O(q*k=q*\left\lfloor \frac n {d} \right\rfloor=q*\left\lfloor \frac n {x} \right\rfloor \approx \left\lfloor \frac {q*n} {x} \right\rfloor)
O(q∗k=q∗⌊dn⌋=q∗⌊xn⌋≈⌊xq∗n⌋) ，也就是求
⌊
q
∗
n
x
⌋
+
n
∗
x
≈
n
∗
(
x
+
q
x
)
≥
2
∗
n
∗
q
\left\lfloor \frac {q*n} {x} \right\rfloor+n*x \approx n*(x+\frac q x) \ge 2*n*\sqrt q
⌊xq∗n⌋+n∗x≈n∗(x+xq)≥2∗n∗q
，当
d
=
x
=
q
d=x=\sqrt q
d=x=q
时等号成立（均值不等式死去的高中知识突然开始攻击我 ）。不过n q差不多，所以
d
=
x
=
n
d=x=\sqrt n
d=x=n
其实也差不多。
到这里做法就很明显了，根号分治（分治就是分而治之，换句话说就是分情况分开处理），当
d
>
q
d\gt \sqrt q
d>q
时直接暴力计算，当
d
≤
q
d\le \sqrt q
d≤q
时预处理前缀和然后查询区间和即可。最坏时间复杂度是
O
(
2
∗
n
∗
q
)
O(2*n*\sqrt q)
O(2∗n∗q
)（虽然费力预处理出来了，但是查询全是暴力来做） ，
q
=
2
∗
1
0
5
q=2*10^5
q=2∗105 所以
q
≈
500
\sqrt q\approx500
q
≈500 ，总的就要跑
1
0
8
10^8
108 次，虽然时限有2s，还是比较极限的。
那怎么预处理前缀和呢，上面说了把
a
t
+
i
⋅
(
j
−
1
)
⋅
j
a_{ t + i \cdot (j - 1)} \cdot j
at+i⋅(j−1)⋅j 当做一个元素，这样
a
s
+
a
s
+
d
⋅
2
+
⋯
+
a
s
+
d
⋅
(
k
−
1
)
⋅
k
a_s + a_{s+d} \cdot 2 + \dots + a_{s + d \cdot (k - 1)} \cdot k
as+as+d⋅2+⋯+as+d⋅(k−1)⋅k 就变成了前缀和的形式了，设置
f
[
i
]
[
j
]
f[i][j]
f[i][j]，表示第 i 个位置，在步长为 j 的序列里的前缀和，那么它所在序列的第一个元素应该是
(
i
−
1
)
%
d
+
1
(i-1) \% d +1
(i−1)%d+1（因为第1个元素从1开始编号，下标为1 ~ d的元素分别为步长为d时的d个子序列的开头元素，后面类推，需要先把第一个元素和下标0对齐，模完，之后再偏移回去，否则直接模会出错，比如第d个元素本来应该是第一个元素，
i
%
d
i\%d
i%d得到的却是下标0的元素才是序列第一个元素），第 i 个元素的下标应该是
(
⌊
i
−
1
j
⌋
+
1
)
(\left\lfloor \frac {i-1} {j} \right\rfloor+1)
(⌊ji−1⌋+1)（这里 i-1 的原因和上面一样）。那么
f
[
i
]
[
j
]
=
f
[
i
−
j
]
[
j
]
+
(
⌊
i
−
1
j
⌋
+
1
)
∗
a
i
f[i][j]=f[i-j][j]+(\left\lfloor \frac {i-1} {j} \right\rfloor+1)*a_i
f[i][j]=f[i−j][j]+(⌊ji−1⌋+1)∗ai。
在查询
a
s
+
a
s
+
d
⋅
2
+
⋯
+
a
s
+
d
⋅
(
k
−
1
)
⋅
k
a_s + a_{s+d} \cdot 2 + \dots + a_{s + d \cdot (k - 1)} \cdot k
as+as+d⋅2+⋯+as+d⋅(k−1)⋅k 的时候
f
[
s
+
d
⋅
(
k
−
1
)
]
[
d
]
−
f
[
s
−
d
]
[
d
]
f[s + d \cdot (k - 1)][d]-f[s-d][d]
f[s+d⋅(k−1)][d]−f[s−d][d] 得到的却是
a
s
⋅
(
⌊
s
−
1
d
⌋
+
1
)
+
a
s
+
d
⋅
(
⌊
s
−
1
d
⌋
+
2
)
+
⋯
+
a
s
+
d
⋅
(
k
−
1
)
⋅
(
⌊
s
−
1
d
⌋
+
k
)
a_s \cdot {(\left\lfloor \frac {s-1} {d} \right\rfloor+1)} + a_{s+d} \cdot {(\left\lfloor \frac {s-1} {d} \right\rfloor+2)} + \dots + a_{s + d \cdot (k - 1)} \cdot {(\left\lfloor \frac {s-1} {d} \right\rfloor+k)}
as⋅(⌊ds−1⌋+1)+as+d⋅(⌊ds−1⌋+2)+⋯+as+d⋅(k−1)⋅(⌊ds−1⌋+k)，多了
a
s
⋅
⌊
s
−
1
d
⌋
+
a
s
+
d
⋅
⌊
s
−
1
d
⌋
+
⋯
+
a
s
+
d
⋅
(
k
−
1
)
⋅
⌊
s
−
1
d
⌋
a_s \cdot {\left\lfloor \frac {s-1} {d} \right\rfloor} + a_{s+d} \cdot {\left\lfloor \frac {s-1} {d} \right\rfloor} + \dots + a_{s + d \cdot (k - 1)} \cdot {\left\lfloor \frac {s-1} {d} \right\rfloor}
as⋅⌊ds−1⌋+as+d⋅⌊ds−1⌋+⋯+as+d⋅(k−1)⋅⌊ds−1⌋，所以我们还需要再搞一个前缀和来算
a
s
+
a
s
+
d
+
⋯
+
a
s
+
d
⋅
(
k
−
1
)
a_s + a_{s+d} + \dots + a_{s + d \cdot (k - 1)}
as+as+d+⋯+as+d⋅(k−1)，弄个
g
[
i
]
[
j
]
=
g
[
i
−
j
]
[
j
]
+
a
i
g[i][j]=g[i-j][j]+a_i
g[i][j]=g[i−j][j]+ai 即可。给
f
[
s
+
d
⋅
(
k
−
1
)
]
[
d
]
−
f
[
s
−
d
]
[
d
]
f[s + d \cdot (k - 1)][d]-f[s-d][d]
f[s+d⋅(k−1)][d]−f[s−d][d] 减去
(
g
[
s
+
d
⋅
(
k
−
1
)
]
[
d
]
−
g
[
s
−
d
]
[
d
]
)
⋅
⌊
s
−
1
d
⌋
(g[s + d \cdot (k - 1)][d]-g[s-d][d])\cdot {\left\lfloor \frac {s-1} {d} \right\rfloor}
(g[s+d⋅(k−1)][d]−g[s−d][d])⋅⌊ds−1⌋ 即可。
根号分治威力如此巨大，把两个时间复杂度平方的算法合在一起就变成了一个时间复杂度n根号q的算法。究其原因是暴力算在步长很大的时候枚举次数很少，所以把步长很大的情况交给暴力来算，从而减轻了前缀和的负担，使得前缀和只需要对长为n的序列，步长小于
O
(
n
)
O(\sqrt n)
O(n
) 的情况进行处理即可。而这个情况的划分就是以步长为
n
\sqrt n
n
为界，完美的暴力！
code：
通过时间不稳定，两次1800ms，一次1500ms，而且
s
q
t
=
q
sqt=\sqrt q
sqt=q
和
s
q
t
=
n
sqt=\sqrt n
sqt=n
的用时没有太大差别。有点卡常，能优化的地方尽量优化。
#include
#include
#include
#include
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
int T,n,q,a[maxn];
ll f[maxn][500],g[maxn][500];//序号 步长
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&q);
int sqt=sqrt(q);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
for(int d=1;d<=sqt;d++){
// printf("d=%d:\n",d);
for(int i=1;i<=n;i++){
f[i][d]=((i-d>0)?f[i-d][d]:0ll)+1ll*a[i]*((i-1)/d+1);
g[i][d]=((i-d>0)?g[i-d][d]:0ll)+a[i];
// printf("%d %d\n",f[i][d],g[i][d]);
}
}
ll ans;
for(int i=1,s,d,k;i<=q;i++){
scanf("%d%d%d",&s,&d,&k);
ans=0;
if(d>sqt){
for(int j=0;j<k;j++)
ans+=1ll*a[s+j*d]*(j+1);
}
else {
ans=f[s+d*(k-1)][d]-((s-d>0)?f[s-d][d]:0);
// printf("%d\n",ans);
ans-=(g[s+d*(k-1)][d]-((s-d>0)?g[s-d][d]:0))*((s-1)/d);
}
printf("%lld\n",ans);
}
}
return 0;
}
G. Mischievous Shooter
题意：
有一个
n
∗
m
n*m
n∗m 的网格图，每个格子有一个或者没有猎物。Shel有一把幸运猎枪，一次只能向左上、右上、左下、右下四个方向开火，开火后可以击中所有在这个方向上到开火位置曼哈顿距离
≤
k
\le k
≤k 的猎物。Shel可以站在任何位置向任何方向开火一次，问最多能击中多少猎物。（建议去题目看图和样例解释，非常详细）。
思路：
发现
n
∗
m
≤
1
0
5
n*m \le 10^{5}
n∗m≤105，所以可以暴力枚举地图上的每个位置，对每个位置枚举四个方向，如果可以快速查询的话就好了。
先确定一个朝向，看怎么实现快速查询，假设我们只向左下射击（第一个配图的的第3个）。枚举肯定不行，如果预处理每列的前缀和，可以优化成每次
O
(
k
)
O(k)
O(k)查询，仍然会超时。既然从零开始算行不通，试试从上一个情况递推过来。可以发现，从白点移动到黑点，移动一格，就会有 k+1 个竖着的蓝色方格加入，k+1个红色方格失去。如下图：
所以可以预处理每列 猎物个数的前缀和，假设
a
[
i
]
[
j
]
a[i][j]
a[i][j] 为第 j 列前 i 格的猎物数，那么蓝色部分就等于
a
[
x
+
k
]
[
y
]
−
a
[
x
−
1
]
[
y
]
a[x+k][y]-a[x-1][y]
a[x+k][y]−a[x−1][y]。再搞一个斜着的前缀和（135°对角线上的元素），即
b
[
i
]
[
j
]
=
b
[
i
−
1
]
[
j
−
1
]
+
该处猎物个数
b[i][j]=b[i-1][j-1]+该处猎物个数
b[i][j]=b[i−1][j−1]+该处猎物个数，那么红色部分就等于
b
[
x
+
k
]
[
y
−
1
]
−
b
[
x
−
1
]
[
y
−
k
−
2
]
b[x+k][y-1]-b[x-1][y-k-2]
b[x+k][y−1]−b[x−1][y−k−2]。
问题在于有时候在地图边缘会卡掉一部分格子，空间没开足来算会RE，如何解决？
先看蓝色格子，发现只有下面有可能超出 n，超出的部分就不要了，取
m
i
n
(
n
,
x
+
k
)
min(n,x+k)
min(n,x+k) 即可。
红色格子比较难搞，首先是这个位置是在刁钻，没有红色的生存位置，这时就不用算红色了，如下图：
要想
(
n
,
1
)
(n,1)
(n,1) 坐标摸到红色格子，需要它到
(
x
,
y
−
1
)
(x,y-1)
(x,y−1) 的曼哈顿距离
≥
k
\ge k
≥k，也就是
n
−
x
+
y
−
2
≥
k
n-x+y-2\ge k
n−x+y−2≥k。这时才需要算红色格子，这时需要找到两个点的位置，分别是 圈黑圈 和 圈绿圈 的位置。
由于这两个圈都在边缘位置，所以到
(
x
,
y
−
1
)
(x,y-1)
(x,y−1) 的曼哈顿距离都是
k
k
k。
黑圈第一维确定是
n
n
n，因此坐标就是
(
n
,
n
−
x
−
1
+
y
−
k
)
(n,n-x-1+y-k)
(n,n−x−1+y−k)，当
n
≥
x
+
k
n\ge x+k
n≥x+k 时，取
(
x
+
k
,
y
−
1
)
(x+k,y-1)
(x+k,y−1) 点。
绿圈第二维确定是
1
1
1，因此坐标就是
(
x
+
k
−
y
+
2
,
1
)
(x+k-y+2,1)
(x+k−y+2,1)，它左上的那个点就是
(
x
+
k
−
y
+
1
,
0
)
(x+k-y+1,0)
(x+k−y+1,0)，当
y
−
1
−
k
≥
1
y-1-k\ge 1
y−1−k≥1 时，取
(
x
,
y
−
1
−
k
)
(x,y-1-k)
(x,y−1−k) 点，这时它左上角的点为
(
x
−
1
,
y
−
2
−
k
)
(x-1,y-2-k)
(x−1,y−2−k)。
之后就只需要抄一段超长的意义不明的算式上去就可以了（我一开始把上面所有的情况在一句话里讨论了，然后就…）
好的，我们现在解决了朝向左下的情况，还有三种情况，直接再抄三个豆腐块上去就行了 。可以发现另外三种情况对朝向左下的情况进行旋转就行了，因为旋转朝向和旋转地图没有差别，所以我们对地图进行旋转，预处理前缀和，枚举位置，旋转，然后循环。就能用一个for循环实现四种情况的检验了。
另一个问题是怎么存储地图，由于
n
,
m
≤
1
0
5
n,m\le 10^5
n,m≤105 而
n
∗
m
≤
1
0
5
n*m\le 10^5
n∗m≤105，静态空间肯定开不下，所以开动态空间，但是在旋转的时候，n会变成m，所以我们存储旋转后的地图也要动态来开，地图数组开到
[
n
+
1
]
[
m
+
1
]
[n+1][m+1]
[n+1][m+1]，旋转后数组开到
[
m
+
1
]
[
n
+
1
]
[m+1][n+1]
[m+1][n+1] 即可，之后直接赋值给地图数组即可。这题对代码实现能力要求很高，思路倒是不是很难。
code：
#include
#include
#include
#include
using namespace std;
int T,n,m,k;
int main(){
cin>>T;
while(T--){
cin>>n>>m>>k;
vector<vector > mp(n+1,vector(m+1));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf(" %c",&mp[i][j]);
int ans=0,tmp;
for(int round=1;round<=4;round++){
vector<vector > a(n+1,vector(m+1));//列前缀和
vector<vector > b(n+1,vector(m+1));//对角线前缀和
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
a[i][j]=a[i-1][j]+(mp[i][j]=='#');
b[i][j]=b[i-1][j-1]+(mp[i][j]=='#');
}
// for(int i=1;i<=n;i++,puts(""))
// for(int j=1;j<=m;j++){
// printf("%d ",a[i][j]);
// }
// puts("");
// for(int i=1;i<=n;i++,puts(""))
// for(int j=1;j<=m;j++){
// printf("%d ",b[i][j]);
// }
// puts("");
for(int x=1;x<=n;x++){
tmp=0;
for(int y=1;y<=m;y++){
tmp+=a[min(x+k,n)][y]-a[x-1][y];
if(n-x+y-2>=k)
tmp-=((n>=x+k)?b[x+k][y-1]:b[n][n-x-1+y-k])-((y-1-k>=1)?b[x-1][y-2-k]:b[x+k-y+1][0]);
ans=max(ans,tmp);
}
}
vector<vector > t(m+1,vector(n+1));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
t[m-j+1][i]=mp[i][j];
swap(n,m);
mp=t;
// for(int i=1;i<=n;i++,puts(""))
// for(int j=1;j<=m;j++)
// cout<<mp[i][j];
// puts("");
}
cout<
也算是广义AK了吧，累死我了。
本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/9fa6a9a72f.html
相关推荐
-
【Python】让Anaconda不再下载慢下载失败，Anaconda的下载源更换为国内源（保姆级图文）
目录 对于源的添加与修改 1. 查看源 3. 移除源 4. 恢复默认源 检查添加源是否生效 清理原来的索引配置 总结 欢迎关注 『Python』 系列，持续更新中 欢迎关注 『Py…
-
遍历网络密码（python系列之——pywifi库）
目录 1.pywifi下载方式 2.pywifi使用方法 扫描可用的无线网络 连接WiFi 3.实战 1.pywifi下载方式 pywifi是一个可以在python中连接网络的第…
-
Jupyter notebook没有创建python3的选项解决
jupyter提示找不到kernel，因此为其增加内核 首先安装ipkernel包： python3 -m pip install ipykernel 针对当前用户安装ipkern…
-
关于 【AttributeError: module ‘collections‘ has no attribute ‘Mapping‘】出现的问题
这个错误通常是由于在Python 3.9或更高版本中，从以上图片中看到的版本是Python3.11，`collections.Mapping`被删除所致。如果使用的是…
-
【数据结构与算法】之排序系列-20240201
【数据结构与算法】之排序系列-20240201 一、88. 合并两个有序数组 二、169. 多数元素 三、217. 存在重复元素 四、242. 有效的字母异位词 五、268. 丢失…
-
【python】如何安装requests库，以及如何引用（含报错如何解决）
非常非常重要，后期操作大多都需要requests库，那么这篇文章就来分享下如何安装requests库，以及在python中如何引用 首先，看一下如何安装 1、定位到python的 …
-
Python | 基于Mediapipe框架的手势识别系统
一、项目要求 1、题目 本题着力于解决会商演示系统中的非接触式人机交互问题，具体而言，其核心问题就是通过计算机视觉技术实现对基于视频流的手势动作进…
-
python 查找波峰和波谷
import numpy as np import matplotlib.pyplot as plt from scipy.signal import find_peaks # 生…
-
average
最近在复现论文时发现作者使用了 sklearn.metrics 库中的 average_precision_score() 函数用来对分类模型进行评价。 看了很多博文都未明白其原理…
-
【JAVA】为什么代码会重排序
🍎个人博客：个人主页 🏆个人专栏：JAVA ⛳️ 功不唐捐，玉汝于成 目录 前言 正文 编译器重排序： 处理器重排序： 内存屏障（Memory B…
