本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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);
}
鲁ICP备2025150228号