USACO 2024 January Contest Bronze 铜组题解

前言

感觉这次难度完全没有去年 12 月的铜组高，那个时候刚学三个月看到那几个题直接爆零，这次直接在研学路上用手机 ak 了。。

T1 - Majority Opinion

题意

给定一个长度为 $N$ 的序列 $h$，每次操作可以选择一个 $h$ 的连续子串，并且将其中的元素全部修改成子串中出现次数最多且超过其长度一半的元素，输出在经过若干次操作后，可以让哪些元素 $h_i$ 成为序列中唯一一种元素。

思路

看到 $N$ 的数据范围是 $2\times 10^5$，我们首先思考 $\mathcal O(N)$ 的算法。
很容易想到，序列 $h$ 中存在三个元素，其中有两个相同的 $h_i$（即序列中存在两个距离相隔不超过一个元素的 $h_i$） 是 $h_i$ 满足题面要求的充分条件，因为我们可以先把这三个元素全部修改为 $h_i$，然后就可以一点点将 $h_i$ 扩展到整个 $h$ 序列里。
以下是充要条件的证明：

做法证明

假设 $h$ 中距离相隔最短的两个 $h_i$ 之间间隔为两个元素或以上。
那么一个包含最多 $h_i$ 的子串必然是以下形式：

$h_i,x,x,h_i,x,x,h_i$

即头、尾均为 $h_i$，每两个 $h_i$ 相隔两个元素，子串长度 $l=3k+1(k\in \mathbb{N^+})$。
此时子串里包含的 $h_i$ 数量为 $\frac{l-1}{3}+1=\frac{l+2}{3}=\frac{2l+4}{6}$，而题面中的要求数量最少为 $\lceil\frac{l}{2}\rceil=\frac{l+1}{2}$，由于 $l\geq4$，解不等式可得该子串中的 $h_i$ 数量一定不满足题目要求。

实现

在循环里对每个 $h_i$ 扫一遍，判断是否出现 $h_{i-1}=h_{i+1}$，$h_i=h_{i-1}$ 或 $h_i=h_{i+1}$ 的情况，如果出现就用一个 map 记录下来，然后排序输出即可。

代码

int h[200005];
int d[200005];    //满足要求的元素
map<int,bool> f;    //记录满足要求的元素
map<int,bool> vis;
void solve(){
    f.clear();vis.clear();
    int n;read(n);
    for(int i=1;i<=n;i++){read(a[i]);}
    a[0] = -1,a[n+1] = -1;	//防止第1个元素被判定为与第0个元素相同或最后一个元素被判定为与第n+1个元素相同
    bool nf = 0;	//记录是否有解，无解输出-1
    for(int i=1;i<=n;i++){
        if(a[i-1]==a[i] || a[i+1]==a[i]){
            nf = 1;
            f[a[i]] = 1;
        }
        if(a[i-1]==a[i+1]){
            nf = 1;
            f[a[i-1]] = 1;
        }	//标记当前的解
    }
    if(nf){
        int cnt = 0;
        for(int i=1;i<=n;i++){	//再扫一遍，把所有满足要求的元素放到数组d里
            if(f[a[i]] && !vis[a[i]]){	//有解且不与之前的解重复
                cnt++;
                d[cnt] = a[i];
                vis[a[i]] = 1;
            }
        }
        sort(d+1,d+1+cnt);	//排序
        for(int i=1;i<=cnt;i++){
            cout<<d[i];
            if(i!=cnt)	cout<<" ";
        }
    }
    else	cout<<-1;	//无解
    cout<<"\n";
}

int main(){
    int t = 1;
    read(t);
    for(int tt=1;tt<=t;tt++){
        solve();
    }
}

T2 - Cannonball

题意

给定一个长度为 $N$ 的序列和 Bessie 的起始位置 $S$，Bessie 在初始状态下在序列的 $S$ 处，能量为 $1$，方向向右。Bessie 每次进行弹跳会向前跳 $k$ 个单位。
如果 Bessie 跳到的位置 $i$ 是跳板，Bessie 的能量会增加 $v_i$；如果位置 $i$ 是目标，且 Bessie 的能量大于 $q_i$，则 Bessie 可以击破该目标，否则不能击破。目标不会改变她的方向或能量值。
输出在 Bessie 离开序列范围内或在序列内无限弹跳之前，她能击破多少个目标。

思路

按照题意模拟即可。
终止的条件有两种，第一种自然是 Bessie 跳到 $\leq 0$ 或 $\geq N$ 的位置上，第二种则是在跳到同一个目标上时，Bessie 面朝的方向、能量值均相同，会陷入死循环。

代码

int n,s;
int t[100005],v[100005],tg[100005];
//tg[i]代表如果第i个位置是目标，能否在退出前被击破
map<int,bool> vis[100005];    //判断死循环
int ans = 0;
void search(int p,int x,int d){    //代表当前位置、能量值和方向，向右为1，向左为-1
    int fp = p;	//代表下一次跳到的位置
    if(t[p]){	//如果该点是目标
        if(x>=v[p])	tg[p] = 1;	//可以击破
        if(vis[p][x*d])	return;	//死循环
        vis[p][x*d] = 1;
    }
    else{	//如果该点是跳板
        x+=v[p];	//增加能量
        d = -d;		//改变方向
    }
    fp = p+d*x;
    if(fp<=0 || fp>n)	return;	//越界
    else	search(fp,x,d);	//继续模拟
}
void solve(){
    cin>>n>>s;
    reset(tg,0);
    for(int i=1;i<=n;i++){
        cin>>t[i]>>v[i];
    }
    search(s,1,1);
    for(int i=1;i<=n;i++)	ans+=tg[i];	//统计答案
    cout<<ans;
}
int main(){
    //int t = 1;
    //read(t);
    for(int tt=1;tt<=1;tt++){
        solve();
    }
}

T3 - Balancing Bacteria

题意

给定一个长度为 $N$ 的序列 $a$，可以进行如下操作：

• 选定一个值 $L$（$1\leq L\leq N$）
• 对序列进行两种修改之一，使得 $a_N\gets a_N+L,a_{N-1}\gets a_N+(L-1),\cdots,a_{N-L+1}\gets a_{N-L+1}+1$ 或 $a_N\gets a_N-L,a_{N-1}\gets a_N-(L-1),\cdots,a_{N-L+1}\gets a_{N-L+1}-1$。

求进行若干次操作，使得序列 $a$ 中的元素全部变为 $0$ 的最少次数。

思路

想让序列全部归零，必须从第 $1$ 个元素开始修改，否则如果从第 $i$ 个元素进行修改，那后续再对 $[1,i)$ 之间的元素进行修改就会影响到 $i$ 的值。
所以我们的修改流程就是首先选定 $L=N$，进行 $|a_1|$ 次操作使 $a_1$ 归零，然后选定 $L=N-1$，进行 $|a_2|$ 次操作后使 $a_2$ 归零（注意此时 $a_2$ 的值是已经被修改过的），最后选定 $L=1$，进行 $a_N$ 次操作后序列就全部归零了。
现在的问题就是求出第 $i$ 次修改前 $a_i$ 的值是多少，设第 $i$ 次修改前 $a_i$ 的值是 $d_i$，操作次数总和即为 $\sum^{N}_{i=1}|d_i|$。
下面就是愉快的推式子环节。

递推方法

显然 $d_1=a_1$，因为第一个元素是第一个被修改的。
在进行完 $|d_1|$ 次 $L=N$ 的操作后，$a_1$ 的值变为 $0$，也就是减小了 $d_1$，则 $a_2$ 被修改为 $d_2-d_1\times 2=a_2-a_1\times 2$，$a_i$ 被修改为 $d_i-d_1\times i=a_i-a_1\times i$。
同理，在进行完 $|d_2|$ 次 $L=N-1$ 的操作后，$a_2$ 的值变为 $0$，也就是减小了 $d_2$，则 $a_3$ 被修改为 $d_3-d_2\times 2=a_3-d_1\times 3-d_2\times 2$，$a_i$ 被修改为 $d_i-d_2\times 2=a_i-a_1\times i-a_2\times i-1$。
于是在上面对过程的模拟后，我们可以得到如下公式：

$d_i=a_i-2\times a_{i-1}-3\times a_{i-2}-\cdots-i\times a_1$

但好像没有什么方法能直接算出这个式子的值，于是考虑用递推的方法去做，找一找 $d_i$ 和 $d_{i-1}$ 的关系：
将式子后一大段的值设为 $g_i$，即 $d_i=a_i+g_i$，则：

$g_{i-1}=-2\times a_{i-2}-3\times a_{i-3}-\cdots-(i-1)\times a_{1}$

$g_i=-2\times a_{i-1}+(-2\times a_{i-2}-3\times a_{i-3}-\cdots-(i-1)\times a_1)-\sum^{i-2}_{j=1}a_j$
$=-2\times a_{i-1}+g_{i-1}-\sum^{i-2}_{j=1}a_j$

于是我们的递推关系就求出来了，至于后面的 $\sum^{i-2}_{j=1}a_j$ 用前缀和求出即可，初始状态为 $g_1=0$ 且 $d_1=a_i+g_1=a_1$。

代码

const int N = 200005;
ll a[N],d[N],pf[N],g[N];    //pf代表前缀和数组
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){cin>>a[i];}
    d[1] = a[1];g[1] = 0;pf[0] = 0;pf[1] = a[1];	//设置初始状态
    for(int i=2;i<=n;i++){
        g[i] = 2*d[i-1]+g[i-1]+pf[i-2];	//更新g[i]
        d[i] = a[i]-g[i];	//更新d[i]
        pf[i] = pf[i-1]+d[i];	//更新前缀和
    }
    ll sum = 0;
    for(int i=1;i<=n;i++){
        sum+=abs(d[i]);	//答案即为d[i]的绝对值之和
    }
    cout<<sum;
}

int main(){
    int t = 1;
//    read(t);
    for(int tt=1;tt<=t;tt++){
        solve();
    }
}