2017.5.14入门组总结
第一题:
题意:求1~n a[i]*b[i]+c[i]的和
思路:暴力实现容易,一看数据“1<=n<=1,000,000”!!!
直接暴力模拟,时间复杂度o(n)!
于是乎,直接码程序2min搞定
第二题:
题意:将a[i][j]的位置,往下移i位,到底就换到第一行
思路:也是一道水题,不愧是入门组
n<=100,暴力没毛病
迅速码.......下一题
第三题:
题意:一开始有容量为v[i]的杯子,如果杯子里的水溢出来就留到下面的集水盘。现在有两个操作:
①:倒水,在a~b区间倒水,每个杯子倒s水,如果a杯子溢出来,就将a杯子与b杯子交换(注意不换集水盘)
②:交换,直接交换a杯子和b杯子(不换集水盘)
求最后杯子和集水盘里有多少水
思路:先看数据:1<=n<=3000 1<=m<=100 1<=a<=b<=n 0<=s<=30
咦!最大时间复杂度o(100*3000)
也是暴力模拟就行,于是瞬间码完
第四题:
题意:求C(n,m),取模23333
思路:推了推,发现这是一个C(n,m),一看数据,就兴致勃勃的开始码了,自认为可以切掉第四题,初评AK!!
考试思路:直接暴力求然后取模
结果......神奇的Wrong Answer ,一脸“( ⊙o⊙?)不懂”这应该是正 解啊?为啥GG 20分
正确思路:后来,老师说可以推公式,也可以用杨辉三角做
我便果断选择了杨辉三角:推了推,发现第i层的第j个就是C(n,m) 的结果
①杨辉三角,两层就可以,f[1/0,j] i用mod 2维护
公式:f[i mod 2,j]:=f[(i+1) mod 2,j-1]+f[(i+1) mod 2,j]
也就是上一层和上一层的左边相加(杨辉三角公式)
初评:100+100+100+20=320
这次的入门组还是有点水,主要是第四题坑
立个flag:下次AK
第一题标程:
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
long long n=0,max=0;
int a,b,c;
scanf("%lld",&n);
for (int i=1;i<=n;i++)
{
scanf("%d%d%d",&a,&b,&c);
max=max+a*b+c;
}
printf("%lld",max);
return 0;
}
第二题标程:
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
int n,a[101][101],b[101][101];
scanf("%d",&n);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++) if (i+j>n) b[i+j-n][j]=a[i][j]; else b[i+j][j]=a[i][j];
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++) printf("%d ",b[i][j]);
printf("
");
}
return 0;
}
第三题程序:
var n,m,i,x,a,b,j:longint;
v,s,k:array[0..3001]of longint;
t:boolean;
begin
assign(input,'c.in');
assign(output,'c.out');
reset(input);
rewrite(output);
readln(n,m);
for i:=1 to n do read(v[i]);
readln;
for i:=1 to m do
begin
readln(a,b,x);
if x<>0 then
begin
t:=true;
for j:=a to b do
if s[j]+x>v[j] then begin k[j]:=s[j]+x-v[j]+k[j]; s[j]:=v[j]; if j=a then t:=false;end
else s[j]:=s[j]+x;
if t=false then begin s[0]:=s[a]; s[a]:=s[b]; s[b]:=s[0]; v[0]:=v[a]; v[a]:=v[b]; v[b]:=v[0]; end;
end
else begin s[0]:=s[a]; s[a]:=s[b]; s[b]:=s[0]; v[0]:=v[a]; v[a]:=v[b]; v[b]:=v[0]; end;
end;
for i:=1 to n do write(s[i],' ');
writeln;
for i:=1 to n do write(k[i],' ');
close(input);
close(output);
end.
第四题杨辉三角标程:
var n,m,i,j:longint;
f:array[0..1001,-1..10001]of longint;
begin
assign(input,'d.in');
assign(output,'d.out');
reset(input);
rewrite(output);
readln(n,m);
f[0,0]:=1;
for i:=1 to m do
for j:=0 to i do
f[i mod 2,j]:=(f[(i+1) mod 2,j]+f[(i+1) mod 2,j-1]) mod 23333;
write(f[m mod 2,n]);
close(input);
close(output);
end.
第四题公式法+快速幂标程:
#include<cstdio>
#include<iostream>
using namespace std;
long long f[2];
int n,m;
int ksm(int x,int y)
{
int ans=1;
while (y)
{
if (y&1) ans=ans*x%23333;
x=x*x%23333;
y=y/2;
}
return ans;
}
int main()
{
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
scanf("%d%d",&m,&n);
f[0]=1;
for (int i=1;i<=m;i++)
f[i%2]=f[(i+1)%2]*(n-i+1)*ksm(i,23331)%23333;
printf("%lld",f[m%2]);
fclose(stdin);
fclose(stdout);
}