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;
}