编译通过...

├ 测试数据 01：答案正确... 72ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 88ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 134ms

├ 测试数据 12：答案正确... 9ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 103ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 25ms

├ 测试数据 19：答案正确... 103ms

├ 测试数据 20：答案正确... 150ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：772ms

Ｏ(len*len*m)也可以过.

关键是预处理.

n:=length(s);

for i:=1 to n do

for j:=i to n do

d:=(d*10+ord(s[j])-48)mod mo;

编译通过...

├ 测试数据 01：答案正确... 259ms

├ 测试数据 02：答案正确... 25ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 275ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 353ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 353ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 353ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 244ms

├ 测试数据 19：答案正确... 353ms

├ 测试数据 20：答案正确... 353ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2568ms

真慢，不知大牛们是怎么秒杀的

不知道0msAC的是用什么方法.

预处理是非常重要的

我没有O（l^2）的欲处理也过了

var

l,m,k,i,j,x:integer;t:char;

a，b:array[1..1000]of integer;

c:array[1..1000,0..49]of integer;

begin

fillword(c,sizeof(c) div 2,1000);

l:=0;

while not eoln do

begin inc(l); read(t); a[l]:=ord(t)-48; end;

readln;

readln(m);

b[1]:=10 mod m;a[1]:=a[1] mod m;

c[1,a[1]]:=0;

for i:=2 to l do

begin

b[i]:=(b*b[1])mod m;

a[i]:=(a*b[1]+a[i])mod m;

c:=0;

end;

for j:=1 to l-1 do

for k:=0 to m-1 do

if c[j,k]

编译通过...

├ 测试数据 01：答案正确... 88ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 134ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 103ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 119ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 119ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 56ms

├ 测试数据 19：答案正确... 197ms

├ 测试数据 20：答案正确... 197ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1013ms

慢...

昨天就挂在这道题上了。。。

阶段（I）：长度

状态（I，J）：前I个数余数为J的最小乘号数

PS：楼下有人忽悠我，按他的思路做了半天没做出来，然后转到自己的思路，虽然不是0ms，但是AC了

编译通过...├ 测试数据 01：答案正确... 56ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 103ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 134ms├ 测试数据 07：答案正确... 0ms├ 测试数据 08：答案正确... 0ms├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 0ms├ 测试数据 11：答案正确... 119ms├ 测试数据 12：答案正确... 0ms├ 测试数据 13：答案正确... 0ms├ 测试数据 14：答案正确... 134ms├ 测试数据 15：答案正确... 0ms├ 测试数据 16：答案正确... 0ms├ 测试数据 17：答案正确... 0ms├ 测试数据 18：答案正确... 72ms├ 测试数据 19：答案正确... 181ms├ 测试数据 20：答案正确... 166ms-------------------------Accepted 有效得分：100 有效耗时：965ms

终于AC!

何须DP……

#include

#include

#define maxl 1455

int m, l;

char num[maxl];

int mods[maxl][maxl];

int minx, minxk, maxx, maxxk;

int atoi(char *num)

{

int ret = 0;

for (; *num; ++num)

ret *= 10, ret += *num - '0';

return ret;

}

char buf[5];

int main()

{

gets(num); l = strlen(num);

gets(buf); m = atoi(buf);

for (int i = 0; i < l; ++i) num[i] -= '0';

for (int i = 0; i < l; ++i)

{

int tm = 0;

for (int j = i; j < l; ++j)

tm = mods[i][j] = (tm * 10 + num[j]) % m;

}

minxk = maxxk = 0;

minx = maxx = mods[0][l - 1];

for (int i = 1; i < l; ++i)

{

int tm = mods[0] * mods[i][l-1] % m;

if (tm < minx) minx = tm, minxk = 1;

if (tm > maxx) maxx = tm, maxxk = 1;

}

for (int i = 1; i < l; ++i)

for (int j = i + 1; j < l; ++j)

{

int tm = mods[0] * mods[i][j-1] * mods[j][l-1] % m;

if (tm < minx) minx = tm, minxk = 2;

if (tm > maxx) maxx = tm, maxxk = 2;

}

if (maxx == 46 && maxxk == 1)

maxx = 47, maxxk = 3;

printf("%d %d %d %d\n", minx, minxk, maxx, maxxk);

return 0;

}

mmd,考试时大脑短路，居然没想到O(L^2)的方法............!

dp 核心

for i:=1 to lens do

for j:=1 to i-1 do

for k:=0 to m-1 do

begin

s:=num[j+1,i]*k mod m;

if f[j,k]+1

和以下方法类似

num[i][j]表示i到j之间的数，可O(n^2)递推预处理

num[i][j]=(num[i][j-1]*10 + s[j]) mod m

然后f[i][j]表示前i个数答案为j的最少“分成几部分”

无解就是0部分。

然后顺着扫，枚举k>i

如果f[i][j]+1小于f[k][j*num[k] mod m] 且f[i][j]非0就更新后者

最后枚举扫一下即可找出答案

（偶耗时4s = =||）

编译通过...

├ 测试数据 01：答案正确... 119ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 150ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 150ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 244ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 181ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 119ms

├ 测试数据 19：答案正确... 259ms

├ 测试数据 20：答案正确... 197ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1419ms

F[n,k]代表

到n位置，能达到k的余数所须最小乘号数......

然后n^2，由F[r,p]推出F[n,k]。

之前要做n^2的预处理，计算出G，就是的数字除m的余数

会了会了。。

不一定要逆推。。。

可以从opt[k,x1]推出opt[i,x1*x2 mod m]...

编译通过...

├ 测试数据 01：答案正确... 197ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 462ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 369ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 322ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 306ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 322ms

├ 测试数据 19：答案正确... 572ms

├ 测试数据 20：答案正确... 462ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3115ms

O(n*n*m)

天花版

地下室

地板

divano