USACO 2024 Jan B题解

本期是USACO 2024年1月铜组的题解。(洛谷上有题目，可以提交)

Majority Opinion:

这题关键在于一个长度为3的区间内如果有两只牛有相同的喜好，那么是可以将这个区间全部同化，那么可以一步一步的拓展，最终一定可以覆盖所有。其他情况都是不可能的比如说:abbabba...

放个代码↓

#include <bits/stdc++.h>
using namespace std;
long long a[100005];
set<long long> ans;
int main(){
	int tc;
	cin>>tc;
	while(tc--){
		ans.clear();
		int n;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(i>=3){
				if(a[i]==a[i-2] || a[i]==a[i-1])
			  		ans.insert(a[i]);
				else if(a[i-1]==a[i-2])
			  		ans.insert(a[i-1]);
			}
		}
		if(n==2){
			if(a[1]==a[2])
				cout<<a[1]<<endl;
			else
		  		cout<<"-1"<<endl;
		}
		else{
			if(ans.empty())
	  			cout<<"-1";
	  		for(set<long long>::iterator itr=ans.begin();itr!=ans.end();itr++){
	  			cout<<*itr;
                cout<<' ';//注意判断itr是否是ans.end()的前一位(ans.end()是空的)
			}
			cout<<endl;		
		}
	}
	return 0;
}

Cannonball:

其实就是简单地模拟。判环的话，就记录一下每个点的力度和方向，只要再次出现就break。

//可怜的奶牛啊,被当做加农炮使
#include <bits/stdc++.h>
using namespace std;
int a[100005],b[100005],p[100005],d[100005];
bool vis[100005];
int main(){
	int n,s;
	cin>>n>>s;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i];
	int dir=1,power=1,ans=0;
	while(s>=1 && s<=n){
		if(a[s]){
			if(!vis[s] && power>=b[s]){
				vis[s]=true;
				p[s]=power;
				d[s]=dir;
				ans++;
			}
			else if(p[s]==power && d[s]==dir)
				break;
		}
		else{
			power+=b[s];
			dir*=-1;
		}
		s+=power*dir;
	}
	cout<<ans<<endl;
	return 0;
}

Balancing Bacteria:

非常需要G(技)巧的题目。我看了半天也不会，暴力都打不了，结果一看题解是二阶差分!!!!!!!什么鬼玩意啊啊啊啊啊啊啊啊啊啊

如果在差分两次后的数组的第i位上加1，就相当于在原数组i~n上加上了一个首项为1公差为1的等差数列。所以，a两次差分后所有数的绝对值的和，就是答案。代码实现很简单，我就放了。

---------------------------------------------------------------------------------------------------------------------------

OK，这就是本期的全部内容。我们下期再见！

友情提示:本期的全部代码都有问题，请不要无脑Ctrl C+Ctrl V

//彩蛋
#include <bits/stdc++.h>
using namespace std;
long long a[200005],opt1[200005],opt2[200005];
int main(){
	long long n;
    cin>>n;
    long long ans=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        opt1[i]=a[i]-a[i-1];
        opt2[i]=opt1[i]-opt1[i-1];
        ans+=abs(opt2[i]);
    }
    cout<<ans<<endl;
    return 0;
}