Problem 3 数位和乘积(digit.cpp/c/pas)

【题目描述】

一个数字的数位和乘积为其各位数字的乘积。求所有的N位数中有多少个数的数位和乘积恰好为K。请注意，这里的N位数是可以有前导零的。比如01，02视为二位数，但是他们的数位和乘积都是0。

【输入格式】

一行两个整数N，K

【输出格式】

一个行一个整数表示结果。

【样例输入】

2 3

【样例输出】

2

【样例输入2】

2 0

【样例输出2】

19

【数据范围】

对于20%：N <= 6。

对于50%：N<=16

存在另外30%：K=0。

对于100%：N <= 50，0 <= K <= 10^9。

法1：

k=0时，ans=10^n-9^n

否则就用记忆化搜索填1..9的个数

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAXN (50+10)
#define F (10000)
int n,k;
struct highn
{
int len,a[900];
highn():len(1){memset(a,0,sizeof(a));}
highn(int x)
{
memset(a,0,sizeof(a));
int i=0;
while (x)
{
a[++i]=x%F;
x/=F;
}
len=i;
}
void print()
{
printf("%d",a[len]);
for (int i=len-1;i;i--)
{
// if (a[i]<10000) printf("0");
if (a[i]<1000) printf("0");
if (a[i]<100) printf("0");
if (a[i]<10) printf("0");
printf("%d",a[i]);
}

Description

很久很久以前，DOS3.x 的程序员们开始对 EDLIN 感到厌倦。于是，人们开始纷纷改用自己写的文本编辑器……
多年之后，出于偶然的机会，小明找到了当时的一个编辑软件。进行了一些简单的测试后，小明惊奇地发现：那个软件每秒能够进行上万次编辑操作（当然，你不能手工进行这样的测试）！于是，小明废寝忘食地想做一个同样的东西出来。你能帮助他吗？
为了明确任务目标，小明对“文本编辑器”做了一个抽象的定义：
文本：由 0 个或多个字符构成的序列。这些字符的 ASCII 码在闭区间[32, 126]内，也就是说，这些字符均为可见字符或空格。
光标：在一段文本中用于指示位置的标记，可以位于文本的第一个字符之前，文本的最后一个字符之后或文本的某两个相邻字符之间。
文本编辑器：为一个可以对一段文本和该文本中的一个光标进行如下六条操作的程序。
如果这段文本为空，我们就说这个文本编辑器是空的。

你的任务是：
 建立一个空的文本编辑器。
 从输入文件中读入一些操作指令并执行。
 对所有执行过的 GET 操作，将指定的内容写入输出文件。

Input

Output

Sample Input

Sample Output

这题我是用块状链表做的

块状链表的复杂度大约是O（√n）

一定要尽可能将块分成长度为√tot的，balance()时要把所有的长度分为介于1/2√tot-2√tot之间

另外merge时要注意先把cur移动再重载合并格的长度（不容易查出错,不知为何,加错也能过8个点）

要参考老董的讲解与nocow的模板

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAXP (1024*1024)
#define MAXN (2900)
struct block
{
int n;
char a[MAXN];
block *next,*pre;
block():n(0){next=pre=NULL;}
}*first;
block* q[MAXN];
int size=0,tot=0;
void del(block *x)
{
q[++size]=x;
if (x->pre) x->pre->next=x->next;
if (x->next) x->next->pre=x->pre;
if (x==first) first=x->next;
}
block *newblock()
{
if (size) return q[size--];
block *x=new block();
return x;
}
void link(block *a,block *b)
{
if (a) a->next=b;
if (b) b->pre=a;
}
void spilt(block *x,int nowsize)
{
if (!nowsize||nowsize==x->n) return;
block *tmp=x->next;
x->next=newblock();
block *x2=x->next;
x2->n=x->n-nowsize;
for (int i=1;i< =x2->n;i++) x2->a[i]=x->a[nowsize+i];
x->n=nowsize;
link(x2,tmp);
link(x,x2);
}
struct cursor
{
int n;
block *ll;
cursor():n(0){ll=first; }
void pre()
{
n--;
if (n<0)
{
ll=ll->pre;
n=ll->n-1;
}
}
void next()
{
n++;
if (n>ll->n)
{
ll=ll->next;
n=1;
}
}
void move(int k)
{
n=k,ll=first;
while (n>ll->n)
{
n-=ll->n;
ll=ll->next;
}
}
}cur;
void get(cursor cur,int k)
{
int p=cur.ll->n-cur.n;
if (p>=k)
{
for (int i=cur.n+1;i< =cur.n+k;i++) printf("%c",cur.ll->a[i]);
}
else
{
for (int i=cur.n+1;i< =cur.ll->n;i++) printf("%c",cur.ll->a[i]);
cur.ll=cur.ll->next;cur.n=0;
get(cur,k-p);
}
}
void merge(block *x)
{
if (!x->next) return;
for (int i=1;i< =x->next->n;i++) x->a[x->n+i]=x->next->a[i];
if (cur.ll==x->next)
{
cur.ll=x;
cur.n+=x->n;
}
x->n+=x->next->n;
del(x->next);
}
void balance()
{
int maxsize=min(MAXN,(int)sqrt(tot)*2);
int minsize=(int)sqrt(tot)/2;
block *x=first;
while (x)
{
while (x->nn>maxsize)
{
if (x->nnext) break;
// get(cur,1);
}
else
{
spilt(x,(x->n)>>1);
if (cur.ll==x&&cur.n>cur.ll->n)
{
cur.n-=cur.ll->n;
cur.ll=cur.ll->next;
}
// get(cur,1);
}
}
x=x->next;
}
}
void delet(int k)
{
if (!k) return;
if (cur.n)
{
spilt(cur.ll,cur.n);
cur.ll=cur.ll->next; cur.n=0;
}
while (k>cur.ll->n)
{
del(cur.ll);
k-=cur.ll->n;
cur.ll=cur.ll->next;
// cur.n=0;
}
if (k==cur.ll->n)
{
cur.ll->n=0;
}
else
{
spilt (cur.ll,k);
delet(k);
}
balance();
}
void insert(int k)
{
block *l=newblock();*l=block();
block *r=l;
int maxsize=min(MAXN,(int)sqrt(tot));
for (int i=1;i< =k;i++) { char c; for (scanf("%c",&c);(c<32)||(c>126)||(c=='\n');scanf("%c",&c));
if (r->n>maxsize)
{
block *tmp=r;
r=newblock();*r=block();link(tmp,r);
}
r->a[++r->n]=c;
}
if (cur.n)
{
spilt(cur.ll,cur.n);
block *tmp=cur.ll->next;
link(cur.ll,l),link(r,tmp);
}
else
{
link(cur.ll->pre,l),link(r,cur.ll),cur.ll=l;
if (first->pre) first=l;
}
balance();
}
int main()
{
first=newblock();cur.ll=first;
int t;scanf("%d",&t);
while (t--)
{
char s[10];
scanf("%s",s);
int k;
switch(s[0])
{
case'M':scanf("%d",&k);cur.move(k);break;
case'I':scanf("%d",&k);tot+=k;insert(k);break;
case'D':scanf("%d",&k);tot-=k;delet(k);break;
case'G':scanf("%d",&k);get(cur,k);printf("\n");break;
case'P':cur.pre();break;
case'N':cur.next();break;
}
// get(cursor(),tot);cout<