2024牛客寒假算法基础集训营1

🕗 发布于 2024-02-05 18:08 算法 c++

A

找dfs这三个字符即可

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long ll;

const int N = 55;

int n;
char s[N];

void solve()
{
cin >> n >> s + 1;
int pos1 = -1, pos2 = -1, pos3 = -1;
int f1 = 1, f2 = 1;
for(int i = 1; i <= n; i ++)
{
if(s[i] == 'D')
{
pos1 = i;
break;
}
}
if(pos1 == -1)f1 = 0;
for(int i = n; i >= 1; i --)
{
if(s[i] == 'S')
{
pos3 = i;
break;
}
}
if(pos3 == -1)f1 = 0;
for(int i = pos1 + 1; i < pos3; i ++)
{
if(s[i] == 'F')
{
pos2 = i;
break;
}
}
if(pos2 == -1)f1 = 0;

pos1 = -1, pos2 = -1, pos3 = -1;
for(int i = 1; i <= n; i ++)
{
if(s[i] == 'd')
{
pos1 = i;
break;
}
}
if(pos1 == -1)f2 = 0;
for(int i = n; i >= 1; i --)
{
if(s[i] == 's')
{
pos3 = i;
break;
}
}
if(pos3 == -1)f2 = 0;
for(int i = pos1 + 1; i < pos3; i ++)
{
if(s[i] == 'f')
{
pos2 = i;
break;
}
}
if(pos2 == -1)f2 = 0;

cout << f1 << ' ' << f2 << endl;
}

int main()
{
IOS
int _;
cin >> _;
while(_ --)
{
solve();
}

return 0;
}

B

枚举情况

考虑左右各堵住了几格和特判(1,-1)(1,1)(2,0)这三个点

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long ll;

const int N = 100010;

void solve()
{
int n;
cin >> n;
map<PII, int> mp;
for(int i = 0; i < n; i ++)
{
int x, y;
cin >> x >> y;
mp[{x, y}] = 1;
}

int l = 0, r = 0;
for(auto t : mp)
{
int x = t.first.first, y = t.first.second;
//cout << "===" << x << ' ' << y << endl;
if(y < 0)
{
l = max(l, 1);
int tmp = 1;
if(x == 1)tmp = 2;

if(mp.count({tmp, y - 1}) || mp.count({tmp, y}) || mp.count({tmp, y + 1}))
{
l = 2;
}
}
else if(y > 0)
{
r = max(r, 1);
int tmp = 1;
if(x == 1)tmp = 2;

if(mp.count({tmp, y - 1}) || mp.count({tmp, y}) || mp.count({tmp, y + 1}))
{
r = 2;
}
}
}

    int res = 4 - l - r;
int tmp = 4;
    if(mp[{2, 0}])
    {
        tmp = 2;
        if(mp[{1, -1}])tmp --;
        if(mp[{1, 1}])tmp --;
        if(r == 2)res = min(res, 1);
        if(l == 2)res = min(res, 1);
    }
    res = min(res, tmp);
    if(mp[{1, -1}])
    {
        res = min(res, 2);
        if(mp[{1, 1}])res = min(res, 1);
    }
    if(mp[{1, 1}])
    {
        res = min(res, 2);
    }
    res = min(res, 3);
    cout << res << endl;
}

int main()
{
IOS
int _;
cin >> _;
while(_ --)
{
solve();
}

return 0;
}

C

可以排序然后前缀和预处理出来在哪个人前面插队增加的时间，对每次询问可以二分来找

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long ll;

const int N = 100010;

ll a[N], b[N];

void solve()
{
int n, Q, t;
cin >> n >> Q >> t;
for(int i = 1; i <= n; i ++)cin >> a[i];
sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i ++)a[i] += a[i - 1];
for(int i = 1; i <= n; i ++)//第i个时刻前插队 
{
        b[i] = (ll)(n - i + 1) * t;
}
b[n + 1] = 0;

while(Q --)
{
ll x;
cin >> x;
int l = 1, r = n + 1;
while(l < r)
{
int mid = l + r >> 1;
if(b[mid] <= x)r = mid;
else l = mid + 1;
}
cout << a[l - 1] + t << endl;
}
}

int main()
{
IOS
int _ = 1;
//cin >> _;
while(_ --)
{
solve();
}

return 0;
}

E

范围只有10，可以3的n次方枚举所有情况

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long ll;

const int N = 15;

int a[N], b[N];
int q1[N], q2[N];

void solve()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++)cin >> a[i];

for(int i = 0; i < m; i ++)
{
cin >> q1[i] >> q2[i];
}

int num = 1;
for(int i = 0; i < m; i ++)num *= 3;
int ans = 2e9;
for(int i = 0; i < num; i ++)
{
for(int j = 1; j <= n; j ++)b[j] = a[j];
int t = i;
for(int j = 0; j < m; j ++)
{
int A = q1[j], B = q2[j];
if(t % 3 == 0)
{
b[A] += 3;
}
else if(t % 3 == 1)
{
b[B] += 3;
}
else
{
b[A] ++;
b[B] ++;
}
t /= 3;
}  

int x = b[1];
sort(b + 1, b + 1 + n);
int l = 1, r = n;
while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(b[mid] <= x)l = mid;
        else r = mid - 1;
    }
    ans = min(ans, n + 1 - l);
    
}

    cout << ans << endl;
}

int main()
{
IOS
int _;
cin >> _;
while(_ --)
{
solve();
}

return 0;
}

F

第二类斯特林数

将n个不同的元素分为k个集合或者将n个不同的小球放进k个相同的箱子

S(n, k) = S(n - 1, k) + k * S(n - 1, k)

n=k时为1，S(n, k) = 1

S(n, 0) = 0，特别地S(0, 0) = 1

容斥原理计算公式

$S(n,m)=\frac{1}{m!}\sum_{k=0}^{m}(-1)^{k}C(m,k)(m-k)^{n}$

搭配快速幂可以mlogn求出来

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long ll;

const int N = 100010, mod = 1e9 + 7;
 
int n, m;
int fact[N], infact[N], inv[N];
 
int C(int a, int b)
{
    if(a < b)return 0;
return (ll)fact[a] * infact[b] % mod * infact[a - b] % mod;
}

ll qmi(ll a, ll k)
{
ll res = 1;
while(k)
{
if(k & 1)res = res * a % mod;
a = a * a % mod;
k >>= 1;
}
return res;
}
 
int main()
{
IOS

fact[0] = fact[1]= infact[0] = infact[1] = inv[1] = 1;
for(int i = 2; i < N; i ++)
{
fact[i] = ((ll)fact[i - 1] * i) % mod;
inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
infact[i] = (ll)infact[i - 1] * inv[i] % mod;
}

cin >> n >> m;
int sign = 1;
ll ans = 0;
for(int k = 0; k <= m; k ++)
{
ll res = C(m, k) * qmi(m - k, n) % mod * sign;
ans = (ans + res) % mod;
        sign *= -1;
} 
ans = (ans + mod) % mod;
ll tmp = 1;
for(int i = 2; i <= m; i ++)
{
tmp = tmp * i % mod;
}
ans = ans * qmi(tmp, mod - 2) % mod;
cout << ans;

return 0;
}

G

本金+b[i] >= a[i]时就说明可以买，可以先把所有b[i]加到本金里，然后从最大的a[i]往小枚举，不满足的话就-b[i]

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long ll;

const int N = 100010;

PII a[N];

bool cmp(PII A, PII B)
{
return A.first - A.second < B.first - B.second;
}

void solve()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++)
{
int x, y;
cin >> x >> y;
a[i] = {x, y};
}

sort(a + 1, a + 1 + n);
ll t = m;
for(int i = 1; i <= n; i ++)
{
t += a[i].second;
}
for(int i = n; i >= 1; i --)
{
if(t < a[i].first)
{
t -= a[i].second;
}
}
cout << t << endl;
}

int main()
{
IOS
int _;
cin >> _;
while(_ --)
{
solve();
}

return 0;
}

H

标题说是背包但其实解法跟背包也没什么关系

如果背包容量为10101 （二进制）

物品重量为10101 10011

如果选了第一个物品第二个就选不了，如果选了第二个第一个就选不了，无法同时选

可以考虑将背包容量的某一位1强制转为0，然后这一位上为1的物品都不选，只要在这一位之前，物品的重量的位为1时背包这一位也为1就说明可选。这一位之后怎么都无所谓的，不论怎么选都会小于原背包容量的

这样在每次过程中每个物品都变成了可选和不可选两种情况。

然后背包原重量也这么来一遍，取一个最大值即可

这样枚举是包含所有情况的

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long ll;

const int N = 100010;

int n, m;
int v[N], w[N];

void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)
{
cin >> v[i] >> w[i];
}

ll ans = 0;
for(int i = 1; i <= n; i ++)
{
if((w[i] | m) == m)
{
ans += v[i];
}
}

while(m)
{
if(m & 1)
{
m >>= 1;
ll res = 0;
for(int i = 1; i <= n; i ++)
{
                if(w[i] & 1)
                {
                    w[i] >>= 1;
                    continue;
                }
                w[i] >>= 1;
if((w[i] | m) == m)
{
res += v[i];
}
}
ans = max(ans, res);
}
else 
        {
            m >>= 1;
            for(int i = 1; i <= n; i ++)w[i] >>= 1;
        }
}
cout << ans << endl;
}

int main()
{
IOS
int _;
cin >> _;
while(_ --)
{
solve();
}

return 0;
}

I

正统解法其实是看点的分布概率，第一个人的点分布概率是平均的，第二个人的点分布概率是偏中心的。

我想的是算两个人半径的期望，第二个人的期望一定比第一个人的期望大

最终半径的平均值离谁更近就说明是谁，那肯定有一个临界值，我的想法是找这个临界值

或者也可以真的按这两个人的办法分别模拟1e5或者更多次，看期望是多少

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long ll;

int main()
{
IOS
    
    int n;
cin >> n;
double r = 0;
for(int i = 1; i <= n; i ++)
{
double tmp;
cin >> tmp >> tmp >> tmp;
r += tmp;
}
r /= (double)n;

if(r <= 20.0)cout << "bit-noob";
    else cout << "buaa-noob";


return 0;
}

K

一个题的选项是对应题的答案，可以构建出一个基环树（其实是若干个基环树，或者说森林）。

一个环可以有好几条链，所以从链的起点出发其实不好算，但也可以发现后者答案固定后前者的答案是可以逆推出来的，所以可以从一个环上的任意一个点当成起点出发，枚举A-F选项，如果选项合理就计入答案

最终答案数其实就是每个环的方案数相乘

这里学到了一种很好写的方法，用vector存这次遍历到的所有点，然后看最后一个点的下一个点是否在vector中，如果在就说明有环，把这个点之前的点清除剩下的就是一个环。如果最后一个点的下一个点没在vector中就说明没环（环已经被标记了），非常方便的写法

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long ll;

const int N = 100010, mod = 998244353;

int n;
int a[N];
string s[N];
bool st[N];

int main()
{
IOS
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> a[i] >> s[i];
}

ll ans = 1;
for(int i = 1; i <= n; i ++)
{
if(st[i])continue;
int j = i;
vector<int> v;
for(; !st[j]; j = a[j])
{
st[j] = true;
v.push_back(j);
}

vector<int>::iterator it = find(v.begin(), v.end(), j);
if(it == v.end())continue;

v.erase(v.begin(), it);//这样只剩下环里的点了
ll res = 0;
for(char ch = 'A'; ch <= 'E'; ch ++)
{
int t = ch - 'A';
for(auto x : v)
{
t = s[x][t] - 'A';
}
if(ch - 'A' == t)res ++;
}
ans = ans * res % mod;
}
cout << ans;

return 0;
}

L

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long ll;

const int N = 100010;

ll a[N], b[N];

void solve()
{
ll c, d, h, w;
    cin >> c >> d >> h >> w;
cout << 3 * w * c << endl;
}

int main()
{
IOS
int _;
cin >> _;
while(_ --)
{
solve();
}

return 0;
}

M

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long ll;

const int N = 55;

void solve()
{
int n;
cin >> n;
if(n % 6)
{
cout << n / 6 * 2 << endl;
}
else cout << n / 6 << endl;
}

int main()
{
IOS
int _;
cin >> _;
while(_ --)
{
solve();
}

return 0;
}

原文地址：https://blog.csdn.net/a1695574118/article/details/136013659

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【Java篇】—— Object类
下一篇：集成开发环境 IntelliJ IDEA的基本使用

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20

2024牛客寒假算法基础集训营1

A

B

C

E

F

G

H

I

K

L

M

相关文章