今晚CF A-E1题解
2026-02-12 02:13:00
发布于：广东
爽！！！！！
A
Difficulty: 3- / Easy
Tag：-
何意味啊。好久没看见过 A 是暴力题的了。上次见到还是在有 个 ，可以擦去其中两个换剩下一个，求最后剩下的数可能是什么。
注意到当 时，，所以 往后取 个判肯定是没问题的。
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';
}
}
时间复杂度：，其中 。
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";
}
}
时间复杂度：。
C
Difficulty：3- / Easy
Tag：巴巴博弈
为什么我说 C<B。
不知道为什么要设置成 。难道说出题人也刚学待修莫队？
首先当 时，显然 Alice 减 ，Bob 为了更优只能减 ，此时 ，Bob 不炸了。
然后当 时，显然 Alice 减 ，Bob 为了更优只能减 ，此时 ，Bob 不炸了。
然后当 时，显然 Alice 减 还是减 Bob 跟着就行了，显然最终可以到 ，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";
}
}
时间复杂度：。
D
Difficulty：4.7 / Easy+
Tag：根号分治
首先先打暴力。我们可以枚举长度 ，然后判断。代码如下：
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';
}
}
时间复杂度：。
然后发现这个很能根号分治的样子。设置阈值为 。
- ：直接暴力，。
- ：把所有 相同的放一块查询。将所有数按对 取模的余数分组，然后加个偏移放桶里查询就行了。。
总共是 的， 取 时有 。
// 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 了。嗯。
其实我场上最终代码空间是 的，但这个看得更清楚吧应该。
E1
Difficulty：4.3 / Easy
Tag：构造
注意到限制很宽松，只需要在 次询问内求出即可。所以怎么乱搞都行吧。
注意到第如果第 条路径不包含第 条路径的话，一定只有最后一个元素不同。
所以我们对于新点，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';
}
}
}
}
感觉我这个应该也只用了不到 个询问？
卧槽我是不是没去重。 如果这个代码被 hack 了，我将把 Difficulty 升至 7+ / Hard。
有帮助，赞一个