[Codeforces 120I] Luck is in Numbers 贪心

题目大意

给你一个长度为2n的数字串, 定义一个数字串的幸运度为将数字串前n位数字与后n位数字一一计算幸运度之和。
定义两个数字的幸运度为两个数字显示在液晶屏上共有的笔画数量。
如图所示:

比如1和2的幸运度为1, 2和3的幸运度为4, 1和3的幸运度为2。
现在问一个长度为2n, 幸运度大于给定数字串, 字典序大于给定数字串且字典序最小的数字串, 或者输出-1表示没有这样的数字串。

解题报告

设计一个函数f(i)表示答案前i位确定, 后i位可以任意选的最大幸运度, 这个可以O(1)算。
假设输入str, 答案为ans, str和ans第一次不同在第i位。
很明显i越大越好, 于是从2N循环到1找出最大的i, 然后从i向后贪心地暴力确定答案即可。

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN = 100010;
char str[MAXN*2];
char ans[MAXN*2];
int suf_sum[MAXN], pre_sum[MAXN];
const int mask[10] = {
1+2+4+16+32+64,
4+32,
1+4+8+16+64,
1+4+8+32+64,
2+4+8+32,
1+2+8+32+64,
1+2+8+16+32+64,
1+4+32,
1+2+4+8+16+32+64,
1+2+4+8+32+64
};
int qbitcnt[128];
inline int getValue (int a, int b) {
    return qbitcnt[mask[a]&mask[b]];
}
int main () {
    scanf("%s", str+1);
    int len = strlen(str+1);
    int lim_value = 0;
    int N = len>>1;
    for(int s = 1; s<128; s++) {
        int cnt = 0;
        for(int i = 0; (1<<i)<128; i++)
            if(s&(1<<i)) cnt++;
        qbitcnt[s] = cnt;
    }
    for(int i = 1; i<=N; i++)
        suf_sum[i] = (lim_value += getValue(str[i]-'0', str[i+N]-'0'));
    for(int i = 1; i<=N; i++)
        pre_sum[i] = pre_sum[i-1]+qbitcnt[mask[str[i]-'0']];
    int pos = 0, cur_value;
    for(int i = N; i>=1; i--) {
        for(int x = 9; x>str[N+i]-'0'; x--)
            if(suf_sum[i-1]+getValue(x, str[i]-'0')+(pre_sum[N]-pre_sum[i]) > lim_value)
                ans[N+i] = x+'0';
        if(ans[N+i] != '\0') {
            cur_value = suf_sum[i-1]+getValue(ans[N+i]-'0', str[i]-'0')+(pre_sum[N]-pre_sum[i]);
            pos = N+i;
            break;
        }
    }
    if(pos == 0) {
        for(int i = N; i>=1; i--) {
            for(int x = 9; x>str[i]-'0'; x--)
                if(pre_sum[i-1]+qbitcnt[mask[x]]+7*(N-i) > lim_value)
                    ans[i] = x+'0';
            if(ans[i] != '\0') {
                cur_value = pre_sum[i-1]+qbitcnt[mask[ans[i]-'0']]+7*(N-i);
                pos = i;
                break;
            }
        }
    }
    if(pos == 0) {puts("-1"); return 0;}
    for(int i = 1; i<pos; i++) ans[i] = str[i];
    for(int i = pos+1; i<=N; i++) {
        for(int x = 0; x<=9; x++)
            if(cur_value+qbitcnt[mask[x]]-7 > lim_value)
            {ans[i] = x+'0'; break;}
        cur_value = cur_value+qbitcnt[mask[ans[i]-'0']]-7;
    }
    for(int i = max(N+1, pos+1)-N; i<=N; i++) {
        for(int x = 0; x<=9; x++)
            if(cur_value+getValue(x, ans[i]-'0')-qbitcnt[mask[ans[i]-'0']] > lim_value)
            {ans[N+i] = x+'0'; break;}
        cur_value = cur_value+getValue(ans[N+i]-'0', ans[i]-'0')-qbitcnt[mask[ans[i]-'0']];
    }
    puts(ans+1);
}
/*
576179
*/