济南CSP-J刷题营集训

Day1比赛

T1

方差

求和可以用前缀和。
求平均值时，特判是否整除而输出结果。
求方差，我们直接用他给的公式以分数形式算出结果，维护两个分子和分母，通分相减后特判输出。
注意要输出最简分数，所以我们用 \(\text gcd\) 约分。

代码：

#include<bits/stdc++.h>
#define gt getchar
#define pt putchar
#define int long long
using namespace std;
int a[100005];
int sum1[100010],sum2[100010];
int fc1,fc2;
int gcd(int a,int b){
	return(b==0?a:gcd(b,a%b));
}
int lcm(int a,int b){
	return a*b/gcd(a,b);
}
signed main(){
	int n;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		sum1[i]=a[i]+sum1[i-1];
		cout<<sum1[i]<<' ';
		sum2[i]=(a[i]*a[i])+sum2[i-1];
		if(sum1[i]%i==0){
			cout<<sum1[i]/i<<' ';
		}
		else{
			int g=gcd(sum1[i],i);
			cout<<sum1[i]/g<<'/'<<i/g<<' ';
		}
		
		int fm1=i;
		int fz1=sum1[i];
		int g=gcd(fm1,fz1);
		fm1/=g;
		fz1/=g;
		fz1=fz1*fz1;
		fm1=fm1*fm1;
		int fm2=i;
		int fz2=sum2[i];
		int l=lcm(fm2,fm1);
		int x=l/fm2,y=l/fm1;
		fm2*=x;
		fz2*=x;
		fm1*=y;
		fz1*=y;
		int fzans=abs(fz2-fz1);
		if(fzans%fm1==0)cout<<fzans/fm1<<'\n';
		else{
			int k=gcd(fzans,fm1);
			cout<<fzans/k<<'/'<<fm1/k<<'\n';
		}
	}	
	return 0;
}

T2

暴力 35pts

直接枚举每一个二元组，然后算出 \(a_j + b_j \times c_i\)，然后排序，输出第 \(k\) 个数即可、

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+10;
int a[MAXN],b[MAXN],c[MAXN];
vector<int>x;
signed main(){
	int n,k;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			x.push_back(a[j]+b[j]*c[i]);
		}
	}
	sort(x.begin(),x.end());
	cin>>k;
	cout<<x[k-1];
	return 0;
}

正解：二分

我们把序列 \(c\) 排序，二分答案查找在序列 \(c\) 中最后一个不大于 \(mid\) 的位置，寻找位置等于 \(k\) 的位置，更新答案，输出。

#include<bits/stdc++.h>
#define int long long
using namespace std; 
int a[100010],b[100010],c[100010];
int n;
int check(int x){
	int sum=0;
	for(int i=1;i<=n;i++)
		if(x-a[i]>=0)sum+=upper_bound(c+1,c+n+1,(x-a[i])/b[i])-c-1;
	return sum;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n;i++)cin>>c[i];
	sort(c+1,c+n+1);
	int l=0,r=1e18+1e9;
	int k;
	cin>>k;
	while(l<r){
		int m=(l+r)>>1;
		if(check(m)>=k)r=m;
		else l=m+1;
	}
	cout<<r;
	return 0;
}

T3

暴力 30pts

枚举每一个 \(a,b,c\)，从小到大枚举可保证有序，判断 \(q\) 是否大于 \(1e5\)，然后按规定输出。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5;
struct pair3{
	int f,s,t;
};
vector<pair3>x;
signed main(){
	int n,n3,p;
	cin>>n>>n3>>p;
	const int n0=n*n+1;
	for(int i=1;i<=p;i++){
		for(int j=0;j<=p;j++){
			for(int k=1;k<=p;k++){
				int n1,n2;	
				n1=n0%i; 
				n2=n1+j;
				if(n2%k==n3){
					pair3 y={i,j,k};
					x.push_back(y);
				}
			}
		}
	}
	int q=x.size();
	if(q>100000){
		cout<<q<<'\n';
		for(int i=0;i<100000;i++){
			cout<<x[i].f<<' '<<x[i].s<<' '<<x[i].t<<'\n';
		}
	}
	else{
		cout<<q<<'\n';
		for(int i=0;i<q;i++){
			cout<<x[i].f<<' '<<x[i].s<<' '<<x[i].t<<'\n';
		}
	}
	return 0;
}

T4

不会

最后只得了 \(150\) pts,太蒻了。

Day1讲解

基础算法

• 模拟
• 枚举
• 递推
• 贪心 -> 哈夫曼树
• 前缀和/差分
• 二分
• 倍增 -> ST表