【问题描述】
小 M 在做数学作业的时候遇到了一个有趣的问题：有一个长度为 n 的数字
串 S，小 M 需要在数字之间填入若干个“+”和恰好一个“=”，使其成为一个
合法的等式。如对于 S=“2349”，可以通过添加 2个“+”和 1 个“=”成为
“2+3+4=9”。
小 M 发现有些数字串是无法通过添加符号成为一个合法的等式的，她想知
道对于每一个给定的数字串 S，是否可以通过添加符号使之成为一个合法的等
式（允许前导 0）？
【输入】
第一行为数据组数 T，表示有 T组输入数据。
接下来 T行每行一个数字串 S。
【输出】
对于每组数据，若 S可以成为合法的等式，输出“Yes”，否则输出
“No”，以单行回车隔开。
【输入输出样例】
4
2349
233233
122323
2344322322
Yes
Yes
No
Yes
【输入输出样例解释】
2+3+4=9
233=233
2+34=4+3+2+2+3+22
【数据范围】
对于 50%的数据：1 ≤ T ≤ 3，1 ≤ n ≤ 4。
对于 100%的数据：1 ≤ T ≤ 5，1 ≤ n ≤ 10。
本题纯正dfs，代码并不是很难。
用状态压缩更优，但直接dfs也能过。
#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define mp make_pair #define pb push_back #define xx first #define yy second typedef long long ll; typedef pair<int,int> pii; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=10; char s[maxn]; int n; int solve() { scanf("%s",s+1); n=strlen(s+1); rep(x,1,n-1) { rep(S,0,(1<<n-1)-1) { int left=0,cur=0,right=0; rep(i,1,x) { cur=cur*10+s[i]-'0'; if(S>>i-1&1) left+=cur,cur=0; } left+=cur;cur=0; rep(i,x+1,n) { cur=cur*10+s[i]-'0'; if(S>>i-1&1) right+=cur,cur=0; } right+=cur;cur=0; if(left==right) return 1; } } return 0; } int main() { freopen("equation.in","r",stdin); freopen("equation.out","w",stdout); int T=read(); while(T--) puts(solve()?"Yes":"No"); return 0; }