P8318『JROI-4』淘气的猴子 题解

· · 题解

题意

有一个长度为 n 的序列 a，对这个序列进行 m 次操作，得到序列 b，操作类型具体如下：

如果 x=y，那新的 x 就等于原来的 x 的两倍或平方。

现在给出序列 b 和 m 次操作，请还原出序列 a。

思路

体面看起来挺吓唬人，甚至线段树的题刷多了还以为是线段树，但就是一道简单的模拟。

建一些数组或一个结构体记录这些操作，然后逆序进行操作。这里逆序指操作顺序相反，加变成减（b_x-b_y），乘变成除（b_x\div b_y）。如果 x=y 就要特判一下，两倍变成除以二（b_x\div2），平方变成开方（\sqrt{b_x}）。最后就能还原出序列 a。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,b[N];
struct node{//建一个记录操作的结构体
    int opt,x,y;
}f[N];
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
    for(int i=1;i<=m;i++){//输入操作
        scanf("%lld%lld%lld",&f[i].opt,&f[i].x,&f[i].y);
    }
    for(int i=m;i>0;i--){//进行“逆序”操作
        int opt=f[i].opt,x=f[i].x,y=f[i].y;
        if(opt==1){
            if(x!=y)b[x]-=b[y];
            else b[x]/=2;//特判x=y
        }else if(opt==2){
            if(x!=y)b[x]/=b[y];
            else b[x]=sqrt(b[x]);//特判x=y
        }
    }
    for(int i=1;i<=n;i++)printf("%lld ",b[i]);//还原
    return 0;
}