该篇Codeforces解题日志撰写时，距离上一次发布【主站】《Codeforces Round #832 (Div. 2) 解题日志》已经过去了整整45天，警钟撅烂（
赛后总结
UPD：成功拿回了自己的Pupil QAQ。
运气实在过于好了，好的有点危险（
说实话如果考核赛没取消，在考试环境下，我还不一定能靠自己推出连续平方之和的公式，D题的查错也会慢个几分钟，就不一定能在比赛的时候小优
说实话赛后的虚拟赛和真的打比赛虽然大差不差，但还是有区别的：能够强化自己“功亏一篑”的懊悔感（bushi）。在赛后做完题看题解的“事后诸葛亮”我也经历了不少（都写在之前的题解里呢），“不就是XX思想嘛”和“我X，还是败给了XX思想”，真的是完全不同的两种心情。现在作为连Pupil底裤都输光的人，算是克服了“题目不难，但是真不敢做”的心理，毕竟掉分也是计划内的一部分（雾）。
A. Joey Takes Money
又是迎·新·赛.jpg，所有数两两求积约等于把所有数都乘起来。
namespace lovelive{
typedef long long LL;
LL ai,n,sumi;
void main(){
cin>>n;sumi=1;
for(int i=1;i<=n;i++){
cin>>ai;
sumi *= ai;
}
sumi += n-1;
cout<<2022*sumi<<endl;
return;
}
}B. Kill Demodogs
十分羞愧地靠直觉找出了沿对角线走最大的走法并在赛时做了简单的验证，更严格的证明可以看官方解。
官方解证明的大致方式是第一数学归纳法（由于是对称矩阵所以只讲一种情况）：
- 若已知从(1,1)到(n-1,n-1)的最大值，则这个值一定不小于在第 $i$ 行时赶到第 $n-1$ 列并且笔直走到 $(n-1,n-1)$ 的值；
- 根据 $n-1$ 得出的情况，得到沿对角线走到(n,n)的情况：(n-1,n-1) -> (n,n) = 从(1,1)到(n-1,n-1)的最大值 + (n-1,n) + (n,n)；
- 然后将第二步得到的值 与 第 $i$ 行时赶到第 $n$ 列并且笔直走到 $(n,n)$ 的值相比较，经过运算得到前者不小于后者。
官方给出的公式解为：
$$
\sum{i = 1}^n{i \cdot i} + \sum{i = 1}^{n-1}{i (i + 1)} = \frac{n(n + 1)(4n – 1)}{6}
$$
我自己实际上的解法（其实就是把两个sum分开算了）：
$$
\sum{i = 1}^n{i \cdot i} = \frac{(n-1)\cdot n\cdot (n+1)}{3} \newline
\sum{i = 1}^{n-1}{i (i + 1)} = \frac{n\cdot(n+1) \cdot (2\cdot n+1)}{6}
$$
因为c++总是爆一些奇怪的精度问题，于是直接上Python了（
t = int(input())
while t:
t-=1
n = int(input())
a = ((n-1)*n*(n+1)) // 3
b = (n*(n+1)) * (2*n+1) // 6
c = 2022*(a+b)
c %= 10**9 + 7
print(c)C. Even Subarrays
比赛时已经想到的：
- 记录前缀异或和；
- 对于一个异或和，通过枚举可行解的方式，对该可行解利用异或的“两次异或等于没做”找出另一个端点；
- 预记录前缀异或和出现的次数减少查询异或和的时间复杂度；
- 奇数个约数的数，只有完全平方数。
比赛时没有想到的/功亏一篑的：
- 可行解太多了，枚举不过来 -> 正难则反，只枚举完全平方数，最后用总方案减去不合法方案不就可以了吗？！
（错误想法：脑子糊涂，想到差分去了，绕了半天没绕出来） - 在线处理前缀异或和以及其计数，这样可以轻松避免重复情况；
- 注意上限问题：由于最大值不超过 $n$ ，可行前缀和不会超过
n << 1，但有可能超过 $n$ ； - 注意运算优先级：位运算的优先级有些混乱，赛后被这个地方卡了半天。
namespace lovelive{
//最后还是输在了正难则反
int ai[400005],xori[400005],cnti[400005];
LL ans,n;int maxn;
void main(){
memset(cnti,0,sizeof(cnti));
cin>>n;xori[0] = 0;cnti[0] = 1;
ans = 0;maxn = 0;
for(int i=1;i<=n;i++){
cin>>ai[i];
xori[i] = xori[i-1] ^ ai[i];
for(LL j=0;j*j<2*n;j++){
if(((j*j)^xori[i])<(2*n))ans += cnti[(j*j)^xori[i]];
}
cnti[xori[i]]++;
}
ans = ((n+1)*n)/2 - ans;
cout<<ans<<endl;
}
}D. Valiant’s New Map
求二维区间最小值……不就是之前吐槽过的“进行两次处理的大号滑动窗口”【主站】《ZJUT2022入门题单Week4 程序简注》 – R – 理想的女主角正方形？！由于格子的总数是确定的，估算下用于“答案判断”的时间复杂度为O(N)没什么问题，根据数据范围很自然地就往O(logN)的方向寻找“寻找答案”的算法了——二分呼之欲出。由于对于 $l \times l$ 并且最小值不小于 $l$ 的矩阵来说，其所有的 $(l-1) \times (l-1)$ 子矩阵最小值也不会小于 $l$ ，自然也不会小于 $l-1$ 。
namespace lovelive{
typedef long long LL;
int n,m,ai[1000005],mini[1000005],l,r,mid;
inline int calc(int i,int j){
return i*m+j;
}
bool check(int l){
deque<pair<int,int>> que;
//先按照行处理
bool flag=false;
//debug//cout<<"check : "<<l<<endl;
for(int i=0;i<n;i++){
que.clear();
for(int j=0;j<l-1;j++){
while(!que.empty()&&que.back().first>ai[calc(i,j)]){
que.pop_back();
}
que.push_back(make_pair(ai[calc(i,j)],j));
}
for(int j=l-1;j<m;j++){
while(!que.empty()&&que.back().first>ai[calc(i,j)]){
que.pop_back();
}
que.push_back(make_pair(ai[calc(i,j)],j));
while(!que.empty()&&que.front().second<j-l+1)que.pop_front();
mini[calc(i,j-l+1)] = que.front().first;
if(mini[calc(i,j-l+1)]>=l)flag=true;
//debug//cout<<que.front().first<<" ";
}
//debug//cout<<endl;
}
if(!flag)return false;
flag = false;
for(int j=0;j<=m-l;j++){
que.clear();
for(int i=0;i<l-1;i++){
while(!que.empty()&&que.back().first>mini[calc(i,j)]){
que.pop_back();
}
que.push_back(make_pair(mini[calc(i,j)],i));
}
for(int i=l-1;i<n;i++){
while(!que.empty()&&que.back().first>mini[calc(i,j)]){
que.pop_back();
}
que.push_back(make_pair(mini[calc(i,j)],i));
while(!que.empty()&&que.front().second<i-l+1)que.pop_front();
if(que.front().first>=l)flag = true;
//debug//cout<<que.front().first<<" ";
}
//debug//cout<<endl;
}
return flag;
}
void main(){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>ai[calc(i,j)];
}
}
l = 1;r = min(n,m);
while(l<r){
mid = (l+r+1)>>1;
if(check(mid)){
l = mid;
}else{
r = mid - 1;
}
}
if(check(l))cout<<l<<endl;
else cout<<0<<endl;
return;
}
}E. Graph Cost
深入未知领域
题目明着告诉你的：
- 初始为一张没有边的点图，$n$ 个点的值为 $1$ 到 $n$；
- 每一次操作可以以 $k+1$ 的代价，添加恰好 $k$ 条边，以下称为“操作 $k$ ”；
- 两个点（不允许自环）之间可以通过“操作 $k$ ”添加边的充要条件为：两个点值 $a$ 、 $b$ 满足 $gcd(a,b) = k+1$ ，并且两个点之间没有加过边；
- 题目想知道进行如上若干次操作添加恰好 $m$ 条边的最小代价（可能不可行）。
分析题目的信息：
- $n$ 最高有 $10^6$ 数量级，而可能添加的边可能会使最终产生一张稠密图，稠密图的边数过多无法通过存图解决问题，故这是一道披着图论外表的纯数题；
- 执行一次“操作 $k$ ”产生 $k+1$ 的代价 -> 执行 $s$ 次不同的“操作 $k$ ”制造总共 $m$ 条边会产生总共 $m+s$ 的代价，由于该代价中的 $m$ 由题目给定而没有优化空间，为了使代价尽可能小，需要优化操作使得操作数量尽可能少，也就是说单次操作加的边要尽可能多；这个贪心处理的好处在于，在处理那些比较小的类似于$1$之类的gcd值的时候，有了之前的铺垫，复杂度最多为
O(N)级别的，也就不用担心接下来的处理会爆炸； - 注意看“操作 $k$ ”可行的操作点中，其值一定带有约数 $(k+1)$，但由所有“带有约数 $(k+1)$ ”的点集中，可能存在两两之间 $gcd(a,b) = a \times (k+1),(a \gt 1)$ 的点对，也同样可能存在 $a \times gcd(a,b) = (k+1),(a \gt 1)$ 的点对；遇到这种纠缠不清的情况不要慌！由于操作的前置条件为充要条件，所以同一条边不可能通过多种方式被添加，这时候就可以用容斥原理再次正难则反，把点集中所有满足条件的点两两配对，再把所有不满足条件的全部删掉，而计算出不满足条件的点可以运用到之后gcd值更小的计算中，这就是动态规划（或者官解中提到的数论方向的“莫比乌斯函数$\mu (n)$”）；
如何付诸实践：
-
判断每一个gcd值所能操作的数量：灵活运用动态规划，得到每一个权值为$k$的边的可能性：
$$
dp[k] = \frac{1}{2} \left\lfloor \frac{n}{k} \right\rfloor ( \left\lfloor \frac{n}{k} \right\rfloor – 1) − dp[2k] − dp[3k] − \dots − dp[\left\lfloor \frac{n}{k} \right\rfloor k]
$$以及可以进行的操作数量：
$$
s[k] = \left\lfloor \frac{dp[k]}{k – 1} \right\rfloor
$$ -
选择适合的操作：注意到 $s[k]$ 是单调不增的，而 $k$ 的值越大，每一次操作中的加边数量就越多，于是就可以从右到左贪心取包。
一些啸问题：
- 虽不经常但是致命的没有memset0问题；
- 经典的数据精度太小问题；
- 与没有memset0问题伴生的memset超时问题；
- 在比赛正式评测时给得意的你当头痛击的数组开太小问题。
namespace lovelive{
typedef long long LL;
LL dp[1000005],s[1000005];
LL n,m,m1,cnt;
void main(){
cin>>n>>m;m1=m;
for(int i=n/2;i>1;i--){
//只有n/2开始才会有至少两个点
dp[i] = (n/i) * (n/i - 1) / 2;
for(int j=2;j<=(n/i);j++){
dp[i] -= dp[j*i];
}
s[i] = dp[i] / (i-1);
}
cnt = 0;
for(int i=n/2;i>1;i--){
if(s[i] * (i-1)<=m){
m -= s[i] * (i-1);
cnt += s[i];
}else{
cnt += m / (i-1);
m -= (m / (i-1)) * (i-1);
}
//cout<<"DEBUG\t"<<i<<"\t"<<s[i]<<"\t"<<cnt<<"\t"<<m<<endl;
dp[i] = 0;
}
if(m)cout<<-1<<endl;
else cout<<cnt+m1<<endl;
return;
}
}
