专栏文章

题解：P11670 [USACO25JAN] Cow Checkups S

cchenxi2009
P11670题解参与者 8已保存评论 13

文章操作

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

当前评论
12 条
当前快照
1 份
快照标识符
@miqc0gdp
此快照首次捕获于
2025/12/04 02:19
3 个月前
此快照最后确认于
2025/12/04 02:19
3 个月前
查看原文
本文含有二创成分。
我和乐土仙尊乃是至交好友！
你是蛊修世界中的一名蛊师，以传播大爱为己任。
今天你收到至交好友乐土的传信，信中称他遭具羊、星宿两名魔头的围攻，恳求你速速送来一件关键蛊材助他脱困。
事实浮冰的形成十分繁琐，这需要你洞悉一种律道蛊方的所有变式。具体而言，这道蛊方由上、下两卷组成，每一卷均由 nn 个凡蛊组成，上卷的凡蛊从左向右为 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n，下卷对应的蛊虫为 b1,b2,⋯ ,bnb_1,b_2,\cdots,b_n。蛊方的契合度为 ai=bia_i=b_i 的位置 ii 的个数。
形成蛊方的变式需要你恰好做一次如下操作：选择两个正整数 l,rl,r，将 al⋯ra_{l\cdots r} 翻转。
由于事实往往不是完美的，你只需要知道所有 n(n+1)2\frac{n(n+1)}{2} 种变式的契合度之和，而不需要给出具体每一种方案的契合度。
附加任务
事态紧急，若是有线性复杂度的方案就再好不过了。

思路

考虑统计每一对 ax=bya_x=b_y 配对起来做出贡献的方案数。
axa_x 与 bxb_x 配对
有两种情况可以使原本处在相同位置的两个蛊配对：它们不处在翻转范围内（r<xr<x 或 x<lx<l），或它们是翻转操作的中心（x=l+r2x=\frac{l+r}{2}）。
前者分开计算翻转区间在 xx 左边和右边的的方案数，具体为：
x(x−1)2+(n−x)(n−x+1)2=x(x−1)+(n−x)(n−x+1)2\frac{x(x-1)}{2}+\frac{(n-x)(n-x+1)}{2}=\frac{x(x-1)+(n-x)(n-x+1)}{2}
后者计算以 xx 为中心的方案数即可，简单统计发现数量为 min⁡(x,n−x+1)\min(x,n-x+1)。
axa_x 与 byb_y（x≠yx\ne y）配对
axa_x 与 byb_y 配对当且仅当 axa_x 被翻转到了 aya_y 的位置，我们不妨钦定 x<yx<y。显然要做到这一点操作必须是 (x−m,y+m)(x-m,y+m)（mm 为自然数）的形式，根据边界 x−m≥1,y+m≤nx-m\ge1,y+m\le n 可得这样的方案有 min⁡(x,n−y+1)\min(x,n-y+1) 种。
考虑拆掉这个 min⁡\min，统计每一个 xx 或 n−y+1n-y+1 作为较小值被取了多少次。
可以发现 xx 作为较小值，代表的就是 xx 与序列左端的距离比 yy 离序列的右端的距离短，做出贡献的次数就是比 xx 更靠近中央的 yy 使 ax=bya_x=b_y 的数量。n−y+1n-y+1 的贡献同理。
当然 ay=bxa_y=b_x 也要统计。
整体来看，做法就是从中央向两边扩展，统计 aa、bb 数组中已经被扩展部分中每个值的出现次数，每次加入一个 axa_x、bxb_x，它做出贡献的次数就是在它之前另一个数组内相同的值出现的次数，每次做出贡献的量为 min⁡(x,n−x+1)\min(x,n-x+1)。
可以参考代码理解，时间复杂度 O(n)O(n)。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
int n,a[600000],b[600000],cnta[600000],cntb[600000],l,r;
long long ans;
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
    for(int i = 1;i <= n;i ++) scanf("%d",&b[i]);
    l = n / 2 + 1,r = n / 2;//从中央开始扩展
    for(int i = 1;i <= n;i ++) if(a[i] == b[i]) ans += min(i,n - i + 1) + (1ll * i * (i - 1) + 1ll * (n - i) * (n - i + 1)) / 2;//a_i = b_i 做出的贡献
    for(int i = 1;i <= (n + 1) / 2;i ++){//每次扩展往左往右都分别扩展一个长度
        if(++ r > n) break;//防越界
        ans += 1ll * (cntb[a[r]] + cnta[b[r]]) * (n - r + 1);//a_r 和 b_r 做出的贡献
        cnta[a[r]] ++,cntb[b[r]] ++;//统计 a_r 和 b_r 出现的次数
        if(-- l <= 0) break;
        ans += 1ll * (cntb[a[l]] + cnta[b[l]]) * l;//向左扩展，同理
        cnta[a[l]] ++,cntb[b[l]] ++;
    }
    printf("%lld",ans);
    return 0;
}

后记

在最关键的时刻，你终于来到了乐土身边，扭转了战局。
乐土抓住你的手臂做出/bx 的表情，双眼瞪大，感动地说不出话来。
又是传播大爱的一天呢。

评论

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

正在加载评论...