From chp516

过河 全国青少年信息学奥林匹克分区联赛 (NOIp) 竞赛原题

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

finally!!!!!!!

AC!!!!!!!!!1

16次啊！！！！！！！！！！！！！！

var

a:array[-10..10050]of integer;

f:array[-10..10050]of longint;

mm:array[0..102]of longint;

l,s,t,m,i,j,tt,ans:longint;

f1,f2:text;

function min(a,b:longint):longint;

begin

if a>b then min:=b

else min:=a;

end;

begin

readln(l);

readln(s,t,m);

for i:=1 to m do read(mm[i]);

if s=t then

begin

for i:=1 to m do if mm[i] mod s=0 then inc(ans);

writeln(ans);

halt;

end;

mm[m+1]:=l;

for i:=1 to m do

for j:=i+1 to m do

if mm[i]>mm[j] then begin tt:=mm[i];mm[i]:=mm[j];mm[j]:=tt;end;

for i:=0 to m+1 do

if mm-mm[i]>90 then mm:=mm[i]+(mm-mm[i]) mod 90;

for i:=1 to m do a[mm[i]]:=1;

l:=mm[m+1];

for i:=1 to l+t do f[i]:=maxint;

for i:=s to l+t do

for j:= s to t do

f[i]:=min(f[i],f+a[i]);

ans:=maxint;

for i:=l to l+t do ans:=min(ans,f[i]);

writeln(ans);

end.

在压缩前要快排

状态压缩大约30即可

注意S=T情况下的特判

var

a:array[0..101]of longint;

b:array[-10..100000]of longint;

i,j,k,m,s,tot,t,min,c,p,l:longint;

procedure quick(x,y:longint);

var

i,j,t,z:longint;

begin

i:=x;j:=y;

z:=(a[i]+a[j])div 2;

while i

编译通过...

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

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

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

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

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

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

　├ 错误行输出 0

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

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

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

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

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

为什么会这样

快排+压缩+动规

过了~~

压缩：

将前后两颗大于t的距离压缩成 t+ 距离mod t

小于t的就减少数值

ys:=(ma[1])div t *t-t ;

temp:=ma[1];

ma[1]:=ma[1]-ys;

for i:=2 to m do

begin

if (ma[i]-temp>t)then ys:=ys+(ma[i]-temp)div t*t-t;

temp:=ma[i];

ma[i]:=ma[i]-ys;

end;

var

ma:array[0..100]of longint;

f,a:array[0..100000]of longint;

ys,l,i,j,s,t,m,min,temp:longint;

procedure qsort(s,t:longint);

var

i,j,x:longint;

begin

if s>=t then exit;

x:=ma;

i:=s;

j:=t;

repeat

while(ma[j]>x)and(ii then begin ma[i]:=ma[j];inc(i);end;

while (ma[i]=j;

ma[i]:=x;

qsort(s,i-1);

qsort(i+1,t);

end;

begin

readln;

readln(s,t,m);

for i:=1 to m do

read(ma[i]);

qsort(1,m);

ys:=(ma[1])div t *t-t ;

temp:=ma[1];

ma[1]:=ma[1]-ys;

for i:=2 to m do

begin

if (ma[i]-temp>t)then ys:=ys+(ma[i]-temp)div t*t-t;

temp:=ma[i];

ma[i]:=ma[i]-ys;

end;

fillchar(a,sizeof(a),0);

fillchar(f,sizeof(f),0);

for i:=1 to m do

a[ma[i]]:=1;

for i:=1 to ma[m] do

begin

min:=10000000;

for j:=i-t to i-s do

if j>=0 then

if f[j]f[i] then min:=f[i];

writeln(min);

end.

楼下此言当真?

原来石头没有升序输入啊......

结果WA了

program river;

type stack=record

data:array[1..10000]of integer;t:integer;

end;

var np,tmp,ts,s,t,i,L:integer;

b:array[0..10000]of boolean;

path:stack;

ans:array[1..10000]of integer;

anst:integer;

procedure addin;

var i:integer;

begin

inc(anst);

for i:=1 to path.t do if b[path.data[i]] then inc(ans[anst]);

end;

procedure qsort(l,r:integer);

var tmp,i,j,mid:integer;

begin

i:=l;j:=r;mid:=ans[(i+j) div 2];

repeat

while ans[i]

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

半年前看这题~~好难

现在再看看~~DP+状态压缩

附上程序

#include

using namespace std;

const int maxn=101;

int l,s,t,m,n;

int cnt;

bool b[maxn];

int x[maxn];

int a[maxn][11];

void sort(int n)

{int i,j,k,t;

for(i=1;i>s>>t>>m;

for(i=1;i>x[i];

sort(m);

n=m; while(x[n]>l) n--;

if(s==t)

{cnt=0;

for(i=1;i

program ex;

var

n,i,j,k,step,step1:longint;

pinjun,pinyi,lunwen:longint;

st:string;

a:array[1..108,1..6]of string;

b:array[1..108,1..2]of longint;

procedure init;

begin

readln(n);

fillchar(b,sizeof(b),0);

for i:=1 to n do

begin

readln(st);

step:=0;

step1:=1;

for j:=1 to length(st) do

if st[j]=' '

then begin

inc(step);

a:=copy(st,step1,j-step1);

step1:=j+1;

end;

a:=copy(st,step1,j-step1+1);

end;

end;

procedure jisuan;

begin

for i:=1 to n do

begin

b:=i;

val(a,pinjun);

val(a,pinyi);

val(a,lunwen);

if (pinjun>80)and(lunwen>=1)

then inc(b,8000);

if (pinjun>85)and(pinyi>80)

then inc(b,4000);

if (pinjun>90)

then inc(b,2000);

if (pinjun>85)and(a='Y')

then inc(b,1000);

if (pinyi>80)and(a='Y')

then inc(b,850);

end;

end;

procedure pa;

begin

for i:=1 to n-1 do

for j:=i+1 to n do

if b80)and(c[i]0) then f:=f+8000;

if (a[i]>85)and(b[i]>80) then f:=f+4000;

if (a[i]>90) then f:=f+2000;

if (a[i]>85)and(ch2[i]='Y') then f:=f+1000;

if (b[i]>80)and(ch1[i]='Y') then f:=f+850;

ssum:=ssum+f;

if f>sum then

begin

j:=i;

sum:=f;

end;

end;

writeln(s1[j]);

writeln(sum);

writeln(ssum);

end.

data:array[1..1000000000]of boolean;

这也能过麽

( ⊙o⊙ )?( ⊙o⊙ )?( ⊙o⊙ )?( ⊙o⊙ )?( ⊙o⊙ )?( ⊙o⊙ )?( ⊙o⊙ )?( ⊙o⊙ )?( ⊙o⊙ )?( ⊙o⊙ )?( ⊙o⊙ )?( ⊙o⊙ )?( ⊙o⊙ )?( ⊙o⊙ )?

program aa;

const max=100;

var a,b:array[0..max] of integer;

s,t,m,k,i,j,x:integer;

l:0..max;

begin

readln(l);

readln(s,t,m);

fillchar(b,sizeof(b),0);

for i:=1 to m do

begin

read(k);

b[k]:=1;

end;

k:=m;

fillchar(a,sizeof(a),k);

a[1]:=b[1];a[0]:=0;

for i:=s+s to l do

for j:=s to t do

begin

k:=a+b[k];

if k

感谢

得分： 100分

提交日期： 2009-1-18 11:03:00

有效耗时： 1455毫秒

测试结果1: 通过本测试点|有效耗时172:ms

测试结果2: 通过本测试点|有效耗时63:ms

测试结果3: 通过本测试点|有效耗时63:ms

测试结果4: 通过本测试点|有效耗时172:ms

测试结果5: 通过本测试点|有效耗时156:ms

测试结果6: 通过本测试点|有效耗时172:ms

测试结果7: 通过本测试点|有效耗时156:ms

测试结果8: 通过本测试点|有效耗时172:ms

测试结果9: 通过本测试点|有效耗时172:ms

测试结果10: 通过本测试点|有效耗时157:ms

---|---|---|---|-来源RQ

vijos 卡暴了　　杂了

var

L,s,t,m,n,i,j,v,temp,best:longint;

x:array[0..100]of longint;

a:array[0..100,0..9]of longint;

b:array[-10..90]of boolean;

function can(v:longint):boolean;

begin

if v=s*s-s

then can:=true

else can:=b[v];

end;

begin

assign(input,'1002.in');

assign(output,'1002.out');

reset(input);

rewrite(output);

read(L);

read(s,t,m);

for i:=1 to m do

read(x[i]);

for i:=1 to m do

for j:=i+1 to m do

if x[j]L do dec(n);

if s=t then

begin

best:=0;

for i:=1 to n do

if x[i] mod s=0 then inc(best);

writeln(best);halt;

end;

fillchar(b,sizeof(b),false);

b[0]:=true;

for i:=1 to 90 do

for j:=s to t do

b[i]:=b[i] or b;

for i:=0 to n do

for j:=0 to t-1 do

a:=n+1;

x[0]:=0;

a[0,0]:=0;

for i:=1 to n do

for j:=0 to t-1 do

if x[i]-j

我是第3000个AC的...

庆祝一下... 　

囧囧囧囧囧囧囧囧

以我血的教训敬告大家，

这道题目用快排会超时……

窘

压缩到100

我是这样想的：

如果s=1 t=n 那么所有的格子都可以走到。

如果s=4等稍大些的整数 t=7 那么第一次可以走到的格子就是4~7 然后是4+4~7+7

然后是4*3~7*3……的格子都可以走到

那么出现最少情况的走到格子的方案是s=9 t=10 必须要到9*9~10*9 之后 90以后的格子无论是几都可以走到，那么再向大考虑就是无用的。

貌似按这个理论 可以压缩到 满足[t*n] - >= 0 的 n 的最小值。

比赛的时候或者不太仔细考虑的时候 100是可行的。