HDU-4403 A very hard Aoshu problem 열거

7165 단어 HDU
등호의 위치를 직접 매거한 뒤 좌우 양쪽에 두 개의 MAP로 구성된 화의 개수를 기록한 뒤 곱셈 원리를 적용해 답을 얻는다.
코드는 다음과 같습니다.
#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<queue>

#include<set>

#include<map>

#include<cstring>

#include<vector>

#include<string>

#define LL long long

using namespace std;



char s[20];



int len;



map<long long,int>fmp, tmp;



long long get(int x, int y) {

    long long ret = 0;

    for (int i = x; i <= y; ++i) {

        ret = ret * 10 + s[i] - '0';

    }    

    return ret;

}



void cal(int a, int b, map<long long,int>&mp) {

    if (a == b) {

        ++mp[s[a]-'0'];

        return;

    }

    int mask = 1 << (b-a), last;

    for (int i = 0; i < mask; ++i) {

        long long temp = 0;

        last = a;

        for (int j = 0; j < (b-a); ++j) {

            if (i & (1 << j)) {

                temp += get(last, a + j);

                last = a + j + 1;

            }

        }

        temp += get(last, b);

        ++mp[temp];

    }

}



long long solve(int x) {

    long long ret = 0;

    fmp.clear(), tmp.clear();

    map<long long, int>::iterator it;

    cal(0, x, fmp);

    cal(x+1, len-1, tmp);

    for (it = fmp.begin(); it != fmp.end(); ++it) {

        ret += (long long)(it->second) * (long long)tmp[it->first];

    }

    return ret;

}



int main(  )

{

    long long ret;

    while (scanf("%s", s), s[0] != 'E') {

        ret = 0;

        len = strlen(s);

        for (int i = 0; i <= len-2; ++i) {

            //          

            ret += solve(i);

        }

        printf("%I64d
", ret); } return 0; }

좋은 웹페이지 즐겨찾기