26杭电暑期第九场贪心|bitset|分层图DP|线性基|笛卡尔树|KMP|随机哈希|博弈|随机游走|二位数点|分类讨论

Maxwell_Newton

165人浏览 · 2026-08-22 20:40:00

Maxwell_Newton · 2026-08-22 20:40:00 发布

1001

贪心

n个商品，如果一个商品价格超过当前钱的一半，则不会买。问至少准备多少钱，才能买下所有商品，并且商品购买顺序不确定。

显然最贵的商品，最可能超过剩余钱的一半，导致买不了。并且如果所有商品价格一样，最后一个买的商品，前面已经花的钱最多，剩余钱最少，最可能超过钱的一半，导致买不了。综合一下，越贵，越靠后的越可能买不了。

最严格的条件是：最贵的东西最后一个买，如果这个情况钱都够，前面的也都够。要满足这个条件，至少准备 $∑ai+max⁡(ai)\sum a_i+\max(a_i)$ 实际上就够了。

void solve() {
	int n;
	cin >> n;
	int sum = 0, mx = 0;
	rep(i, 1, n) {
		int x;
		cin >> x;
		sum += x;
		mx = max(mx, x);
	}

	cout << sum + mx << '\n';
}

1003

bitset 分层图最短路 DP

一个路径的邻域定义为这个路径所有点，加上路径所有点的邻居。问从s到t的最短路中，邻域最小多小，达到这个最小值的路径有多少个。

首先只用考虑在最短路上的边，这很好做。分别从s,t出发跑最短路，枚举所有边，如果一个边 $(u, v, w)$ 满足 $d_s(u)+d_t(v)+w=最短路$ ，则这条边在最短路上。
所有在最短路上的点，根据到s的距离，实际上构成了一个分层图，第i层只和i-1,i+1之间存在边。并且i层的一个点，只会和i-2,i-1,i+1,i+2这几层的邻域有交点，可以这样考虑：如果和i-3层的邻域有交点，那么i-3层经过这个交点中转，可以到第i层，那么i-3层和i层之间应该只隔了一层！，但实际隔了两层，矛盾。

于是可以定义 $d p (a, b)$ 表示在这个分层图上，向下移动形成一条路径，最后两个点是a,b，的最小邻域大小。为了维护方案数，还可以再维护另一个cnt数组 $c n t (a, b)$ 表示分层图上一条向下的路径，最后两个点是a,b，邻域大小最小的方案数。

转移时移动到下一层的一个点c，c在i层的话,a,b分别在i-2,i-1层，那么c对邻域大小的贡献，应该是c的邻域，删掉路径上在其他点的邻域后的大小。根据前面的分析，和c的邻域有交集的，只有前两层的a,b两点，于是c对邻域大小的贡献就是 $∣Cc∖(Ca∪Cb)∣\left|C_c\setminus(C_a\cup C_b)\right|$ ， $C_x$ 是x的邻域集合。

维护最小值的同时，维护最小值方案数是简单的这里不细说了。这个转移难点在于求 $∣Cc∖(Ca∪Cb)∣\left|C_c\setminus(C_a\cup C_b)\right|$ 这个集合的大小。朴素做法是枚举a,b,c的邻居，更新set，这个dp状态数 $O(n^2)$ ，每个状态可能的转移有 $O (n)$ 个（因为b的邻居c可能有 $O (n)$ 个），整体复杂度已经 $O(n^3)$ 了，转移必须很快，复杂度应该小于 $O (n)$ 。

注意这里我们只关系几个集合取并，做差后的大小，那么可以用一个bitset表示一个点的邻域集合，这样可以支持集合取并，做差，查询集合大小，并且复杂度只有 $O (n / w)$ 。注意开始需要设置每个点的邻域集合，要把点本身和它的邻居放进去，这里的邻居不是分层图上的，是原始图上所有邻居。

整体复杂度 $O(n^4/w)$

void solve() {
	int n, m, s, t;
	cin >> n >> m >> s >> t;

	vvi g(n + 1);
	rep(i, 1, m) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	vi ds(n + 1, inf);
	queue<int>q;
	q.push(s);
	ds[s] = 0;

	while (q.size()) {
		int u = q.front();
		q.pop();

		for (int v : g[u]) {
			if (ds[u] + 1 < ds[v]) {
				ds[v] = ds[u] + 1;
				q.push(v);
			}
		}
	}

	vi dt(n + 1, inf);
	q = queue<int>();
	q.push(t);
	dt[t] = 0;

	while (q.size()) {
		int u = q.front();
		q.pop();

		for (int v : g[u]) {
			if (dt[u] + 1 < dt[v]) {
				dt[v] = dt[u] + 1;
				q.push(v);
			}
		}
	}

	vvi e(n + 1, vi(n + 1));
	vi vis(n + 1);
	rep(i, 1, n) {
		for (int j : g[i]) {
			if (ds[i] + dt[j] + 1 == ds[t]) {
				e[i][j] = e[j][i] = 1;
				vis[i] = vis[j] = 1;
			}
		}
	}

	int mx = ds[t];
	vvi layer(mx + 1);

	vector<bitset<505>>st(n + 1);
	rep(i, 1, n) {
		if (vis[i]) {
			layer[ds[i]].push_back(i);
			for (int j : g[i]) {
				st[i][j] = 1;
			}
			st[i][i] = 1;
		}
	}

	vvi dp(n + 1, vi(n + 1, inf));
	vvi cnt(n + 1, vi(n + 1));
	for (int a : layer[0]) {
		for (int b : layer[1]) {
			if (!e[a][b]) continue;
			int val = (st[a] | st[b]).count();
			dp[a][b] = val;
			cnt[a][b] = 1;
		}
	}

	rep(i, 2, mx) {
		for (int a : layer[i - 2]) {
			for (int b : layer[i - 1]) {
				if (!e[a][b]) continue;
				for (int c : layer[i]) {
					if (!e[b][c]) continue;
					int add = (st[c] & (~(st[a] | st[b]))).count();
					if (dp[a][b] + add < dp[b][c]) {
						dp[b][c] = dp[a][b] + add;
						cnt[b][c] = cnt[a][b];
					} else if (dp[b][c] == dp[a][b] + add) {
						cnt[b][c] += cnt[a][b];
						cnt[b][c] %= M2;
					}
				}
			}
		}
	}

	int mn = inf, ans = 0;
	for (int a : layer[mx - 1]) {
		for (int b : layer[mx]) {
			if (!e[a][b]) continue;
			if (dp[a][b] < mn) {
				mn = dp[a][b];
				ans = cnt[a][b];
			} else if (dp[a][b] == mn) {
				ans += cnt[a][b];
				ans %= M2;
			}
//			cout << a << ' ' << b << ' ' << ans << ' ' << mn << '\n';
		}
	}
	cout << mn << ' ' << ans << '\n';
}

1004

线性基

一个数组a，一个和a长度相同的01序列b，初始全0，每次操作可以在b上选一个长度k的子区间取反。每次询问给一个x，问任意次操作后， $(⊕i=1naibi)⊕x(\oplus_{i=1}^n a_ib_i)\oplus x$ 的最大值

注意到 $⊕i=1naibi\oplus_{i=1}^n a_ib_i$ 这部分，在 $b_i=0/1$ 可以任取时，类似于一个线性基可表示的数字集合，查询它异或上x的最大值，就是个线性基最大值查询。

关键是维护这个线性基，每次操作可以选一个长度k的子区间，全部取反，那么实际上这个线性基内的元素就是 $⊕i=1kai,⊕i=2k+1ai...⊕i=n−k+1nai\oplus_{i=1}^k a_i,\oplus_{i=2}^{k+1} a_i...\oplus_{i=n-k+1}^n a_i$ 这些元素。

把这些元素插入线性基后，正常查询即可。插入这些元素可以使用异或前缀和或者滑窗。

class LinearBasis {
	private:
		static const int MN = 63;
		long long a[MN + 1], tmp[MN + 1];
		int sz;
		bool flag;

	public:
		LinearBasis() : sz(0), flag(false) {
			memset(a, 0, sizeof(a));
			memset(tmp, 0, sizeof(tmp));
		}

		bool insert(long long x) {
			for (int i = MN; i >= 0; i--) {
				if (x & (1LL << i)) {
					if (!a[i]) {
						a[i] = x;
						sz++;
						return 1;
					}
					x ^= a[i];
				}
			}
			flag = true;
			return 0;
		}

		bool check(long long x) {
			for (int i = MN; i >= 0; i--) {
				if (x & (1LL << i)) {
					if (!a[i]) return false;
					x ^= a[i];
				}
			}
			return true;
		}

		long long queryMax(long long res = 0) {
			for (int i = MN; i >= 0; i--) {
				res = max(res, res ^ a[i]);
			}
			return res;
		}

} lb;
void solve() {
	int n, len, q;
	cin >> n >> len >> q;

	vi sum(n + 1);
	rep(i, 1, n) {
		int x;
		cin >> x;
		sum[i] = sum[i - 1] ^ x;
	}

	LinearBasis lb;
	rep(i, len, n) {
		lb.insert(sum[i]^sum[i - len]);
	}

	rep(i, 1, q) {
		int x;
		cin >> x;
		cout << lb.queryMax(x) << '\n';
	}

}

1005

笛卡尔树 KMP 单调栈

问对于每个前缀 $[1, i]$ ，满足 $[1, j] [i - j + 1, i]$ 这两个区间构建的小根笛卡尔树形态相同的最大 $j$ 是多少。注意是形态相同，就是树的拓扑相同，不是节点权值相同。

注意到，这个问题类似于求每个前缀的最长公共前后缀，这可以KMP。但是KMP是字符串匹配，这里的匹配条件是什么？

回顾笛卡尔树的构建过程，


// stk 维护笛卡尔树中节点对应到序列中的下标
for (int i = 1; i <= n; i++) {
  int k = top;  // top 表示操作前的栈顶，k 表示当前栈顶
  while (k > 0 && w[stk[k]] > w[i]) k--;  // 维护右链上的节点
  if (k) rs[stk[k]] = i;  // 栈顶元素.右儿子 := 当前元素
  if (k < top) ls[i] = stk[k + 1];  // 当前元素.左儿子 := 上一个被弹出的元素
  stk[++k] = i;                     // 当前元素入栈
  top = k;
}

实际上决定笛卡尔树形态的，只有每个点插入时的这个while退栈，会执行多少次，这构成一个数组 $p r e$ ， $pre_i$ 表示 $a_i$ 会退栈多少次，或者会退栈到序列中第几个元素。如果两个序列的 $p r e$ 数组完全相同，即使值不同，构建的笛卡尔树也是相同的。

这里 $pre_i$ 显然就是 $a_i$ 往左走，第一个不大于 $a_i$ 的元素位置。这可以单调栈 $O (n)$ 计算。

然后把 $k m p$ 的匹配条件，从 $s [j + 1] = s [i]$ ，改成 $i-pre_i=j-pre_j$ 即可，这表示的就是 $i, j$ 两个位置，在建笛卡尔树时需要退栈的次数相等。

注意边界情况，i,j如果左侧都没有更小元素了，单调栈跑出来的 $pre_i,jpre_j$ 应该都是0，也是可以的。此外可能 $[1, j]$ 内的 $a_x$ 左侧没有更小的，但是 $[i - j + 1, j]$ 内的 $a_y$ ，左侧有更小的，但不在 $[i - j + 1, i]$ 的范围内，这同样视为左侧没有更小的。具体看check函数内的判断

注意这里套的是1base的kmp模板，已匹配前缀长度为p，那么接下来应该检查 $(p + 1, i)$ 是否匹配。

void solve() {
	int n;
	cin >> n;
	vi a(n + 1);
	rep(i, 1, n) {
		cin >> a[i];
	}

	vi pre(n + 1);
	stack<int>s;
	rep(i, 1, n) {
		while (s.size() && a[s.top()] > a[i]) {
			s.pop();
		}
		if (s.size()) {
			pre[i] = s.top();
		}
		s.push(i);
	}

	vi f(n + 1);
	f[1] = 0;

	auto check = [&](int i, int j)->bool{
		if (pre[j] == 0 && (pre[i] == 0 || pre[i] < i - j)) {
			return 1;
		} else {
			return i - pre[i] == j - pre[j];
		}
	};
	int p = 0;
	rep(i, 2, n) {
		while (p && !check(i, p + 1)) {
			p = f[p];
		}
		if (check(i, p + 1)) {
			p++;
		}
		f[i] = p;
	}

	rep(i, 1, n) {
		cout << f[i] << ' ';
	}
	cout << '\n';
}

1007

随机哈希树状数组

每个物品有两种属性x,c。两类操作：

单点修改
询问区间内，是否每个x的所有k种c出现次数相等

如果 $n, q = 2 e 5$ ，这题可以带修莫队，复杂度 $O(n53)O(n^\frac53)$ 。对于每种x，维护一个cnt数组记录每种c的出现次数，以及一个变量维护c的值有几种，只有一种时这个x合法。对于每个x都要满足，那么再维护一个变量，记录满足条件的x的个数。

但这题数据量 $n, q = 2 e 6$ ，莫队直接废了。而莫队其实已经是最快的确定性算法了。想要更快，就得用随机化乱搞了。

其实这个问题是经典随机化问题，问一个区间内k种元素出现次数是否相等，考虑随机哈希，把每种元素映射到一个随机值，并且第k种元素的哈希值，是前k-1种元素哈希值之和的相反数。这样如果所有k种元素都出现一次，他们的哈希值之和就是0，如果所有k种元素出现次数都相等，哈希值之和仍然是0。对于每一种x的k种值，都分别这样哈希，树状数组维护元素哈希值，查询区间哈希值之和是否为0，即可判断区间内是否对每个x，k种元素出现次数都相等。

注意x种类是 $O (n)$ 的，如果开始对于n*k种元素全部给一个哈希值，复杂度是 $O (nk)$ ，n,k同阶，那么是 $O(n^2)$ 的，太慢了。考虑动态哈希，也就是查询到一个元素时，如果这个元素哈希值被缓存了则直接返回，如果没有哈希值，再现场哈希并缓存。这样总的哈希次数是 $O (n + q)$ 的。

哈希时，为了保证每个x的k种元素，哈希值之和为0。维护一下当前x已经出现的不同c种类数，以及这些k的哈希值之和，前k-1种c的哈希值，都使用随机数。当出现第k种c时，哈希值不使用随机数，而是前k-1种哈希值之和的相反数。

为了保证足够的随机性，使用mt19937随机数生成器，并使用当前时间作为种子。

mt19937_64 rnd(
	chrono::steady_clock::now().time_since_epoch().count()
);
void solve() {
	int n, m, k;
	cin >> n >> m >> k;

	vi a(n + 1), b(n + 1);
	rep(i, 1, n) {
		cin >> a[i];
	}
	rep(i, 1, n) {
		cin >> b[i];
	}

	map<pii, int>mp;
	unordered_map<int, unordered_set<int>>st;
	unordered_map<int, int>sum;
	auto get = [&](int x, int c)->int{
		if (mp.count({x, c})) {
			return mp[ {x, c}];
		}
		if (st[x].size() == k - 1 && !st[x].count(c)) {
			st[x].insert(c);
			return mp[ {x, c}] = -sum[x];
		}
		int v = rnd();
		sum[x] += v;
		st[x].insert(c);
		return mp[{x, c}] = v;
	};

	FenwickTree tr(n + 10);

	rep(i, 1, n) {
		tr.update(i, get(a[i], b[i]));
	}
	rep(i, 1, m) {
		int op;
		cin >> op;
		if (op == 1) {
			int p, x, c;
			cin >> p >> x >> c;
			int v = get(a[p], b[p]);
			int nv = get(x, c);
			tr.update(p, nv - v);
			a[p] = x;
			b[p] = c;
		} else {
			int l, r;
			cin >> l >> r;
			int sum = tr.rangeQuery(l, r);
			if (sum == 0) {
				cout << "YES\n";
			} else {
				cout << "NO\n";
			}
		}
	}
}

1011

博弈随机游走概率

先手在树上选一个叶子，后手看到先手操作后，也选一个叶子。一个人从根也就是1号点出发随机游走，走到先手选的叶子就是先手赢，走到后手的叶子则是后手赢，问双方都最优操作下，先手赢的概率？

假设先手后手分别选了叶子u,v。那么实际上，由于随机游走是无后效性的，我们只用考虑路径 $(u, v)$ 这条链上的点，从链上点随机游走到树上其他点，再回到链上出发点，不管中间怎么走的，对结果概率仍然无影响。甚至在链上怎么走的也没有影响，唯一有影响的是当前位于链上哪个点。那么考虑第一次进入这个链时位于哪个点，根据这个点在链上的位置就能确定答案。

第一次进入路径 $(u, v)$ 处于的点显然是 $l c a (u, v)$ ，那么问题转化为，一个链，当前起点距离左端点x，距离右端点y，问随机游走，第一个到达的端点是左端点的概率？

这可以手玩，找规律。由于这是个马尔可夫过程，概率肯定收敛，也可以模拟一定轮数，计算概率，观察收敛值大概多少。这也是一维随机游走的经典结论，可以记住。总之答案就是 $yx+y\frac{y}{x+y}$ ，这样比较符合常理，如果x小于y，那么游走到左端点的概率应该更大，更具体来说，游走到一个点的概率，和起点到这个点的距离成反比。

有了这个结论，如果两人选择的叶子是确定的，答案也就确定了。枚举全部 $O(n^2)$ 个叶子，复杂度也可以接受，可以在 $O(log⁡n)O(\log n)$ 甚至 $O (1)$ 内计算出 $l c a$ ，然后就可以 $O (1)$ 计算答案了。 $O (1)$ 确定 $l c a$ 是因为这题允许 $O(n^2)$ ，可以先类似启发式合并，在dfs过程中以 $O(nlog⁡n)O(n\log n)$ 或 $O(n^2)$ 的复杂度计预处理出任意两点的 $l c a$

考虑这还是个博弈，因此不能随便枚举 $O(n^2)$ 个叶子对，后手会根据显瘦的选择，选择对自己最优的叶子，这实际上是个minmax博弈。那么实际应该外层枚举先手的选择，内层枚举后手的选择，我们维护的答案是先手胜率，那么先手想让他尽量大，后手想让他尽量小，内层循环应该维护最小胜率，外层循环应该枚举最大胜率。

并且这题要输出模意义下分数，不能用浮点，但又要比较大小，取模分数无法比较大小。考虑使用一个分数类，保存整型的分子分母，并且定义一个比较大小的函数。

实际上这题的数据有点炸骗。手玩或者分析可以发现，先手最优的选择一定是深度最小的叶子，只需要一层循环，枚举后手选哪个叶子即可，枚举量可以降低到 $O (n)$ ，考虑 $l c a$ 的计算，整体复杂度可以降低到 $O(nlog⁡n)O(n\log n)$

以下代码是一个 $O(n^2)$ 枚举的实现

struct frac {
	int p, q;
};
void solve() {
	int n;
	cin >> n;

	vi INV(2 * n + 10);
	rep1(i, 2 * n, 1) {
		INV[i] = inv(i, M2);
	}

	vvi g(n + 1);
	rep(i, 1, n - 1) {
		int u, v;
		cin >> u >> v;

		g[u].push_back(v);
		g[v].push_back(u);
	}

	vvi s(n + 1);

	vvi lca(n + 1, vi(n + 1));
	vi d(n + 1);
	auto &&dfs = [&](auto &&dfs, int u, int f)->void{
		for (int v : g[u]) {
			if (v == f)continue;
			d[v] = d[u] + 1;
			dfs(dfs, v, u);

			for (int x : s[v]) {
				for (int y : s[u]) {
					lca[x][y] = lca[y][x] = u;
				}
			}
			for (int x : s[v]) {
				s[u].push_back(x);
			}
		}

		for (int x : s[u]) {
			lca[x][u] = lca[u][x] = u;
		}
		s[u].push_back(u);
	};
	dfs(dfs, 1, 0);


	auto les = [](frac a, frac b)->bool{
		return a.p * b.q < b.p * a.q;
	};
	frac mx;
	mx.p = 0;
	mx.q = 1;

	rep(i, 2, n) {
		if (g[i].size() != 1)continue;
		frac mn;
		mn.p = mn.q = 2;
		rep(j, 2, n) {
			if (i == j)continue;
			if (g[j].size() != 1)continue;
			int l = lca[i][j];
			int d1 = d[i] - d[l];
			int d2 = d[j] - d[l];

			frac t;
			t.p = d2;
			t.q = d1 + d2;
			if (les(t, mn)) {
				mn = t;
			}
		}
		if (mn.p == 2 && mn.q == 2) {
			continue;
		}
		if (les(mx, mn)) {
			mx = mn;
		}
//		cout << i << ' ' << mx.p << ' ' << mx.q << '\n';
	}



//	cout << mx.p << ' ' << mx.q << ' ';
	cout << mx.p*INV[mx.q] % M2 << '\n';
//	cout << mx.p*inv(mx.q, M2) % M2 << '\n';

}

1012

树状数组二位数点分类讨论推式子

数组权值定义为 $f(a)=∑i=1n−1(ai−ai+1)2f(a)=\sum_{i=1}^{n-1}(a_i-a_{i+1})^2$ 。可以交换一组元素 $a_i,a_j)$ 。问有多少种交换方法，交换后权值变大。

显然一个 $a_i$ 只能和相邻的两个元素 $a_{i-1},a_{i+1}$ 产生贡献，交换 $a_i,a_j$ ，可以 $O (1)$ 计算出权值改变量

接下来需要分类讨论，因为 $a_i,a_j$ 的相邻元素，可能有重合，以及可能位于边界根本没有相邻元素

最一般的情况，不位于边界， $a_{i-1},a_{i+1},a_{j-1},a_{j+1}$ 都存在，且没有重合。把 $f (A^{'}) > f (A)$ 完全展开，可以得到 $i, j$ 交换后变大，等价于 $ai<aja_i\lt a_j$ 且 $ai−1+ai+1<aj−1+aj+1a_{i-1}+a_{i+1}\lt a_{j-1}+a_{j+1}$ ，可以转化为二位数点，这是简单的，扫描线+树状数组即可，这里的 $i, j$ 都属于 $[2, n - 1]$
一种边界是 $i = 1, i = n$ ，只有一侧有相邻元素，但这样的点对只有 $O (n)$ 个，可以全部暴力，两次循环，第一次枚举 $i = 1, j = [2, n - 1]$ ，第二次枚举 $i = n, j = [2, n - 1]$ ，最后还有一个 $i = 1, j = n$
另一种边界是 $j = i + 1$ ，原来的式子不成立了，但仍然只有 $O (n)$ 对，考虑直接暴力。问题是第一种情况的二位数点，也会错误地计算这种情况，因此既然我们把这种情况独立出来算了，为了不重不漏，应该在第一种二位数点里排除这种情况。具体来说，二维数点查询点 $i$ 的答案时，临时把 $i - 1, i + 1$ 的点从树状数组中删掉，查询完了再加回来。

void solve() {
	int n;
	cin >> n;
	vi a(n + 10);
	int mx = 0;
	rep(i, 1, n) {
		cin >> a[i];
		mx = max(mx, a[i]);
	}

	if (n == 1) {
		cout << 0 << '\n';
		return;
	}

	auto f = [&](int x, int y, int z)->int{
		return (a[y] - a[x]) * (a[y] - a[x]) + (a[y] - a[z]) * (a[y] - a[z]);
	};
	int ans = 0;


	//abc def

	vvi bin(mx + 10);
	vi b(n + 1);
	rep(i, 2, n - 1) {
		b[i] = a[i - 1] + a[i + 1];
		bin[a[i]].push_back(i);
	}


	FenwickTree tr(2 * mx + 10);
	rep(i, 1, mx) {
		if (!bin[i].size()) {
			continue;
		}

		for (int id : bin[i]) {
			int v = b[id];
			if (v - 1 >= 1) {
				if (id - 1 >= 2) {
					if (a[id - 1] < i) {
						tr.update(b[id - 1], -1);
					}
				}
				if (id + 1 <= n - 1) {
					if (a[id + 1] < i) {
//						cout << "del:" << i << ' ' << id + 1 << ' ' << b[id + 1] << '\n';
						tr.update(b[id + 1], -1);
					}
				}
//				cout << "ans:" << i << ' ' << tr.query(v - 1) << '\n';
				ans += tr.query(v - 1);
				if (id - 1 >= 2) {
					if (a[id - 1] < i) {
						tr.update(b[id - 1], 1);
					}
				}
				if (id + 1 <= n - 1) {
					if (a[id + 1] < i) {
						tr.update(b[id + 1], 1);
					}
				}
			}
		}

		for (int id : bin[i]) {
//			cout << "add:" << i << ' ' << id << ' ' << b[id] << '\n';
			tr.update(b[id], 1);
		}
	}
//	cout << ans << ' ';

	rep(i, 2, n - 1) {
		//f(a)>=f(a')
		int v1 = (a[1] - a[2]) * (a[1] - a[2]) + f(i - 1, i, i + 1);
		swap(a[1], a[i]);
		int v2 = (a[1] - a[2]) * (a[1] - a[2]) + f(i - 1, i, i + 1);;
		swap(a[1], a[i]);
//		cout<<i<<' '<<v1<<' '<<v2<<'\n';
		if (v2 > v1) {
			ans++;
		}
	}
//	cout << ans << ' ';

	rep(i, 2, n - 1) {
		//f(a)>=f(a')
		int v1 = (a[n] - a[n - 1]) * (a[n] - a[n - 1]) + f(i - 1, i, i + 1);
		swap(a[n], a[i]);
		int v2 = (a[n] - a[n - 1]) * (a[n] - a[n - 1]) + f(i - 1, i, i + 1);
		swap(a[n], a[i]);
//		cout<<i<<' '<<v1<<' '<<v2<<'\n';
		if (v2 > v1) {
			ans++;
		}
	}
//	cout << ans << ' ';


	int v1 = (a[1] - a[2]) * (a[1] - a[2]) + (a[n] - a[n - 1]) * (a[n] - a[n - 1]);
	swap(a[1], a[n]);
	int v2 = (a[1] - a[2]) * (a[1] - a[2]) + (a[n] - a[n - 1]) * (a[n] - a[n - 1]);
	if (v2 > v1) {
		ans++;
	}
	swap(a[1], a[n]);
//	cout << ans << '\n';


	rep(i, 2, n - 2) {
		int v1 = f(i - 1, i, i + 1) + f(i, i + 1, i + 2);
		swap(a[i], a[i + 1]);
		int v2 = f(i - 1, i, i + 1) + f(i, i + 1, i + 2);
		swap(a[i], a[i + 1]);

		if (v2 > v1) {
			ans++;
		}
	}
	cout << ans << '\n';

}

EazyDevelop社区

一站式 AI 云服务平台

更多推荐

响应式界面：用关键状态做视觉回归

跨端一致不是每一像素都相同。更重要的是内容层级、阅读顺序和操作反馈在不同宽度下仍然成立。先选典型的窄屏、常用桌面宽度和容器受限场景，再为它们准备稳定的页面状态。

EazyDevelop社区

OpenClaw中文官网下载安装部署指引，TopClaw零代码自动识别系统

它实际上是一个更高阶的零代码自动识别与应用平台聚合入口，上面沉淀了很多现成的方案和实战思路，相当于把你的OpenClaw连接到了一个更庞大的能力库里。你可以把它理解为“开箱即用的技能商店”，无论是常见的截屏识别、定时提醒，还是复杂一些的多步骤数据处理，你都能在上面找到灵感，直接拿来用，连动脑设计流程都省了。它更像一个“积木盒子”，把复杂的底层逻辑都封装好了，你只需要动动鼠标，把模块拼接起来，就能跑