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表