526互联

Codeforces Round891（Div3）

发布时间 2023-08-12 00:29:52作者: LsmQwQ

说在前面的话：

心血来潮想要补一场Div3，这些题目确实很有意思。英文题面真的难懂，但是洛谷上的简洁题面无疑降低了难度。

然后通过这次补题经历，更加感到了不开long long见祖宗，所以，读者可以发现有几道题用了signed（源代码已经改成这样力，不想被long long再搞一次了）。

最后，碍于DevC++的功能有限，不能像VS Code等软件那样直接在界面进行类似文件读入输出的操作，使得界面十分清晰，所以还用什么DevC++个人认为文件读入输出操作更能辨别正确与否。

A

就是给出一个数组，将数组元素染上两种不同的颜色，判断是否存在某种染色方案，使得每种颜色的数字之和的奇偶性相同。

当然有结论：数字之和为偶数即可。不证。
我当时觉得把奇数偶数配对，这样一层一层算下去知道一方为\(0\)。属于瞎做做法（。

#include <bits/stdc++.h>
#define ll long long
#define re register
using namespace std;
const int N=100, INF=0x3f3f3f3f;
int T,n,a[N];
int ou,ji;
void f(int x,int y){
	while(x!=0&&y!=0){
		int k=min(x,y);
		y-=k;
	}
	if(x==0)puts("YES");
	else{
		if(x%2==0)puts("YES");
		else puts("NO");
	}
}
int main(){
	/*freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);*/
	cin>>T;
	while(T--){
		cin>>n;
		ou=0;ji=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(a[i]%2==0)ou++;
			else ji++;
		}
		f(ji,ou);
	}
	return 0;
}

B

B就是将一个数字进行若干次（或不进行）五入的进位操作，求可得到的最大值。

很明显贪心，我们从右往左遍历，能进位就进位，记得处理一下\(9\)进位即可。

#include <bits/stdc++.h>
#define ll long long
#define re register
using namespace std;
const int N=800, INF=0x3f3f3f3f;
string s;
int T;
int main(){
	/*freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);*/
	cin>>T;
	while(T--){
		cin>>s;s='0'+s;
		int num=s.size();
		for(int i=s.size()-1;i>0;i--){
			if(s[i]=='9'+1){
				s[i]='0';
				s[i-1]++;
			}
			if(s[i]>='5'){
				num=i;
				s[i-1]++;
			}
		} 
		for(int i=0;i<s.size();i++){
			if(i==0&&s[i]=='0')continue;
			if(i<num)cout<<s[i];
			else cout<<0;
		}
		cout<<endl;
	}
	return 0;
}

C

构造题，题面很清楚了已经。

因为对于一个有序数列\(a_1,a_2,...,a_n\)，\(a_1\)要和\(n-1\)个数比较，所以也会有\(n-1\)个\(a_1\)出现在B中，后面以此类推。

#include <bits/stdc++.h>
#define ll long long
#define re register
using namespace std;
const int N=1e6+5, INF=0x3f3f3f3f;
int T,n,a[N],b[N];


int main(){
	/*freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);*/
	cin>>T;
	while(T--){
		cin>>n;
		ll bn=n*(n-1)/2;
		for(int i=1;i<=bn;i++)cin>>b[i];
		sort(b+1,b+bn+1);
		int i=1,j=n-1;
		while(i<=bn){
			cout<<b[i]<<' ';
			i+=j;
			j--;
		}
		cout<<b[bn]<<endl;
	}
	return 0;
}

D

题面更是清晰，洛谷上一概括确实好受不少（

一眼图论题，在一眼傻瓜题，如果按题目来做就是\(O(n^2)\)，肯定超时，那我们就略微移项：

\[a_u-a_v\ge b_u-b_v\implies a_u-b_u\ge a_v-b_v \]

所以只需要求出最大差值，然后看看有几个和最大值一样的值就行了。

#include <bits/stdc++.h>
#define ll long long
#define re register
using namespace std;
const int N=2e5+5, INF=0x3f3f3f3f;
int T,n,a[N],b[N],maxn;
int main(){
	/*freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);*/
	cin>>T;
	while(T--){
		cin>>n;
		maxn=-2e9;//这里注意，每个元素是[-1e9,1e9]，这个最小有-2e9（错了好几次
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++){
			cin>>b[i];
			maxn=max(maxn,a[i]-b[i]);
		}
		int t=0;
		vector<int> S;
		for(int i=1;i<=n;i++)if(a[i]-b[i]==maxn){t++;S.push_back(i);}
		cout<<t<<endl;
		for(auto i:S)cout<<i<<' ';
		cout<<endl;
	}
	return 0;
}

E

题目就是有\(n\)个点，放在数轴上面，对于其中一个数，计算它与其余各点（包括自身）之间点的个数之和。

一眼DP，但是后面没写成DP。这题只要愿意算，基本没啥问题（推的式子都没我以前写的几道复杂,而且也不用证明)，单纯模拟即可：
我们记\(s_k\)表示第\(k\)个数的按题目所求的值。

\[s_k=\Sigma_{i=1}^k(a_k-a_i+1)+\Sigma_{i=k+1}^n(a_i-a_k+1) \]

\[=ka_k-\Sigma_{i=1}^ka_i+k+\Sigma_{i=1}^na_i-(n-k)a_k+(n-k) \]

\[=(2k-n)a_k+n+k+\Sigma_{i=1}^na_i-\Sigma_{i=1}^ka_i \]

前面三项我们可以直接算，后面两个可以用前缀和以及后缀和做。
(可以看出，这题被long long背刺了)

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define re register
using namespace std;
const int N=2e5+5, INF=0x3f3f3f3f;
int T,n,a[N],b[N];
ll pre[N],suf[N];
map<int,ll>ans;
signed main(){
	/*freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);*/
	cin>>T;
	while(T--){
		cin>>n;
		memset(pre,0,sizeof(pre));
		memset(suf,0,sizeof(suf));//多测记得清空
		for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
		sort(a+1,a+n+1);
		for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];//前缀和
		for(int i=n-1;i>=1;i--)suf[i]=suf[i+1]+a[i+1];//后缀和
		for(int i=1;i<=n;i++)ans[a[i]]=(2*i-n)*a[i]+n+suf[i]-pre[i];//套公式
		for(int i=1;i<=n;i++)cout<<ans[b[i]]<<' ';
		cout<<endl;
	}
	return 0;
}

F

题面

一眼梦回2022CSP-J，我们只需运用初中数学一元二次方程即可。
对于题中两个式子移项合并可得：

\[a_i^2-xa_i+y=0 \]

\(a_i\)可以化成\(a_j\)，二者为方程\(x^2-bx+c=0\)的二根。

\[a_i=\dfrac{x\pm\sqrt{x^2-4y}}{2} \]

注意一下\(\Delta\)非负且能开尽，上面是偶数就行了。如果两根相同，那么\(ans=C_k^2=\dfrac{k(k-1)}{2}\)，\(k\)就是值为\(a_i\)的数的个数，组合公式算得。如果两根不同，根据乘法定理，\(ans=k_1 * k_2\)。
(再次被long long薄纱)

#include <bits/stdc++.h>
#define int long long
#define re register
using namespace std;
const int N=2e5+5, INF=0x3f3f3f3f;
map<int,int>check;
bool pd(int n){
	int k=sqrt(n);
	return k*k==n;
}
int delta(int x,int y){
	int k=x*x-4*y;
	if(k<0||!pd(k))return -1;
	return sqrt(k);
}
int T,n,a[N],q;
signed main(){
	/*freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);*/
	cin>>T;
	while(T--){
		cin>>n;
		check.clear();
		for(int i=1;i<=n;i++){cin>>a[i];check[a[i]]++;}
		cin>>q;
		while(q--){
			int ans=0;
			int x,y;cin>>x>>y;
			int del=delta(x,y);
			if(del==-1||(x+del)%2!=0){
				cout<<0<<' ';continue;
			}
			int N_x1=check[(x+del)/2],N_x2=check[(x-del)/2];
			if((x+del)/2==(x-del)/2)ans=N_x1*(N_x1-1)/2;
			else ans=N_x1*N_x2;
			cout<<ans<<' ';
		}
		cout<<endl;
	}
	return 0;
}

G

emm不会，这个真是图论了。以后会了再补。