P10052【IOI2021】位移寄存器题解

wangbinfeng · 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 天，如有错误见谅，烦请评论区回复。

P10052【IOI2021】位移寄存器 题解

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

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

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

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

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

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

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

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

P10052【IOI2021】位移寄存器题解