B3789 题解

Greenzhe · 2023-06-14 19:47:36 · 题解

简述题意：

给你一段仅由 if 和赋值语句组成的程序，输入变量 x，输出变量 y。

问：对于任意输入的在 int 范围内的 x，有多少种可能的输出 y 值？

先考虑，对于一个给定的 x，如何求出 y 的值？

这相对简单，直接模拟：

扫描整个程序，

如果该行是 if 语句，判断 x 是否满足括号内条件。不满足则跳过代码块。
如果该行是赋值语句，直接将 y 赋值即可。

最后得到 y 值。

功能包装成函数 simulate(x)：

struct sentence{ // 每一行
    bool type; // if 语句为 1，赋值语句为 0
    char op; // x>val 还是 x<val
    int val; // 判断的值
    int ed; // 与之匹配的右括号所在的行数
}se[1005];
int simulate(int x){
    int y=0;
    for(int i=1;i<=n;++i){
        if(se[i].type){ // 判断语句
            if(se[i].op=='>')
                if(x<=se[i].val) i=se[i].ed; // 不满足要求就跳
            if(se[i].op=='<')
                if(x>=se[i].val) i=se[i].ed; // 不满足要求就跳
        }
        else y=se[i].val; // 赋值语句
    }
    return y;
}

那么我们现在就有了一种初步做法，对于所有 int 范围内的 x 进行枚举，分别求出 y 的值，扔到 std::set 里求出答案。

然而这样做复杂度是 10^9 级别的。

这个做法可以被显著优化。

由于所有赋值语句都可能对应一个 y 值，合理猜测，所有 if 语句都对应一个 x 值。

当语句是 x<val 时，对应的值是 val-1；当语句是 x>val 时，对应的值是 val+1。

从贪心的角度理解：(\text{val} \pm 1) 最靠近条件的值，且满足条件，必然能通过更多的 if 语句；如果 (\text{val} \pm 1) 也无法通过另外一个 if 语句，那么这两个语句必然无法同时通过。
从几何的角度理解：把每个不等式看做数轴上一条射线，那么覆盖 (\text{val} \pm 1) 位于的点的射线一定有最多条。

于是处理出每个可能的 x 值，逐个模拟一遍即可。

这道题的标算就讲到这里。以下是代码的剩余部分。

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> listx; // 可能的 x 值表
stack<int> ifs; // 括号匹配栈
set<int> answer; // 最后的 y 值表
char program[1005][1005]; // 存输入的程序源代码

int main(){
    // 输入与处理部分
    scanf("%d\n",&n);
    for(int i=1;i<=n;++i){
        gets(program[i]); // 这里写的不太优美，读者可以自行换
        int len=strlen(program[i]);
        se[i].type=false;
        int s=0;
        se[i].op='?';
        for(int j=0;j<len;++j){
            if(program[i][j]=='<') se[i].op='<'; // x<val?
            if(program[i][j]=='>') se[i].op='>'; // x>val?
            if(program[i][j]=='}'){ // 右括号
                se[i].type=true;
                int st=ifs.top();
                ifs.pop();
                se[st].ed=i;
                break;
            }
            if(j>0&&program[i][j-1]=='i'&&program[i][j]=='f'){ // 判断语句（左括号）
                se[i].type=true;
                ifs.push(i);
            }
            if(isdigit(program[i][j])){ // 累加数字
                s=s*10+program[i][j]-48;
            }
        }
        se[i].val=s;
        if(se[i].type){
            if(se[i].op=='<') listx.push_back(s-1);
            // x<val, x=val-1
            else listx.push_back(s+1);
            // x>val, x=val+1
        }
    }
    // 模拟 x 值
    for(int i=0;i<listx.size();++i)
        answer.insert(simulate(listx[i]));
    // 输出
    set<int>::iterator it;
    for(it=answer.begin();it!=answer.end();++it)
        printf("%d ",*it);
    printf("\n");
    return 0;
}