B、爆wa种子!（数学）
一、题目要求
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
爆wa种子发现了上次玩游戏时你和妙wa种子的py交易，所以他要求这次玩游戏你来当爆wa种子的枪手，为他写个程序计算出答案。
给定n个函数方程， 给出函数方程形如y=ax^2+bx+c给出a,b,c求出这些函数方程图像所覆盖的所有点中最低点的值（y值最小）， 如果最小值为负无穷输出 -1000000000 ， 否则输出最小值。
输入描述:
第一行输入n，表示有nnn个函数方程(1≤n≤5e3) 接下来n行每行有三个数a,b,c表示方程三个系数分别为多少，保证a,b,c都是整数(0≤a,b,c≤100
输出描述:
输出一个数表示这些函数图像覆盖的所有点中最低点值为多少。 你输出的答案和标准答案误差不超过10^−6即被视为正确。
示例1
输入
5 4 3 87 2 2 72 0 1 66 2 4 100 3 4 60
输出
-1000000000
示例2
输入
5 5 2 60 3 1 60 5 3 59 5 5 83 2 5 46
输出
42.875000000
示例3
输入
5 5 2 61 2 2 73 2 0 50 4 4 47 5 2 46
输出
45.800000000
二、思路
1.保证了a>=0，所以开口向上，最低点的坐标为（x,y）
x=-a/b y=(4ac-b*b)/(4a)
2.考虑特殊情况，当a=0,b=0的时候，y=c
三、代码
#include<bits/stdc++.h>
#include<limits>
#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int N=5e3+1000;
const int inf=0x3f3f3f3f;
int n;
struct node
{
double a,b,c;
double y;
} q[N];
void solve()
{
int i,j;
cin>>n;
double x=-std::numeric_limits<double>::infinity();
double ans=std::numeric_limits<double>::infinity();
int p=0;
for(i=1; i<=n; i++)
{
cin>>q[i].a>>q[i].b>>q[i].c;
//q[i].x=-(q[i].a/q[i].b)*1.0;
if(q[i].a==0)
{
p++;
}
q[i].y=(4*q[i].a*q[i].c-q[i].b*q[i].b)/(4*q[i].a);
}
if(p)
cout<<"-1000000000"<<endl;
else
{
for(i=1; i<=n; i++)
{
if(ans>q[i].y)
{
ans=q[i].y;
}
//cout<<q[i].y<<' '<<endl;
}
if(ans<=x||p)
cout<<"-1000000000"<<endl;
else
printf("%lf\n",ans);
}
}
signed main()
{
int t=1;
while(t--)
{
solve();
}
return 0;
}
D、书生的负数（思维）
一、题目要求
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
你将得到一个长度为 n 的整数数组 a
你可以执行以下操作任意次：
选择 i, j (1≤i,j≤n),令ai=ai−1,aj=aj+1。
请输出进行操作后序列 a 中最多存在的负数个数。
输入描述:
每个测试包含多个测试用例。第一行包含一个整数 t (1≤t≤10^5) - 测试用例的数量。 测试用例说明如下。 每个测试用例的第一行包含一个整数 n (1≤n≤5⋅10^5)-数组 a 的长度。 第二行包含n个整数 a1...an (−10^5≤ai≤10^5),表示序列 aaa 。 题目保证所有测试样例的 n 的和不超过 5⋅10^5
输出描述:
输出 t 行，每行输出一个整数，表示至多的负整数个数。
示例1
输入
1 5 1 2 3 4 5
输出
4
示例2
输入
1 5 -8 1 1 1 1
输出
4
二、思路
1.由于i,j可以任意选择，可以先统计一下a[i]中负数的个数，然后排序
2.如果负数个数等于n，则不用进行操作，如果（负数的绝对值减1的和）>=（正数+1的和），则也不用进行操作，可以每次让正数变为负数的过程中，让负数++，最极端的时候可以令负数加到负一为止。
3.其他情况下，可以让n-1个数全变为负数，而让最后一个数不断累加，所以肯定会有n-1个负数出现
三、代码
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;
int n;
int a[N];
void solve()
{
cin>>n;
int i,j;
int cnt=0,l=0,r=0;
for(i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]<0)
{
l+=abs(a[i])-1;
cnt++;
}
else
{
r+=a[i]+1;
}
}
sort(a+1,a+1+n);
if(cnt==n||l>=r)
cout<<n<<endl;
else
{
cout<<n-1<<endl;
}
}
signed main()
{
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
E、明天（利用std::string::find）
一、题目要求
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
明天，他期盼着明天，可是他本该摒弃明天的，这种切肤之痛的反抗，就是荒诞。
enterdawn一直在期盼着明天，但是他的本能使得他摒弃明天，所以他希望看到明天的一部分，但是不能看到完整的明天。
当字符串S是tomorrow的一部分时，enterdawn才会希望看到字符串S
如果他希望看到这个字符串，输出yes，否则输出no
输入描述:
第一行一个整数T(1≤T≤1000)，代表数据组数 接下来TTT行每行一个字符串s(1≤len(s)≤20)
输出描述:
对于每组数据，如果enterdawn希望看到这个字符串，输出yes，否则输出no
示例1
输入
4 tomorrow tomorr morr ojgs
输出
no yes yes no
二、思路
string str ("tomorrow.");
string str2 ("row");
if (str.find(str2) != string::npos)
{
//如果不等,则说明找到一样的,如果相等,则说明没找到
} 三、代码
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int N=1100;
const int inf=0x3f3f3f3f;
int n;
string s[N];
string ss="tomorrow";
void solve()
{
cin>>n;
int i,j;
for(i=1;i<=n;i++)
{
cin>>s[i];
}
for(i=1;i<=n;i++)
{
if(ss.find(s[i])!=string::npos)//能找到子串
{
if(ss.size()==s[i].size())
cout<<"no"<<endl;
else
cout<<"yes"<<endl;
}
else
{
cout<<"no"<<endl;
}
}
}
signed main()
{
int t=1;
while(t--)
{
solve();
}
return 0;
}
H、冒险（二分答案）
一、题目要求
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
从前有一个冒险家，他背上背着一个容量为k的背包，准备踏上一段寻宝之旅。在他的旅途中，他遇到了n个神奇的物品，每个物品都蕴含着无穷的力量和价值。
冒险家知道，他只能选择其中的一部分物品放入背包中。然而，当他放入一个物品后，其他物品所占的容量会变成之前的2倍。
面对这个挑战，冒险家开始思考如何最大化他的收获。冒险家希望能够最大限度地利用背包的容量来放入更多的物品。他想知道他最多能携带多少物品，继续他的寻宝之旅。
输入描述:
第一行有两个以空格分隔的整数n和k(1≤n,k≤106)分别代表物品的个数和冒险家的背包体积 第二行n个以空格分隔的整数，代表每个物品的体积，单个物品的体积不超过10^6
输出描述:
一行一个整数，输出冒险家最多能携带多少物品继续他的寻宝之旅
示例1
输入
4 19 5 1 1 1
输出
4
示例2
输入
4 19 1 1 5 1
输出
4
二、思路
1.排序
2.利用二分，枚举答案
3.check()函数
三、代码
//二分答案
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int N=1e6+10;
const int inf=0x3f3f3f3f;
int n,k;
int a[N];
bool check(int x)
{
int i,j;
int sum=0;
for(i=x,j=0;i>=1;i--,j++)
{
sum+=(a[i]<<j);
if(sum>k)
{
return false;
}
}
return true;
}
void solve()
{
cin>>n>>k;
int i,j;
for(i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);//从小到大排序
int l=0,r=n,mid;
while(l<r)
{
mid=(l+r+1)/2;
if(check(mid))
{
l=mid;
}
else
{
r=mid-1;
}
}
cout<<l<<endl;
}
signed main()
{
int t=1;
while(t--)
{
solve();
}
return 0;
}
