A-DFS搜索
思路:
- 遍历字符S, 按顺序分别寻找 "DFS" , "dfs"。
以下是代码部分
#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
int t, n;
ios::sync_with_stdio(false);
cin >> t;
while(t --)
{
cin >> n >> s;
for(auto tem : {"DFS", "dfs"})
{
int kk = 0;
for(int i = 0; i < n; i ++)
if(kk < 3 && s[i] == tem[kk])
kk ++;
cout << (kk == 3) << " ";
}
cout << '\n';
}
return 0;
}
B-关鸡
题目描述:
在一条宽为 长为 + 的管道中,有一只鸡和若干着火点,鸡可以上下左右移动一格、不能出管道上下边界、不能进入着火地点。
鸡初始在 处,现在给出若干个着火点的坐标,请求出为了不让鸡逃出管道(即到达管道最左端或最右端),最少需要添加多少个着火点。
思路:
- 易得最多只需要添加三个着火点
- 想要关住鸡有两种关法:
- 第一种:左边两个着火点,右边两个着火点。共需添加四个
- 第二种:鸡的初始坐标的下面一个着火点,左右个一个着火点。共需添加三个
- 对坐标以横坐标的大小标准排序。
- 判断着火点的相邻个数
- 对比两种添加着火点的方法(选取最优的)。
以下是代码部分, 参考代码来源Scarlett_come_here
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
//存储已存在的着火点坐标
struct Coordinate {
//r代表纵坐标,c代表横坐标
int r, c;
}s[N];
//根据横坐标大小从小到大排序
bool cmp(Coordinate A, Coordinate B) {return A.c < B.c;}
void solve()
{
int maxn = 3, n;
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> s[i].r >> s[i].c;
sort(s + 1, s + n + 1, cmp);//排序
int flag_0 = 2, flag_1 = 2;
for(int i = 1; i < n; i ++)
{
auto [r1, c1] = s[i];
auto [r2, c2] = s[i + 1];
if(c1 == c2)//如果横坐标相等
{
//如果是左边的路被封锁,则左边的无需添加着火点。
if(c1 < 0) flag_0 = 0;
//如果是右边的路被封锁,则右边的无需添加着火点。
if(c2 > 0) flag_1 = 0;
}
if(c1 + 1 == c2)
if(r1 != r2)//如果相邻
{
//如果是左边的路被封锁,则左边的无需添加着火点。
if(c1 < 0) flag_0 = 0;
//如果是右边的路被封锁,则右边的无需添加着火点。
else flag_1 = 0;
}
}
for(int i = 1; i <= n; i ++)
{
auto[r1, c1] = s[i];
//如果为鸡的初始坐标下面
if(r1 == 2 && c1 == 0) maxn --;
//如果为鸡的初始坐标右边
if(r1 == 1 && c1 == 1) maxn --;
//如果为鸡的初始坐标左边
if(r1 == 1 && c1 == -1) maxn --;
//如果左边没有被封锁,且有一个着火点
if(flag_0 > 0 && c1 <= 0)
flag_0 = 1;
//如果右边没有被封锁,且有一个着火点
if(flag_1 > 0 && c1 >= 0)
flag_1 = 1;
}
//两种关住鸡的方法的所需最小数量的对比,选小的
cout << min(maxn, flag_0 + flag_1) << '\n';
}
int main()
{
int t;
ios::sync_with_stdio(false);
cin >> t;
while(t --)
solve();
return 0;
}
C-按闹分配
思路:
- 这题的难点其实是定位很急的鸡插队的位置
- 另一种就是比较基础的前缀和知识了。
- 易得,鸡插队的时间必须在一个人和另一个人之间才能做到等待时间最小
- 且插队后,想要满足 实际就是满足
以下是代码部分,用(快速查询定位,时间消耗更高)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll t[N];
ll r, l, m;
//快速查询
void finds(ll n, ll t_c, ll M)
{
r = n, l = 0;
m = ((r + l) >> 1);
while(l < r - 2)
{
//中间位置
m = ((l + r) >> 1);
//如果插队队太前面了,不合法了
if((n - m) * t_c > M)
l = m;//左端移到中间位置
//如果插队太后面了
else if((n - m) * t_c <= M)
r = m;//右端移到中间位置
}
}
int main()
{
ll q, n, t_c, M;
ios::sync_with_stdio(false);
cin >> n >> q >> t_c;
for(int i = 1; i <= n; i ++) cin >> t[i];
sort(t + 1, t + n + 1);
//前缀和
for(int i = 1; i <= n; i ++)
t[i] = t[i] + t[i - 1];
while(q --)
{
cin >> M;
finds(n, t_c, M);
for(ll i = l; i <= r; i ++)
if((n - i) * t_c <= M)
{
cout << t[i] + t_c << endl;
break;
}
}
return 0;
}
以下是代码部分——(通过计算查询位置)参考来源——jiangly
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n, Q, tc;
ios::sync_with_stdio(false);
cin >> n >> Q >> tc;
vector<ll> t(n + 1);
for(int i = 1; i <= n; i ++)
cin >> t[i];
sort(t.begin(), t.end());
for(int i = 1; i <= n; i ++)
t[i] += t[i - 1];
while(Q --)
{
ll M;
cin >> M;
//(n - pos)* tc <= M
ll c = min((ll)n, M / tc);//防止越界
ll ans = t[n - c] + tc;
cout << ans << '\n';
}
return 0;
}
D-数组成鸡
以下是代码部分,参考代码来源于出题人写的题解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 1e9, N = 2e5 + 10;
ll a[N];
int n;
set<int> s;
//检查是否超过了 1e9
bool check(ll x)
{
ll res = 1;
for(int i = 1; i <= n; i ++)
{
res *= a[i] + x;
if(llabs(res) > Inf) return false;
}
s.emplace(res);
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int q, M; cin >> n >> q;
ll l, r;
for(int i = 1; i <= n; i ++) cin >> a[i];
//必定可以输出0, 先放入0
s.emplace(0);
//降低接下来的判断时间
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i ++)
{
if(a[i] == a[i - 1]) continue;
for(l = -a[i] - 1; check(l); l --);
for(r = -a[i] + 1; check(r); r ++);
}
while(q --)
{
cin >> M;
cout << (s.count(M) ? "Yes\n" : "No\n");
}
return 0;
}
E-本题又主要考察了贪心
思路:
- 其实是dfs做法(深度优先搜索)
-也可以用状压
- 以代表对局情况
- 总共有 种, 枚举每一种情况
以下是代码部分(状压),代码参考来源——Scarlett_come_here
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
//a[]为原积分, now[]为比完赛后的现积分
int a[N], now[N];
int u[N], v[N];
int pw3[N];
void solve()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= m; i ++) cin >> u[i] >> v[i];
int maxn = n;
for(int i = 0; i < pw3[m]; i ++)
{
//存入到现积分中
for(int j = 1; j <= n; j ++) now[j] = a[j];
int p = i;//p 代表第几种情况
for(int j = 1; j <= m; j ++)
{
if (p % 3 == 0)
now[u[j]] += 3;
else if(p % 3 == 1)
now[v[j]] += 3;
else
now[u[j]] ++, now[v[j]] ++;
p /= 3;
}
int id = 1;
for(int j = 2; j <= n; j ++)
if (now[j] > now[1]) id ++;
maxn = min(maxn, id);
}
cout << maxn << '\n';
}
//预处理
void init()
{
//pw3代表在总共有i场比赛时有多少种状态
pw3[0] = 1;
for(int i = 1; i <= 10; i ++)
pw3[i] = pw3[i - 1] * 3;
}
int main()
{
init();
ios::sync_with_stdio(false);
int t;cin >> t;
while(t --) solve();
return 0;
}
F-鸡数题
思路:
- 第二类stirling
以下是代码部分
#include "bits/stdc++.h"
using namespace std;
const int mod = 1e9 + 7, N = 1e5 + 10;
typedef long long ll;
ll c[N], invc[N];
ll power(ll base, ll pow) {
ll res = 1;
while (pow)
{
if(pow & 1)
res = base * res % mod;
pow >>= 1;
base = base * base % mod;
}
return res;
}
ll inv(ll x) {return power(x, mod - 2);}
void init()
{
//求阶乘
c[0] = 1;
for (int i = 1; i < N; i++) c[i] = c[i - 1] * i % mod;
//求最大阶乘的逆元
invc[N - 1] = inv(c[N - 1]);
//求每一个的逆元
for (int i = N - 2; i >= 0; i--) invc[i] = invc[i + 1] * (i + 1) % mod;
}
//求组合数
ll C(int n, int m)
{
if (m < 0 || m > n || n < 0) return 0;
return c[n] * invc[m] % mod * invc[n - m] % mod;
}
int main() {
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
init();//预处理
ll ans = 0;
//第二类stirling数
for (int k = 0; k <= m; k++) {
if (k % 2 == 0)
ans = (ans + C(m, k) * power(m - k, n) % mod) % mod;
else
ans = (ans - C(m, k) * power(m - k, n) % mod + mod) % mod;
}
cout << ans * invc[m] % mod << '\n';
return 0;
}
G-why买外卖
思路:
- 贪心,从大到小排列
- 用后缀和储存
以下是代码部分
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
//存储减免券
typedef struct Mjian{
int a;
ll b;
}Mjian;
Mjian ab[N];
//从大到小按照a的大小排列
bool cmp1(Mjian x, Mjian y) {return x.a > y.a;}
//判断是否可以购买
bool judge(int n, int m)
{
for(int i = 1; i <= n; i ++)
if(ab[i].a - ab[i].b <= m)
{
//如果可以购买直接输出
cout << ab[i].b + m << endl;
return true;
}
//全都不行,则直接输出m
return false;
}
int main()
{
int t, n, m;
cin >> t;
while(t --)
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)
cin >> ab[i].a >> ab[i].b;
sort(ab + 1, ab + n + 1, cmp1);
//后缀和
for(int i = n - 1; i >= 1; i --)
ab[i].b = ab[i].b + ab[i + 1].b;
if(!judge(n, m))
cout << m << endl;
}
return 0;
}
H-01背包,但是bit
思路:牛客竞赛官方题解
具体实现步骤见代码部分,代码参考与——另一篇题解, Kidding_Ma
- 附注释
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
int n, m;
cin >> n >> m;
vector<int> v(n), w(n);
//输入物品的价值及重量
for (int i = 0; i < n; i++)
cin >> v[i] >> w[i];
//lambda写法,相当于自定义了一个函数
auto get = [&](int x) {
ll res = 0;
for (int i = 0; i < n; i++) {
if ((x & w[i]) == w[i])
res += v[i];
}
return res;
};
//先求出取的1为m的最大的1的情况时, 可取的最大价值
ll ans = get(m);
//此方法跳过了初始时最低位的1,初始时最低位的1后面并不能装任何东西
//同时也排除了取的1为最高位为1的情况
// i是否为真 (i & -i)取到 i 最低位的 1
for (int i = m; i; i -= (i & -i))//i - (i & -i)做到把取到1的这一位强制变为0
ans = max(ans, get(i - 1));// i-1 做到后面的全变为 1
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--) solve();
return 0;
}
I-It's bertrand paradox. Again!
思路:
-
方法一,模拟出两种画圆的方法
- 取特征值来判断是哪种
-
方法二,通过数据概率,找到特征值, 比较在区域的概率——Kidding_Ma的题解
- 第一种圆的圆心在范围内均匀分布
- 第二种圆的圆心分布更靠近中心
-
已知, 取的差值即可(不能过小)
以下是方法二的代码部分
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
ll n;
cin >> n;
ll ans = 0;
for(int i = 0; i < n; i ++)
{
int x, y, r;
cin >> x >> y >> r;
if(abs(x) <= 9 && abs(y) <= 9)
ans ++;
}
if(abs(ans * (199 * 199) - 19 * 19 * n) <= 18000000)
cout << "bit-noob\n";
else
cout << "buaa-noob\n";
return 0;
}
J-又鸟之亦心
思路:
- 二分查找最大距离的最小值
- 其中判断的时候用s存储被派去的分部的位置
- 如果s当中有元素存在,也就是在d的距离下,有合法位置
- 如果s为空,就代表没有合法位置使得d距离成立
以下是代码部分,代码参考来源——jiangly
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 1e5 + 10;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, x, y;
//输入
cin >> n >> x >> y;
vector<int> a(n);
for(int i = 0; i < n; i ++)
cin >> a[i];
//检查m的距离是否合法
auto check = [&](int d)
{
//记录其中一人的位置
int lst = y;
set<int> s;
//把其中一个人的位置存入
if(abs(x - y) <= d)
s.insert(x);
//遍历需要出差的地方
for(auto tem : a)
{
//集合s非空 并且 距离合法,存入集合内
if (!s.empty() && abs(tem - lst) <= d)
s.insert(lst);
//集合s非空 并且 距离不合法 删除不合法的值
while (!s.empty() && *s.begin() < tem - d)
s.erase(*s.begin());
//集合非空 并且 距离不合法 删除不合法的值
while (!s.empty() && *s.rbegin() > tem + d)
s.erase(*s.rbegin());
//更新位置
lst = tem;
}
return !s.empty();
};
int lo = 0, hi = 1e9;
while(lo < hi)
{
int m = (lo + hi) / 2;
if(check(m))
hi = m;
else
lo = m + 1;
}
cout << lo << '\n';
return 0;
}
K- 牛镇公务员考试
思路:
- 图论,置换环
以下是代码部分, 代码参考来源——Kidding_Ma的题解
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int mod = 998244353;
int main() {
ios::sync_with_stdio(false);
ll ans = 1;
int n; cin >> n;
//第i题指向第ai题
vector<int> a(n);
//记录这一题的选项
vector<string> s(n);
//标记是否已经处理过
vector<bool> vis(n);
//输入,为使下标统一, a[i] --
for (int i = 0; i < n; i++)
cin >> a[i] >> s[i], a[i]--;
for (int i = 0; i < n; i++)
{
//每题都串联起来
int j = i;
//存储题目之间的串联关系
vector<int> c;
//当第j题没有被串联时
for (; !vis[j]; j = a[j])
//串联,并存入c中
vis[j] = true, c.push_back(j);
//找到 j
auto it = find(c.begin(), c.end(), j);
//如果j被找到也就是,如果c[j]成功存入
if (it != c.end())
{
//避免重复处理
//删掉c[0]到it之前的数据,也就是删掉连在环上的链
c.erase(c.begin(), it);
// res 统计这个环的答案种类数
int res = 0;
//暴力枚举有几种情况
for (char st = 'A'; st < 'F'; st ++)
{
//如果cur能折法回来和原来相同的选项,则合法
char cur = st;
for (auto x : c)
cur = s[x][cur - 'A'];
res += (cur == st);
}
ans = ans * res % mod;
}
}
cout << ans << '\n';
return 0;
}
L-要有光
思路:
- 当光源放到地上的时候阴影面积最大
- 后用梯形面积公式求阴影面积即可
以下是代码部分
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t, c, d, h, w;
cin >> t;
while(t --)
{
cin >> c >> d >> h >> w;
printf("%.6lf\n", 3.0 * w * c);
}
return 0;
}
M-牛客老粉才知道的秘密
思路:
- 找规律发现和6有关
以下是代码部分
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t, n;
cin >> t;
while(t --)
{
cin >> n;
int sum = n / 6;
sum += (n % 6 != 0) * sum;
cout << sum << endl;
}
return 0;
}