A.肿瘤检测 / B.拦截导弹 C.Zipper / D.马走日

#A.肿瘤检测

百练2677

>###描述
>一张CT扫描的灰度图像可以用一个$$N\times N(0 < N < 100)$$的矩阵描述，矩阵上的每个点对应一个灰度值（整数），其取值范围是0-255。我们假设给定的图像中有且只有一个肿瘤。在图上监测肿瘤的方法如下：如果某个点对应的灰度值小于等于50，则这个点在肿瘤上，否则不在肿瘤上。我们把在肿瘤上的点的数目加起来，就得到了肿瘤在图上的面积。任何在肿瘤上的点，如果它是图像的边界或者它的上下左右四个相邻点中至少有一个是非肿瘤上的点，则该点称为肿瘤的边界点。肿瘤的**边界点的个数称为肿瘤的周长**。现在给定一个图像，要求计算其中的肿瘤的面积和周长。
>###输入
>输入第一行包含一个正整数$$N(0 < N < 100)$$，表示图像的大小；接下来$$N$$行，每行包含图像的一行。图像的一行用$$N$$个整数表示（所有整数大于等于0，小于等于255），两个整数之间用一个空格隔开。
>###输出
>输出只有一行，该行包含两个正整数，分别为给定图像中肿瘤的面积和周长，用一个空格分开。

保及格的题，除了一些玄学外没有坑点：
- 边界点的个数为周长。不是指该点周围有几个非肿瘤点周长就加几
- 单组测试数据，用while(cin)之类的似乎会谜之WA
- 其他玄学

```c++
//http://bailian.openjudge.cn/practice/2677/
//http://bailian.openjudge.cn/2016acmmid/a/
#include <cstdio>
#define MAX_N 100
int map[MAX_N][MAX_N];
int n;
bool isEdge(int r, int c) {
 return (r == 0 || map[r-1][c]>50) || //肿瘤的边界点的个数称为肿瘤的周长!!!!不是边的条数！！！！！！
 (r == n-1 || map[r+1][c]>50) ||
 (c == 0 || map[r][c-1]>50) ||
 (c == n-1 || map[r][c+1]>50);
}
int main (){
 int S, C;
 S = C = 0;
 scanf("%d", &n);
 for (int i = 0; i < n; i++) {
 for (int j = 0; j < n; j++) {
 scanf("%d", &map[i][j]);
 if (map[i][j]<=50) S++;
 }
 }
 for (int i = 0; i < n; i++) {
 for (int j = 0; j < n; j++) {
 if (map[i][j]<=50){
 C+=isEdge(i, j); 
 }
 }
 }
 printf("%d %d\n", S, C);
 return 0;
}
```

------------

#B.拦截导弹
百练2945
>###描述
>某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。
>###输入
>输入有两行，
>第一行，输入雷达捕捉到的敌国导弹的数量$$k(k \leq 25)$$，
>第二行，输入$$k$$个正整数，表示$$k$$枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。
>###输出
>输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。

动态规划最长**不增**子序列
```c++
//http://bailian.openjudge.cn/practice/2945/
//http://bailian.openjudge.cn/2016acmmid/b/
#include <cstdio>
int max (int a, int b) {return a>b?a:b;}
int solve(int *arr, int n) {
 int dp[n];
 int maxLen = 0;
 for (int i = 0; i < n; i++) {
 dp[i] = 1;
 int tmp=0;
 for (int j = 0; j < i; j++) {
 if (arr[i] <= arr[j]) //不增，即等于也算
 tmp = max(tmp, dp[j]);
 }
 dp[i] = max(dp[i], tmp+1);
 maxLen = max(maxLen, dp[i]);
 }
 return maxLen;
}
int main (){
 int n;
 scanf("%d", &n);
 int arr[n];
 for (int i = 0; i < n; i++) {
 scanf("%d", &arr[i]);
 }
 printf("%d\n", solve(arr, n));
 return 0;
}
```

------------

#C.Zipper
百练2192

>###描述
>Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed **arbitrarily**, but each must stay in its original order.
>
>For example, consider forming "tcraete" from "cat" and "tree":
>
>String A: cat
>String B: tree
>String C: tcraete
>
>As you can see, we can form the third string by **alternating** characters from the two strings. As a second example, consider forming "catrtee" from "cat" and "tree":
>
>String A: cat
>String B: tree
>String C: catrtee
>
>Finally, notice that it is impossible to form "cttaree" from "cat" and "tree".
>###输入
>The first line of input contains a single positive integer from 1 through 1000. It represents the number of data sets to follow. The processing for each data set is identical. The data sets appear on the following lines, one data set per line.
>
>For each data set, the line of input consists of three strings, separated by a single space. All strings are composed of upper and lower case letters only. The length of the third string is always the sum of the lengths of the first two strings. The first two strings will have lengths between 1 and 200 characters, inclusive.
>###输出
>For each data set, print:
>Data set n: yes
>if the third string can be formed from the first two, or
>Data set n: no
if it cannot. Of course n should be replaced by the data set number. See the sample output below for an example.

题目大意：有A、B、C三个字符串，C串应由A、B串中的字母任意间隔拼成，字母的前后顺序不变。问一组ABC，C是否是一个合法的字符串。

样例说明：
1. cat  tree  tcraete yes
2. cat  tree  catrtee yes
3. cat  tree  cttaree/cttaree no
4. cta  tree  ctareet no
 - ctareet？ctareet？
 - 第四种需要注意，因为C串应为AB串组合而来，所以某一个字母只会从与某一个源串而来，也就是说即使是相同的字母，在搜索时只能使用一次。
 - 不能说C串中有cta和tree子序列就说yes。

```c++
//http://bailian.openjudge.cn/practice/2192/
//DFS
#include <cstdio>
#include <cstring>
#define LEN 201
char str1[LEN], str2[LEN], str3[LEN * 2];
bool hasSolution;
void solve(int str1RIndex, int str2RIndex, int str3RIndex) {
 if (hasSolution) return;
 if (str3RIndex == -1) {
 hasSolution = true;
 return;
 }
 if ( str1[str1RIndex] != str3[str3RIndex] && str2[str2RIndex]!=str3[str3RIndex]) 
 return;
 if (str1[str1RIndex] == str3[str3RIndex])
 solve(str1RIndex-1, str2RIndex, str3RIndex-1);//非此即彼
 if (str2[str2RIndex] == str3[str3RIndex]) 
 solve(str1RIndex, str2RIndex-1, str3RIndex-1);
 return;
}
int main() {
 int n;
 scanf("%d", &n);
 for (int T = 1; T <= n; T++) {
 hasSolution=false;
 scanf("%s %s %s", str1, str2, str3);
 solve(strlen(str1)-1, strlen(str2)-1, strlen(str3)-1);
 printf("Data set %d: %s\n", T, hasSolution? "yes" : "no");
 }
 return 0;
}
```

------------

#D.马走日
百练4123
>###描述
>马在中国象棋以日字形规则移动。
>请编写一段程序，给定$$n*m$$大小的棋盘，以及马的初始位置$$(x,y)$$，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。
>###输入
>第一行为整数$$T(T \lt 10)$$，表示测试数据组数。
>每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标$$n,m,x,y$$。$$(0\leq x\leq n-1, 0\leq y\leq m-1,m\lt 10,n\lt 10)$$
>###输出
>每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，0为无法遍历一次。

纯dfs，结束条件是走满$$(R\times C)$$个点
```c++
//http://bailian.openjudge.cn/2016acmmid/d/
//http://bailian.openjudge.cn/practice/4123/
#include <cstdio>
#include <memory.h>
#define MAX_R 11
#define MAX_C 11
int rr[] = {-1,-2,-2,-1,1,2,2,1};//西偏北 北偏西 北偏东 东偏北 东偏南 南偏东 南偏西 西偏南
int cc[] = {-2,-1,1,2,2,1,-1,-2};
int R, C;
bool vis[MAX_R][MAX_C];
int res;
int stepCnt = 1;//已走步数
int d(int r, int c){
 vis[r][c] = true;
 if (stepCnt == R*C) {
 res++;
 }
 else {
 for (int i = 0; i < 8; i++) {
 int nr = r+rr[i], nc = c+cc[i];
 if (nr >= 0 && nr < R && nc >= 0 && nc < C && !vis[nr][nc]){
 vis[nr][nc] = true;
 stepCnt++;
 d(nr, nc);
 stepCnt--;
 vis[nr][nc] = false;
 }
 }
 }
 return 0;
}
int main (){
 int T;
 scanf("%d", &T);
 while(T--){
 res = 0;
 stepCnt = 1;
 int startR, startC;
 scanf("%d %d %d %d", &R, &C, &startR, &startC);
 memset(vis, false, sizeof(vis));
 d(startR, startC);
 printf("%d\n", res);
 }
 return 0;
}
```

A.肿瘤检测 / B.拦截导弹 C.Zipper / D.马走日

已有 4 条评论

添加新评论

最近回复

分类

归档

Links

其它