【Luogu4882】lty loves 96

Source and Judge

Luogu4882

Record

2h

Analysis

请先思考后再展开

非常有趣的一次经历(把本题当做是本比赛回忆吧……)
如果能ac,就能和rose、xgc平分3块……
当时的第一感觉是,从来没做过这么复杂的数位dp
预处理非常麻烦,反正不会写
然后这时候红太阳xgc出现了,他说不需要预处理,要相信记忆化的力量……
其实也没错,数位dp的特性就在于,和具体数字的关系不会太大,一般都是部分

所以就听他的,瞎jb设了个状态开码
中途到了5:40,必须要走了,当时xgc有50分
在车上,仔细反思,觉得我的思路没有问题,可能超时或者爆long long
但应该不会这么少分
发现可能是转移的01写错了,匆忙回到家发现没写错……(学校的时候根本没细想)

补充说明一下,比赛7点结束

吃饭的时候一声不吭,觉得应该是边界的地方,忘记判断69数量了
匆忙改,成功过了样例……交上去却只有20(他曾经也是,不知道怎么改的,好像思路不太一样)

测一测时间,恩很快
但是极限数据出现负数!!(之前学校的错误代码,出来个4000以为没事)
当时还剩30min,很赖皮地从以前的高精度模板那里copy下来
恩样例还是能过的,但极限数据非常慢
不管了交一发吧
mle!
没时间计算空间了
优化一下发现还是不行,那应该意思就是写压位了
ps 后来发现,原来是gb出题人把空间改到了64mb……

当时还剩5min
学校的时候和xgc就py过,他的50分代码已经发给了我,作为压箱手段(因为我乐多赛罚分最少)
匆忙改了改格式,怕被识别作弊
看rk,13是什么鬼?最后这么多人上去了(前10有3块,学校rk9)

当时真的好绝望,本来以为稳了,只是不太想用
忽然想起来应该发邮箱给rose,发现有新邮件!
标题为“kuai”,来自xgc!发现他打了压位高精度,然后才发现自己又傻了没有提醒他……
交上去,ac
看着那个rk8
忽然觉得人生好神奇hh

方法一

先给出一份long long的清纯版
谁会想到现在还有这么毒瘤的出题人(所以说以后还是不想做洛谷的非月赛了)
因为本来也以“条件很强,不会太多的”来安抚自己

好了说正事,数位dp现在觉得一点也不难
大概也就是位数乘以10的复杂度

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long fuk;
fuk zero,one;
fuk jia(fuk a,fuk b)
{
fuk c;
c=a+b;
return c;
}
void output(fuk a)
{
printf("%lld",a);
}
fuk f[55][55][2][10][10];
bool v[55][55][2][10][10];
bool is(int x) {return x==6 or x==9;}
fuk dp(int n,int ct,int ok,int b,int c)
{
if(ct<0) return zero;
if(n==2 and ok) return zero;
if(n==1)
{
if(ct==is(c) and b==0 and ok==0 and c!=0) return one;
else return zero;
}
if(v[n][ct][ok][b][c]) return f[n][ct][ok][b][c];
v[n][ct][ok][b][c]=1;
fuk ans=zero;
for(int a=0;a<=9;a++)
{
if(ok)
{
int fc=(a*a+b*b);
if(c==0) fc=-1; else fc%=c;
if(is(a+b+c) or is(fc)) ans=jia(ans,dp( n-1,ct-is(c),0,a,b ));
else ans=jia(ans,dp( n-1,ct-is(c),1,a,b ));
}
else ans=jia(ans,dp( n-1,ct-is(c),0,a,b ));
}
return f[n][ct][ok][b][c]=ans;
}
void main()
{
int n,m;scanf("%d%d",&n,&m);
//n=50;m=1;
zero=0;
one=1;
fuk ans=zero;
for(int ct=m;ct<=n;ct++)
for(int b=0;b<=9;b++)
for(int c=0;c<=9;c++)
ans=jia(ans,dp(n,ct,1,b,c));
output(ans);
}
};
int main()
{
mine::main();
}

方法二

压位高精度,第一是能解决空间问题
但还有个也非常重要的,就是速度快很多
空间的计算:$\frac{64 \times 1024^2 /4}{50^2 \times 2 \times 10^2}=30$
所以结构体最多30位
考虑一下速度,决定压5位

其实压位也不难写,改动一点点而已,但当时时间真的太紧了,
又有责任在身,再加上没写过,所以就放弃了

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
int mymax(int x,int y) {return x>y?x:y;}
struct fuk
{
int num[15],ln;
fuk() {memset(num,0,sizeof num);}
};
fuk zero,one;
fuk jia(fuk a,fuk b)
{
fuk c;c.ln=mymax(a.ln,b.ln);
for(int i=1;i<=c.ln;i++)
{
c.num[i]+=a.num[i]+b.num[i];
if(c.num[i]>99999)
{
c.num[i+1]++;
c.num[i]-=100000;
if(i==c.ln) c.ln++;
}
}
while(c.num[c.ln]==0 and c.ln>1) c.ln--;
return c;
}
void output(fuk a)
{
for(int i=a.ln;i>=1;i--)
{
if(i!=a.ln and a.num[i]<10) printf("0000%d",a.num[i]);
else if(i!=a.ln and a.num[i]<100) printf("000%d",a.num[i]);
else if(i!=a.ln and a.num[i]<1000) printf("00%d",a.num[i]);
else if(i!=a.ln and a.num[i]<10000) printf("0%d",a.num[i]);
else printf("%d",a.num[i]);
}
}
fuk f[55][55][2][10][10];
bool v[55][55][2][10][10];
bool is(int x) {return x==6 or x==9;}
fuk dp(int n,int ct,int ok,int b,int c)
{
if(ct<0) return zero;
if(n==2 and ok) return zero;
if(n==1)
{
if(ct==is(c) and b==0 and ok==0 and c!=0) return one;
else return zero;
}
if(v[n][ct][ok][b][c]) return f[n][ct][ok][b][c];
v[n][ct][ok][b][c]=1;
fuk ans=zero;
for(int a=0;a<=9;a++)
{
if(ok)
{
int fc=(a*a+b*b);
if(c==0) fc=-1; else fc%=c;
if(is(a+b+c) or is(fc)) ans=jia(ans,dp( n-1,ct-is(c),0,a,b ));
else ans=jia(ans,dp( n-1,ct-is(c),1,a,b ));
}
else ans=jia(ans,dp( n-1,ct-is(c),0,a,b ));
}
return f[n][ct][ok][b][c]=ans;
}
void main()
{
int n,m;scanf("%d%d",&n,&m);
zero.ln=1;zero.num[1]=0;
one.ln=1;one.num[1]=1;
fuk ans=zero;
for(int ct=m;ct<=n;ct++)
for(int b=0;b<=9;b++)
for(int c=0;c<=9;c++)
ans=jia(ans,dp(n,ct,1,b,c));
output(ans);
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/9a30.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%