2024牛客寒假算法基础集训营1
A.DFS搜索
思路：看dfs其实就是一道字符题目
#include <bits/stdc++.h>
using namespace std;
string x = "dfs";
string y = "DFS";
void solve() {
int n;
cin >> n;
string st;
cin >> st;
int xx = 0, yy = 0;
for (int i = 0; i < n; i++) {
if (st[i] == x[xx]) xx++;
if (st[i] == y[yy]) yy++;
}
if (xx == 3) xx = 1;
else xx = 0;
if (yy == 3) yy = 1;
else yy = 0;
cout << (yy) << " " << (xx) << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
B.关鸡
思路：1.最多就3个就是(0,1)(0,-1)(1,0) 2.左右怎么才能不出去? 左右都被堵死 3.如何堵死? 左右同一根线或者相距一格
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
if (n == 0) {
cout << "3" << endl;
return;
}
set<pair<int, int>> q;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
q.insert({a - 1, b});
}
int res = 4;
int ll = 2;
int rr = 2;
int a = q.count({0, -1}), b = q.count({0, 1}), c = q.count({1, 0});
if (c) {
ll = 1;
rr = 1;
}
if (a || b || c) {
res = min(res, 2ll);
if (a && b || a && c || b && c) {
res = min(res, 1ll);
}
if (a && b && c) {
res = 0;
}
}
for (auto [r, c]: q) {
if (c < 0) {
if (q.count({r ^ 1, c - 1}) || q.count({r ^ 1, c + 1}) || q.count({r ^ 1, c})) {
ll = 0;
} else {
ll = min(ll, 1ll);
}
} else if (c > 0) {
if (q.count({r ^ 1, c - 1}) || q.count({r ^ 1, c + 1}) || q.count({r ^ 1, c})) {
rr = 0;
} else {
rr = min(rr, 1ll);
}
}
}
res = min(res, ll + rr);
cout << res << endl;
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
C.按闹分配
思路：很明显不满意度最小的时候就是前面时间短，后面时间长，可以用前缀和来维护一下
$$
S_c-S_min=n-i(假设他是第i个去的)
$$
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int n, Q, tc;
cin >> n >> Q >> tc;
vector<int> t(n);
vector<int> s(n + 2);
for (int i = 0; i < n; i++) {
cin >> t[i];
}
sort(t.begin(), t.end());
for (int i = 0; i < n; i++) {
s[i + 1] = s[i] + t[i];
}
while (Q--) {
int m;
cin >> m;
int c = min(n, m / tc);
int ans = s[n - c] + tc;
cout << ans << endl;
}
}
E.本题又主要考查了贪心
思路：这题mn很小，根本不用想就狠狠暴力就行(debug搞了好久、、)，后面发现是我后面ans的问题、、、
#include <bits/stdc++.h>
using namespace std;
int m, n, num, ans;
const int MAX = 1e6;
int a[MAX], v[MAX], u[MAX];
void dfs(int x) {
if (x == num) {
int res = 0;
for (int i = 1; i < n; i++) {
if (a[i] > a[0])res++;
}
ans = min(ans, res);
return;
}
a[u[x]] += 3;
dfs(x + 1);
a[u[x]] -= 3;
a[u[x]] += 1;
a[v[x]] += 1;
dfs(x + 1);
a[u[x]] -= 1;
a[v[x]] -= 1;
a[v[x]] += 3;
dfs(x + 1);
a[v[x]] -= 3;
}
void solve() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
num = 0;
for (int i = 0; i < m; i++) {
int u1, v1;
cin >> u1 >> v1;
if (u1 == 1 || v1 == 1)a[0] += 3;
else {
u[num] = u1 - 1;
v[num] = v1 - 1;
num++;
}
}
ans = 1e6;
dfs(0);
cout << min(ans + 1, n) << endl;
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
G.why买外卖
思路：只要超过就能用，那假设都能用，怎么会出现不能用的？ 减去还不行的那种
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> q(n + 1);
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
q[i].first = a;
q[i].second = b;
m+=b;
}
sort(q.rbegin(), q.rend());
for(int i=0;i<n;i++){
if(m>=q[i].first) break;
else{
m-=q[i].second;
}
}
cout << m << endl;
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
L.要有光
思路：纯纯几何题，画个图推一下就行
#include <bits/stdc++.h>
using namespace std;
void solve() {
int c, d, h, w;
cin >> c >> d >> h >> w;
cout << 3 * c * w << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
M.牛客老粉才知道的秘密
思路：就是一个找规律的题就是看与6的关系
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
if (n % 6 == 0) {
cout << n / 6 << "\n";
return;
}
int x = n / 6 + 1;
x = x * 2 - 2;
cout << x << endl;
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
}