周赛的第一次题解

周赛的第一次题解

第一次周赛题解

A、P1969 [NOIP2013 提高组] 积木大赛
B、P5638 【CSGRound2】光骓者的荣耀
C、P7441 「EZEC-7」Erinnerung
D、P2212 [USACO14MAR]Watering the Fields S
E、P3743 kotori的设备
F、P4145 上帝造题的七分钟2 / 花神游历各国

A、P1969 [NOIP2013 提高组] 积木大赛

这是一道noip考了两次的题，我第一次写的时候，是纯暴力模拟，判断连续上升多少次，连续下降多少次，一个连续上升和一个连续下降可以由一个操作来完成，我当时考试的时候调了一个多小时。
这是noip2018铺路的代码

#include<iostream>
#include<fstream>
#include<cmath>
#include<iomanip>//setprecision()
#include<algorithm>//sort(,)
using namespace std;
//struct a{
//	int 
//};
int r[100001];
int main()
{ifstream fin("road.in");ofstream fout("road.out");int i,j=0,k,n,an=0;cin>>n;for(i=1;i<=n;i++){cin>>r[i];}an=r[1];for(i=1;i<n;i++){while(r[i]>=r[i+1]&&i<n){i++;}if(i==n){cout<<an;return 0;}k=r[i];while(r[i]<=r[i+1]&&i<n){j=1;i++;}if(j==1){an=an+r[i]-k;i++;}if(i-1==n){cout<<an;return 0;}j=0;i--;}cout<<an;fin.close();fout.close();return 0;
}

这是利用差分写的积木大赛的代码

#include<iostream> 
#include<fstream>
using namespace std;
int h[100001];
int main()
{int n,i,j,k,now=0,an=0;cin>>n;for(i=1;i<=n;i++){cin>>h[i];}for(i=1;i<=n;i++){while(h[i]>=now&&i<=n)	{now=h[i];i++;}an=an+now;while(h[i]<=now&&i<=n){now=h[i];i++;}i--;if(n!=i){an=an-h[i];}else{an=an+now-h[i];break;}}cout<<an;return 0;
}

B、P5638 【CSGRound2】光骓者的荣耀

这是一道前缀和+贪心的问题求出最大的区间和即可

#include<iostream>
using namespace std;
long long a[1000004],b[1000005];
int main()
{long long i,j,k,n,an;cin>>n>>k;an=0;for(i=1;i<n;i++){cin>>a[i];b[i]=b[i-1]+a[i];an+=a[i];}j=0;for(i=k;i<=n;i++){j=max(j,b[i]-b[i-k]);}cout<<an-j;} 

C、P7441 「EZEC-7」Erinnerung

代码如下

#include<iostream>
using namespace std;
long long a[1000004],b[1000005];
int main()
{long long i,j,k,n,an,t,x,y;cin>>t;while(t--){cin>>x>>y>>k;if(x<y){swap(x,y);}if(y==0){if(x==0||k%x!=0)cout<<0<<endl;else{cout<<1<<endl;}continue;}cout<<k/x<<endl;}} 

D、P2212 [USACO14MAR]Watering the Fields S

这是一道简单的最小生成树的模板
代码如下，要考虑一下数组的大小问题

#include<iostream>
#include<algorithm>
using namespace std;
long long a[2004],b[2005],fa[2008];
long long find(long long o)
{if(o==fa[o]){return o;}return fa[o]=find(fa[o]);
}
struct tt{long long x,y,d;
}t[4000006];
long long jl(long long x1,long long x2,long long y1,long long y2)
{return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
bool cmp(tt a,tt b)
{return a.d<b.d;
}
int main()
{long long i,j,k,n,an,x,y,c;cin>>n>>c;an=0;for(i=1;i<=n;i++){cin>>a[i]>>b[i];fa[i]=i;}long long num=0;for(i=1;i<=n;i++){for(j=i+1;j<=n;j++){k=jl(a[i],a[j],b[i],b[j]);if(k>=c){num++;t[num].d=k;t[num].x=i;t[num].y=j;}}} sort(t+1,t+1+num,cmp);for(i=1;i<=num;i++){j=find(t[i].x);k=find(t[i].y);if(j>k){fa[j]=k;an+=t[i].d;}if(j<k){fa[k]=j;an+=t[i].d;}}for(i=2;i<=n;i++){if(fa[i]==i){cout<<"-1";return 0;}}cout<<an;} 

E、P3743 kotori的设备

我们发现只有一个未知数，就是最长使用时间，且满足单调性，很容易就会想到二分
代码如下

#include<iostream>
#include<algorithm>
using namespace std;
int n;
double p;
struct tt{double a,b,c;
}t[100006];
bool cmp(tt x,tt y)
{return x.c<y.c;
}
bool check(double o)
{int i;double j,k;j=0;k=0;for(i=1;i<=n;i++){if(t[i].a*o>=t[i].b){j+=t[i].a;k+=t[i].b;}}if(j<=p||k/(j-p)>=o){return true;}return false;
}
int main()
{int i,num=0;double j,k,an,x,y,l,r,mid,sum;cin>>n>>p;j=0;sum=0;for(i=1;i<=n;i++){cin>>j>>k;num++;t[num].a=j;t[num].b=k;t[num].c=t[num].b/t[num].a;sum+=j;}if(sum<=p){cout<<-1.000000<<endl;return 0;}l=0;r=1e10;while(r-l>0.000001){mid=(l+r)/2;if(check(mid)){l=mid;}else{r=mid;}}printf("%lf",mid);
}

P4145 上帝造题的七分钟2 / 花神游历各国

“显然这是一道根号线段树模板题，代码：”

#include<iostream>
#include<algorithm>
#include<cmath> 
#define ll long long
using namespace std;
ll a[400007],b[400007],c[400007],an;
void xds(ll l,ll r,ll o)
{ll mid;if(l==r){b[o]=a[l];return;}mid=(l+r)>>1;xds(l,mid,2*o);xds(mid+1,r,2*o+1);b[o]=b[2*o]+b[2*o+1];
}
void cz(ll l,ll r,ll o,ll x,ll y)
{ll mid;mid=(l+r)>>1;if(r<x||y<l){return;}if(x<=l&&r<=y){an+=b[o];return;}cz(l,mid,2*o,x,y);cz(mid+1,r,2*o+1,x,y);} 
void xg(ll l,ll r,ll o,ll x,ll y)
{if(b[o]==r-l+1){return;}if(r<x||y<l){return;}if(l==r){b[o]=sqrt(b[o]);return;}ll mid;mid=(l+r)>>1;xg(l,mid,2*o,x,y);xg(mid+1,r,2*o+1,x,y);b[o]=b[2*o]+b[2*o+1];}
int main()
{ll i,j,k,n,m,l,r,x,y;cin>>n;for(i=1;i<=n;i++){cin>>a[i];}xds(1,n,1);cin>>m; for(i=1;i<=m;i++){cin>>k>>x>>y;if(x>y){swap(x,y);}if(k==0){xg(1,n,1,x,y);}else{an=0;cz(1,n,1,x,y);cout<<an<<endl;}}
}

（呜呜呜当时被吓到了在推公式，没想到居然是暴力…