86 条题解
-
0
玛维-影之歌 LV 10 @ 2008-09-22 20:39:05
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 9ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：9ms
额 最后一个点是为什么...
公式+2分高精 比赛时候居然只写了公式... -
0
var
m,n,i,j,k:longint;
a,b,c:array[0..300]of longint;
s:string;
e:boolean;
procedure chen(q:longint);
var
i,j:longint;
begin
for i:=m downto 1do
for j:=m downto 1do
begin
b[300-2*m+i+j]:=b[300-2*m+i+j]+c[i]*c[j];
b[299-2*m+i+j]:=b[299-2*m+i+j]+b[300-2*m+i+j]div 10;
b[300-2*m+i+j]:=b[300-2*m+i+j]mod 10;
end ;
end;
begin
readln(s);
for i:=1to length(s)do
a[300-length(s)+i]:=ord(s[i])-48;
m:=length(s)div 2+2;
for i:=1to m do
begin
e:=true;
while e do
begin
inc(c[i]);
if c[i]>=10
then k:=c[i]div 10;
c[i]:=c[i]mod 10;
j:=i;
while k0do
begin
dec(j);
c[j]:=c[j]+k;
k:=c[j]div 10;
c[j]:=c[j]mod 10;
end;
fillchar(b,sizeof(b),0);
chen(1);
for j:=(302-2*m)to(300-2*m+2*i)do
if a[j]b[j]
then break;
end;
dec(c[i]);
if c[i] -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms二分法
要写高精，郁闷…… -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 72ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：72ms -
0
3144046cjc LV 3 @ 2008-09-18 18:36:20
我来证明一下这个题目的结论.
假设我们已经求出(n-1)时的
答案为ans,这时添加第n盏灯,
显然不会影响原来(n-1)盏灯
里亮的数目,这样,如果n有奇
数个因子,则现在的答案为(ans+1),
否则现在的答案为ans.什么样的数有奇数个因子呢?
答案是当且仅当n=x*x (x>=1).
证明
充分性:
将n写成如下形式:
n=q1^a1 * q2^a2 * q3^a3 **|* qm^am
qi为质数,显然,所有的a 必然为偶数,否则n
不是平方数.
则n的因子个数c=(a1+1)*(a2+1)\|(am+1) 为奇数,
证毕!
必要性:
如果n不是平方数,
那么 将n写成如下形式:
n=q1^a1 * q2^a2 * q3^a3 ***|* qm^am
a 不可能全部为偶数(如果都是偶数的话n就
明显是一个平方数了)
则n的因子个数c=(a1+1)*(a2+1)\*|(am+1) 必为偶数
证必!即对于给定的输入n,
答案就是1..n中的平方数的个数.
很容易知道,答案为使下面不等关系成立的最小x:
(x+1)^2 >=n+1 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案错误... ├ 标准行输出
├ 错误行输出
├ 测试数据 08：答案错误... ├ 标准行输出
├ 错误行输出
├ 测试数据 09：答案错误... ├ 标准行输出
├ 错误行输出
├ 测试数据 10：运行时错误...| 错误号: 207 | 无效浮点运算
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：60 有效耗时：0ms
两行6个点.........
var n:extended;
begin
readln(n);
writeln(trunc(sqrt(n)));
end. -
0
qwe784153686 LV 8 @ 2008-09-17 21:04:14
program ex3;
type num=array [0..400] of longint;
var i,j,k,n:extended;
time:longint;
s:string;
a,b,c:num;
procedure jiance(var d:num);
var m:longint;
begin
m:=401;
repeat
dec(m);
until (m=0)or(d[m]0);
d[0]:=m;
end;
procedure chuli(n:extended);
var i,j,k:longint;
begin
k:=trunc(n);
str(k,s);
a[0]:=length(s);
for i:=1 to a[0] do
a[a[0]-i+1]:=ord(s[i])-48;
end;
procedure chengfa(a,b:num;var c:num);
var i,j,m,x:longint;
begin
for i:=1 to a[0] do
for j:=1 to b[0] do
begin
m:=i+j-1;
inc(c[m],a[i]*b[j]);
inc(c[m+1],c[m] div 10);
c[m]:=c[m] mod 10;
end;
jiance(c);
end;
procedure solve;
var i,j,k:longint;
begin
for i:=1 to time-1 do
begin
chengfa(a,a,c);
a:=c;
end;
end;
procedure outit;
var i,j,k:longint;
begin
for i:=a[0] downto 1 do
write(a[i]);
end;
begin
readln(n);
if n -
0
注意细节...
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
---|---|---|---|---|---|以下代码仅供参考---|---|---|---|
---|---|---|---|---|---|--已动过手脚---|---|---|---|---|---|-
---|---|---|---|---|---|-请勿直接提交---|---|---|---|---|--
---|---|---|---|---|---|-否则后果自负---|---|---|---|---|--
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|type
num=record
l:longint;
w:array[0..300]of longint;
end;function max(a,b:longint):longint;begin if a>b then exit(a)else exit(b);end;
procedure zl(var a:num);
var i:longint;
begin
i:=1;
while(a.w[i]>0)or(ib.l then exit(false);
if a.l0)and(a.w[l]=b.w[l])do dec(l);
if l=0 then exit(true);
exit(a.w[l] -
0
w122185976 LV 10 @ 2008-09-17 19:57:11
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 9ms
├ 测试数据 10：答案正确... 88ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：97ms├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：运行超时|无输出...
├ 测试数据 10：运行超时|无输出...
一样的题，一样的评测机，不一样的结果，我没话说啊！５～～～～～～～～～
我的ＡＣ率啊！！！！！！！！！！！！！！ -
0
dokd229933 LV 7 @ 2008-09-17 19:04:45
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 103ms
├ 测试数据 10：答案正确... 338ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：441ms高精度+二分
-
0
program ex3;
type num=array [0..400] of longint;
var i,j,k,n:extended;
time:longint;
s:string;
a,b,c:num;
procedure jiance(var d:num);
var m:longint;
begin
m:=401;
repeat
dec(m);
until (m=0)or(d[m]0);
d[0]:=m;
end;
procedure chuli(n:extended);
var i,j,k:longint;
begin
k:=trunc(n);
str(k,s);
a[0]:=length(s);
for i:=1 to a[0] do
a[a[0]-i+1]:=ord(s[i])-48;
end;
procedure chengfa(a,b:num;var c:num);
var i,j,m,x:longint;
begin
for i:=1 to a[0] do
for j:=1 to b[0] do
begin
m:=i+j-1;
inc(c[m],a[i]*b[j]);
inc(c[m+1],c[m] div 10);
c[m]:=c[m] mod 10;
end;
jiance(c);
end;
procedure solve;
var i,j,k:longint;
begin
for i:=1 to time-1 do
begin
chengfa(a,a,c);
a:=c;
end;
end;
procedure outit;
var i,j,k:longint;
begin
for i:=a[0] downto 1 do
write(a[i]);
end;
begin
readln(n);
if n -
0
c248696117 LV 7 @ 2008-09-17 18:18:39
纪念下，AC的第100道题
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 166ms
├ 测试数据 10：答案正确... 525ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：691ms虽然耗时比较多吧
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 150ms
├ 测试数据 10：答案正确... 462ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：612msprogram p1447;
type num=array[0..5000]of integer;
VAR I,J,K,M,N:LONGINT;
wh:string;
r,s:num;
function sqrt0(s:num):num;
var t1,t2,n,i,j,k,h:longint;
t:boolean;
a,b,c,wh1,wh2:num;
function multiply(a,b:num):num;
var i,j:longint;
c:num;
begin
fillchar(c,sizeof(c),0);
c[0]:=a[0]+b[0]-1;
for i:=1 to a[0] do
for j:=1 to b[0] do
begin
inc(c,a[i]*b[j]);
inc(c,cdiv 10);
c:=c mod 10;
end;
if c[c[0]+1]0 then inc(c[0]);
multiply:=c;
end;
function add(a,b:num):num;
var i,j:longint;
c:num;
begin
fillchar(c,sizeof(c),0);
if b[0]>a[0] then c[0]:=b[0] else c[0]:=a[0];
for i:=1 to c[0] do
begin
inc(c[i],a[i]+b[i]);
inc(c,c[i] div 10);
c[i]:=c[i] mod 10;
end;
if c[c[0]+1]0 then inc(c[0]);
add:=c;
end;
function compare(a,b:num):longint;
var i,j:longint;
begin
if a[0]>b[0] then exit(1);
if b[0]>a[0] then exit(2);
for i:=a[0] downto 1 do
begin
if a[i]>b[i] then exit(1);
if b[i]>a[i] then exit(2);
end;
exit(3);
end;
begin
fillchar(a,sizeof(a),0);
n:=s[0]-s[0] div 2;
a[0]:=n;
for i:=n downto 1 do
begin
for j:=0 to 9 do
begin
fillchar(c,sizeof(c),0);
c[0]:=i;
c[i]:=1;
a[i]:=j;
b:=add(a,c);
wh1:=multiply(a,a);
wh2:=multiply(b,b);
t1:=compare(wh1,s);
t2:=compare(wh2,s);
if t1=3 then exit(a);
if t2=3 then exit(b);
if (t1=2)and(t2=1)then
break;
end;
end;
sqrt0:=a;
end;begin
readln(wh);
s[0]:=length(wh);
for i:=s[0] downto 1 do
s[s[0]-i+1]:=ord(wh[i])-48;
r:=sqrt0(s);
for i:=r[0] downto 1 do write(r[i]);
end.好险啊
我也不知道怎么过的！！！！！ -
0
wly888_1214 LV 3 @ 2008-09-16 22:10:15
不像个纯OI题，倒像个数学题……
此题好猥琐啊，逼我用更猥琐的算法……
这题确实可以用来练高精，我是用最直接的高精度开平方运算做的（貌似有部分同志没试过这种算法吧……）
此题原理简单，就是利用“完全平方数的约数个数为奇数”这一性质
至于那个算法，也不麻烦，一共就5大块：
1.初始化 2.比较数字串大小 3.高精度减法 4.高精度乘一位数 5.主程序
写出来也就100来行，不过前提是你得知道怎么手动开平方。
手动开平方的方法相信不论是书上还是网上都能找到，如果同志们嫌麻烦懒得找，可以直接踩本菜鸟的QQ空间（http://user.qzone.qq.com/229682821），里面有详细说明……（大牛勿进，进了会受不了的）
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
w122185976
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 9ms
├ 测试数据 10：答案正确... 88ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：97ms├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：运行超时|无输出...
├ 测试数据 10：运行超时|无输出...
一样的题，一样的评测机，不一样的结果，我没话说啊！５～～～～～～～～～
我的ＡＣ率啊！！！！！！！！！！！！！！
玛维-影之歌
LV 10
@ 2008-09-22 20:39:05
