预备役间学习记录3
一、刷题题解
1、考前临时抱佛脚
# kkksc03考前临时抱佛脚
## 题目背景
kkksc03 的大学生活非常的颓废,平时根本不学习。但是,临近期末考试,他必须要开始抱佛脚,以求不挂科。
## 题目描述
这次期末考试,kkksc03 需要考 $4$ 科。因此要开始刷习题集,每科都有一个习题集,分别有 $s_1,s_2,s_3,s_4$ 道题目,完成每道题目需要一些时间,可能不等($A_1,A_2,\ldots,A_{s_1}$,$B_1,B_2,\ldots,B_{s_2}$,$C_1,C_2,\ldots,C_{s_3}$,$D_1,D_2,\ldots,D_{s_4}$)。
kkksc03 有一个能力,他的左右两个大脑可以同时计算 $2$ 道不同的题目,但是仅限于同一科。因此,kkksc03 必须一科一科的复习。
由于 kkksc03 还急着去处理洛谷的 bug,因此他希望尽快把事情做完,所以他希望知道能够完成复习的最短时间。## 输入格式
本题包含 $5$ 行数据:第 $1$ 行,为四个正整数 $s_1,s_2,s_3,s_4$。
第 $2$ 行,为 $A_1,A_2,\ldots,A_{s_1}$ 共 $s_1$ 个数,表示第一科习题集每道题目所消耗的时间。
第 $3$ 行,为 $B_1,B_2,\ldots,B_{s_2}$ 共 $s_2$ 个数。
第 $4$ 行,为 $C_1,C_2,\ldots,C_{s_3}$ 共 $s_3$ 个数。
第 $5$ 行,为 $D_1,D_2,\ldots,D_{s_4}$ 共 $s_4$ 个数,意思均同上。
## 输出格式
输出一行,为复习完毕最短时间。
## 样例 #1
### 样例输入 #1
```
1 2 1 3
5
4 3
6
2 4 3
```### 样例输出 #1
```
20
```## 提示
$1\leq s_1,s_2,s_3,s_4\leq 20$。
$1\leq A_1,A_2,\ldots,A_{s_1},B_1,B_2,\ldots,B_{s_2},C_1,C_2,\ldots,C_{s_3},D_1,D_2,\ldots,D_{s_4}\leq60$。
1、按题意,我们知道有4组数据,每组数据,对里面的元素进行按时完成,分为左脑和右脑,就是一次可以进行两个元素,问时间最短;
2、我们就知,要使时间最短,就要使计算时左脑和右脑的差距越小,我就想进行一个贪心,进行两个运算,选最小和第二小,或最大和第二大,那门计算下去,看最终谁小就总时间加上谁,但是我提交没过;
3、我就想既然是两个脑子一起计算,就相当于将这组数据的总时间分为两半,左脑一部分,右脑一部分,我们要是左脑最靠近一半,这是总减去左脑,就是最少时间;
4、我们就要对次组数据进行一个01背包,将一半看成总容量,元素的价值和体积就是它的时间,得出最佳的结果;
附代码
- #include <stdio.h>
- int max(int a,int b)
- {if(a>b)return a;
- else
- return b;
- }
- int main()
- {int sxk[40][1000],gzh[100]={0};
- int js[100];
- int sum=0;
- scanf("%d%d%d%d",&js[0],&js[1],&js[2],&js[3]);
- for(int i=0;i<4;i++)
- {for(int j=0;j<js[i];j++)
- {scanf("%d",&sxk[i][j]);gzh[i]+=sxk[i][j];}
- }
- for(int i=0;i<4;i++)
- {int bebao[1000000]={0};
- int k;
- for(int j=0;j<js[i];j++)
- for(k=gzh[i]/2;k>=sxk[i][j];k--)
- bebao[k]=max(bebao[k],bebao[k-sxk[i][j]]+sxk[i][j]);
- sum+=gzh[i]-bebao[gzh[i]/2];
- }
- printf("%d\n",sum);
- return 0;
- }
二、填涂颜色
# 填涂颜色
## 题目描述
由数字 $0$ 组成的方阵中,有一任意形状闭合圈,闭合圈由数字 $1$ 构成,围圈时只走上下左右 $4$ 个方向。现要求把闭合圈内的所有空间都填写成 $2$。例如:$6\times 6$ 的方阵($n=6$),涂色前和涂色后的方阵如下:
```plain
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
```
```plain
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
```## 输入格式
每组测试数据第一行一个整数 $n(1 \le n \le 30)$。
接下来 $n$ 行,由 $0$ 和 $1$ 组成的 $n \times n$ 的方阵。
方阵内只有一个闭合圈,圈内至少有一个 $0$。
//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)
## 输出格式
已经填好数字 $2$ 的完整方阵。
## 样例 #1
### 样例输入 #1
```
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
```### 样例输出 #1
```
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
```## 提示
对于 $100\%$ 的数据,$1 \le n \le 30$。
1、这题就是将二维数组中,用1围成(只有一个)的范围内变成2,在全部输出出来,很简单就是用dfs或bfs将外围的没有包围的标记,输出时,将标记的输出0,是1就输出1,是0就输出2
附代码
- #include <stdio.h>
- int a[100][100];
- int fi[4]={0,1,0,-1};
- int fj[4]={1,0,-1,0};
- int n;
- void dfs(int i,int j)
- { for(int x=0;x<4;x++)
- {int hi=i+fi[x],hj=j+fj[x];
- if(hi>=0&&hi<=n+1&&hj>=0&&hj<=n+1&&a[hi][hj]==0)
- {a[hi][hj]=3;
- dfs(hi,hj);
- }
- }
- }
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- scanf("%d",&a[i][j]);
- dfs(0,0);
- for(int i=1;i<=n;i++)
- {for(int j=1;j<=n;j++)
- {if(a[i][j]==3)printf("%d ",0);
- if(a[i][j]==1)printf("%d ",1);
- if(a[i][j]==0)printf("%d ",2);
- }
- printf("\n");
- }
- return 0;
- }
3、Corn Maze S
# [USACO11OPEN]Corn Maze S
## 题面翻译
奶牛们去一个 $N\times M$ 玉米迷宫,$2 \leq N \leq 300,2 \leq M \leq300$。
迷宫里有一些传送装置,可以将奶牛从一点到另一点进行瞬间转移。这些装置可以双向使用。
如果一头奶牛处在这个装置的起点或者终点,这头奶牛就**必须**使用这个装置。
玉米迷宫除了唯一的一个出口都被玉米包围。
迷宫中的每个元素都由以下项目中的一项组成:
1. 玉米,`#` 表示,这些格子是不可以通过的。
1. 草地,`.` 表示,可以简单的通过。
1. 传送装置,每一对大写字母 $\tt{A}$ 到 $\tt{Z}$ 表示。
1. 出口,`=` 表示。
1. 起点, `@` 表示奶牛能在一格草地上可能存在的四个相邻的格子移动,花费 $1$ 个单位时间。从装置的一个结点到另一个结点不花时间。
## 题目描述
This past fall, Farmer John took the cows to visit a corn maze. But this wasn't just any corn maze: it featured several gravity-powered teleporter slides, which cause cows to teleport instantly from one point in the maze to another. The slides work in both directions: a cow can slide from the slide's start to the end instantly, or from the end to the start. If a cow steps on a space that hosts either end of a slide, she must use the slide.
The outside of the corn maze is entirely corn except for a single exit.
The maze can be represented by an N x M (2 <= N <= 300; 2 <= M <= 300) grid. Each grid element contains one of these items:
\* Corn (corn grid elements are impassable)
\* Grass (easy to pass through!)
\* A slide endpoint (which will transport a cow to the other endpoint)
\* The exit
A cow can only move from one space to the next if they are adjacent and neither contains corn. Each grassy space has four potential neighbors to which a cow can travel. It takes 1 unit of time to move from a grassy space to an adjacent space; it takes 0 units of time to move from one slide endpoint to the other.
Corn-filled spaces are denoted with an octothorpe (#). Grassy spaces are denoted with a period (.). Pairs of slide endpoints are denoted with the same uppercase letter (A-Z), and no two different slides have endpoints denoted with the same letter. The exit is denoted with the equals sign (=).
Bessie got lost. She knows where she is on the grid, and marked her current grassy space with the 'at' symbol (@). What is the minimum time she needs to move to the exit space?
## 输入格式
第一行:两个用空格隔开的整数 $N$ 和 $M$。
第 $2\sim N+1$ 行:第 $i+1$ 行描述了迷宫中的第 $i$ 行的情况(共有$M$个字符,每个字符中间没有空格)。
## 输出格式
一个整数,表示起点到出口所需的最短时间。
## 样例 #1
### 样例输入 #1
```
5 6
###=##
#.W.##
#.####
#.@W##
######
```### 样例输出 #1
```
3
```## 提示
例如以下矩阵,$N=5,M=6$。
```plain
###=##
#.W.##
#.####
#.@W##
######
```唯一的一个装置的结点用大写字母 $\tt{W}$ 表示。
最优方案为:先向右走到装置的结点,花费一个单位时间,再到装置的另一个结点上,花费 $0$ 个单位时间,然后再向右走一个,再向上走一个,到达出口处,总共花费了 $3$ 个单位时间。
1、这题一看就是最快用BFS和队列将一组搜素的时间从0开始1-2-3----,看先到出口时就是最佳时间;
2、当然这题有点特殊,因为有传送,所以我们要记录对应传送的下标,到我们搜索时遇到传送时要传送到对应的另一个位置,并赋上步数,接着继续搜索;
附代码
- #include <stdio.h>
- #include <string.h>
- struct cs
- {int zqi;
- int zqj;
- int zhi;
- int zhj;
- int cz;
- }szz[200];
- int di[100000];
- int dj[100000];
- int qdx,hdx;
- int fi[4]={0,1,0,-1};
- int fj[4]={1,0,-1,0};
- char map[1000][1000];
- int qi,qj,zi,zj,k,s;
- int bdmap[1000][1000];
- void BFS()
- { while(qdx<hdx&&(di[qdx]!=zi||dj[qdx]!=zj))
- {int sum=bdmap[di[qdx]][dj[qdx]]+1;
- for(int x=0;x<4;x++)
- {int i=di[qdx]+fi[x],j=dj[qdx]+fj[x];
- if(i>=1&&i<=k&&j>=1&&j<=s&&map[i][j]!='#'&&bdmap[i][j]==0)
- {if(map[i][j]>='A'&&map[i][j]<='Z')
- {bdmap[i][j]=sum;char szm=map[i][j];int hi,hj;
- if(szz[szm].zqi==i&&szz[szm].zqj==j){hi=szz[szm].zhi;hj=szz[szm].zhj;}
- else {hi=szz[szm].zqi;hj=szz[szm].zqj;}
- bdmap[hi][hj]=sum;
- di[hdx]=hi;dj[hdx]=hj;hdx++;
- }
- else
- {bdmap[i][j]=sum;di[hdx]=i;dj[hdx]=j;hdx++;}
- }
- }
- qdx++;
- }
- }
- int main()
- {
- scanf("%d%d",&k,&s);
- getchar();
- for(int i=1;i<=k;i++)
- {for(int j=1;j<=s;j++)
- {char c=getchar();
- map[i][j]=c;
- if(c=='='){zi=i;zj=j;}
- else
- if(c=='@'){qi=i;qj=j;}
- else
- if(c!='#'&&c!='.')
- {if(szz[c].cz==0){szz[c].zqi=i;szz[c].zqj=j;szz[c].cz=1;}
- else
- {szz[c].zhi=i;szz[c].zhj=j;szz[c].cz=2;}
- }
- }
- getchar();
- }
- di[hdx]=qi;
- dj[hdx]=qj;
- hdx++;
- BFS();
- printf("%d\n",bdmap[zi][zj]);
- return 0;
- }
更多推荐
预备役间学习记录3
发布评论