今晚CF A-E1题解

cjdst

2026-02-12 02:13:00

发布于：广东

36阅读

0回复

0点赞

爽！！！！！

A

Difficulty: 3- / Easy

Tag：-

何意味啊。好久没看见过 A 是暴力题的了。上次见到还是在有 $n,m,k$ 个 $1,2,3$ ，可以擦去其中两个换剩下一个，求最后剩下的数可能是什么。

注意到当 $n\le 10^{18}$ 时， $0\le d(n)\le 1000$ ，所以 $n$ 往后取 $1000$ 个判肯定是没问题的。

namespace cjdst{
    void solve(){
		int n;
		std::cin >> n;
		int ans = 0;
		for(int i = n; i <= n + 1000; i++){
			std::string s = std::to_string(i);
			int cur = 0;
			for(char c:s) cur += c - '0';
			if(i - cur == n) ans++;
		}
		std::cout << ans << '\n';
	}
}

时间复杂度： $O(tk\log n)$ ，其中 $k=1000$ 。

B

Difficulty：3- / Easy

Tag：-

为什么我说 B<A。

随便想几种情况可知，左右端点覆盖一定不会使两个数的顺序改变，而如果所有数的顺序不变的话一定可以操作出来。

所以我们只需要看顺序是否改变即可。

namespace cjdst{
    void solve(){
		int n;
		std::cin >> n;
		std::vector <int> a(n + 5), b(n + 5), idx(n + 5);
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
			idx[a[i]] = i;
		}
		for(int i = 1; i <= n; i++){
			std::cin >> b[i];
		}
		for(int i = 2; i <= n; i++){
			if(idx[b[i - 1]] > idx[b[i]]){
				std::cout << "NO\n";
				return;
			}
		}
		std::cout << "YES\n";
	}
}

时间复杂度： $O(\sum n)$ 。

C

Difficulty：3- / Easy

Tag：巴巴博弈

为什么我说 C<B。

不知道为什么要设置成 $\frac{2}{3}$ 。~~难道说出题人也刚学待修莫队？~~

首先当 $\frac{p}{q}\lt\frac{2}{3}$ 时，显然 Alice 减 $p$ ，Bob 为了更优只能减 $q$ ，此时 $\frac{p-1}{q-1}\lt\frac{p}{q}\lt\frac{2}{3}$ ，Bob 不炸了。

然后当 $\frac{p}{q}\ge 1$ 时，显然 Alice 减 $q$ ，Bob 为了更优只能减 $p$ ，此时 $1\lt\frac{p}{q}\lt\frac{p-1}{q-1}$ ，Bob 不炸了。

然后当 $\frac{2}{3}\le \frac{p}{q}\lt 1$ 时，显然 Alice 减 $p$ 还是减 $q$ Bob 跟着就行了，显然最终可以到 $\frac{2}{3}$ ，Bob 不爽了。

namespace cjdst{
    void solve(){
		ll n, m;
		std::cin >> n;
        std::cin >> m;
		if(n * 3 == m * 2){
			std::cout << "Bob\n";
			return;
		}
		if(n * 3 < m * 2 || n >= m){
			std::cout << "Alice\n";
			return;
		}
		std::cout << "Bob\n";
	}
}

时间复杂度： $O(t)$ 。

D

Difficulty：4.7 / Easy+

Tag：根号分治

首先先打暴力。我们可以枚举长度 $A_i,2\times A_i,3\times A_i,...$ ，然后判断。代码如下：

namespace cjdst{
    void solve(){
		int n;
		std::cin >> n;
		std::vector <ll> a(n + 5);
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
		}
		ll ans = 0;
		for(int i = 1; i <= n; i++){
			for(int j = a[i]; j < i; j++){ 
				if(j == a[i] * a[i - j]) ans++;
			}
		}
		std::cout << ans << '\n';
	}
}

时间复杂度： $O(n^2)$ 。

然后发现这个很能根号分治的样子。设置阈值为 $B$ 。

$A_i\gt B$ ：直接暴力， $O(\frac{n^2}{B})$ 。
$A_i\le B$ ：把所有 $A_i$ 相同的放一块查询。将所有数按对 $A_i$ 取模的余数分组，然后加个偏移放桶里查询就行了。 $O(nB)$ 。

总共是 $O(nB+\frac{n^2}{B})$ 的， $B$ 取 $\sqrt n$ 时有 $O(n\sqrt n)$ 。

// sqrt 那应该得卡常了，换个码风（ 
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
const int N = 200000, B = 300;
ll a[N + 5];
std::mt19937 rng(time(0) * 10ll);
std::map <int, std::vector <int>> mp;
int block[B + 5][N * 2 + 5];
int ct[B + 5];
int belong[N + 5];
ll mer(ll x, ll y){
	return x * 1590033 + y;
}
void solve(){
	ll n;
	std::cin >> n;
	for(int i = 1; i <= n; i++){
		std::cin >> a[i];
		mp[a[i]].push_back(i);
	}
	ll ans = 0;
	for(auto it:mp){
		if(it.first <= B){
			for(int i = 1; i <= n; i++){
				int idx = i % it.first;
				ct[idx]++;
				if(a[i] <= n) block[idx][a[i] + (ct[idx])]++;
				belong[i] = ct[idx];
			}
			for(int i:it.second){
				ans += block[i % it.first][belong[i]];
			}
			for(int i = n; i; i--){
				int idx = i % it.first;
				if(a[i] <= n) block[idx][a[i] + (ct[idx])]--;
				ct[idx]--;
			}
		}else{
			for(int i:it.second){
				for(int j = 1;; j++){
					if(j * a[i] >= i) break;
					if(j == a[i - a[i] * j]) ans++;
				}
			}
		}
	}
	std::cout << ans << '\n';
	mp.clear();
}
int main(){
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	int T;
	std::cin >> T;
	while(T--) solve();
	
	return 0;
}

然后你会发现 MLE 了。嗯。

其实我场上最终代码空间是 $O(n)$ 的，但这个看得更清楚吧应该。

E1

Difficulty：4.3 / Easy

Tag：构造

注意到限制很宽松，只需要在 $32(n+m)$ 次询问内求出即可。所以怎么乱搞都行吧。

注意到第如果第 $k+1$ 条路径不包含第 $k$ 条路径的话，一定只有最后一个元素不同。

所以我们对于新点，dfs 回溯即可。

如果遍历到之前的点了怎么办？

注意到这是个 DAG。所以它的后面几条路径都是固定的，之前也走过。直接加上走过的路径即可。

然后注意第一个遍历到的不一定是源点。dfs 完了还得继续看有没有新点没走。

namespace cjdst{
    std::vector <int> query(int k, std::vector <std::vector <int>> &ans){
		std::cout << "? " << k << '\n';
		int len;
		std::cin >> len;
		std::vector <int> tmp;
		for(int i = 1; i <= len; i++){
			int val;
			std::cin >> val;
			tmp.push_back(val);
		}
		if(len >= 2) ans[tmp[len - 2]].push_back(tmp[len - 1]);
		return tmp;
	}
	
	std::vector <int> dfs(int idx, int dep, int &k, std::vector <int> &siz, std::vector <std::vector <int>> &ans){
		// std::cout << "Cur: " << idx <<'\n';
		if(siz[idx] != -1){
			k += siz[idx];
			return query(++k, ans);
		}
		int kk = k;
		auto tmp = query(++k, ans);
		while(tmp.size() > dep){
			tmp = dfs(tmp.back(), dep + 1, k, siz, ans);
		}
		siz[idx] = k - kk - 1;
		return tmp;
	}

	void solve(){
		int n;
		std::cin >> n;
		std::vector <int> siz(n + 5, -1);
		std::vector <std::vector <int>> ans(n + 5);
		int k = 0;
		auto v = query(++k, ans);
		int idx = -1;
		if(v.size()) idx = v.back();
		while(idx != -1){
			v = dfs(idx, 1, k, siz, ans);
			if(*min_element(siz.begin() + 1, siz.begin() + n + 1) != -1) break;
			if(!v.size()) idx = -1;
			else idx = v.back();
		}
		int tmp = 0;
		for(int i = 1; i <= n; i++){
			tmp += ans[i].size();
		}
		std::cout << "! " << tmp << '\n';
		for(int i = 1; i <= n; i++){
			for(int j:ans[i]){
				std::cout << i << ' ' << j << '\n';
			}
		}
	}
}

感觉我这个应该也只用了不到 $2(n+m)$ 个询问？

~~卧槽我是不是没去重。~~ 如果这个代码被 hack 了，我将把 Difficulty 升至 7+ / Hard。

有帮助，赞一个

去预览

0/2000

全部评论 7

yhz
E1 我简单看了，

1 1 0

能 hack 掉吗
2026-02-12 来自福建
1
- cjdst
  回复
  yhz
  第二个样例就是这个
  
  2026-02-12 来自广东
  1
- yhz
  回复
  cjdst
  好吧
  
  2026-02-12 来自福建
  0
Xylophone
吓哭了

2026-02-12 来自广东
0
cjdst
+117

2026-02-12 来自广东
0
yhz

但是依旧涨了 410

2026-02-12 来自福建
0
- cjdst
  回复
  yhz
  %%%
  
  2026-02-12 来自广东
  0
yhz
www我只切了第一题就去睡觉了

2026-02-12 来自福建
0
cjdst
喜提room rk1

2026-02-12 来自广东
0
- yhz
  回复
  cjdst
  Tips:总共就三个人打
  
  2026-02-12 来自福建
  0
- cjdst
  回复
  yhz
  我说的room是这个
  
  2026-02-12 来自广东
  1
- yhz
  回复
  cjdst
  wc
  
  2026-02-12 来自福建
  0
cjdst
ddd

2026-02-12 来自广东
0

A

B

C

D

E1

全部评论 7

热门讨论