【线上赛】2024牛客寒假营第一场

阅读理解场，没有想象的难

A

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=66961292

签到，双指针

#include <bits/stdc++.h>

using namespace std;

void solve() {

int n;

string s;

cin >> n >> s;

string to = "DFS";

pair<int, int> ans = {0, 0};

for (int i = 0, j = i, k = 0; i < n; i = j) {

while (j < n && k < 3 && s[j] != to[k]) ++ j;

if (k == 3) {

ans.first = 1;

break;

}

k ++;

}

to = "dfs";

for (int i = 0, j = i, k = 0; i < n; i = j) {

while (j < n && k < 3 && s[j] != to[k]) ++ j;

if (k == 3) {

ans.second = 1;

break;

}

k ++;

}

cout << ans.first << ' ' << ans.second << '\n';

}

int main() {

cin.tie(0)->sync_with_stdio(0);

int T; cin >> T;

while (T --) {

solve();

}

M

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=66963145

签到，模拟一下就能把答案猜出来

#include <bits/stdc++.h>

using namespace std;

void solve() {

int n; cin >> n;

if (n % 6 == 0) cout << n / 6 << '\n';

else cout << (n / 6) * 2 << '\n';

}

int main() {

cin.tie(0)->sync_with_stdio(0);

int T; cin >> T;

while (T --) solve();

}

E

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=66968472

诈骗题，看数据范围可知暴搜即可 $O(3^n)$

#include <bits/stdc++.h>

using namespace std;

using PII = pair<int, int>;

int dfs(int p, vector<int> a, vector<PII> &b) {

if (p >= b.size()) {

int ans = 1;

for (auto i: a)

if (i > a[1])

ans ++;

return ans;

}

auto [u, v] = b[p];

int ans = a.size() - 1;

// u win

a[u] += 3;

ans = min(ans, dfs(p + 1, a, b));

a[u] -= 3;

// v win

a[v] += 3;

ans = min(ans, dfs(p + 1, a, b));

a[v] -= 3;

// ping

a[u] ++, a[v] ++;

ans = min(ans, dfs(p + 1, a, b));

a[u] --, a[v] --;

return ans;

}

void solve () {

int n, m;

cin >> n >> m;

vector<int> a(n + 1);

for (int i = 1; i <= n; ++ i) cin >> a[i];

vector<PII> b(m + 1);

for (int i = 1; i <= m; ++ i) cin >> b[i].first >> b[i].second;

cout << dfs(1, a, b) << '\n';

}

int main() {

cin.tie(0)->sync_with_stdio(0);

int T; cin >> T;

while (T --) solve();

}

G

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=66977009

上强度了，先假设所有的优惠券都可以用，然后检查一下是不是符合条件，不符合把最不可能的选择去掉

注意到$a$相同时，优惠券最优是一起使用，所以我们先进行合并，然后我们发现要满足条件只要$m+b\le a$即可，所以我们按照$a-b$排序，值越大越不可能取到

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using PII = pair<LL, LL>;

void solve() {

int n, m;

cin >> n >> m;

vector<PII> v;

map<LL, LL> mp;

for (int i = 1; i <= n; ++ i) {

LL x, y;

cin >> x >> y;

mp[x] += y;

}

for (auto [a, b]: mp) {

v.push_back({a, b});

}

sort(v.begin(), v.end(), [&](const PII &x, const PII &y) -> bool {

return x.first - x.second < y.first - y.second;

});

LL ans = m;

set<LL> st;

for (auto [a, b]: v) {

ans += b;

st.insert(a);

}

for (int i = v.size() - 1; ~i; -- i) {

auto [a, b] = v[i];

if (ans >= *st.rbegin()) break;

ans -= b;

st.erase(a);

}

cout << ans << '\n';

}

int main() {

cin.tie(0)->sync_with_stdio(0);

int T; cin >> T;

while (T --) solve();

}

C

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=66982848

贪心+前缀和，比较明显的一道题

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const int N = 1e5 + 10;

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) {

b[i] = b[i - 1] + a[i];

}

auto check = [&](int x, LL m) -> bool {

// 插队在x位置，容忍度为m

// x以及x之后的元素向后移动一位

return (LL)t * (n - x + 1) <= m;

};

// for (int i = 1; i <= n; ++ i) {

// cout << a[i] << ' ' << b[i] << endl;

// }

while (q --) {

LL m; cin >> m;

int l = 1, r = n + 1;

while (l < r) {

int mid = l + r >> 1;

if (!check(mid, m)) l = mid + 1;

else r = mid;

}

cout << a[l - 1] + t << '\n';

}

int main() {

cin.tie(0)->sync_with_stdio(0);

solve();

}

B

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=66992685

超级分类讨论题，想清楚了就不难

#include <bits/stdc++.h>

using namespace std;

using PII = pair<int, int>;

int solve() {

int n; cin >> n;

if (!n) return 3;

vector<PII> v(n);

for (auto &[x, y]: v) cin >> y >> x;

sort(v.begin(), v.end());

bool _0_2 = false, _1_1 = false, _ne1_1 = false;

bool f1 = false, f2 = false;

bool postive = false, negetive = false;

for (auto [x, y]: v) {

if (x == 0 && y == 2) _0_2 = true;

if (x == 1 && y == 1) _1_1 = true;

if (x == -1 && y == 1) _ne1_1 = true;

if (x > 0) postive = true;

if (x < 0) negetive = true;

}

for (int i = 0; i < v.size() - 1; ++ i) {

auto [x1, y1] = v[i];

auto [x2, y2] = v[i + 1];

if (x2 <= 0) {

if (x2 - x1 <= 1 && y1 + y2 == 3) f1 = true;

}

if (x1 >= 0) {

if (x2 - x1 <= 1 && y1 + y2 == 3) f2 = true;

}

if (_0_2) return (int)(!f1) + (!f2);

if (f1 && f2) return 0;

if (f1 && !f2) {

if (!postive) return 2;

return 1;

}

if (!f1 && f2) {

if (!negetive) return 2;

return 1;

}

if (!postive) {

return 3 - _ne1_1;

}

if (!negetive) {

return 3 - _1_1;

}

if (_1_1 && _ne1_1) return 1;

return 2;

}

int main() {

cin.tie(0)->sync_with_stdio(0);

int T; cin >> T;

while (T --) cout << solve() << '\n';

}

L

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67020644

考场上卡这题了，原因是题目看错了，其实很简单，就是光源在x轴上取到答案

for _ in range(int(input())):

c, d, h, w = map(int, input().split())

print(3 * w * c)

I

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67024865

之前没见到过这种题，算是长见识了，本来考场可以开，结果被新形式吓到了

其实只要本地暴力算一下期望就可以过，这里我求的是到原点距离的平均值

AC code

n = int(input())

aver = 0.0

for i in range(n):

x, y, r = map(int, input().split())

aver += (x * x + y * y)**0.5 / n

dis1 = 76.19537506189376

dis2 = 57.37774189707354

if abs(aver - dis1) < abs(aver - dis2):

print("bit-noob")

else:

print("buaa-noob")

本地代码

from random import randint

def dis(x, y):

return (x * x + y * y)**0.5

def check(x, y, r):

return -100 + r <= x <= 100 - r and -100 + r <= y <= 100 - r

def mk1():

x, y, r = randint(-99, 99), randint(-99, 99), randint(1, 100)

while not check(x, y, r):

r = randint(1, 100)

return (x, y, r)

def solve1(n):

aver = 0.0

for i in range(n):

x, y, r = mk1()

aver += dis(x, y) / n

return aver

def mk2():

x, y, r = randint(-99, 99), randint(-99, 99), randint(1, 100)

while not check(x, y, r):

x, y, r = randint(-99, 99), randint(-99, 99), randint(1, 100)

return (x, y, r)

def solve2(n):

aver = 0.0

for i in range(n):

x, y, r = mk2()

aver += dis(x, y) / n

return aver

n = int(5e5)

print(solve1(n))

print(solve2(n))

F

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67045820

新知识点，第二类斯特林数，建议~~我队友~~学习一下

这里我用到了线性逆元

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

using LL = long long;

constexpr int N = 1e5 + 10;

constexpr int mod = 1e9 + 7;

int jc[N], inv[N];

void init(int n) {

jc[0] = inv[0] = 1;

jc[1] = inv[1] = 1;

for (int i = 2; i <= n; ++ i) {

inv[i] = (LL)(mod - mod / i) * inv[mod % i] % mod;

jc[i] = (LL)jc[i - 1] * i % mod;

}

for (int i = 2; i <= n; ++ i)

inv[i] = (LL)inv[i - 1] * inv[i] % mod;

}

int c(int n, int m) {

return (LL)jc[n] * inv[m] % mod * inv[n - m] % mod;

}

int fpow(int a, int b) {

int res = 1;

for (; b; b >>= 1) {

if (b & 1) res = (LL)res * a % mod;

a = (LL)a * a % mod;

}

return res;

}

int solve(int n, int m) {

int res = 0;

for (int k = 0; k <= m; ++ k) {

if (k & 1) {

res = (res - (LL)c(m, k) * fpow(m - k, n) % mod) % mod;

} else {

res = (res + (LL)c(m, k) * fpow(m - k, n) % mod) % mod;

}

return ((LL)res * inv[m] % mod + mod) % mod;

}

int main() {

int n, m;

cin >> n >> m;

init(1e5);

cout << solve(n, m) << endl;

}

H

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67096210

我被骗了，这题不是背包。虽然有限制但是我们可以让限制从最低位到某一位全为0，这样就一定会小于限制了，每次遍历一遍判断一下子集相加，再更新到答案里面就可以。

#include <iostream>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std;

using LL = long long;

template<typename T> void chkmax(T &a, const T &b) {

if (a < b) a = b;

}

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

auto calc = [&](int m) -> LL {

LL res = 0;

for (int i = 0; i < n; ++ i)

if ((w[i] & m) == w[i])

res += v[i];

return res;

};

LL ans = calc(m);

for (int i = m; i; i -= i & -i) chkmax(ans, calc(i - 1));

cout << ans << '\n';

}

int main() {

cin.tie(0)->sync_with_stdio(0);

int T; cin >> T;

while (T --) solve();

}

【线上赛】2024牛客寒假营第一场

A

M

E

G

C

B

L

I

F

H

发表回复 取消回复

发表回复取消回复