当前位置: 首页 > news >正文

题解:AT_agc057_c [AGC057C] Increment or Xor

题意:很简单了,不再赘述。

做法:

先观察一下打打表,发现首先必须满足 \(a_i\equiv a_{i+\frac{N}2}\pmod {\frac{N}2}\),这里 \(N=2^n\),因为结束状态满足,且这两种操作都不影响他们对 \(\frac{N}{2}\) 取模的关系。

然后考虑我肯定是要让前 \(\frac{N}{2}\) 位的最高位要一样,变成 \(0\) 比较方便,我们就扫一遍,如果找到一个最高位为 \(1\) 的,那么就让他补全所有位再加一,这样就可以做到一个最高位取反的效果。

那么你可能会问这里为什么会保证不会影响其他的最高位呢,因为如果会影响,那么一定是满足他们两个模 \(\frac{N}2\) 同余,这样加一才能一起进位,但是显然是不存在的,所以不会影响到。

然后再用一次异或操作,将 \(a_0\) 变成 \(0\),其他的如果不是 \(a_i=i\) 那么就不可行。

但是这里其实还是可能可以用加一操作的,为什么我们不用考虑呢?

我们先讲如何实现,最后来解决这个问题。

跟位运算有关,大多可以拍到 Trie 树上来做,但是如果从高位往低位排不是很好做 \(+1\),我们考虑从低位往高位建立,这样 \(+1\) 就等于一条左链去 swap 左右儿子,然后就解决了,查询一个点就直接按点的编号向上跳即可,异或 \(x\) 就对 \(x\) 在二进制位上的 \(1\) 的位进行打标记即可。

那么来解释上面为什么不用 \(+1\) 的问题,我们发现最后我们要求的第 \(n-1\) 位一定是左儿子为前 \(\frac{N}{2}\) 位,但是如果 \(+1\) 就会打乱这个顺序,并且稍微手玩并理解一下,如果 \(+x\),第 \(p\) 位为 \(1\),那么就是从最右侧往左数第 \(p\) 组的儿子翻转了一下,可以看看图:

并且异或只是对整体一起交换,不会对底层内部交换,所以还是得靠加一才能交换内部,\(\frac{N}{2}\) 一个周期,但是显然是无意义的,所以只用考虑一次异或后是否合法就可以了。

代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = (1 << 18) + 5;
struct node {int son[2], tag, fa;
} ;
vector<int> ans;
int n, N, a[maxn], p[maxn];
struct Trie {node tr[maxn << 2];int tot = 1, tag[maxn];int insert(int x) {int p = 1;for (int i = 0; i < n; i++) {int t = (x >> i) & 1;if(!tr[p].son[t])tr[p].son[t] = ++tot, tr[tot].fa = p;p = tr[p].son[t];}return p;}void make_xor(int x) {ans.push_back(x);for (int i = 0; i < n; i++)tag[i] ^= (x >> i) & 1;}void make_add() {int p = 1;for (int i = 0; i < n; i++) {swap(tr[p].son[0], tr[p].son[1]);if(tag[i])p = tr[p].son[1];elsep = tr[p].son[0];}ans.push_back(-1);}int query(int u) {int res = 0;for (int i = n - 1; i >= 0; i--) res += (tr[tr[u].fa].son[tag[i] ^ 1] == u) * (1 << i), u = tr[u].fa;return res;} 
} tree;
int main() {cin >> n, N = (1 << n);for (int i = 0; i < N; i++)cin >> a[i];for (int i = 0; i < N / 2; i++)if(a[i] % (N / 2) != a[i + N / 2] % (N / 2)) {cout << "No" << endl;return 0;}for (int i = 0; i < N; i++)p[i] = tree.insert(a[i]);for (int i = 0; i < N / 2; i++) {int x = tree.query(p[i]);//	cout << x << endl;if(x & (N / 2)) tree.make_xor(N - 1 - x), tree.make_add();}tree.make_xor(tree.query(p[0]));for (int i = 0; i < N; i++)	if(tree.query(p[i]) != i) {cout << "No" << endl;return 0;}cout << "Yes" << endl;cout << ans.size() << endl;for (int i = 0; i < ans.size(); i++)cout << ans[i] << " ";cout << endl;return 0;
}
http://www.hskmm.com/?act=detail&tid=23731

相关文章:

  • 占个位置
  • 使用 Copilot AI + Blazor 编一个五子棋游戏
  • 关于VMware虚拟机如何下载-2025.10.3
  • 国庆集训做题10.1 - 10.3
  • 玳瑁的嵌入式日记---0928(ARM--UART) - 指南
  • 解决Visual Studio中无法使用scanf和C++万能头的问题
  • 英文笔记
  • 解码红黑树
  • 10/3
  • Advanced Computer Graphics
  • Netflix确保数亿用户观影体验的“事件”管理是如何构建与实践的?
  • 为什么词嵌入可以和位置编码相加
  • 【比赛记录】2025CSP-S模拟赛57
  • 实用指南:软件设计师——04 操作系统
  • 20251001国庆模拟
  • 线段树合并 [POI 2011] ROT-Tree Rotations
  • CSS的选择器 - 指南
  • C# Net9的模块初始化器(Module Initializer)
  • 离线轻量大模型,Ollama部署到docker方法
  • 应用拓扑讲义整理 Chapter 6. 单纯复形(Simplicial Complexes)
  • 完整教程:华为麒麟9010、9020、9030、9040系列芯片的性能参数及其与高通芯片的对比
  • AQS(ReentrantLock)源码浅析
  • 05. 事件处理
  • 总结问题2 软工10.3
  • BPL包无法调试的问题
  • 信息科学与数据分析:真正的区别是什么?
  • 最短路练习
  • 杂题,为什么博客的标题必须互异
  • 学习笔记:压位高精
  • 吉司机 + 历史和练习