2025.10.28 模拟赛

排队

枚举 数学

思路

首先考虑如何支持等差，不难想到枚举差 $k$ 然后在此方差的情况下选择修改次数最小的方案。由于它规定了值域是 $[1,w]$，而方差为 $k$ 时目标 $a_n$ 至少为 $1+(n-1)k$，所以枚举上界就是 $k=\lfloor \frac{w-1}{n-1}\rfloor$。这个枚举时间复杂度 $\mathcal{O}\left(\frac{w}{n}\right)$。

对于第 $i$ 个元素，我们生成基准目标元素 $a_i=1+(i-1)k$，那么需要将原始 $a$ 修改成和基准目标元素每个差值相同的（保证插值 $k$）。具体来说，选择与基准元素差值相同数量最多的，最后需要修改的数量就越少。

这个检查是 $\mathcal{O}(n)$ 线性的。但是由于需要用到负数下标，我使用了 map。

注意

需要特别注意第一个元素和最后一个元素，不能超过 $[1,w]$。

Hack 数据 $n=4,m=7$，有 $a=(2,4,6,7)$。

对于

答案是 $2$ 不是 $1$，因为最后一个元素无法别改成 $8$。

时间复杂度 $\mathcal{O}\left(\frac{w}{n}\times n{\log }_{2}n\right)=\mathcal{O}\left(w{\log }_{2}n\right)$。

const LL kMaxN = 3e5 + 5;
 
LL a[kMaxN], n, m, ans = 1e18;
map<LL, LL> f;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (LL i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (LL k = 0; 1 + (n - 1) * k <= m; k++) {
    f.clear();
    for (LL i = 1; i <= n; i++) {
      int d = 1 + (i - 1) * k - a[i];
      if (1 - d >= 1 && 1 + (n - 1) * k - d <= m) {
        f[d]++;
      }
    }
    for (auto i : f) {
      ans = min(ans, n - i.second);
    }
  } 
  cout << ans << '\n';
  return 0;
}

攀比

结论 找规律

思路

这道题目有多个询问，这代表着我们可能需要 $\mathcal{O}(\log )$ 级别求出单次询问的答案。

首先考虑找规律/猜结论。对于一个点 $x$，我们删掉之后这个连通块会变成多少个呢？当然是 $d_x$ 个；然而，由于 $x$ 是之前更小的点删去后分出来的连通块的新的最小点，所以实际上是变成 $d_x-1$ 个，但是对于一个初始连通块本身就有一个。所以答案就是连通块数量+$\sum \max (0,d_i-1)$……吗？

随便画一个不是树的连通块，就发现一个点删掉之后并不会出现 $d_x-1$ 个连通块。现在我们知道从连通块个数的增加上考虑思路有点困难了，不如直接考虑最后不被删除需要什么条件。

思考两年半，我们可以得知一个节点如果最后会留下来，那么它的邻居节点的编号一定均小于它，因为如果有大于它的它就会因为存在于一个大小大于 $1$ 的连通块中删除。

所以我们直接用 set 动态维护每个节点的邻点编号，动态计算答案即可。

时间复杂度 $\mathcal{O}(q{\log }_{2}n)$，当然可以通过标记的方式去掉 set 的 $\log$。

const int kMaxN = 1e5 + 5;
 
int n, m, q, ans;
set<int> e[kMaxN];
 
bool check(int x) {
  return e[x].empty() || *e[x].rbegin() < x;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1, u, v; i <= m; i++) {
    cin >> u >> v;
    e[u].insert(v);
    e[v].insert(u);
  }
  for (int i = 1; i <= n; i++) {
    ans += check(i);
  }
  cin >> q;
  for (int o, u, v; q; q--) {
    cin >> o;
    if (o == 1) {
      cin >> u >> v;
      ans -= check(u);
      ans -= check(v);
      e[u].insert(v);
      e[v].insert(u);
      ans += check(u);
      ans += check(v);
    } else if (o == 2) {
      cin >> u >> v;
      ans -= check(u);
      ans -= check(v);
      e[u].erase(v);
      e[v].erase(u);
      ans += check(u);
      ans += check(v);
    } else {
      cout << ans << '\n';
    }
  }
  return 0;
}

排排队

暴力 找规律 结论 前缀和

重点

这种题目又出现了，就是优化枚举。普通的暴力枚举肯定过不了，但是对于大多数情况都不可能造成最优解的，直接不考虑。

思路

若干次合并相邻的两个元素可以看作区间合并为一个，于是想到异或前缀和，这样就可以 $\mathcal{O}(1)$ 求出区间异或和了。

一个显而易见的结论是：

• [n] 我们只会进行区间合成最多两次，因为只需要构造一对逆序的。

于是可以想出时间复杂度为 $\mathcal{O}(n^3)$ 的暴力，即枚举左端点 $i$ 和右端点 $j$，中间枚举 $k$ 让 $[i,k]$ 的合并，$[k+1,j]$ 的合并，满足的要求就是 $p_k\oplus p_{i-1}=p_j\oplus p_k$。答案取 $\min (j-i-1)$。

对于 $n>400$，直接输出 $1$。此时就可以直接获得 $100$ 分了。

疑问 $400$ 还是其它？

为什么这样做是对的呢？怎么想到的？具体的边界真的是

证明

实际上边界是 $60$。

对于 $3$ 个相邻的数，如果它们最高 $1$ 位是相同的，那么前两个异或之后这一位就没有了，所以答案是 $1$。

为了避免这种情况，我们需要构造相邻 $3$ 个数最高位均不同的，但是最高位不能单调递减（这样本身答案就是 $0$ 了）。所以最好的构造方案是每个数位作为最高位构造两个数，最高数位单调递增。这样子就是 $60$ 个数了。大于 $60$ 必然崩盘，答案就为 $1$。

我的做法更奇特。没有钦定对于 $n>60$ 答案一定为 $1$，因为不保险。我钦定答案不会超过 $2\times 30=60$，所以对于每个 $i$，$j$ 只枚举往后最多 $60$ 个。

注意

这种做法的运算量高达 $7.2\times 10^8$，需要配合最优性剪枝才能通过。当然忽略常数时间复杂度 $\mathcal{O}(n)$。

这是我的做法。

const int kMaxN = 2e5 + 5;
 
int p[kMaxN], a[kMaxN], t, n, ans;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      p[i] = p[i - 1] ^ a[i];
    }
    ans = 1e9;
    for (int i = 1; i <= n; i++) {
      for (int j = i + 2; j <= min(n, i + 60); j++) {
        if (j - i - 1 >= ans) {
          break;
        }
        for (int k = i; k < j; k++) {
          if ((p[k] ^ p[i - 1]) > (p[j] ^ p[k])) {
            ans = j - i - 1;
          }
        }
      }
    }
    cout << (ans != 1e9 ? ans : -1) << '\n';
  }
  return 0;
}

南斯拉夫

深度优先搜索 广度优先搜索 并查集

思路

我采用的暴力。

首先可以看作二选一，每个元素最后必须被选偶数次，于是 DFS 暴搜 $\mathcal{O}(2^{m}n)$，$\mathcal{O}(n)$ 判断优化为 $\mathcal{O}(m)$ 判断后直接获得 $40$ 分。