FZU Problem 1895 整除45问题（整除问题+字符串维护+优化）

这个题有点烧脑啊,但是只要想清楚被45整除的数,肯定能被5和9整除,能被9整除的数各位加起来肯定是9的倍数,能被5整除的末尾是0或5.

然后dfs的过程稍微不太好懂,还有几个优化必须要注意.dfs的过程是选出哪些数我们不要,而且不要的数越少越好,所以删除的数在dfs的过程中应该越来越小,这一步必须有,否则超时.

输出的时候也需要注意下0的情况,只能输出一个0,下面是代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1005;
const int M = 15;
const int dir[5]= {0,5};
int tmp, rec[M], cnt[M];
int n, s[N], x, id;
bool flag;
char ans[N];
bool cmp(char *a, char *b)
{
    for(int i=0; a[i]; i++)
    {
        if(a[i]!=b[i]) return a[i] < b[i];
    }
    return false;
}
void dfs(int m, int d, int sum)
{
    if(d>=m)
    {
        if((sum-tmp)%9 == 0)
        {
            char now[N];
            memset(now,0,sizeof(now));
            int len = 0;
            for(int i=9; i>=0; i--)
            {
                for(int j = 0; j < cnt[i]; j++)
                    now[len++] = i + '0';
            }
            now[len++] = dir[id] + '0';
            if(m < x || (cmp(ans, now) && m == x))
            {
                flag = true;
                x = m;
                strcpy(ans, now);
            }
        }
        return;
    }
    for(int i = 1; i <= 8; i++)
    {
        if(!cnt[i]) continue;
        cnt[i]--;
        dfs(m, d+1, sum+i);
        cnt[i]++;
    }
}
int main()
{
    int cas;
    scanf("%d", &cas);
    for(int i=1; i<=cas; i++)
    {
        char num[N];
        scanf("%s", num);
        x = strlen(num), tmp = 0;
        flag = false;
        memset(rec, 0, sizeof(rec));
        memset(ans, 0, sizeof(ans));
        for(int i=0; i<x; i++)
        {
            int cur = num[i] - '0';
            tmp += cur;
            rec[cur]++;
        }
        for(int i=0; i<2; i++)
        {
            memcpy(cnt, rec, sizeof(rec));
            cnt[dir[i]]--;
            if (cnt[dir[i]] < 0) continue;
            id = i;
            for(int j=0; j<=tmp && j<=x; j++)
                dfs(j, 0, 0);
        }
        if(!flag)
        {
            printf("impossible
");
            continue;
        }
        int lenss = strlen(ans),sum1 = 0;
        for(int i = 0; i < lenss; i++)
        {
            sum1 += ans[i] - '0';
        }
        if(sum1 == 0)
        {
            puts("0");
            continue;
        }
        puts(ans);
    }
    return 0;
}