题目大意
给你一个长度为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 */
Join the discussion