20231015题解

wflengxuenong · 2023-10-15 08:36:56 · 个人记录

T1 函数

表达式基本运算与输出考察，入门难度。

注意的点：a可能为0,变为一次方程。

a！=0 bb-4a*c<0无解

bb-4a*c==0只有一个解

bb-4ac>0 两个解。 x1=(-b-sqrt(bb-4ac)/(2a)

x2=(-b+sqrt(bb-4a*c)/(2a)

bb-4a*c==0只有一个解

坑点：考察输出，四舍五入和截尾巴的处理。

参考代码：

#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;

int k; 
double a,b,c;
double f(double x){
    int temp=int(x*10000);
    return 1.0*temp/10000.0;
}
int main(){
    freopen("func.in","r",stdin);
    freopen("func.out","w",stdout);
    int ans;
    double x,y,dt;
    cin>>k>>a>>b>>c;
    if(a==0){
        x=-1.0*c/(1.0*b);
        printf("%.4lf",(k==0)?x:f(x));
        return 0;
    }
    if(fabs(b*b-4*a*c)<=0.00001){
        x=-1.0*b/(2.0*a);
        printf("%.4lf",(k==0)?x:f(x));
        return 0; 
    }
    if((b*b-4*a*c)<-0.000001){printf("WTF");return 0;}
    else {
        dt = sqrt(1.0*(b*b-4*a*c));
        x=(-b-dt)/(2.0*a);
        y=(-b+dt)/(2.0*a);
        if(k==0)printf("%.4lf %.4lf",x,y);
        else  printf("%.4lf %.4lf",f(x),f(y));
    }
}

T2 打怪

读题审题。

方法1：可以理解为背包。 背包的总容量就是能量单位W. 遇到攻击力xi大于a+b的选手就避过去。 时间复杂度n*w，预计得分50.

#include <iostream>
using namespace std;
const int N = 10010;
int n, w, a, b, f[N];
int main()
{
     freopen("guai.in","r",stdin);
    freopen("guai.out","w",stdout);
    scanf("%d %d", &n, &w);
    scanf("%d %d", &a, &b);
    for(int i = 1; i <= n; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        for(int j = w; j >= y && x <= a + b; j--)
        {
            f[j] = max(f[j], f[j - y] + 1);
        }
    }
    printf("%d", f[w]);
}

方法二：贪心 在可以攻击的选手里面挑选出能量消耗少的怪兽。

时间复杂度o(n*logn）

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int n, w, a, b, x,y,f[N];
using namespace std;
int main(){
    freopen("guai.in","r",stdin);
    freopen("guai.out","w",stdout);
    cin>>n>>w>>a>>b;
    a+=b;
    int cnt=0;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        if(x>a)
            cin>>y;
        else
            cin>>f[cnt++];//cin>>a[cnt];cnt++;
    }
    sort(f,f+cnt);  //力气从小到大排序
    int sum=0;
    for(int i=0;i<cnt;i++){
        w-=f[i];
        if(w<0)break;
        sum++;
    }
    cout<<sum<<endl;
}

T3:修路

• 子任务1:50分 可以看做求最短路问题。暴力上foyed，发现超时,时间复杂度是O(N^3)。
• 子任务2

  方法1

    因为图很简单，就是一天直线上添加一条边，只有在告诉公路左右两侧的端点最短路会改变。也就是只需要用x或y重新一次，降低时间复杂度,时间复杂度是O(N*N)。

  方法2

    因为图步长值为1，还可以跑n遍bfs，时间复杂度也是O(N*N) 参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2e3+9;
int a[N][N], s[N];
int main()
{
    freopen("short.in","r",stdin);
    freopen("short.out","w",stdout); 
    int n, x, y;
    cin >> n >> x >> y;
    //int a[n+1][n+1], s[n];
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++) a[i][j]=fabs(i-j);//求出加边前的最短距离
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            a[i][j]=min(a[i][j], min(a[i][x]+a[y][j]+1, a[i][y]+a[x][j]+1));//开始优化~
    for (int i=1; i<n; i++) s[i]=0;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++) s[a[i][j]]++;//统计
    for (int i=1; i<n; i++) cout << s[i]/2 << endl;
    return 0;//愉快地结束
}

T4:笨鸟

闫总讲解 （x,a,b）可以经过的范围为(a+1,b-1)

因为在前行的过程中，不点击就要往下掉。横坐标增加时候，纵坐标最多+1 在整个过程中，不断取合法的跳跃区间。

      x+1,y+1 
(x,y)
      x+1,y-1

这个点只能到达只能到达奇偶性不相同的结点。因此取值的时候，不能只考虑大小，还要考虑奇偶性。

从（x0，y0）设最终的位置为(x1,y1) 设其水平距离差为。x=x1-x0 那么最多点击次数是x，最少点击次数是0.可以到达的区间是：(x1，y0-x) (x1,y0+x)

设点击次数为t 那么上升的高度是t，下降的高度是(x-t)

最终的值为y1=y0+t-(x-t) =y0+2t-x

 t=(y1+x)/2

这就是跳跃的最小次数。

参考代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#define N 500005
using namespace std;
template <typename T> 
inline void _read(T& x){ 
    char ch=getchar();bool sign=true; 
    while(!isdigit(ch)){if(ch=='-')sign=false;ch=getchar();} 
    for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0'; 
    if(!sign)x=-x; 
}
int T,n;
int ans[N];
int main(){
    freopen("birds.in","r",stdin);
    freopen("birds.out","w",stdout); 
    int i,j,k,temp=0,l=0,r=0,pos,x,a,b;
    cin>>n>>pos;
    for(i=1;i<=n;i++){
        _read(x);_read(a);_read(b);
        a++;b--;
        l-=x-temp;l=max(l,a);
        r+=x-temp;r=min(r,b);
        if((l&1)!=(x&1))l++;//考虑不同的奇偶性 
        if((r&1)!=(x&1))r--;//考虑不同的奇偶性 
        if(l>r)break;
        temp=x;
        ans[i]=(x+l)>>1;
    }
    if(i>n){//注意，题目给定是到达这个点的最小点击次数，不一定是最终到达终点的次数。 
        for(i=1;i<=n;i++){
            printf("%d\n",ans[i]);
        }
        printf("%d\n",ans[n]);
    }
    else puts("Stupid bird!");
}

T5:楼梯

根据提议，两个楼直接越宽，那么c越小，两个楼之间越近，c越大。 我们设楼间的距离为len，脚垫垂线左侧为a，右侧为b，则a+b=len. 设交点的高度为h.x对应hx，y对应墙的高度hy

hy/len=h/a

hx/len=h/b

a+b=len

a=h*len/hy

b=h*len/hx

a+b=h*len(1/hx+1/hy)=len

h*(1/hx+1/hy)=1

1/h=1/hx+1/hy

hx=sqrt(xx-lenlen) hy=sqrt(yy-lenlen)

判断1/c与1/h的大小。

视频讲解：来自ACWING 闫总视频讲解

参考代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#define siz 
#define minn(a,b) (a<b?a:b)
using namespace std;
double x, y, c;
double work(double t) {
    return 1 / sqrt(x * x - t * t) + 1 / sqrt(y * y - t * t);
}
int main() {
    freopen("ladder.in","r",stdin);
    freopen("ladder.out","w",stdout);
    cin>>x>>y>>c;
    double l = 0, r = minn(x,y), mid;
    while(r - l > 1e-5) {
        mid = l + (r - l) / 2; 
        if( work(mid) > (1/c) ) r=mid;
        else l=mid;
    }
    printf("%.3lf\n",mid);
}