HDU4403-模拟、数学

一道很难的奥数题，给出一个数字串，插入加号和等号使之成立。求成立的算式数。

我的做法是，先分成两段，中间插入等号，再分别求出左右两边可能的值和个数，然后对比，把值相等的情况乘起来，加到最终结果上。

求可能值用递归，每次遇到一个数就选择是插入加号还是不插入，不插入加号就把之前维护的值乘以10加上此值，插入加号把维护的值加到和里。这样可以把所有的情况存进map里。

 #include <algorithm>

 #include <cstring>

 #include <ctype.h>

 #include <cstdlib>

 #include <cstdio>

 #include <vector>

 #include <string>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <set>

 #include <map>

 using namespace std;

 int N,M,T;

 char save[];

 map <long long,int> m[];

 void solve(int l,int r,long long cur,long long combo,int d)

 {

     if(l >= r)

     {

         cur += combo;

         if(m[d].count(cur) == )

             m[d].insert( pair<long long,int>(cur,));

         else m[d][cur]++;

         return;

     }

     solve(l+,r,cur+combo,save[l+]-'',d);

     solve(l+,r,cur,combo*+save[l+]-'',d);

     return;

 }

 int main()

 {

     while(scanf("%s",save) && save[] != 'E')

     {

         int n = strlen(save);

         int ans = ;

         for(int i = ;i < n-;i++)

         {

             m[].clear();m[].clear();

             solve(,i,,save[]-'',);

             solve(i+,n-,,save[i+]-'',);

             map<long long,int>::iterator it = m[].begin();

             for(;it != m[].end();it++)

             {

                 //printf("%d %d\n",it->first,it->second);

                 if(m[].count(it->first) )

                     ans += (it->second * m[][it->first]);

             }

         }

         printf("%d\n",ans);

     }

 }

巴特西

HDU4403-模拟、数学

最新文章

热门文章