2024牛客寒假算法基础集训营1
A DFS搜索
考点：双指针
思路：从左往右和目标字串依次比较，用bool来标记即可
#include <bits/stdc++.h>
using namespace std;
string s;
string s1 = "dfs";
string s2 = "DFS";
int n;
int main()
{
cin >> n >> s;
int i = 0,j = 0,k = 0;
bool fDFS = false,fdfs = false;
//dfs
while(i < s.size() && j < s1.size())
{
if(s[i] == s1[j])
{
j++;
}
i++;
}
if(j == s1.size()) fdfs = true;
//DFS
i = 0;
while(i < s.size() && k < s2.size())
{
if(s[i] == s2[k])
{
k++;
}
i++;
}
if(k == s2.size()) fDFS = true;
cout << fDFS << ' ' << fdfs << '\n';
return 0;
}
B 关鸡
C 按闹分配
考点：排序，二分，前缀和
思路：0.o
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1e5 + 10;
i64 a[N],s[N];
i64 n,Q,tc;
// 二分
i64 check(i64 M)
{
i64 l = 0,r = n,mid,res = -1;
while (l <= r)
{
mid = (l + r) / 2;
i64 dec = tc * (n - mid); // 计算不满意度增加量
i64 t = s[mid] + tc; // 鸡完成办事的时刻
if (dec <= M)
{ // 检查是否在容忍度范围内
res = t;
r = mid - 1;
}
else
l = mid + 1;
}
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> Q >> tc;
for (i64 i = 1;i <= n;i ++) cin >> a[i];
sort(a + 1,a + n + 1);
for (i64 i = 1;i <= n;i ++) s[i] = s[i-1] + a[i];
while (Q--)
{
i64 M; cin >> M;
cout << check(M) << '\n';
}
return 0;
}
E 本题又主要考察了贪心
考点：dfs
思路：数据较小，情况多，没有明确的贪心，很容易想到dfs,让一号选手的对局必胜，然后去用dfs走其他所有的可能。
#include <bits/stdc++.h>
#define PII pair<int, int>
using namespace std;
using i64 = long long;
int n,m;
vector<int> a;
vector<PII> mp;
int res;
// 更新排名
int Rank()
{
int rank = 1;
for (int i = 0;i < n;i ++)
{
if (a[i] > a[0]) rank ++;
}
return rank;
}
// 用dfs枚举所有情况
void dfs(int dep)
{
//出口
if (dep == m)
{
res = min(res,Rank());
return;
}
// 模拟胜、负、平
int u = mp[dep].first - 1;
int v = mp[dep].second - 1;
// u 胜
a[u] += 3;
dfs(dep + 1);
a[u] -= 3;
// v 胜
a[v] += 3;
dfs(dep + 1);
a[v] -= 3;
// 平局
a[u] += 1;
a[v] += 1;
dfs(dep + 1);
a[u] -= 1;
a[v] -= 1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;cin >> t;
while (t--)
{
cin >> n >> m;
a.resize(n);
for (int i = 0;i < n;i ++)
cin >> a[i];
mp.resize(m);
for (int i = 0;i < m;i ++)
cin >> mp[i].first >> mp[i].second;
res = 0x3f3f3f3f;
dfs(0);
cout << res << '\n';
}
return 0;
}
G why买外卖
考点：思维，STL，排序
思路：把满减优惠从小到大排序，依次满足，只要能够买就继续往上优惠，维护更新最大值
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
vector<pair<int,int>> yh;
int n,m;
void solve()
{
cin >> n >> m;
i64 res = m;
yh.resize(n);
for(i64 i = 0;i < n;i ++)
{
i64 a,b;
cin >> a >> b;
yh[i] = {a,b};
}
sort(yh.begin(),yh.end());
i64 sum = 0;
for(const auto& ab : yh)
{
sum += ab.second;
if(sum + m >= ab.first)
{
res = max(sum + m,res);
}
}
cout << res << '\n';
}
int main()
{
int t;cin >> t;
while(t --)
{
solve();
}
return 0;
}
I It's bertrand paradox. Again!
考点：数学，思维
思路：bit-noob的方法:会保持圆心不变，一直改变半径，按道理来说圆的位置会更靠近中心，因为边界会收到半径限制，但是如果按照生成逻辑，生成的原因一定是因为边界问题，所以它新生成的圆，应该更靠近边界
buaa-noob的方法：会让圆更倾向于均匀分布，圆心会更随机
思路：出于这种原因，我们可以假设圆就在中间，来统计圆心绝对值的和，如果和大于一个阈值，说明是bit-noob的方法，相反就是buaa-noob
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
i64 s = 0;
i64 n;cin >> n;
for(int i = 0;i < n;i ++)
{
i64 x,y,r;
cin >> x >> y >> r;
s += abs(x) + abs(y);
}
//0-200,每次圆心绝对值之和的范围，假设圆心在+-50
//那绝对值范围就是0-100，取集中，往上找阈值，为了更快速，我们可以倒着取值
if(s > 88 * n)//范围取[74,99]都可以（别问为什么，问就是挨个试了一遍）
puts("bit-noob");
else
puts("buaa-noob");
return 0;
}
L 要有光
考点：数学，思维
思路：要让地面阴影最大，考虑光源在杆上面只要不在地上都会出现夹角投影，肯定不是最大的，所以光源一定在地上，最大面积即为梯形面积，用相似比例可以得出结果
#include <bits/stdc++.h>
using namespace std;
int c,d,h,w;
void solve()
{
cin >> c >> d >> h >> w;
printf("%.10f\n",3.0*c*w);
}
int main()
{
int t;cin >> t;
while(t --)
{
solve();
}
return 0;
}
M 牛客老粉才知道的秘密
考点：思维
思路：很容易想到整除6一定结果为n/6,剩余的由于过去回来的对称性，一定会有两倍的int(n/6),向下取整是因为回去的时候一定和初始位置重合，会多一种,可以用数学归纳（找规律）得出
#include <bits/stdc++.h>
using namespace std;
int n;
void solve()
{
cin >> n;
if(n % 6 == 0) cout << n / 6 << '\n';
else cout << n / 6 * 2 << '\n';
}
int main()
{
int t;cin >> t;
while(t --)
{
solve();
}
return 0;
}
投递小红书等公司7个岗位