自动搬运

查看原文

来自洛谷，原作者为

	Greenzhe Everything that kills me makes me feel alive

搬运于2025-08-24 21:15:03，当前版本为作者最后更新于2023-06-14 19:47:36，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

简述题意：

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

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

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

这相对简单，直接模拟：

扫描整个程序，

1. 如果该行是 if 语句，判断 $x$ 是否满足括号内条件。不满足则跳过代码块。

2. 如果该行是赋值语句，直接将 $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;
}