2025牛客寒假算法基础集训营2 题解
Preface作为一名半退役选手，个人感觉本场难度不是太大，感觉和去年比难度貌似是下降了。在打的时候实在是由于乱七八糟的原因（包括不限于眼瞎，眼瞎，还有眼瞎），打得一般般。
感觉本场模拟题偏多，实在是吃屎。
我会在代码一些有必要的地方加上注释，签到题可能一般就不会写了.
以下是代码火车头：
#include <iostream>
#include
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <iomanip>
#define endl '\n'
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rep2(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
template<typename T>
void cc(const vector<T> &tem) {
for (const auto &x: tem) cout << x << ' ';
cout << endl;
}
template<typename T>
void cc(const T &a) { cout << a << endl; }
template<typename T1, typename T2>
void cc(const T1 &a, const T2 &b) { cout << a << ' ' << b << endl; }
template<typename T1, typename T2, typename T3>
void cc(const T1 &a, const T2 &b, const T3 &c) { cout << a << ' ' << b << ' ' << c << endl; }
void cc(const string &s) { cout << s << endl; }
void fileRead() {
#ifdef LOCALL
freopen("D:\\AADVISE\\Clioncode\\untitled2\\in.txt", "r", stdin);
freopen("D:\\AADVISE\\Clioncode\\untitled2\\out.txt", "w", stdout);
#endif
}
void kuaidu() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); }
inline int max(int a, int b) {
if (a < b) return b;
return a;
}
inline double max(double a, double b) {
if (a < b) return b;
return a;
}
inline int min(int a, int b) {
if (a < b) return a;
return b;
}
inline double min(double a, double b) {
if (a < b) return a;
return b;
}
void cmax(int &a, const int &b) { if (b > a) a = b; }
void cmin(int &a, const int &b) { if (b < a) a = b; }
void cmin(double &a, const double &b) { if (b < a) a = b; }
void cmax(double &a, const double &b) { if (b > a) a = b; }
using PII = pair<int, int>;
using i128 = __int128;
using vec_int = std::vector<int>;
using vec_char = std::vector<char>;
using vec_double = std::vector<double>;
using vec_int2 = std::vector<std::vector<int> >;
using que_int = std::queue<int>;Problem E. 一起走很长的路！
一个很典典的题，简简单单推式子就好了，比\(C\)题简单不少。
设前缀和\(pre_i=a_1+a_2+...+a_i\)，那么需要满足条件：\(pre_i-pre_{l-1}>=a_{i+1}\)，\(l r1) return; if (l11; if (r1r1) return info(); if (l11; if (r1 > T; while (T--) { cin >> n; int q; cin >> q; rep(i, 1, n) { cin >> A; pre += A; pre += pre; } seg.clear(1, n - 1); rep(i, 1, n-1) { dis = pre - A; seg.add(i, i, dis); } rep(i, 1, q) { int l, r; cin >> l >> r; int tem = seg.qry(l, r - 1).mmin; int ans = 0; if (tem < pre) { ans = pre - tem; } cc(ans); } } return 0;}Problem F. 一起找神秘的数！
稍微画一画就能发现，满足条件需要\(x=y\)。
具体推的话，可以用韦恩图画一下就好了，记住，‘或’是求并集，异或是去重，and 是求交集。
//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
//--------------------------------------------------------------------------------
//struct or namespace:
//--------------------------------------------------------------------------------
signed main() {
fileRead();
kuaidu();
T = 1;
//cin >> T;
while (T--) {
bool fl = 0;
rep(i, 1, 7) {
int a;
cin >> a;
if (a == 4 or a == 7) fl = 1;
}
if (!fl) cc("YES");
else cc("NO");
}
return 0;
}Problem G. 一起铸最好的剑！
直接模拟就好了，不要直接用\(pow\)函数就好。
//--------------------------------------------------------------------------------
const int N = 5e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
int A;
//--------------------------------------------------------------------------------
//struct or namespace:
//--------------------------------------------------------------------------------
signed main() {
fileRead();
kuaidu();
T = 1;
//cin >> T;
while (T--) {
cin >> n;
rep(i, 1, n) cin >> A;
sort(A + 1, A + n + 1);
// rep(i, 1, n) cc(A);
int val = A[(n + 1 + 1) / 2] - 1;
cc(val);
}
return 0;
}Problem H. 一起画很大的圆！
最吃屎的时候，交了\(12\)发才过，还是最后蒙过去的。
首先先读题，边界！一开始读题读成了内部也可以，然后就先固定了两个点在斜线，然后找了最接近斜线的横坐标的每一个点去判断，时间复杂度按理来说是横坐标或者纵坐标的差值，\(1\)秒应该是能勉强跑过才对的，但是\(wa\)了，要不就是\(t\)了。
然后发现是在边界上...，但是依旧不会，脑子已经秀逗了。
最后暴力枚举了角落边界和中间边界的位置，然后跑过的。（其实也是有直觉是感觉两个点在角落，一个点在另一个同侧的角落，但是不确定）
//--------------------------------------------------------------------------------
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
char s;
//--------------------------------------------------------------------------------
//struct or namespace:
//--------------------------------------------------------------------------------
signed main() {
fileRead();
kuaidu();
T = 1;
cin >> T;
while (T--) {
cin >> n >> m;
if (n == m) {
cc("NO");
continue;
}
if (m >= n - m + 1) {
if (n - m - 1 <= 25 and n >= 4 and m >= 3) {
cc("YES");
s = 'a';
s = 'a';
rep(i, n-m+1, m) s = 'a';
rep(i, 2, n-m+1-1) {
s = 'a' + i - 1;
s = s;
}
rep(i, 1, n) { cout << s; }
cout << endl;
}
else {
cc("NO");
}
}
else {
if (m - 1 + (n - m - m) <= 25) {
cc("YES");
int k = m - 1 + (n - m - m);
int x = n - k - 2, y = k - x;
rep(i, 1, x) { cout << char('a' + i); }
cout << 'a';
rep(i, x+1, x+y) { cout << char('a' + i); }
cout << 'a';
rep(i, 1, x) { cout << char('a' + i); }
cout << endl;
}
else {
cc("NO");
}
}
}
return 0;
}Problem I. 一起看很美的日落！
一个典典的树形dp，但是赛时没有时间做了，应该是有铜+的难度的。
首先我们对于每一位可以独立看待，于是每个点的权值变成了0或者1，然后经典树形dp。
设\(dp_x\)是包含了\(x\)的联通块的\(ans\)，\(f_{x,0}\)是联通块里0的个数，\(f_{x,1}\)同理，\(g_x\)是联通块大小。
然后考虑如何合并两个联通块：
//--------------------------------------------------------------------------------
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
int pre;
int suf;
string s;
//--------------------------------------------------------------------------------
//struct or namespace:
//--------------------------------------------------------------------------------
bool check(int len) {
rep(i, 1, n) {
int l = i, r = i + len - 1;
if (l < 1 or r > n) break;
if (pre - 'a'] or suf - 'a']) {
return 1;
}
}
return 0;
}
signed main() {
fileRead();
kuaidu();
T = 1;
//cin >> T;
while (T--) {
cin >> n;
cin >> s;
s = ' ' + s;
rep(i, 1, n) {
rep(j, 0, 25) pre = pre;
pre - 'a'] = 1;
}
rep2(i, n, 1) {
rep(j, 0, 25) suf = suf;
suf - 'a'] = 1;
}
int ans = 0;
int l = 0, r = n;
while (l + 1 != r) {
int mid = l + r >> 1;
if (check(mid)) l = mid;
else r = mid;
}
cc(l);
}
return 0;
}我觉得式子很显然，大家看了就晓得了。代码很简洁，顺手抄了个题解的取模类。
//--------------------------------------------------------------------------------
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
//--------------------------------------------------------------------------------
//struct or namespace:
class SEG {
#define xl x+x
#define xr x+x+1
//TODO 节点维护信息、apply函数、up函数
struct info {
int mmin = INF;
void apply(int k) {
mmin = k;
}
friend info operator+(const info &q1, const info &q2) {
info q;
q.mmin = min(q1.mmin, q2.mmin);
return q;
}
};
int L, R;
info F;
void init(int x, int l, int r) {
if (l == r) {
F = info();
return;
}
int mid = l + r >> 1;
init(xl, l, mid), init(xr, mid + 1, r);
F = F + F;
}
void add(int x, int l, int r, int l1, int r1, int k) {
if (l1 > r1) return;
if (l1 <= l and r <= r1) {
F.apply(k);
return;
}
int mid = l + r >> 1;
if (r1 <= mid) add(xl, l, mid, l1, r1, k);
else if (mid < l1) add(xr, mid + 1, r, l1, r1, k);
else add(xl, l, mid, l1, mid, k), add(xr, mid + 1, r, mid + 1, r1, k);
F = F + F;
}
info qry(int x, int l, int r, int l1, int r1) {
if (l1 > r1) return info();
if (l1 <= l and r <= r1) return F;
int mid = l + r >> 1;
if (r1 <= mid) return qry(xl, l, mid, l1, r1);
else if (mid < l1) return qry(xr, mid + 1, r, l1, r1);
else { return qry(xl, l, mid, l1, mid) + qry(xr, mid + 1, r, mid + 1, r1); }
}
#undef xl
#undef xr
public:
void clear(int l, int r) {
L = l, R = r;
init(1, l, r);
}
void add(int l, int r, int k) { add(1, L, R, l, r, k); }
info qry(int l, int r) { return qry(1, L, R, l, r); }
};
SEG seg;
int A, pre, dis;
//--------------------------------------------------------------------------------
signed main() {
fileRead();
kuaidu();
T = 1;
//cin >> T;
while (T--) {
cin >> n;
int q;
cin >> q;
rep(i, 1, n) {
cin >> A;
pre += A;
pre += pre;
}
seg.clear(1, n - 1);
rep(i, 1, n-1) {
dis = pre - A;
seg.add(i, i, dis);
}
rep(i, 1, q) {
int l, r;
cin >> l >> r;
int tem = seg.qry(l, r - 1).mmin;
int ans = 0;
if (tem < pre) {
ans = pre - tem;
}
cc(ans);
}
}
return 0;
}Problem L. 还会再见吗？
看了题解，虚树。
于是直接再见。
学虚树不如继续搞开发。
Problem M. 那是我们的影子
赛时没有做出来，赛后看题解发现不算太难。
但是个人感觉难度应该和\(I\)差不多才对。只能说这种题自己总会写的复杂，感慨大佬写的代码很简洁。
感觉官方题解写的很好很清楚，建议去看（不是自己懒了
借鉴了\(Heltion\)的代码：
//--------------------------------------------------------------------------------
const int N = 5e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
int A;
//--------------------------------------------------------------------------------
//struct or namespace:
//--------------------------------------------------------------------------------
signed main() {
fileRead();
kuaidu();
T = 1;
//cin >> T;
while (T--) {
cin >> n;
rep(i, 1, n) {
int a, b;
cin >> a >> b;
cc(b - a + 1);
}
}
return 0;
}PostScript
只能说自己吃屎吃得太多，有些题自己写的太烂，点名批评\(h\)题。
感觉难度比去年真的少了很多，不知道是不是错觉。
题解如果有误希望可以指出来。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]