8.27 总结 - 洛谷保存站

# [T1 U593635 交换](https://www.luogu.com.cn/problem/U593635?contestId=272916)

## 思路

~~这需要讲吗~~

用 `swap()` 按题意交换三个变量即可。

## 代码

```cpp line-numbers
#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,y,z;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>x>>y>>z;
	swap(x,y);
	swap(x,z);
	cout<<x<<" "<<y<<" "<<z;
	return 0;
}
```

# [T2 T643661 猜猜芭蕾舞剧将如何结束](https://www.luogu.com.cn/problem/T643661?contestId=272916)

## 思路

这道题想明白它们什么情况下能在一个 $x$ 上（一列）上就非常简单了。

众所周知，题目并不知道有多少人，那么就用两个极端来看，一个从最左边的边界开始跳舞，一个从最右边的边界开始跳舞，如果这两个人同时都在一个点——正常跳舞不可能在一块，只能一同在边界。这种情况就可以最后在一个 $x$ 上结束，所以算完最后的结果输出任意一个人的坐标就可以了。

## 代码

```cpp line-numbers
#include<bits/stdc++.h>
#define int long long
using namespace std;
int r,n,cnt1,cnt2;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>r>>n;
	cnt2=r;
	bool flag=0;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		cnt1+=x;
		cnt2+=x;
		if(cnt1>=r) cnt1=r;
		if(cnt2>=r) cnt2=r;
		if(cnt1<=0) cnt1=0;
		if(cnt2<=0) cnt2=0;
		
		if(cnt1==cnt2 && cnt1==r) flag=1;
		if(cnt1==cnt2 && cnt2==0) flag=1;
	}
	if(flag==1) cout<<cnt1;
	else cout<<-1;
	return 0;
}
```

# [T3 U593646 落落的去的数学问题五](https://www.luogu.com.cn/problem/U593646?contestId=272916#submit)

## 思路

这道题我们可以用广搜，比如说 $1$ 那它的下一位只能是 $0,1,2$ 这三种，广搜时，每取出一次队首就算是一种可能，知道题目中的 $k$，然后输出。

## 代码

```cpp line-numbers
#include<bits/stdc++.h>
#define int long long
using namespace std;
int k,cnt;
queue<int> q;
void bfs(){
    for(int i=1;i<=9;i++){
        q.push(i);
    }
    cnt=0;
    while(!q.empty()){
        int a=q.front();
        q.pop();
        cnt++;
        if (cnt==k){
            cout<<a;
            return;
        }
        int b=a%10;
        for (int i=-1;i<=1;i++){
            int x=b+i;
            if (x<0 || x>9) continue;
            int ans=a*10+x;
            q.push(ans);
        }
    }
}
signed main(){
    cin>>k;
    if (k<=9){
        cout<<k;
        return 0;
    }
    bfs();
    return 0;
}
```

# [T4 U593645 操作2](https://www.luogu.com.cn/problem/U593645?contestId=272916)

## 思路

这道题要用前缀和加上二分查找来写。

先来看第一个样例中的 $5$，虽然很简单，一看就知道是所有的数遍历减去这个要变的数字，输出这些的和。但是这样必定超时，于是我们就要上操作了。

首先这里的两个 $5$ 是完全不需要变的，那就不用管他。那剩下的如何处理呢？这个数组现在又不规则——所以我们 `sort` 排序一下，让整个数组从小到大来。

此时二分查找就有用了，时间复杂度不高，可以过这道题。我们要找的就是要变的区域（相等的不用变）——那就是到 `int l=lower_bound(a+1,a+1+n,x)-a-1;` 的位置（`lower_bound` 是用来查找大于或等于这个数的第一个位置的函数），这些是比要变成的 $x$ 要小的，理论值应该为 $l \times x$，实际值就是我们说的前缀和 $sum_l-sum_0$，用理论值减实际值算出答案（不放心就加一个绝对值）。

然后看了要变的且比 $x$ 要小的区域，现在我们要找更大的区域 `int r=upper_bound(a+1,a+1+n,x)-a;` （`upper_bound` 是用来查找大于这个数的第一个位置的函数）的位置就是这一段的起始，一直到最后都是比要变成的 $x$ 大的区域。这里的理论值应该是 $(n-r+1) \times x$，实际值是 $sum_n-sum_{r-1}$，同样的用实际值减去理论值算出答案累加，最终输出就行。

注意：这里我们既然要排序，那么这个前缀和就一定要在排序的后面求出来，要不然每一位都无法对应。

## 代码

```cpp line-numbers
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxx=2e5+10;
int n,q,a[maxx],sum[maxx];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i];
	}
	while(q--){
		int x,ans=0;
		cin>>x;
		int wei=lower_bound(a+1,a+1+n,x)-a-1;
		int num=sum[wei]-sum[0];
		int tmp=x*wei;
		ans=ans+abs(tmp-num);
		wei=upper_bound(a+1,a+1+n,x)-a;
		num=sum[n]-sum[wei-1];
		tmp=x*(n-wei+1);
		ans=ans+abs(tmp-num);
		cout<<ans<<endl;
	}
	return 0;
}
```

正在渲染内容...