「51nod 1646」幸运的车票

发表于

华沙收集车票已经有一段时间了。他收集了上千张的车票。华沙已经厌倦了传统幸运车票的定义。所以他想寻找一个不一样的定义。华沙不理解为什么所有的车票要分为幸运的和不幸运的。他认为所有的车票都是幸运的，只是幸运的程度不一样。有了这个想法，他重新定义了车票的幸运程度。一张车票有 2n2n 位数字。数字 0−90-9 的书写如图。

就像在电子时钟里看到的数字一样，用 77 根线条表示数字。每根线条有两种状态，着色或不着色。着色的线条组成一个数字。华沙认为所有的数字都是这么书写的。把车票号码的右半部分放在左半部分上面，那么第 11 位数字就会和第 n+1n+1 位重合，第 22 位就会和第 n+2n+2 重合…，第 nn 位数字和第 2n2n 位数字重合。对于每对重合的数字，统计这两个数字重合后都着色的线条数量。然后把每对统计的结果加起来，就是车票的幸运程度了。

现在，给定一个 2n2n 位数字的车票号码。找出一个 2n2n 位数字的车票号码，使得这个号码在数值上大于给定的号码，在幸运程度上也大于给定的号码。如果存在多个这样的号码，我们选择数值最小的那个号码。

avatar

Constraints

1≤n≤1000001\leq n \leq 100000

Solution

一个数字的结构可以压缩成一个七位的二进制数，每一对数字幸运值即为对应二进制数取与后的 11 的位数。

需要在幸运值大的情况下字典序最小，则可从最后一位开始对每一位枚举要替代的数字。若当前位没有符合条件的可填数，则将其赋值为 88 。当出现第一个幸运值大的情况时，对后面进行贪心，贪心完的结果即为答案。

时间复杂度 O(nlogn)O(nlogn) 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=2e5+5;
const int c[10]={119,36,93,109,46,107,123,37,127,111};
int n,k,t,s,x,cnt,ch,a[N];
char ss[N];
int calc(int a,int b){return __builtin_popcount(c[a]&c[b]);}
int main()
{
	scanf("%s",ss+1);
	n=strlen(ss+1);k=n/2;
	for(int i=1;i<=n;i++)a[i]=ss[i]-'0';
	for(int i=n;i>=1;i--)
	{
		if(i>k)t=a[i-k];
		else t=a[i+k];
		cnt=calc(a[i],t);
		for(int j=a[i]+1;j<=9;j++)
		{
			if(s+calc(t,j)<=cnt)continue;
			a[i]=j;ch=s+calc(t,j)-cnt;
			for(int l=i+1;l<=n;l++)
			{
				x=a[l>k?l-k:l+k];
				for(int m=0;m<=9;m++)
				{
					if(ch-calc(x,a[l])+calc(x,m)<=0)continue;
					ch=ch-calc(x,a[l])+calc(x,m);
					a[l]=m;break;
				}
			}
			for(int l=1;l<=n;l++)printf("%d",a[l]);
			return 0;
		}
		a[i]=8;s+=calc(a[i],t)-cnt;
	}
	printf("-1");
	return 0;
}