囧~~囧~~~ 检查了半天循环变量写错了………………- -!

这题思路就是简单地容斥原理(还是裸的)

裸的容斥原理……

简单的搜索题，我沙茶传了两遍才过（原来要int64）

哪位大牛帮我看下为什么错....

var n,i,a,b,max,t,s,j:Longint;

c:array[1..16] of Longint;

begin

readln(n);

for i:=1 to n do

read(c[i]);

readln;

read(a,b);

max:=0;

for i:=1 to n do

if c[i]>max then max:=c[i];

s:=b div Max;

s:=s*max;

repeat

if s mod 8=0 then

for i:=1 to n do

if s mod c[i]0 then

break;

if (i=n) and (s mod c[n]=0) then inc(t);

s:=s-max;

until s

好题，考虑分解质因数，变化成乘一个数使得不包含给定数，最小公倍数做即可

记录号 Flag 得分 记录信息 环境 评测机 程序提交时间

R1482688 Unaccepted 30 From 747470666－

　 P1629 GCC Vivid Puppy 2009-8-27 22:02:00

From cai0715

八 NOIP 2009·Dream Team 模拟赛 系列

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include

int n,f[16],q[100001],t,s,a,b;

int pc (int x,int y)

{

int i;

for (i=1;i0;j--)

if (j%8==0)

break;

s=(j-i)/8+1;

t=0;

for (i=1;i

我悲剧了……

宣布：此题本人现在不会做

有哪个大牛发发善心帮帮小女子！……………

编译通过...

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

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

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

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

　├ 错误行输出 3646869...

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

　├ 错误行输出 3626975...

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

　├ 错误行输出 ...161076...

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

　├ 错误行输出 78963...

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

　├ 错误行输出 ...1598457...

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

　├ 错误行输出 ...2250893...

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

　├ 错误行输出 ...2391758...

var

i,j,x,y,nn,n,nx:longint;

ans:int64;

a:array[0..52000,1..15]of int64;

function gcd(a,b:int64):int64;

begin

if b=0 then gcd:=a

else gcd:=gcd(b,a mod b);

end;

procedure make(i1,en:longint);

var j:longint;q:int64;

begin

q:=ans;

ans:=ans*a[i1,1]*gcd(ans,a[i1,1]);

if (en=i)and(ansy then a:=0;

end;

nn:=y shr 3-(x-1)shr 3;

for j:=1 to n do

for i:=1 to a[0,j]do

if a0then

begin

nx:=y div a-(x-1) div a;

if odd(j)then nn:=nn-nx else nn:=nn+nx;

end;

writeln(nn);

end.

楼下的，我跟你讲吧：

方法一：对[left,right]之间的数字进行逐一检查

这样空间复杂度是0，时间复杂度为O((right-left)*16)。

但如果是比赛，你不会的话，这个方法最多可以过3-4个点！不是3个，是3或4个！

甚至5个。

第一，说不定傻瓜出题的时候，n个数里面，有1或2或4或8的，你可以直接输出0.

这里可能可以骗到10分，但机会很小很小

第二，这个程序可以优化,最大优化到O((right-left) div 8 *15)，

优化如下：

原来的代码：

for i:=left to right do

更改为：

while left mod 8>0 do inc(left); (预处理left)

while ia then begin a:=a+b; b:=a-b; a:=a-b; end;

if b=0 then gcd:=a else gcd:=gcd(b,a mod b);

end;

procedure work(p:integer);

var

i:integer;

k,gbs:int64;

begin

gbs:=8;

for i:=1 to p do

begin

if gbsk then work(k)

else for i:=sav[p-1]+1 to n-k+p do

begin

sav[p]:=i;

opp(p+1,k);

end;

end;

begin

an1:=0;

an2:=0;

read(n);

for i:=1 to n do

begin

read(a[i]);

if (a[i]=1) or (a[i]=2) or (a[i]=4) or (a[i]=8) then

begin

writeln(0);

exit;

end;

end;

read(left,right);

num:= right div 8 - (left-1) div 8;

a[0]:=8;

for i:=1 to n do

opp(1,i);

kp:=an1;

if an2>an1 then kp:=an2;

for i:=1 to kp do

begin

if i

能大致讲讲算法流程吗

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

感谢fammiebright。。

暴力容斥即可。

int main()

{

cin>>n;

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

if(a[i]%2==0)a[i]/=2;

if(a[i]%2==0)a[i]/=2;

if(a[i]%2==0)a[i]/=2;

}

cin>>l>>r;

l=(l-1)/8+1;r/=8;

ans=(r-l+1);

for(k=1;k

终于秒掉了……

现在我想了解一下所谓的“暴力容斥”算法

希望用0ms的算法交换一下200ms的算法看一下 大家一起讨论讨论~

最小公倍数为longint，过三个点，改为int64,0ms杀

这么会超时？请教大牛！

var

n:longint;

ans,i,j:longint;

num:array[1..100] of longint;

a,b,x,y,k,temp:longint;

begin

readln(n);

for i:=1 to n do

read(num[i]);

readln;

read(a,b);

if b

编译通过...

├ 测试数据 01：内存溢出...

├ 测试数据 02：内存溢出...

├ 测试数据 03：内存溢出...

├ 测试数据 04：内存溢出...

├ 测试数据 05：内存溢出...

├ 测试数据 06：内存溢出...

├ 测试数据 07：内存溢出...

├ 测试数据 08：内存溢出...

├ 测试数据 09：内存溢出...

├ 测试数据 10：内存溢出...

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

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

???????????????????

传说中的暴力容斥...可是不用int64的话很容易打成三十分.....

orz0ms搞定的牛人...本人后两个记录的的时间接近200....

int64....

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

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

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

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

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

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

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

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

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

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

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

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

细心才是王道

Melody是豆粉吗

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

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

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

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

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

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

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

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

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

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

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

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

神鸡，第一次超一个，第二次AC。。。。