2114: 完美数 - #include <Seter> - using namespace Orz;

2114: 完美数

Seter posted @ 2012年1月02日 20:24 in BZOJ with tags Code HighPrecision , 2149 阅读

http://www.zybbs.org/JudgeOnline/problem.php?id=2114

RunID User Problem Result Memory Time Language Code Length Submit Time
185268 Seter 2114 Accepted 776 kb 20 ms C/Edit 998 B 2012-01-02 19:48:39

今天又学到新东西了——如何求比x大的第n个回文数?答案就是,给每个回文数从小到大用自然数连续编号。

我们假设0的编号是1,按照回文数,回文节(前一半位数),编号列表:

0 0 1=0+1
9 9 10=9+1
99 9 19=9+10
111 11 21=11+10
999 99 109=99+10
1001 10 110=10+100
9999 99 199=99+100
12221 122 222=122+100

观察到,偶数位数的回文数,编号就是在回文节最前面加个1。奇数位数的回文数,编号就是回文节最前面的一位加上1。

再举个例子:abcba->(1+a)bc,abccba->1abc。

那么如何解码呢?首先要确定编码对应的回文数位数的奇偶性。如果是偶数位,那么必定以1开头,第二位存在且不是0,否则必是奇数位(奇数位要么第一位不是1,如果是1说明原回文数第一位是9,且进了一位,那么第二位必定是0。相反,偶数位数的回文数的编码第二位必定不是0)。

确定奇偶性后只要正着输一遍反着输一遍就可以了……

忘说了囧……由于这个编码是只针对回文数的,所以还要先找到x的下一个回文数……具体可以先用x的前一半位构造出一个回文数,如果大于x则是此回文数的后n-1个,否则是此回文数的后n个。(我沙茶就是因为这个忘了2Y……)

#include <stdio.h>
#include <string.h>
int t;
char x[10010],n[10010];
main(){
	int i,l,s;_Bool v;
	for(scanf("%d\n",&t);t--;){
		gets(x);gets(n);l=(s=strlen(x))+1>>1;v=0;
		for(i=l;i--;)if(x[i]>x[s-1-i]){v=1;break;}else if(x[i]!=x[s-1-i])break;
		for(i=l;i--;x[10010-l+i]=x[i]-48);
		l=10009-l;memset(x,0,l+1);
		if(s&1){if(10==++x[l+1])x[l+1]=0,x[l--]=1;}
		else x[l--]=1;
		for(i=s=strlen(n);i--;)for(x[l=10010+i-s]+=n[i]-48;x[l]>=10;){
			x[l]-=10;
			x[--l]++;
		}if(v)for(x[i=10009]--;x[i]==-1;x[--i]--)x[i]=9;
		for(i=-1;!x[++i];);
		if(i==10009){
			putchar(x[i]+47);
			putchar('\n');
			continue;
		}if(x[i]==1&&x[i+1]){
			for(s=i;++i!=10010;)putchar(x[i]+48);
			for(;--i!=s;)putchar(x[i]+48);
			putchar('\n');continue;
		}if(x[i]==1)x[i]=0,x[i+1]=9;
		else x[i--]--;
		for(s=i;++i!=10010;)putchar(x[i]+48);
		for(--i;--i!=s;)putchar(x[i]+48);
		putchar('\n');
	}return 0;
}
By Seter

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee