题解：P15078 [ICPC 2024 Chengdu R] Expanding Array

huangboning · 2026-01-26 20:42:20 · 题解

这里称一种运算符为 x 和 y 到 z 的一个映射，其中三个数值域均为 \{0,1\}。猜测用这三个运算符能搞出所有运算符。实则不然，你发现 0 和 0 只能是 0。于是枚举剩下 8 种运算符，对所有相邻的数，把运算结果都存进 map。最后输出 map 的大小即可。

#include<bits/stdc++.h>
using namespace std;
int n,a[100010];
map<int,bool>pd;
int f(int x,int y,int t){
    int s=0;
    for(int i=29;i>=0;i--){
        int a=0,b=0;
        if((x>>i)&1)a=1;
        if((y>>i)&1)b=1;
        if(a==0&&b==0)s+=0;
        if(a==0&&b==1)s+=((t>>1)&1)*(1<<i);
        if(a==1&&b==0)s+=((t>>2)&1)*(1<<i);
        if(a==1&&b==1)s+=((t>>3)&1)*(1<<i);
    }
    return s;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],pd[a[i]]=1;
    for(int i=1;i<n;i++){
        for(int j=0;j<16;j++)pd[f(a[i],a[i+1],j)]=1;
    }
    cout<<pd.size();
}