题解 | 2025牛客寒假算法基础集训营2 题解

Preface

作为一名半退役选手，个人感觉本场难度不是太大，感觉和去年比难度貌似是下降了。在打的时候实在是由于乱七八糟的原因（包括不限于眼瞎，眼瞎，还有眼瞎），打得一般般。

感觉本场模拟题偏多，实在是吃屎。

我会在代码一些有必要的地方加上注释，签到题可能一般就不会写了.

以下是代码火车头：

#include <iostream>
#include <algorithm>
#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 A. 一起奏响历史之音！

开场就了两发，详情不说了。好好看题就好。

//--------------------------------------------------------------------------------
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 B. 能去你家蹭口饭吃吗

实际就是求中间的数，即（偶数就是向上取整），这个数减一就好了。

//--------------------------------------------------------------------------------
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[N];
//--------------------------------------------------------------------------------
//struct or namespace:

//--------------------------------------------------------------------------------

signed main() {
	fileRead();
	kuaidu();
	T = 1;
	//cin >> T;
	while (T--) {
		cin >> n;
		rep(i, 1, n) cin >> A[i];
		sort(A + 1, A + n + 1);
		// rep(i, 1, n) cc(A[i]);

		int val = A[(n + 1 + 1) / 2] - 1;
		cc(val);
	}
	return 0;
}

Problem C. 字符串外串

对于这种构造题，我真的讲不出为什么。只能说是直觉。实则是瞎猜。猜着猜着就过了，不要问我为什么这样想。

思考的时候发现，我们不妨固定那一对决定了可爱度的字符，在的位置，相对应的，由于必须要有一对，所以我们也可以在对称的位置的位置也放一个。然后分类讨论一下，当的时候，那么我们空着的那些位置，我们发现我们可以都填，但是在的时候，中间并不能填。然后别的位置我们可以也拿一对字符来写写画画，然后两边只能一边一个，或者是只在一边放，另一边不放。如果放了三个或者同一侧放了两个显然是不行的。所以不可行的情况也能写出来了，当字符集（26个）不够用的时候，就是的情况，的情况多讨论讨论就好了。

//--------------------------------------------------------------------------------
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[N];
//--------------------------------------------------------------------------------
//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[1] = 'a';
				s[n] = 'a';
				rep(i, n-m+1, m) s[i] = 'a';
				rep(i, 2, n-m+1-1) {
					s[i] = 'a' + i - 1;
					s[n - i + 1] = s[i];
				}

				rep(i, 1, n) { cout << s[i]; }

				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 D. 字符串里串

我们可以想到，当固定一个连续子串的时候，去找寻一个连续的子序列到底有没有，我们只需要判断这个子串的右侧是否还有一个子串右端点的那个字符就可以了，左侧也同理。

以下都只讨论右侧：判断是否右侧有没有字符可以提前后缀和预处理出来。

然后首先二分长度，然后就暴力的扫一遍就好了。

//--------------------------------------------------------------------------------
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[N][31];
int suf[N][31];
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[l - 1][s[l] - 'a'] or suf[r + 1][s[r] - '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[i][j] = pre[i - 1][j];
			pre[i][s[i] - 'a'] = 1;
		}
		rep2(i, n, 1) {
			rep(j, 0, 25) suf[i][j] = suf[i + 1][j];
			suf[i][s[i] - '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;
}

Problem E. 一起走很长的路！

一个很典典的题，简简单单推式子就好了，比题简单不少。

设前缀和，那么需要满足条件：，。

式子挪一下，就是，。

右边的常量，左边我们用一个数组存起来就好了。然后这个式子代表我们要把这个区间里的最小值都要大于等于这个常量，所以我们需要一个区间查询的数据结构，直接套上线段树，虽然此处ST表更好。

然后答案就是两者的差值。

//--------------------------------------------------------------------------------
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[unsigned(N * 2.7)];
 
    void init(int x, int l, int r) {
        if (l == r) {
            F[x] = info();
            return;
        }
        int mid = l + r >> 1;
        init(xl, l, mid), init(xr, mid + 1, r);
        F[x] = F[xl] + F[xr];
    }
 
    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[x].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[x] = F[xl] + F[xr];
    }
 
    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[x];
        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[N], pre[N], dis[N];
//--------------------------------------------------------------------------------
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    //cin >> T;
    while (T--) {
        cin >> n;
        int q;
        cin >> q;
        rep(i, 1, n) {
            cin >> A[i];
            pre[i] += A[i];
            pre[i] += pre[i - 1];
        }
        seg.clear(1, n - 1);
 
        rep(i, 1, n-1) {
            dis[i] = pre[i] - A[i + 1];
            seg.add(i, i, dis[i]);
        }
 
        rep(i, 1, q) {
            int l, r;
            cin >> l >> r;
            int tem = seg.qry(l, r - 1).mmin;
            int ans = 0;
            if (tem < pre[l - 1]) {
                ans = pre[l - 1] - tem;
            }
            cc(ans);
        }
 
    }
    return 0;
}

Problem F. 一起找神秘的数！

稍微画一画就能发现，满足条件需要。

具体推的话，可以用韦恩图画一下就好了，记住，‘或’是求并集，异或是去重，and 是求交集。

//--------------------------------------------------------------------------------
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[N];
//--------------------------------------------------------------------------------
//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;
}

Problem G. 一起铸最好的剑！

直接模拟就好了，不要直接用函数就好。

//--------------------------------------------------------------------------------
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[N];
//--------------------------------------------------------------------------------
//struct or namespace:

//--------------------------------------------------------------------------------
int dfs(int b,int a) {

	if (b == 1) {
		return 1;
	}

	int ans = 0;
	int mmax = INF;
	int l = 0;
	int bas = b;
	b = b, l = 1;
	while (b <= a) {
		if (abs(b - a) < mmax) mmax = abs(b - a), ans = l;
		l++;
		b = b * bas;
	}
	if (abs(b - a) < mmax) mmax = abs(b - a), ans = l;
	return ans;
}

signed main() {
	fileRead();
	kuaidu();
	T = 1;
	//cin >> T;
	while (T--) {
		cin >> n;
		rep(i, 1, n) {
			int a, b;
			cin >> a >> b;
			cc(dfs(b, a));
		}
	}
	return 0;
}

Problem H. 一起画很大的圆！

最吃屎的时候，交了发才过，还是最后蒙过去的。

首先先读题，边界！一开始读题读成了内部也可以，然后就先固定了两个点在斜线，然后找了最接近斜线的横坐标的每一个点去判断，时间复杂度按理来说是横坐标或者纵坐标的差值，秒应该是能勉强跑过才对的，但是了，要不就是了。

然后发现是在边界上...，但是依旧不会，脑子已经秀逗了。

最后暴力枚举了角落边界和中间边界的位置，然后跑过的。（其实也是有直觉是感觉两个点在角落，一个点在另一个同侧的角落，但是不确定）

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
int ans_x[4], ans_y[4];
double ans = 0;
int a, bb, c, d;

//--------------------------------------------------------------------------------
//struct or namespace:

//--------------------------------------------------------------------------------

bool pan(int x,int y) {
	if (x < a or x > bb or y < c or y > d) return 1;
	return 0;

}

double radi(int x11,int y11,int x22,int y22,int x33,int y33) {
	if (pan(x11, y11)) return 0;
	if (pan(x22, y22)) return 0;
	if (pan(x33, y33)) return 0;
	if (x11 == x22 and y11 == y22) return 0;
	if (x11 == x33 and y11 == y33) return 0;
	if (x22 == x33 and y22 == y33) return 0;
	// cc(x11, y11);
	// cc(x22, y22);
	// cc(x33, y33);
	// cc("");
	double A, B, C, D;
	double x1 = x11, y1 = y11, x2 = x22, y2 = y22, x3 = x33, y3 = y33;

	A = x1 * (y2 - y3) - y1 * (x2 - x3) + x2 * y3 - x3 * y2;
	B = (x1 * x1 + y1 * y1) * (y3 - y2) + (x2 * x2 + y2 * y2) * (y1 - y3) + (x3 * x3 + y3 * y3) * (y2 - y1);
	C = (x1 * x1 + y1 * y1) * (x2 - x3) + (x2 * x2 + y2 * y2) * (x3 - x1) + (x3 * x3 + y3 * y3) * (x1 - x2);
	D = (x1 * x1 + y1 * y1) * (x3 * y2 - x2 * y3) + (x2 * x2 + y2 * y2) * (x1 * y3 - x3 * y1) + (x3 * x3 + y3 * y3) * (
		    x2 * y1 - x1 * y2);
	if (!A) return 0;
	double r = sqrt((B * B + C * C - 4 * A * D) / (4 * A * A));
	if (r > ans) {
		ans = r;
		ans_x[0] = x11, ans_x[1] = x22, ans_x[2] = x33;
		ans_y[0] = y11, ans_y[1] = y22, ans_y[2] = y33;

	}
	return r;
}


void dfs(int a,int b,int c,int d) {

	int x1 = a, y1 = d;
	int x2 = (a + b + 1) / 2, y2 = d;
	int x3 = b, y3 = d;

	rep(d1, 0, 100) {
		rep(d2, 0, 100) {
			rep(d3, 0, 10) {

				radi(x1, y1 - d1, x2 - d2, y2, x3, y3 - d3);
			}
		}
	}


	x1 = a, y1 = d;
	x2 = a, y2 = d;
	x3 = b, y3 = d;

	rep(d1, 0, 100) {
		rep(d2, 0, 100) {
			rep(d3, 0, 10) {
				radi(x1, y1 - d1, x2 + d2, y2, x3, y3 - d3);
			}
		}
	}


	x1 = a, y1 = c;
	x2 = a, y2 = (c + d + 1) / 2;
	x3 = a, y3 = d;

	rep(d1, 0, 100) {
		rep(d2, 0, 100) {
			rep(d3, 0, 10) {

				radi(x1 + d1, y1, x2, y2 - d2, x3 + d3, y3);
			}
		}
	}

	x1 = a, y1 = c;
	x2 = a, y2 = c;
	x3 = a, y3 = d;

	rep(d1, 0, 100) {
		rep(d2, 0, 100) {
			rep(d3, 0, 10) {

				radi(x1 + d1, y1, x2, y2 + d2, x3 + d3, y3);
			}
		}
	}

}


signed main() {
	fileRead();
	kuaidu();
	T = 1;
	cin >> T;
	while (T--) {
		cin >> a >> bb >> c >> d;

		ans = 0;
		// ans_x = 0, ans_y = 0;
		dfs(a, bb, c, d);

		rep(i, 0, 2) {
			cc(ans_x[i], ans_y[i]);
		}

	}
	return 0;
}

Problem I. 一起看很美的日落！

一个典典的树形dp，但是赛时没有时间做了，应该是有铜+的难度的。

首先我们对于每一位可以独立看待，于是每个点的权值变成了0或者1，然后经典树形dp。

设是包含了的联通块的，是联通块里0的个数，同理，是联通块大小。

然后考虑如何合并两个联通块：

dp[x] += dp[x] * g[y] + dp[y] * g[x];
dp[x] += f[x][0] * f[y][1] + f[y][0] * f[x][1];
f[x][0] += f[y][0] * g[x] + f[x][0] * g[y];
f[x][1] += f[y][1] * g[x] + f[x][1] * g[y];
g[x] += g[x] * g[y];

我觉得式子很显然，大家看了就晓得了。代码很简洁，顺手抄了个题解的取模类。

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;

int d[N], val[N];

//--------------------------------------------------------------------------------
//struct or namespace:
template<const int T>
struct ModInt {
	const static int mod = T;
	int x;

	ModInt(int x = 0) : x(x % mod) {
	}

	int val() { return x; }

	ModInt operator +(const ModInt &a) const {
		int x0 = x + a.x;
		return ModInt(x0 < mod ? x0 : x0 - mod);
	}

	ModInt operator -(const ModInt &a) const {
		int x0 = x - a.x;
		return ModInt(x0 < 0 ? x0 + mod : x0);
	}

	ModInt operator *(const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }
	ModInt operator /(const ModInt &a) const { return *this * a.inv(); }
	bool operator ==(const ModInt &a) const { return x == a.x; };
	bool operator !=(const ModInt &a) const { return x != a.x; };

	void operator +=(const ModInt &a) {
		x += a.x;
		if (x >= mod) x -= mod;
	}

	void operator -=(const ModInt &a) {
		x -= a.x;
		if (x < 0) x += mod;
	}

	void operator *=(const ModInt &a) { x = 1LL * x * a.x % mod; }
	void operator /=(const ModInt &a) { *this = *this / a; }

	friend ModInt operator +(int y, const ModInt &a) {
		int x0 = y + a.x;
		return ModInt(x0 < mod ? x0 : x0 - mod);
	}

	friend ModInt operator -(int y, const ModInt &a) {
		int x0 = y - a.x;
		return ModInt(x0 < 0 ? x0 + mod : x0);
	}

	friend ModInt operator *(int y, const ModInt &a) { return ModInt(1LL * y * a.x % mod); }
	friend ModInt operator /(int y, const ModInt &a) { return ModInt(y) / a; }
	friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x; }
	friend istream &operator>>(istream &is, ModInt &t) { return is >> t.x; }

	ModInt pow(int n) const {
		ModInt res(1), mul(x);
		while (n) {
			if (n & 1) res *= mul;
			mul *= mul;
			n >>= 1;
		}
		return res;
	}

	ModInt inv() const {
		int a = x, b = mod, u = 1, v = 0;
		while (b) {
			int t = a / b;
			a -= t * b;
			swap(a, b);
			u -= t * v;
			swap(u, v);
		}
		if (u < 0) u += mod;
		return u;
	}

};

using MI = ModInt<mod>;

MI dp[N], f[N][2], g[N];

namespace z {
	struct ED {
		int y;
		int val;
	};

	vector<ED> A[N];
	int son[N], dep[N];

	void dfs(const int x, const int pa) {
		g[x] = 1;
		dp[x] = 0;
		if (val[x] == 1) {
			f[x][1] = 1, f[x][0] = 0;
		}
		else {
			f[x][0] = 1, f[x][1] = 0;
		}
		for (auto &[y, val]: A[x]) {
			if (y == pa) continue;
			dfs(y, x);
			dp[x] += dp[x] * g[y] + dp[y] * g[x];
			dp[x] += f[x][0] * f[y][1] + f[y][0] * f[x][1];
			f[x][0] += f[y][0] * g[x] + f[x][0] * g[y];
			f[x][1] += f[y][1] * g[x] + f[x][1] * g[y];
			g[x] += g[x] * g[y];
		}
		// cc(x, f[x][1], f[x][0]);
	}

	void clear(const int &n) {
		rep(i, 1, n) {
			A[i].clear();
		}
	}

	void add(const int &x, const int &y, int c = 1) {
		A[x].push_back({y, c});
	}
};

//--------------------------------------------------------------------------------


signed main() {
	fileRead();
	kuaidu();
	T = 1;
	//cin >> T;
	while (T--) {

		cin >> n;
		z::clear(n);
		rep(i, 1, n) cin >> d[i];
		rep(i, 1, n-1) {
			int a, b;
			cin >> a >> b;
			z::add(a, b);
			z::add(b, a);
		}
		MI ans = 0;
		rep(j, 0, 31) {
			rep(i, 1, n) val[i] = (d[i] >> j) & 1;
			z::dfs(1, 0);
			rep(i, 1, n) {
				MI tem = (1ll << j);
				ans += dp[i] * tem;
			}
		}
		ans *= 2;
		cc(ans);
	}
	return 0;
}

Problem J. 数据时间？

模拟题模拟题，但是题意不明？ 因为感觉忽视了天数，常理来说应该同一个人同一个时间段不同的天数应该是算作不同的人数才对。不管了，按照题干模拟就完事了。

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
set<string> mp[3];
//--------------------------------------------------------------------------------
//struct or namespace:
void dfs(string &s, string &id) {
	// cc(s);

	int q1, q2, q3;
	string s1 = "", s2 = "", s3 = "";
	s1.push_back(s[0]);
	s1.push_back(s[1]);
	q1 = stoi(s1);

	s2.push_back(s[3]);
	s2.push_back(s[4]);
	q2 = stoi(s2);

	s3.push_back(s[6]);
	s3.push_back(s[7]);
	q3 = stoi(s3);

	// cc(q1, q2, q3);

	if (q1 < 9 and q1 >= 7 || q1 < 20 and q1 >= 18) {
		mp[0].insert(id);
		return;
	}

	if (q1 == 9 and q2 == 0 and q3 == 0) {
		mp[0].insert(id);
		return;
	}

	if (q1 == 20 and q2 == 0 and q3 == 0) {
		mp[0].insert(id);
		return;
	}

	if (q1 < 13 and q1 >= 11) {
		mp[1].insert(id);
		return;
	}

	if (q1 == 13 and q2 == 0 and q3 == 0) {
		mp[1].insert(id);
		return;
	}

	if (q1 < 24 and q1 >= 22 || q1 < 1) {
		mp[2].insert(id);
		return;
	}

	if (q1 == 1 and q2 == 0 and q3 == 0) {
		mp[2].insert(id);
		return;
	}

}

//--------------------------------------------------------------------------------

signed main() {
	fileRead();
	kuaidu();
	T = 1;
	//cin >> T;
	while (T--) {
		cin >> n;
		string ye, yue;
		cin >> ye >> yue;
		while (ye.size() < 2) ye = '0' + ye;
		while (yue.size() < 2) yue = '0' + yue;

		rep(i, 1, n) {
			string id;
			cin >> id;
			string a, b;
			cin >> a >> b;
			string ye1 = "", yue1 = "";
			rep(i, 0, 3) ye1.push_back(a[i]);
			rep(i, 5, 6) yue1.push_back(a[i]);
			// cc(ye1, yue1);
			if (ye1 != ye or yue1 != yue) continue;
			dfs(b, id);
		}
		rep(i, 0, 2) {
			cout << mp[i].size() << " ";
		}
	}
	return 0;
}

Problem K. 可以分开吗？

又是一个很臭的模拟，看个乐呵吧。

大体思路就是把每个点的上下左右以及这个点都标记，然后查询有多少个点被标记了，再减去当前联通块的点的个数。

有点容易，有一点点优化手段。在此再计算的，时间复杂度应该不会超时才对，但是由于了，于是做了一点点优化，详细看代码。

//--------------------------------------------------------------------------------
const int N = 5e2 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
int A[N][N];
bool biao[N][N];
int Q[5] = {0, 0, 1, -1};
int W[5] = {1, -1, 0, 0};
//tem数组是上述中用来记录标记的点
bool tem[N][N], lu[N][N];
//--------------------------------------------------------------------------------
//struct or namespace:

//--------------------------------------------------------------------------------

void ddd(int x,int y) {
	rep(i, 0, 3) {
		tem[x + Q[i]][y + W[i]] = 1;
	}
	tem[x][y] = 1;
}

int dfs(int x,int y) {
	queue<PII> F;
	F.push({x, y});

	int siz = 0;

	siz++;
	biao[x][y] = 1;
	tem[x][y] = 1;
	vec<PII> pa;
	pa.push_back({x, y});
	ddd(x, y);

	while (!F.empty()) {
		auto [x,y] = F.front();
		F.pop();
		// if (biao[x][y]) continue;
		for (int i = 0; i <= 3; i++) {
			int tx = x + Q[i], ty = y + W[i];
			if (tx < 1 or ty < 1 or tx > n or ty > m) continue;
			if (A[tx][ty] == 0) continue;
			if (biao[tx][ty]) continue;
			siz++;
			biao[tx][ty] = 1;
			tem[tx][ty] = 1;
			ddd(tx, ty);
			pa.push_back({tx, ty});
			F.push({tx, ty});
		}
	}
	// cc(siz);
//此处，记录下来路径的pa数组，去枚举这个而不是直接双重for循环，这样可以快一些。
	int val = 0;
	for (auto &[x,y]: pa) {
		if (tem[x][y] == 1) {
			tem[x][y] = 0;
			val++;
		}
		rep(i, 0, 3) {
			if (x + Q[i] < 1 or x + Q[i] > n) continue;
			if (y + W[i] < 1 or y + W[i] > m) continue;

			if (tem[x + Q[i]][y + W[i]]) {
				tem[x + Q[i]][y + W[i]] = 0;
				val++;
			}
		}
	}

	return val - siz;

}

signed main() {
	fileRead();
	kuaidu();
	T = 1;
	//cin >> T;
	while (T--) {
		cin >> n >> m;
		rep(i, 1, n) {
			rep(j, 1, m) {
				char a;
				cin >> a;
				A[i][j] = a - '0';
			}
		}

		int ans = INF;

		rep(i, 1, n) {
			rep(j, 1, m) {
				if (biao[i][j]) continue;
				if (A[i][j] == 0) continue;
				cmin(ans, dfs(i, j));
			}
		}
		cc(ans);
	}
	return 0;
}

Problem L. 还会再见吗？

看了题解，虚树。

于是直接再见。

学虚树不如继续搞开发。

Problem M. 那是我们的影子

赛时没有做出来，赛后看题解发现不算太难。

但是个人感觉难度应该和差不多才对。只能说这种题自己总会写的复杂，感慨大佬写的代码很简洁。

感觉官方题解写的很好很清楚，建议去看（不是自己懒了

借鉴了的代码：

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
string s[4];
int pos[10];
bool vis[N][10];
vec<int> col[3];
 
//--------------------------------------------------------------------------------
//struct or namespace:
 
//--------------------------------------------------------------------------------
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    cin >> T;
    while (T--) {
        cin >> n;
        rep(i, 0, 2) cin >> s[i];
 
        rep(j, 0, n-1) {
            rep(i, 0, 9) vis[j][i] = 0;
        }
        rep(i, 0, 2) col[i].clear();
        rep(i, 0, 9) pos[i] = -1;
        int ans = 1;
 
        rep(j, 0, n-1) {
            int tem = 0;
            rep(i, 0, 2) {
                if (s[i][j] == '?') tem++;
                else {
                    int k = s[i][j] - '0';
                    if (vis[j][k]) ans = 0;
                    vis[j][k] = 1;
 
                    if (pos[k] != -1 and pos[k] != j % 3) ans = 0;
                    pos[k] = j % 3;
 
                }
            }
            if (tem == 2) ans *= 2;
            if (tem == 3) ans *= 6;
            ans %= mod;
        }
 
        if (ans == 0) {
            cc(0);
            continue;
        }
 
        int val = 0;
        auto dfs = [&](auto &dfs,int x) {
            if (x == 10) {
                val++;
                return;
            }
            rep(i, 0, 2) {
                if (col[i].size() < 3 and (pos[x] == i or pos[x] == -1)) {
                    col[i].push_back(x);
                    dfs(dfs, x + 1);
                    col[i].pop_back();
                }
            }
        };
        dfs(dfs, 1);
        ans *= val % mod;
        ans %= mod;
        cc(ans);
 
    }
    return 0;
}
 

PostScript

只能说自己吃屎吃得太多，有些题自己写的太烂，点名批评题。

感觉难度比去年真的少了很多，不知道是不是错觉。

题解如果有误希望可以指出来。