#include<bits/stdc++.h>usingnamespace std;intgcd(int a,int b){return b ?gcd(b, a % b): a;}intmain(){int i, j, b=1, c=0, a=1;for(i=1; i<20; i++){
a = a*2;
b += a;}int t =gcd(b, a);while(t !=1){
b /= t;
a /= t;
t =gcd(b, a);}printf("%d/%d\n",b,a);return0;}
动态规划,
d
p
[
i
]
=
m
i
n
(
d
p
[
p
3
]
∗
3
,
d
p
[
p
5
]
∗
5
,
d
p
[
p
7
]
∗
7
)
dp[i] = min(dp[p_3]*3,dp[p_5]*5,dp[p_7]*7)
dp[i]=min(dp[p3]∗3,dp[p5]∗5,dp[p7]∗7), 初始时
p
3
=
0
,
p
5
=
0
,
p
7
=
0
p_3 = 0, p_5 = 0, p_7 = 0
p3=0,p5=0,p7=0,
d
p
[
0
]
=
1
dp[0] = 1
dp[0]=1
n=1时:
o
ooo
o
n=2时:
o
ooo
o
o o o
ooooooooo
o o o
o
ooo
o
n=3时
o
ooo
o
o o o
ooooooooo
o o o
o
ooo
o
o o o
ooo ooo ooo
o o o
o o o o o o o o o
ooooooooooooooooooooooooooo
o o o o o o o o o
o o o
ooo ooo ooo
o o o
o
ooo
o
o o o
ooooooooo
o o o
o
ooo
o
思路
搞清各个变量的含义,t 代表的是几行
代码
#include<stdio.h>#include<stdlib.h>voidshow(char* buf,int w){int i,j;for(i=0; i<w; i++){for(j=0; j<w; j++){printf("%c", buf[i*w+j]==0?' ':'o');}printf("\n");}}voiddraw(char* buf,int w,int x,int y,int size){if(size==1){
buf[y*w+x]=1;return;}int n = size/3;//填空draw(buf, w, x, y, n);draw(buf, w, x-n, y ,n);draw(buf, w, x+n, y ,n);draw(buf, w, x, y-n ,n);draw(buf, w, x, y+n ,n);}intmain(){int N =2;int t =1;int i;for(i=0; i<N; i++) t *=3;char* buf =(char*)malloc(t*t);for(i=0; i<t*t; i++) buf[i]=0;draw(buf, t, t/2, t/2, t);show(buf, t);free(buf);return0;}
$h1:m1:s1 \ \ h2:m2:s2 $或 $h1:m1:s1 \ \ h3:m3:s3 (+1) $或
h
1
:
m
1
:
s
1
h
4
:
m
4
:
s
4
(
+
2
)
h1:m1:s1 \ \ h4:m4:s4 (+2)
h1:m1:s1h4:m4:s4(+2) 表示该航班在当地时间
h
1
h1
h1时
m
1
m1
m1分
s
1
s1
s1秒起飞,
第一种格式表示在当地时间 当日
h
2
h2
h2时
m
2
m2
m2分
s
2
s2
s2秒降落 第二种格式表示在当地时间 次日
h
3
h3
h3时
m
3
m3
m3分
s
3
s3
s3秒降落。 第三种格式表示在当地时间 第三天
h
4
h4
h4时
m
4
m4
m4分
s
4
s4
s4秒降落。
对于此题目中的所有以$ h : m : s $形式给出的时间, 保证
(
0
<
=
h
<
=
23
,
0
<
=
m
,
s
<
=
59
)
( 0<=h<=23, 0<=m,s<=59 )
(0<=h<=23,0<=m,s<=59).
【输出格式】 输出到标准输出。 对于每一组数据输出一行一个时间
h
h
:
m
m
:
s
s
hh:mm:ss
hh:mm:ss,表示飞行时间为
h
h
hh
hh小时
m
m
mm
mm分
s
s
ss
ss秒。注意,当时间为一位数时,要补齐前导零。如三小时四分五秒应写为
03
:
04
:
05
03:04:05
03:04:05。
【题目描述】 三体人将对地球发起攻击。为了抵御攻击,地球人派出了
A
×
B
×
C
A × B × C
A×B×C 艘战舰,在太空中排成一个$ A$ 层
B
B
B 行$ C$ 列的立方体。其中,第
i
i
i 层第
j
j
j 行第 $k $列的战舰(记为战舰
(
i
,
j
,
k
)
(i, j, k)
(i,j,k))的生命值为
d
(
i
,
j
,
k
)
d(i, j, k)
d(i,j,k)。
三体人将会对地球发起 $m $轮“立方体攻击”,每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。具体地,第 t 轮攻击用 7 个参数 $lat, rat, lbt, rbt, lct, rct, ht $描述;
【数据约定】 对于 10% 的数据,
B
=
C
=
1
B = C = 1
B=C=1; 对于 20% 的数据,
C
=
1
C = 1
C=1; 对于 40% 的数据,
A
×
B
×
C
,
m
≤
10
,
000
A × B × C, m ≤ 10, 000
A×B×C,m≤10,000; 对于 70% 的数据,
A
,
B
,
C
≤
200
A, B, C ≤ 200
A,B,C≤200; 对于所有数据,
A
×
B
×
C
≤
1
0
6
,
m
≤
1
0
6
,
0
≤
d
(
i
,
j
,
k
)
,
h
t
≤
1
0
9
。
A × B × C ≤ 10^6, m ≤ 10^6, 0 ≤ d(i, j, k), ht ≤ 10^9。
A×B×C≤106,m≤106,0≤d(i,j,k),ht≤109。
思路
满分题解:三维差分。
考试中:暴力。
代码
#include<bits/stdc++.h>usingnamespace std;int a[200][200][200];intmain(){freopen("7.txt","r",stdin);int A, B, C, m;scanf("%d%d%d%d",&A,&B,&C,&m);for(int i =0; i < A; i++){for(int j =0; j < B; j++){for(int k =0; k < C; k++)scanf("%d",&a[i][j][k]);}}int lat, rat, lbt, rbt, lct, rct, ht;for(int i =1; i <= m; i++){scanf("%d%d%d%d%d%d%d",&lat,&rat,&lbt,&rbt,&lct,&rct,&ht);for(int j = lat -1; j <= rat -1; j++){for(int k = lbt -1; k <= rbt -1; k++){for(int p = lct -1; p <= rct -1; p++){
a[j][k][p]-= ht;if(a[j][k][p]<0){printf("%d\n", i);exit(0);}}}}}return0;}
全球变暖
题目
标题:全球变暖
【题目描述】 你有一张某海域
N
x
N
NxN
NxN像素的照片,".“表示海洋、”#"表示陆地,如下所示:
标准差的介绍:标准差是多个数与它们平均数差值的平方平均数,一般用于刻画这些数之间的“偏差有多大”。形式化地说,设第$ i
个
人
付
的
钱
为
个人付的钱为
个人付的钱为 b_i $元,那么标准差为 :
s
=
1
n
∑
i
=
1
n
(
b
i
−
1
n
∑
i
=
1
n
b
i
)
2
s=\sqrt{\frac{1}{n} \sum_{i=1}^{n}\left(b_{i}-\frac{1}{n} \sum_{i=1}^{n} b_{i}\right)^{2}}
s=n1∑i=1n(bi−n1∑i=1nbi)2
【输入格式】 从标准输入读入数据。
第一行包含两个整数
n
、
S
n、S
n、S; 第二行包含 n 个非负整数
a
1
,
.
.
.
,
a
n
。
a_1, ..., a_n。
a1,...,an。
【数据说明】 对于 10% 的数据,所有
a
i
a_i
ai 相等; 对于 30% 的数据,所有非 0 的
a
i
a_i
ai 相等; 对于 60% 的数据,
n
≤
1000
;
n ≤ 1000;
n≤1000; 对于 80% 的数据,
n
≤
1
0
5
n ≤ 10^5
n≤105; 对于所有数据,
n
≤
5
×
1
0
5
,
0
≤
a
i
≤
1
0
9
n ≤ 5 × 10^5, 0 ≤ a_i ≤ 10^9
n≤5×105,0≤ai≤109。
思路
贪心,将不能够付起平均值的钱平均分给可以付起的人。
代码
#include<bits/stdc++.h>usingnamespace std;constint maxn =5e5+10;double a[maxn];intmain(){int n, S;
cin >> n >> S;double avg =1.0* S / n;for(int i =0; i < n; i++) cin >> a[i];sort(a, a + n);double ans =0.0, navg = avg;for(int p =0; p < n; p++){if(a[p]< navg){
ans +=(double)pow(avg-a[p],2);
S -= a[p];
navg =1.0* S /(n-p-1);}else{
ans +=(double)pow(navg-avg,2);}}printf("%.4lf",sqrt(ans/n));return0;}