CF2052E Expression Correction 题解

FFTotoro · 2024-12-20 21:02:05 · 题解

简单模拟题。

考虑实现一个简单的函数 f(s)（其中 s 为一个合法表达式串）来检验一个表达式是否成立，具体实现方法只需要从左到右扫过去，像平常写的快速读入一样逐字符处理，判断等号两边是否相等即可。

然后我们注意到给定字符串长度 \le 100，也就代表可以暴力枚举需要移动的数字，再枚举它移动到了哪里，之后检验表达式串是否合法，时间复杂度 O(n^3)。这道题就做完了。

但是这题有挺多的坑点。以下是本题一些常见的坑（摘自官方题解）：

• 表达式中的数不能带有前导 0（WA 3）；
• 表达式中的数位数不超过 10（WA 5）；
• 只能移动数字（WA 6）；
• 表达式中的数不能为空（WA 23）；
• 表达式不能以 \texttt{+} 或 \texttt{-} 开头（WA 50）。

特判完这些容易出错的点，代码就非常好写了。放代码：

#include<bits/stdc++.h>
using namespace std;
const long long L=1e10;
// 表达式中数的上限（不超过 10 位）
inline bool check(string s){
  if(!isdigit(s[0]))return false;
  if(!isdigit(s.back()))return false;
  // 表达式头尾不能是符号
  for(int i=1;i<s.length();i++){
    if(s[i-1]=='0'){
      if(isdigit(s[i])&&(i==1||!isdigit(s[i-2])))return false;
    } // 特判“0d”的情况（其中 d 为一个数字）
    else if(!isdigit(s[i-1])){
      if(!isdigit(s[i]))return false;
    } // 特判其中某个数为空 / 等号两边有其他符号的情况
  }
  long long x=0,cl=0,cr=0;
  // 当前的数的绝对值、等号左边的值、等号右边的值
  int sgn=1; // 当前的数的符号
  bool f=false;
  for(char i:s){
    if(isdigit(i))x=x*10+i-'0';
    else{
      if(x>=L)return false;
      f?cr+=sgn*x:cl+=sgn*x;
      if(i=='=')f=true;
      x=0,sgn=i=='-'?-1:1;
    } // 遇到符号就处理当前的数
  }
  if(x>=L)return false;
  return cl==cr+sgn*x;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  string s; cin>>s;
  if(check(s))cout<<"Correct\n",exit(0);
  for(int i=0;i<s.length();i++)
    if(isdigit(s[i])){
      string tl=s,tr=s;
      for(int j=i;j;j--){
        swap(tl[j],tl[j-1]);
        if(check(tl))cout<<tl<<endl,exit(0);
      } // 往左交换
      for(int j=i;j<s.length()-1;j++){
        swap(tr[j],tr[j+1]);
        if(check(tr))cout<<tr<<endl,exit(0);
      } // 往右交换
    }
  cout<<"Impossible\n"; // 无解情况
  return 0;
}