HackPluto's Blog

蓝桥杯刷题记录

字数统计: 2.5k阅读时长: 15 min
2020/10/05 Share

马上就是蓝桥杯省赛了,冲一波,好好准备一下,记录一下刷的蓝桥杯真题

蓝桥练习系统

整商问题

水题

1
2
3
4
5
6
7
8
9
10
11
12
int a,b;
int main(){
printf("Please enter the dividend:\n");
cin>>a;
printf("Please enter the divisor:\n");
cin>>b;
while(b==0){
printf("Error: divisor can not be zero! Please enter a new divisor:\n");
cin>>b;
}
printf("%d\n",a/b);
}

第二点五个不高兴的小明

一个简单的DP

1
2
3
dp[i][j] 表示第i跳到j格子时的权重最大值;
状态转移方程为:
(a) j > p

1
2
3
4
5
6
7
if((j-p)>0){
int Max = dp[i-1][j-p+1];
for(int k=j-p;k<=j-1;k++){
Max = max(Max,dp[i-1][k]);
}
dp[i][j] = Max + Map[j];
}
1
(b) j < p
1
2
3
4
int Max2 = dp[i-1][1];
for(int k=1;k<j;k++)
Max2 = max(Max2,dp[i-1][k]);
dp[i][j] = Max2 + Map[j];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int Map[1005];
int dp[1005][1005];
int main(){
int n,p,t;
cin>>n>>p>>t;
for(int i=1;i<=n;i++)
cin>>Map[i];
memset(dp, -999999, sizeof(dp));
for(int i=1;i<=p;i++)
dp[1][i] = Map[i];
for(int i=2;i<=t-1;i++){
for(int j=i;j<=min(n,i*p);j++){
if((j-p)>0){
int Max = dp[i-1][j-p+1];
for(int k=j-p;k<=j-1;k++){
Max = max(Max,dp[i-1][k]);
}
dp[i][j] = Max + Map[j];
}
else{
int Max2 = dp[i-1][1];
for(int k=1;k<j;k++)
Max2 = max(Max2,dp[i-1][k]);
dp[i][j] = Max2 + Map[j];
}
}
}
int id = max(t-1,n-p+1);
int Max = dp[t-1][id];
for(int i = id;i<=n;i++){
Max = max(dp[t-1][i],Max);
}
printf("%d\n",Max);
}

第十一届蓝桥杯大赛个人赛校内选拔

通电

UOQsId

最小生成树 Prim算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>

using namespace std;
double Map[1005][1005];
double lowcost[1005],sum;
typedef struct{
long long x,y,h;
}Node;
Node node[1005];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>node[i].x>>node[i].y>>node[i].h;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
if(i==j||Map[i][j])
continue;
Map[i][j] = sqrt(pow((node[i].x-node[j].x)*1.0,2) + pow((node[i].y-node[j].y)*1.0,2)) + pow((node[i].h-node[j].h)*1.0,2);
Map[j][i] = Map[i][j];
}
for(int i=1;i<n;i++){
lowcost[i] = Map[i][0];
}
for(int i=1;i<n;i++){
double minnum = 999999.0;
int minid;
for(int j=1;j<n;j++){
if(lowcost[j]&&lowcost[j]<minnum){
minnum = lowcost[j];
minid = j;
}
}
lowcost[minid] = 0;
sum += minnum;
for(int j=1;j<n;j++){
if(Map[minid][j]<lowcost[j])
lowcost[j] = Map[minid][j];
}
}
printf("%.2f\n",sum);
}

植树

DFS 暴力搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>

using namespace std;

typedef struct{
int x,y,r;
}Node;
Node node[35];
int flag[35];
int n,sum;

int check(int i){
for(int j=0;j<n;j++){
if(flag[j]&&i!=j){
int d = sqrt(pow((node[i].x-node[j].x),2) + pow((node[i].y-node[j].y),2));
if(d<(node[i].r+node[j].r))
return 0;
}
}
return 1;
}
void dfs(int id,int area){
if(id==n){
sum = max(sum,area);
return;
}
for(int i=0;i<n;i++){
if(!flag[i]){
flag[i] = 1;
if(check(i))
dfs(id+1,area+node[i].r*node[i].r);
else
dfs(id+1,area);
flag[i] = 0;
}
}
}

int main(){
cin>>n;
for(int i=0;i<n;i++)
cin>>node[i].x>>node[i].y>>node[i].r;
dfs(0,0);
printf("%d\n",sum);

}

第十届蓝桥杯大赛省赛

迷宫

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
char Map[100][100];
char s[2000];
int vis[100][100];
struct node{
int hang;
int lie;
char lu;
};
node pre[100][100];
queue<node>q;
int dlie[] = {0,-1,1,0};
int dhang[] = {1,0,0,-1};
string S = "DLRU";
void bfs(){
while(!q.empty()){
q.pop();
}
node first;
first.hang = first.lie = 0;
q.push(first);
vis[0][0] = 1;
while(q.size()){
node tmp = q.front();
q.pop();
int hang = tmp.hang,lie = tmp.lie;
for(int i=0;i<4;i++){
int nlie = lie + dlie[i],nhang = hang + dhang[i];
if(nlie<50 && nhang<30 && nlie >=0 && nhang >=0 && Map[nhang][nlie] == '0' && !vis[nhang][nlie]){
vis[nhang][nlie] = 1;
pre[nhang][nlie].hang = hang;
pre[nhang][nlie].lie = lie;
pre[nhang][nlie].lu = S[i];
node qqq;
qqq.hang = nhang;qqq.lie = nlie;
q.push(qqq);
if(nlie==49&&nhang==29)
return;
}
}
}
}
void print(int x,int y){
if(x == 0&& y == 0)
return;
print(pre[x][y].hang,pre[x][y].lie);
//printf("(%d, %d)\n", pre[x][y].hang,pre[x][y].lie);
printf("%c", pre[x][y].lu);
}
int main(){
FILE * f = fopen("//Users//liuhaohui//Desktop//maze.txt","r");
char a;
int k = 0;
while(k<1500){
fscanf(f,"%c",&a);
if(a==49||a==48)
s[k++] = a;
}
k = 0;
for(int i=0;i<30;i++){
for(int j=0;j<50;j++)
Map[i][j] = s[k++];
}
bfs();
print(29,49);
}

洛谷练习

P2241 统计方形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
long long zn=0,cn=0;
for (int i=0; i<min(n, m); i++) {
zn += (n-i)*(m-i);
}
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (i==j) {
continue;
}
cn += (n-i)*(m-j);
}
}
printf("%lld %lld\n",zn,cn);
}

P2089 烤鸡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
int num,n;
int ans[10000][10];
int c[10];
void dfs(int id,int sum){
if (id==10&&sum==n) {
for (int i=0; i<10; i++) {
ans[num][i] = c[i];
}
num++;
return;
}
for (int j = 1; j<=min(3,n-9); j++) {
if ((sum+j)<=n) {
c[id] = j;
dfs(id+1, sum+j);
}
}
}
int main(){
cin>>n;
if (n>30) {
printf("0\n");
return 0;
}
dfs(0, 0);
printf("%d\n",num);
for (int i=0; i<num; i++) {
for (int j=0; j<10; j++) {
printf("%d ",ans[i][j]);
}
printf("\n");
}
}

P1618 三连击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int flag[10];
int k;
void dfs(int n,int first,int second,int third){
int f=first,s=second,t=third;
if (n==9) {
if (first*b==a*second&&second*c==b*third&&first*c==a*third) {
printf("%d %d %d\n",first,second,third);
k++;
}
return;
}
for (int i=1; i<=9; i++) {
if (!flag[i]) {
if (n<3) {
f = first*10+i;
}
else if (n<6){
s = second*10+i;
}
else
t = third*10+i;
flag[i] = 1;
dfs(n+1, f, s, t);
flag[i] = 0;
}
}
}
int main(){
cin>>a>>b>>c;
dfs(0, 0, 0, 0);
if (k==0) {
printf("No!!!\n");
}
return 0;
}

P1036 选数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
int num[100];
int flag[100];
int n,k,ans;
int check(long long a){
for (int i=2; i<=sqrt(a); i++) {
if (a%i==0) {
return 0;
}
}
return 1;
}
void dfs(int id,long long sum){
if (id==k) {
if (check(sum)) {
ans++;
}
return;
}
for (int i=0; i<n; i++) {
if (!flag[i]) {
flag[i] = 1;
dfs(id+1, sum+num[i]);
flag[i] = 0;
}
}

}
int main(){
cin>>n>>k;
for (int i=0; i<n; i++) {
cin>>num[i];
}
dfs(0, 0);
for (int j=k; j>=2; j--) {
ans /= j;
}
printf("%d\n",ans);
}

P1157 组合的输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int n,r;
int num[25];
void dfs(int id){
if (id==r) {
for (int i=0; i<r; i++) {
cout<<setw(3)<<num[i];
}
printf("\n");
return;
}
for (int i=num[id-1]+1; i<=n; i++) {
num[id] = i;
dfs(id+1);
}
}
int main(){
cin>>n>>r;
dfs(0);
}

P1706 全排列问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
int n;
int num[25];
int flag[25];
void dfs(int id){
if (id==n) {
for (int i=0; i<n; i++) {
cout<<setw(5)<<num[i];
}
printf("\n");
return;
}
for (int i=1; i<=n; i++) {
if (flag[i]) {
continue;
}
flag[i] = 1;
num[id] = i;
dfs(id+1);
flag[i] = 0;
}
}
int main(){
cin>>n;
dfs(0);
}

P1088 火星人

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
int a[10005],n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
while(m--) next_permutation(a,a+n);
for(int i=0;i<n-1;i++) printf("%d ",a[i]); printf("%d",a[n-1]);
return 0;
}

P3392 涂国旗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;
char Map[55][55];
char flag[55];
int ans;
int n,m;
int blue;
string color="WBR";
void dfs(int id,char f){
if (id==n) {
int num = 0;
for (int i=0; i<n; i++) {
if (flag[i]=='B') {
blue = 1;
}
for (int j=0; j<m; j++) {
if (Map[i][j]!=flag[i]) {
num++;
}
}
}
if (blue==0) {
return;
}
blue = 0;
if (ans==0) {
ans=num;
}
else
ans = min(ans,num);
return;
}
if (id==0) {
flag[id] = 'W';
dfs(id+1,'W');
}
else if (id==(n-1)){
flag[id] = 'R';
dfs(id+1,'R');
}
else{
if (f=='W') {
for (int i=0; i<=1; i++) {
flag[id] = color[i];
dfs(id+1,color[i]);
}
}
else if (f=='B'){
for (int i=1; i<=2; i++) {
flag[id] = color[i];
dfs(id+1,color[i]);
}
}
else{
flag[id] = 'R';
dfs(id+1,'R');
}
}
}
int main(){
cin>>n>>m;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
cin>>Map[i][j];
}
}
dfs(0, 'W');
printf("%d\n",ans);
}

P3654 First Step

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
char Map[105][105];
int r,c,k;
int ans;

int main(){
cin>>r>>c>>k;
for (int i=0; i<r; i++) {
for (int j=0; j<c; j++) {
cin>>Map[i][j];
}
}
for (int i=0; i<r; i++) {
for (int j=0; j<c; j++) {
if (Map[i][j]!='#') {
int m;
for (m=0; m<k; m++) {
int heng = i;
int shu = j+m;
if (heng>=0&&shu>=0&&heng<r&&shu<c) {
if (Map[heng][shu]=='#') {
break;
}
}
else
break;
}
if (m==k) {
ans++;
}
for (m=0; m<k; m++) {
int heng = i+m;
int shu = j;
if (heng>=0&&shu>=0&&heng<r&&shu<c) {
if (Map[heng][shu]=='#') {
break;
}
}
else
break;
}
if (m==k) {
ans++;
}
}
}
}
if (k==1) {
ans /= 2;
}
printf("%d\n",ans);
}

P1217 [USACO1.5]回文质数

直接打表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
int check1(long long num){
for (long long i=3; i<=sqrt(num); i++) {
if (num%i==0) {
return 0;
}
}
return 1;
}
char a[20];
int check2(long long num){
memset(a, '\0', sizeof(a));
int i=0;
while (num) {
a[i] = '0' + num%10;
num /= 10;
i++;
}
int len = strlen(a);
for (int i=0; i<len/2; i++) {
if (a[i]!=a[len-i-1]) {
return 0;
}
}
return 1;
}
int main()
{
long long a,b;
cin>>a>>b;
FILE* f;
f = fopen("/Users/1.txt", "w");
for (long long i=a; i<=b; i++) {
if (i%2==0) {
continue;
}
if (check1(i)) {
if (check2(i)) {
fprintf(f, "%lld\n",i);
}
}
}
fclose(f);
}

CATALOG
  1. 1. 蓝桥练习系统
    1. 1.1. 整商问题
    2. 1.2. 第二点五个不高兴的小明
  2. 2. 第十一届蓝桥杯大赛个人赛校内选拔
    1. 2.1. 通电
    2. 2.2. 植树
  3. 3. 第十届蓝桥杯大赛省赛
    1. 3.1. 迷宫
  4. 4. 洛谷练习
    1. 4.1. P2241 统计方形
    2. 4.2. P2089 烤鸡
    3. 4.3. P1618 三连击
    4. 4.4. P1036 选数
    5. 4.5. P1157 组合的输出
    6. 4.6. P1706 全排列问题
    7. 4.7. P1088 火星人
    8. 4.8. P3392 涂国旗
    9. 4.9. P3654 First Step
    10. 4.10. P1217 [USACO1.5]回文质数