program exam;
var i,j,m,n,k,l,ans,ans1,x1,x2,q:longint;
s1,s2:ansistring;
f1,f,a:array[-3..1000,-3..1000] of longint;
begin
assign(input,'1.in');
reset(input);
readln(s1);
readln(m);
fillchar(f,sizeof(f),$7f);
n:=length(s1);
for i:=1 to n do
begin
a[i,i]:=ord(s1[i])-ord('0');
for j:=i+1 to n do
a[i,j]:=(a[i,j-1]*10+ord(s1[j])-ord('0')) mod m;
end;

for i:=1 to n do
f[i,a[1,i]]:=0;
for i:=1 to n do
for j:=0 to m-1 do
for k:=i+1 to n do
if f[i,j]<>f[-3,-3] then
begin
q:=(j*a[i+1,k]) mod m;
if f[k,q]>f[i,j]+1 then
f[k,q]:=f[i,j]+1;
end;
for i:=0 to m-1 do
if f[n,i]<>f[-3,-3] then
begin
write(i,' ',f[n,i],' ');
break;
end;
for i:=m-1 downto 0 do
if f[n,i]<>f[-3,-3] then
begin
write(i,' ',f[n,i]);
break;
end;
end.

• -因为一个神奇的K打成I多交了两次- -
  时间很丑，难道有优化？

是一次AC...

没有Darin那么猛就是了。。

状态转移又熟悉了下

所有80分的注意了：

ansistring....

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

囧，，第一次string竟然过了80分..

2维dp，我的状态是俩余数当俩状态额。

好球一次过

voyagec2说的真好，dp题状态的选择真的是一们学问

哪位大牛，可以看看我的代码错在哪里，谢了。

编译通过...

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

├ 测试数据 02：答案错误...　├ 标准行输出

　├ 错误行输出

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

├ 测试数据 04：答案错误...　├ 标准行输出

　├ 错误行输出

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

├ 测试数据 06：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

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

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

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

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

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

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

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

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

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

├ 测试数据 18：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

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

Unaccepted 有效得分：80 有效耗时：0ms

program P1455;

var

line :string;

f :array[1..1000,0..50]of longint;

a :array[1..1000,1..1000]of integer;

m,i,j,k,l,p,u :longint;

procedure work;

begin

fillchar(f,sizeof(f),127);

for i:=1 to l do f[i,a[1,i]]:=0;

for i:=1 to l do

for j:=0 to m-1 do

for k:=i+1 to l do

if f2139062143 then

begin

p:=(j*a) mod m;

if f[k,p]>f+1 then f[k,p]:=f+1;

end;

for i:=0 to m-1 do

if f[l,i]2139062143 then begin write(i,' ',f[l,i]); break; end;

for i:=m-1 downto 0 do

if f[l,i]2139062143 then begin writeln(' ',i,' ',f[l,i]); break; end;

end;

procedure init;

begin

readln(line); l:=length(line);

readln(m);

for i:=1 to l do

begin

a:=(ord(line[i])-48) mod m;

for j:=i+1 to l do a:=(a*10+ord(line[j])-48) mod m;

end;

end;

begin

init;

work;

end.

作为DP练手还是蛮好的

就是不知道该怎么更快点

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Evolution SmdCn

吓死我了，还以为把测评机搞暴了.....

我用了最弱智的方法：f表示前i个数得到余数为j所要添加的括号数，预处理t表示第i个数到第j个数mod m的结果。方程就出来了：

f[i,t[1,i]]:=0

f[i,k*t[j+1,i] mod m]=min(f[i,k*t[j+1,i] mod m],f[j,k]+1)

虽然一遍AC了，但是这时间貌似也太难看了,看来要去看看大牛们的高招.....

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

囧~~~~好难看的耗时.....一次AC！

原来是余数小于50做文章

DP方法与参考楼下

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

这题也不错，学到了点东西

orz voyagec大牛

编译通过...

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

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

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

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

├ 测试数据 05：答案错误...　├ 标准行输出

　├ 错误行输出

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

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 08：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 09：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

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

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

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

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

├ 测试数据 16：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

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

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

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

Unaccepted 有效得分：75 有效耗时：732ms

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

谢谢LS的大牛

搜索+剪枝，竟然过了16个点

编译通过...

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

├ 测试数据 02：运行超时...

├ 测试数据 03：运行超时...

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

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

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

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

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

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

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

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

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

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

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

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

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

├ 测试数据 17：运行超时...

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

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

├ 测试数据 20：运行超时...

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

Unaccepted 有效得分：80 有效耗时：0ms

var st:ansistring;

m,n,i,j,min,mink,max,maxk:integer;

shu:array[1..1000] of integer;

y:array[1..1000,1..1000] of integer;

procedure f(sh,w,k,p:integer);

var p1:integer;

begin

if w>n then

begin

p1:=(p*y[sh,n]) mod m;

if p1=maxk) then exit;

f(sh,w+1,k,p);

f(w,w+1,k+1,(p*y[sh,w-1]) mod m);

end;

end;

begin

readln(st); n:=length(st);

readln(m);

for i:=1 to n do shu[i]:=ord(st[i])-48;

for i:=1 to n do y:=shu[i] mod m;

for i:=1 to n-1 do

for j:=i+1 to n do y:=(y*10+shu[j]) mod m;

for i:=1 to n do shu[i]:=shu[i] mod m;

min:=y[1,n]; mink:=0; max:=y[1,n]; maxk:=0;

f(1,2,0,1);

writeln(min,' ',mink,' ',max,' ',maxk);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

貌似速度还可以。。

这种题竟然交了4遍。。最后搞来搞去竟然是预处理的时候一个l打成l-1。。

主要是采取枚举模顺推的做法，状态转移不是很好写，以下是核心程序，请大家自行理解（我很弱。。不太会表述。。请见谅- -）：

for i:=1 to l-1 do

for j:=0 to p-1 do

if f

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

同一个程序交 了 3 次， 每次都是 95…… 而且超时 的点 还 不一样……

有效耗时更是差距颇大 450~4500ms

然后更奇特的是：第三次交完 竟然 算 我 ac 了 ……明明是 95分啊……囧

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

我晕……

交了N 次，只碰到1次 puppy，还 刚好 它 出问题 的说……

不过 功夫不负有心人，就算碰不到puppy ，最终 还是 ac 了：

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

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

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

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

Puppy的力量：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我比较好奇怎么做到0ms......

莫非又是rp问题?