浅谈一些（可能）有启发的题目

userId_undefined
Asdfre
时空双修者

2026-08-11 13:31:10

发布于：广东

97阅读
0回复
0点赞

[UOI 2021] 哥萨克与 GCD

模拟赛遇到的，做法非常有启发，但如果见过能很快秒的类型。

让我们先从怎么才能唯一确定一个bb数组来考虑，记Si=∑j=1ibjS_i = \sum_{j=1}^{i} {b_j}，我们询问一段区间的和，也就相当于询问了Sr−Sl−1S_r - S_{l-1}的值，而要确定bb则要∀i\forall {i}，SiS_i都是确定的。

这样我们可以做一个转化，每次询问相当于l−1l-1和rr点连一条边，最后使得nn个点是连通的。到这我们可以写一个非常暴力的MSTMST拿到前两个点的分。

进一步思考。从gcdgcd本身性质看，对于任意一个序列的前缀gcdgcd一定是单调不增的（显然好证明）。这样在询问的过程中一定是中间的点连向11或者nn点，显然最优。

怎么计算答案呢？考虑一个简单贪心，既然每个点要不连向11或者nn，贪心取一个代价最小的连显然是对的。

记Li=gcd⁡j=1iajL_i = \gcd_{j=1}^{i} {a_j}，Ri=gcd⁡j=inajR_i = \gcd_{j=i}^{n} {a_j}，
Ans=∑i=2n−1min(Li,Ri)+gcd⁡i=1naiAns = \sum_{i=2}^{n-1} {min(L_i,R_i)} + \gcd_{i=1}^{n} {a_i} 显然最后需要nn连向11有一个全局gcdgcd。

现在再考虑带修，对于单点修改，我们考虑可以用线段树维护这个东西（或许在我的做法中树状数组也可以？你们可以试一试）。每个线段树节点维护一个当前区间的gcdgcd和当前区间中每一段不同的gcdgcd值和对应的长度。

为什么这样看似暴力是对的？这就涉及到一个重要性质（或许后面考虑gcdgcd问题就遇到了呢？）：每次前缀gcdgcd改变时，值一定至少缩小一半！，所以在这题中不同的gcdgcd值在线段树节点存的必然不大于log⁡(109)≈30\log (10^9) \approx 30。当然pushuppushup也是好做的相同的合并，不同的加入。

统计答案时用双指针同时处理LL和RR即可，记得处理LL和RR边界，因为是∑i=2n−1\sum_{i=2}^{n-1}。

这样我们就做完了一道紫题。

#include <bits/stdc++.h>
using namespace std;
namespace CZW
{
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
#define PLI pair<ll,int>
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	constexpr int N=1e5+5;
	ll a[N];
	int n,q;
	struct Seg{
		ll g;
		vec<PLI> pre,suf;
#define g(rt) tr[rt].g
#define pre(rt) tr[rt].pre
#define suf(rt) tr[rt].suf
	}tr[N<<2];
	void merge(vec<PLI>& res,const vec<PLI>& r,ll G){
		for (auto& i:r){
			ll val=__gcd(G,i.first);
			if (!res.empty()&&res.back().first==val){
				res.back().second+=i.second;
			}else res.eb(val,i.second);
		}
	}
	void up(const int rt){
		g(rt)=__gcd(g(rt<<1),g(rt<<1|1));
		pre(rt)=pre(rt<<1);
		merge(pre(rt),pre(rt<<1|1),g(rt<<1));
		suf(rt)=suf(rt<<1|1);
		merge(suf(rt),suf(rt<<1),g(rt<<1|1));
	}
	void build(int rt,int l,int r){
		if (l==r){
			g(rt)=a[l];
			pre(rt)={{a[l],1}};
			suf(rt)={{a[l],1}};
			return ;
		}
		int mid=(l+r)>>1;
		build(rt<<1,l,mid);
		build(rt<<1|1,mid+1,r);
		up(rt);
	}
	void update(int rt,int l,int r,int p,ll x){
		if (l==r){
			g(rt)=x;
			pre(rt)={{x,1}};
			suf(rt)={{x,1}};
			return ;
		}
		int mid=(l+r)>>1;
		if (p<=mid) update(rt<<1,l,mid,p,x);
		else update(rt<<1|1,mid+1,r,p,x);
		up(rt);
	}
	ll get(){
		vec<PLI> L=pre(1),R=suf(1);
		reverse(R.begin(),R.end());
		--L.back().second;
		if (L.back().second==0) L.pop_back();
		--R.front().second;
		if (R.front().second==0) R.erase(R.begin());
		int sz1=L.size(),sz2=R.size(),i=0,j=0;
		ll ans=0;
		while(i<sz1&&j<sz2){
			int num=min(L[i].second,R[j].second);
			ans+=1ll*num*min(L[i].first,R[j].first);
			L[i].second-=num,R[j].second-=num;
			if (L[i].second==0) ++i;
			if (R[j].second==0) ++j;
		}
		return ans+g(1);
	}
	void Main()
	{
		cin>>n>>q;
		for (int i=1;i<=n;++i) cin>>a[i];
		build(1,1,n);
		cout<<get()<<endl;
		while(q--){
			int p; ll x;
			cin>>p>>x;
			update(1,1,n,p,x);
			cout<<get()<<endl;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int Test = 1;
//	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

P14943 浅谈矩阵乘法

一道图论建模的好题。

题意是对于一个n×nn \times n方阵AA，是否∀i,j∈[1,n]\forall {i,j \in [1,n]}且kk为任意非负整数，(Ak)i,j(A^k)_{i,j}有上限？

如果我们考虑把矩阵抽象成一个图，Ai,jA_{i,j}表示ii到jj有一条长为Ai,jA_{i,j}的有向边，而(Ak)i,j(A^k)_{i,j}表示的是从ii到jj恰好走kk步的距离，考虑到kk理论上是一个+∞+\infty的值，所以我们要判断无论从ii到jj走多少步答案不是+∞+\infty。

反向考虑什么时候会达到+∞+\infty？考虑到任意两点ii和jj对答案有影响，当且仅当i,ji,j在一个sccscc内或者有路径到达，所以我们有三种情况：
1.sccscc内权值和 >1>1，显然在kk足够大时，答案达到+∞+\infty。
2.sccscc不是一个简单环，多个环相交错，导致形成指数级路径个数，从而答案达到+∞+\infty。
3.多个满足上面条件的sccscc相连，导致多个sccscc分配步数呈线性或者多项式级增长。

前两个条件用tarjantarjan处理即可，3的话用缩点建DAGDAG跑拓扑+dpdp即可。

应该会有更好的实现吧（赛时做时实现的没用到tarjantarjan但思路一样的）。

这里给出这种做法的代码。

#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	void Main() {
		int n;
		cin >> n;
		vec<vec<int>> a(n + 2, vec<int> (n + 2, 0));
		vec<vec<pair<int, int>>> adj(n + 2);
		for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) {
				cin >> a[i][j];
				if (a[i][j]) adj[i].eb(j, a[i][j]);
			}
		int ti = 0, top = 0, scc_cnt = 0;
		vec<int> dfn(n + 2, 0), low(n + 2, 0), stk(n + 2, 0), sz(n + 2, 0), sid(n + 2, 0);
		vec<char> in(n + 2, 0);
		auto tarjan = [&](auto & self, int u) ->void{
			dfn[u] = low[u] = ++ti;
			stk[++top] = u;
			in[u] = 1;
			for (auto [v, w] : adj[u]) {
				if (!dfn[v]) {
					self(self, v);
					low[u] = min(low[u], low[v]);
				} else if (in[v]) low[u] = min(low[u], dfn[v]);
			}
			if (low[u] == dfn[u]) {
				++scc_cnt;
				while (1) {
					int tmp = stk[top];
					--top;
					in[tmp] = 0;
					sid[tmp] = scc_cnt;
					++sz[scc_cnt];
					if (tmp == u) break;
				}
			}
		};
		for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(tarjan, i);
		vec<int> edges(n + 2, 0), deg(n + 2, 0);
		vec<vec<int>> g(n + 2);
		vec<char> bad(n + 2, 0), is(n + 2, 0);
		for (int u = 1; u <= n; ++u) {
			int sc_u = sid[u];
			for (auto [v, w] : adj[u]) {
				int sc_v = sid[v];
				if (sc_u == sc_v) {
					++edges[sc_u];
					if (w > 1) bad[sc_u] = 1;
				} else {
					g[sc_u].pb(sc_v);
					++deg[sc_v];
				}
			}
		}
		bool f = true;
		for (int i = 1; i <= scc_cnt; ++i) {
			is[i] = (sz[i] > 1 || edges[i] > 0);
			if (is[i]) {
				if (sz[i] != edges[i]) {
					f = false;
					break;
				}
				if (bad[i]) {
					f = false;
					break;
				}
			}
		}
		if (!f) {
			cout << "NO" << endl;
			return ;
		}
		queue<int> q;
		vec<int> dp(n + 2, 0);
		for (int i = 1; i <= scc_cnt; ++i) {
			if (deg[i] == 0) q.push(i);
			dp[i] = (is[i] ? 1 : 0);
		}
		while (!q.empty()) {
			int uid = q.front();
			q.pop();
			for (int vid : g[uid]) {
				dp[vid] = max(dp[vid], dp[uid] + (is[vid] ? 1 : 0));
				--deg[vid];
				if (deg[vid] == 0) q.push(vid);
			}
		}
		for (int i = 1; i <= scc_cnt; ++i) if (dp[i] > 1) {
				f = false;
				break;
			}
		if (!f) {
			cout << "NO" << endl;
			return ;
		}
		cout << "YES" << endl;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int Test = 1;
	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

转圈

神秘数论题，感觉比较简单。

刚刚开始看没思路，但我们可以先用草稿纸手推一下前几次操作：

1→(m+1)→(m+1)+(m+1)m=(m+1)2→(m+1)3......1 \to (m+1) \to (m+1)+(m+1)m=(m+1)^2 \to (m+1)^3......（当然要模nn）

wow！！原来是这样，我们要求的就是：

满足(m+1)k≡1(m+1)^k \equiv 1 (mod(mod n)n)，的最小正整数kk。

然后我们发现nn为质数，所以ϕ(n)=n−1\phi {(n)}=n-1且gcd(m+1,n)=1gcd(m+1,n)=1（要特判m=n−1m=n-1）。

由欧拉定理得：(m+1)ϕ(n)≡1(m+1)^{\phi(n)} \equiv {1} (mod(mod n)n)。

当然这可能不是最小的，我们预处理出n−1n-1的质因数，从大到小试除即可，这样写最简单。

时间复杂度O(Tlog⁡2n)O(T \log^2 n)，最大只跑了800多ms。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll read() {
	ll num = 0;
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9') {
		num = num * 10 + (c - '0');
		c = getchar();
	}
	return num;
}
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ull = unsigned long long;
	using i128 = __int128;
	constexpr int N = 1e7+5;
	int primes[700005], spf[N], k;
	ll fpow(ll a, ll b, ll mod) {
		ll res = 1;
		a %= mod;
		while (b) {
			if (b & 1) res = res * a % mod;
			a = a * a % mod;
			b >>= 1;
		}
		return res;
	}
	void init() {
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
		for (int i = 2; i < N; ++i) spf[i] = i;
		for (int i = 2; i < N; ++i) {
			if (spf[i] == i) primes[++k] = i;
//			cout<<k<<endl;
			for (int j = 1; j <= k; ++j) {
				int p = primes[j];
				if (1ll * p * i > (N - 1)) break;
				spf[i * p] = p;
				if (i % p == 0) break;
			}
		}
	}
	void Main() {
		ll n = read(), m = read();
		if (m == n - 1) {
			cout << 2 << endl;
			return ;
		}
		ll tmp = n - 1, ans = n - 1;
		while (tmp > 1) {
			if (fpow(m + 1, ans / spf[tmp], n) == 1) ans /= spf[tmp];
			tmp /= spf[tmp];
		}
		cout << ans << endl;
	}
}
int main() {
//	freopen("1.in","r",stdin);
//	freopen("my.out","w",stdout);
	CZW::init();
	int Test = 1;
	Test = read();
	while (Test--)
		CZW::Main();
	return 0;
}

Sugar Sweet II

树上bfs期望题：

考虑期望递推式子：E(i)=ai+wi∗P(i)E(i) = a_i + w_i * P(i)，从中我们可以将每个 ii 分成三种人：

  • 类型0：永远都提升不了的人，即满足 ai≥abi+wbia_i \ge ab_i + wb_i 的人，所以 P(i)=0P(i) = 0。
  • 类型1：一定能提升的人，即满足 ai<abia_i < ab_i，此时 P(i)=1P(i) = 1。
  • 类型2：可能能提升的人，即满足 ai∈[abi,abi+wi]a_i \in [ab_i, ab_i + w_i]，这种需要进一步考虑。

如何处理类型2情况？

考虑到如果类型2想要提升，必须满足 posbi<posipos_{b_i} < pos_i 且 bib_i 一定提升，又因为每个人只有一个 bib_i，约束关系可以形成多条相交但互不影响的链，约束的对象不是类型2的人结束。

即：

i→x1→x2⋯→X,X∉类型2i \rightarrow x_1 \rightarrow x_2 \dots \rightarrow X, \quad X \notin \text{类型2}

分讨一下 XX 的情况

  • XX 是类型0：全链 P=0P = 0。
  • X=iX = i：导致全链关系矛盾，P=0P = 0。
  • XX 为类型1：若 ii 想提升，则一定全链是发生由后到前，呈唯一排列顺序，此时的 P(i)=1m!P(i) = \frac{1}{m!}，mm 为全链元素个数。

所以我们就可以知道，如果一个类型2点经过 dd 条边到一个类型0点，则 P(i)=1(d+1)!P(i) = \frac{1}{(d+1)!}。

这样我们就做完了。

#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	constexpr ll N = 5e5+5, mod = 1e9+7;
	ll fact[N], inv[N];
	ll fpow(ll a, ll b) {
		ll res = 1;
		a %= mod;
		while (b) {
			if (b & 1) res = res * a % mod;
			a = a * a % mod;
			b >>= 1;
		}
		return res;
	}
	void init() {
		fact[0] = 1;
		for (int i = 1; i < N; ++i) fact[i] = fact[i - 1] * i % mod;
		inv[N - 1] = fpow(fact[N - 1], mod - 2);
		for (int i = N - 2; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
	}
	void Main() {
		int n;
		cin >> n;
		vec<ll> a(n + 1, 0), w(n + 1, 0), p(n + 1, 0);
		vec<int> b(n + 1, 0), id(n + 1, -1), dis(n + 1, 0);
		vec<vec<int>> adj(n + 1);
		for (int i = 1; i <= n; ++i) cin >> a[i];
		for (int i = 1; i <= n; ++i) cin >> b[i];
		for (int i = 1; i <= n; ++i) cin >> w[i];
		for (int i = 1; i <= n; ++i) {
			if (a[i] >= a[b[i]] + w[b[i]]) id[i] = 0;
			else if (a[i] < a[b[i]]) id[i] = 1;
			else id[i] = 2;
		}
		for (int i = 1; i <= n; ++i) {
			if (id[i] == 2) {
				adj[b[i]].pb(i);
			}
		}
		queue<int> q;
		for (int i = 1; i <= n; ++i) {
			if (id[i] == 1) {
				q.push(i);
				p[i] = 1;
				dis[i] = 0;
			}
		}
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			for (int v : adj[u]) {
				dis[v] = dis[u] + 1;
				p[v] = inv[dis[v] + 1];
				q.push(v);
			}
		}
		for (int i = 1; i <= n; ++i) {
			cout << (a[i] + w[i]*p[i] % mod) % mod << (i == n ? endl : " ");
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	CZW::init();
	int Test = 1;
	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

CF2205E

首先我们得转化一下思路，题目中问有多少不同SS可以变为TT，按照翻转的性质，我们可以转化为TT可以转化为多少不同的S′S'，这样就变成了一个正向计数题。

考虑一个Str=M+B+MStr=M+B+M的问题，分两种情况：
1.rev(Str)=[M+B+M]R=rev(M)+rev(B)+rev(M)rev(Str)=[M+B+M]^R=rev(M)+rev(B)+rev(M)
2.rev(Str)=[M]R+[B]R+[M]R=rev(M)+rev(B)+rev(M)rev(Str)=[M]^R+[B]^R+[M]^R=rev(M)+rev(B)+rev(M)
所以这两种所产生的贡献是一样的，所以只有BorderlessBorderless的串才能产生贡献。

既然这样，再回看题目，长序列计数问题，最常用dpdp或者组合计数，观察数据范围，我们可以大胆猜一下用一个O(n2)O(n^2)的dpdp去解决。

dpjdp_j表示S[1...j]S[1...j]的方案数，我们可以采用推表的方法，枚举i=j+1...ni=j+1...n，用KMPKMP判断S[j....i]S[j....i]是否为BorderlessBorderless，即nxti=0nxt_i=0。再加上本身的方案数即可。

#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	void init() {
//		freopen("1.in","r",stdin);
//		freopen("my.out","w",stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
	}
	constexpr ll mod = 998244353;
	void Main() {
		int n;
		cin >> n;
		vec<int> a(n + 1, 0), nxt(n + 1, 0);
		for (int i = 1; i <= n; ++i) cin >> a[i];
		vec<ll> dp(n + 2, 0);
		dp[0] = 1;
		for (int j = 1; j <= n; ++j) {
			if (!dp[j - 1]) continue;
			dp[j] = (dp[j] + dp[j - 1]) % mod;
			nxt[1] = 0;
			int len = n - j + 1;
			for (int i = 2, k = 0; i <= len; ++i) {
				while (k && a[i + j - 1] != a[k + j]) k = nxt[k];
				if (a[i + j - 1] == a[k + j]) ++k;
				nxt[i] = k;
				if (!nxt[i]) dp[i + j - 1] = (dp[i + j - 1] + dp[j - 1]) % mod;
			}
		}
		cout << dp[n] << endl;
	}
}
int main() {
	CZW::init();
	int Test = 1;
	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

ARC191C

神秘数论脑电波题目。。。。

结论是(A,M)=(N+1,N2)(A,M)=(N+1,N^2)

ll n; cin >> n;
if (n == 1){
	cout << 114514 << ' ' << 1 << endl;
	return ;
}
cout << n + 1 << ' ' << n * n <<endl;

浅浅证明一下吧：

1.为什么可行？

(N+1)N−1=∑k=1NCNk×Nk(mod(N+1)^N-1=\sum_{k=1}^{N}{C_{N}^{k}\times N^k} (mod N2)N^2)

当k≥2k\ge 2时，NkN^k一定包含N2N^2因子，所以取模为00。

所以可以转化为(N+1)N−1=N2≡0(mod(N+1)^N-1=N^2 \equiv 0(mod N2)N^2)。

2.为什么是最小？

令1≤n<N1\le n < N，(N+1)n−1=∑k=1nCnk×Nk(mod(N+1)^n-1=\sum_{k=1}^{n}{C_{n}^{k}\times N^k}(mod N2)N^2)

根据上面结论，显然答案在模N2N^2意义下为nNnN，再看nn的范围，显然不是倍数，得证。

模拟赛的一道题

观察1h后，发现vv的值比较小，说明每个数最大贡献为10001000，当区间长度为kk的情况下，整个区间最大贡献为1000×k1000\times k
，而整个区间的子集个数为2k−12^k-1，根据鸽巢定理，如果2k−1>1000×k2^k-1>1000 \times k，所以当k≥14k\ge14，一定找出满足题意的XX和YY。

如果<14<14，用一个bitset判一下即可，位运算非常的快。

那待修也比较好想，因为有一个取模，不好直接做。用差分树状数组维护某个数立方次数，再预处理出某个数立方次数为kk对vv取模的值，这样就做完了。

#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	constexpr int M = 1005, N = 1e5 + 5;
	int n, m, v;
	int a[N];
	vec<int> p[M];
	int cur1[M], cur2[M];
	void init() {
//		freopen("4.in", "r", stdin);
//		freopen("my.out", "w", stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
	}
	namespace BIT {
		int c[N];
		void add(int i, int k) {
			while (i <= n) {
				c[i] += k;
				i += i & -i;
			}
		}
		int query(int i) {
			int res = 0;
			while (i > 0) {
				res += c[i];
				i -= i & -i;
			}
			return res;
		}
	}
	bool chk(const vec<int>& b) {
		bitset<14000> bt;
		bt[0] = 1;
		for (int i : b) {
			if ((bt & (bt << i)).any()) {
				return true;
			}
			bt |= bt << i;
		}
		return false;
	}
	void Main() {
		cin >> n >> m >> v;
		for (int  i = 1 ; i <= n ; ++i ) cin >> a[i];
		for (int i = 0; i < v ; ++i) {
			vec<int> vis(v, -1);
			int cur = i;
			while (vis[cur] == -1) {
				vis[cur] = (int)p[i].size();
				p[i].pb(cur);
				cur = 1ll * cur * cur % v * cur % v;
			}
			cur1[i] = vis[cur], cur2[i] = (int)p[i].size() - cur1[i];
		}
		auto get = [&](int x, int k)->int{
			if (k < (int)p[x].size()) return p[x][k];
			int rem = k - (int)p[x].size();
			return p[x][cur1[x] + rem % cur2[x]];
		};
		while (m -- ) {
			int op, l, r;
			cin >> op >> l >> r;
			if (op == 2) {
				BIT::add(l, 1);
				BIT::add(r + 1, -1);
			} else {
				if (r - l + 1 >= 14) {
					cout << "Yes" << endl;
					continue;
				}
				vec<int> num;
				for (int i = l ; i <= r; ++i) {
					int k = BIT::query(i);
					num.pb(get(a[i], k) +1);
				}
				if (chk(num)) cout << "Yes" << endl;
				else cout << "No" << endl;
			}
		}
	}
}
int main() {
	CZW::init();
	int Test = 1;
//	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

持续更新中........

userId_undefined
去预览
0/2000

全部评论 12

  • userId_undefined
    Asdfre
    时空双修者
    置顶

    当然这些题难度都不会特别大，因为本人很蒻（悲

    2026-08-01 来自 广东

    1
    • userId_undefined
      🥥
      回复
      Asdfre

      P话s are forbidden in AIGO.

      2026-08-04 来自 上海

      1
    • userId_undefined
      cjdst
      回复
      Asdfre

      你好强，你要 AK NOI 了

      1周前 来自 浙江

      0
  • userId_undefined
    Xylophone
    传道者

    广东 OIer 夯爆了

    2026-07-30 来自 广东

    2
    • userId_undefined
      Asdfre
      回复
      Xylophone

      您比我强

      2026-07-30 来自 广东

      0
    • userId_undefined
      Xylophone
      回复
      Asdfre

      您比我强，我比您强，左脚踩右脚，你我兄弟其上焉有一合之敌

      2026-07-30 来自 广东

      3
  • userId_undefined
    Eucatastrophe‌
    禁言
    GESP6级

    前 缀 和 好 题

    2026-07-30 来自 浙江

    2
  • userId_undefined
    Xylophone
    传道者

    啊？我第一题的想法是波鲁乌卡求 MST，每次合并时由于区间 gcd 特性只用一个数组维护每个元素到左右一个联通块外元素最近点然后计算合并即可，修改时由于性质不变再计算一下就行了（求大佬看看，感觉完全没有前途（不是

    2026-08-01 来自 广东

    1
    • userId_undefined
      Xylophone
      回复
      Xylophone

      sorry 说错了应该反过来，这样每个联通块只考虑左右端点，反而还更快了（大雾

      2026-08-01 来自 广东

      1
    • userId_undefined
      Xylophone
      回复
      Xylophone

      这样是单 log⁡\log ？@Asdfre

      2026-08-01 来自 广东

      1
    • userId_undefined
      Xylophone
      回复
      Xylophone

      卧槽答案有影响，倒闭了/ll

      2026-08-01 来自 广东

      1
  • userId_undefined
    🥥
    尊贵铂金

    前 缀 和 好 题 但是我被骗了还真去做了（然后我一晚上就废了）

    2026-07-31 来自 上海

    1
  • userId_undefined
    prediction
    秩序白银

    初识暴力枚举

    浅谈暴力枚举好题。

    这题一看没有思路，哇是红题，听别人说写出来一道就能拿图灵奖的那种，我要试试。

    哎发现了！我们好像可以用很厉害的fro 循环！天啊，我们来验证一下：哎，为啥我不会，算了，先这样写，我要翻翻iowiik看看咋写...okok！终于写出来了，接下来...天啊是不是判断啊，我记得好像算法竞赛里有个叫什么fi的东西，啊啊啊不是是if，对！看我写一个！接下来...不会吧，难道说写完了？好像是的，交一下。

    妈呀过了，我的图灵奖呢？？？

    #include <iostream>
using namespace syh;
int main()
{
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++) 
        {
            if(i%3==0&&i%5!=0) cout<<i<<'\n';
        }
}
//哦耶我的代码过了！！！
//庆祝

    2026-07-30 来自 浙江

    1
  • userId_undefined
    prediction
    秩序白银

    大佬您到底还有多少期没发...

    2026-07-30 来自 浙江

    1
    • userId_undefined
      🥥
      回复
      prediction

      注意到你GO大佬越来越多了

      2026-08-05 来自 上海

      0
  • userId_undefined
    cjdst
    禁言
    小有名气尊贵铂金CSP-S一等奖

    好的，我用一个最生活的例子给你讲明白。

    1. 先看个“笨办法”

    假设你是一个老师，班里同学排成一排，每个同学手里拿着一张扑克牌，点数分别是：[3, 1, 4, 1, 5]。

    这时候校长问你：“前3个同学手里的点数总和是多少？”
    你算一下：3+1+4 = 8，轻松答出。

    校长又问：“第2个到第4个同学的总和是多少？”
    你算一下：1+4+1 = 6，也算出来了。

    但如果校长连续问你100遍，每次问不同的区间（比如第3到第5，第1到第4），你每次都得从头一个一个加起来算，是不是累死了？这就是笨办法，每次都要重新循环加一遍。

    2. 前缀和是什么？——“记账本”思维

    前缀和，就是提前把“从开头到当前位置”的总数记在一个小本本上。

    还拿 [3, 1, 4, 1, 5] 举例，我们拿出一个新本子（前缀和数组），记下：

    • 第0位：先写个 0（代表还没开始加）。
    • 第1位（前1个和）：0 + 3 = 3
    • 第2位（前2个和）：3 + 1 = 4
    • 第3位（前3个和）：4 + 4 = 8
    • 第4位（前4个和）：8 + 1 = 9
    • 第5位（前5个和）：9 + 5 = 14

    所以这个“记账本”就是：[0, 3, 4, 8, 9, 14]

    3. 有了这个本子，怎么快速答题？

    记住一个万能口诀：“要求哪一段，就用大数减小数”。

    • 校长问：“前3个总和是多少？”
      看本子第3位：8（直接拿出来，不用算）。

    • 校长问：“第2个到第4个（1+4+1）总和是多少？”
      那就是 本子第4位 减去 本子第1位。
      计算：9 - 3 = 6。完美，一秒出答案！

    为什么？ 因为“前4个总和（9）”减去“前1个总和（3）”，剩下的正好是第2、3、4个的和。

    4. 总结三个要点

    1. 本质：空间换时间。多花一点内存存“记账本”，但换来了飞快的查询速度。
    2. 核心操作：预处理时，每一项都是 前一项 + 当前数。
    3. 最大的好处：当你需要反复、多次求不同区间的和时，用前缀和只需要做一次减法，而不用每次都循环累加。数据量越大，它比笨办法快得越离谱（从 O(n) 变成 O(1)）。

    5. 一个生活联想

    就像你每月的花销。不记账的话，你想知道“3月到8月花了多少钱”，得把每月账单翻出来加一遍。
    前缀和就是你每个月都记一笔“今年到目前为止一共花了多少钱”。那么想查任意两个月份之间的开销，直接拿“截止到8月的总数”减去“截止到2月的总数”就行了，省时省力！

    2026-07-30 来自 广东

    1
    • userId_undefined
      Xylophone
      回复
      cjdst

      就像你每月的花销。不记账的话，你想知道“3月到8月花了多少钱”，得把每月账单翻出来加一遍。
      剪枝就是你每个月都记得“我早就没有钱了”。那么想查任意两个月份之间的开销，直接拿“0”减去“0”就行了，省时省力！

      2026-07-30 来自 广东

      0
    • userId_undefined
      Eucatastrophe‌
      回复
      cjdst

      2040 年洛谷前缀和文章 belike

      2026-07-30 来自 浙江

      0
  • userId_undefined
    Xylophone
    传道者

    我要米浴的数据结构课（在地上打滚大叫

    2026-08-01 来自 广东

    0
  • userId_undefined
    cjdst
    禁言
    小有名气尊贵铂金CSP-S一等奖

    你咋会这么多

    2026-07-31 来自 广东

    0
    • userId_undefined
      cjdst
      回复
      cjdst

      哦不不不我无疑是拜谢的

      2026-07-31 来自 广东

      1
    • userId_undefined
      Asdfre
      回复
      cjdst

      /bx

      2026-07-31 来自 广东

      0
  • userId_undefined
    cjdst
    禁言
    小有名气尊贵铂金CSP-S一等奖

    不应该是 Sr−Sl−1S_r-S_{l-1} 吗/yiw

    2026-07-30 来自 广东

    0
    • userId_undefined
      Asdfre
      回复
      cjdst

      打错了。。

      2026-07-30 来自 广东

      0
  • userId_undefined
    Asdfre
    时空双修者

    d

    2026-07-29 来自 广东

    0

热门讨论