自动搬运

查看原文

来自洛谷，原作者为

	wangbinfeng 今天搞完大概就永远不会碰 OI 了，大家祝好！

搬运于2025-08-24 22:39:49，当前版本为作者最后更新于2024-02-15 16:22:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\texttt{Part\;1.\;supplementary\;description:}$

搬题人漏搬了题面中的好多内容，先放一个官方中文 PDF 文件。具体地，在官方文件中有样例解释和输入输出格式的内容，以及重点词加粗。

$\texttt{Part\;2.\;brief\;description\;of\;the\;topic:}$

输入数组 $a$ 存在寄存器 $0$ 中，可以用 $\texttt{MOVE(=),SROTE(=),AND(\&),OR(|),XOR(\textasciicircum),NOT(\textasciitilde),LEFT(<<),RIGHT(>>),ADD(+)}$ 共 $9$ 种指令。求 $\begin{cases}最小值 && \text{if} && s=0 \\排序 &&\text{if}&& s=1\end{cases}$。

$\texttt{Part\;3.\;explanation\;of\;ideas:}$

$\texttt{Case\;1.\;Subject\;1\textasciitilde4(s=0):}$

先写一个 ADD 操作的二进制单位实现：$\begin{matrix} \qquad\;\;\; a \\+\qquad b \\ \hline \;\;\;\;c_1\;\;\;c_2 \end{matrix}$，显然，$c_1\gets a\texttt{\;AND\;}b,c_2\gets a\texttt{\;XOR\;}b$。
然后考虑给定三个寄存器，暂且记作 $r_a,r_b,r_c$，其中 $r_a,r_b$ 已知，求 $r_c\gets\begin{cases}r_a && \text{if} && r_a=r_b \\0 &&\text{if}&& r_a\neq r_b \end{cases}$。考虑取一个新的寄存器 $r_d\gets r_a\texttt{\;AND\;}r_b$，显然，$\begin{cases}r_a=r_b && \text{if} && r_d=0 \\r_a\neq r_b &&\text{if}&& r_d\neq0\end{cases}$。然后 $\underbrace{r_d\gets r_d<<1,r_d\gets r_d<<1,...,r_d\gets r_d<<1}_{2^k\text{\;times}},$ $\underbrace{r_d\gets r_d>>1,r_d\gets r_d>>1,...,r_d\gets r_d>>1}_{2^{k}\;\text{times}}$（结束后 $k$ 的最低 $2^k$ 位均为 $\begin{cases}0 && \text{if} && r_a=r_b \\1 &&\text{if}&& r_a\neq r_b \end{cases}$）。此时，$r_c\gets(\texttt{\;NOT\;}r_d)\texttt{\;AND\;}r_a$。 对于 $\texttt{Subject\;1}$ $n,k\le2$，直接对 $16$ 种情况编码即可。
考虑如何比较 $r_0$ 和 $r_1$ 的大小，$r_1=r_0\texttt{\;AND\;}k, r_2\gets\texttt{\;NOT\;}r_1,r_3\gets r_0\texttt{\;ADD\;}r_2$，$r_{3,k}$ 的值即 $r_0$ 和 $r_1$ 的大小关系。重复执行 $\lceil \log_2 n\rceil$ 次即可，询问次数为 $12\lceil \log_2 n\rceil+4$。

$\texttt{Case\;2.\;Subject\;5\textasciitilde6(s=1):}$

考虑冒泡排序，可通过 $\texttt{Subject\;5}$。回归冒泡排序的本质，要将 $a_1,a_2,a_3,...a_n$ 进行非降序排序排序，可以将其修改为 $\min(a_1,a_2),\max(a_1,a_2),\min(a_3,a_4),\max(a_3,a_4),...,\min(a_{n-1},a_n),\max(a_{n-1},a_n)$，再进行奇偶反转校验（如 $\max(a_1,a_2),\min(a_3,a_4)$ 修改为 $\min(a_3,a_4),\max(a_1,a_2)$），重复 $n$ 次即可，询问次数为 $19n+6$。

$\texttt{Part\;4.\;code:}$

#include<bits/stdc++.h>
#ifdef ONLINE_JUDGE
void append_move(int t, int y);
void append_store(int t, std::vector<bool> v);
void append_and(int t, int x, int y);
void append_or(int t, int x, int y);
void append_xor(int t, int x, int y);
void append_not(int t, int x);
void append_left(int t, int x, int p);
void append_right(int t, int x, int p);
void append_add(int t, int x, int y);
void append_print(int t);
#else 
#include"registers.h"
#endif
const int m=100,b=2000;
void construct_min(const int n,const int k){
   std::vector<bool>v(b,0);
   const int fill_up=m-1,mask_ones=m-2,low_one=m-3;
   for(int i=0;i<b;i++)if(i%(2*k)==0)v[i]=1;
   append_store(low_one,v),v.assign(v.size(),0);
   for(int i=0;i<b;i++)if((i/k)%2==0)v[i]=1;
   append_store(mask_ones,v),v.assign(v.size(),0);
   for(int i=n*k;i<b;i++)v[i]=1;//将寄存器0中不属于a的部分全部置1 
   append_store(fill_up,v);
   append_or(0,0,fill_up);
   for(int T=ceil(log2(n)),a=k;T--;a*=2)
       append_right(1,0,a),
       append_not(3,1),
       append_and(3,3,mask_ones),
       append_and(0,0,mask_ones),
       append_add(2,0,3),
       append_right(2,2,k),
       append_and(2,2,low_one),
       append_add(2,2,mask_ones),
       append_and(4,2,0),
       append_not(5,2),
       append_and(5,1,5),
       append_or(0,4,5);
}
void construct_sort(const int n,const int k){
   std::vector<bool>v(b,0);
   const int fill_up=m-1,mask_ones=m-2,low_one=m-3;
   for(int i=0;i<b;i++)if(i%(2*k)==0)v[i]=1;
   append_store(low_one,v),v.assign(v.size(),0);
   for(int i=0;i<b;i++)if((i/k)%2==0)v[i]=1;
   append_store(mask_ones,v),v.assign(v.size(),0);
   for(int i=n*k;i<b;i++)v[i]=1;//将寄存器0中不属于a的部分全部置1 
   append_store(fill_up,v);
   append_or(0,0,fill_up);
   for(int T=0;T<n;T++) {
       if(T%2)append_left(1,0,k);else append_right(1,0,k);
       append_not(5,1);
       append_and(5,5,mask_ones);
       append_and(0,0,mask_ones);
       append_add(2,0,5);
       append_right(2,2,k);
       append_and(2,2,low_one);
       append_add(2,2,mask_ones);
       append_not(4,2);
       append_and(3,2,0);
       append_and(5,1,4);
       append_or(7,3,5);
       append_and(7,7,mask_ones);
       append_and(3,2,1);
       append_and(5,4,0);
       append_or(6,3,5);
       append_and(6,6,mask_ones);
       if(T%2)append_right(7,7,k);else append_left(6,6,k);//注意这里奇偶移位的寄存器不同 
       append_or(0,6,7);
   }
   append_not(fill_up,fill_up);
   append_and(0,0,fill_up);
}
void (*fun[2])(const int,const int)={construct_min,construct_sort};
void construct_instructions(int s,int n,int k,int){fun[s](n,k);}

$\texttt{Part\;5.\;express\;gratitude:}$

感谢 luogu 网站提供平台支持，感谢 IOI 官方组织比赛，感谢 Maxim Akhmedov 出这么好的题 ，感谢搬题人私自乱改题号还忘记改附件名称（只是调侃，不喜私信或评论即删）。

$\texttt{Part\;6.\;appendix:}$

• 小提示：本地用 DEV 做本题时记得建项目哦（因为跨文件了）。

（以下为题外话，可跳过）
在机房推了 5 个小时公式，用了三四面黑板，不得不说 IOI 出的题真不错（没有算法难度，全是数学和位运算的难点）。公式显然不是自己推出来的，感谢官方题解。话说这么多位运算的题是咋想到的。这种题建议还是自己得手推几遍的。
交互题真的会上瘾。我做这道题就因为做 IOI2021Day2T1 上瘾了，那道题比较简单，可以一做。
字数有点多，$\KaTeX$ 打的快吐了，如有手误欢迎评论。
超多 $\KaTeX$，在博客编辑区无法显示，但是博客页面和其他编辑区、显示区均正常。烦请题解志愿者注意一下，$\KaTeX$ 真的真的没炸！（逃了）
如果题解区显示炸了欢迎前往博客查看哦。
【UPD.2024/3/1】由于本题解提交时间恰逢过年管理放假，从写完初稿到被打回已经过去整 15 天，如有错误见谅，烦请评论区回复。