Scratch编程一级 题库
成绩判定
给定一门课的考试分数,如果分数大于等于60,则该门课成绩合格,记为"P", 否者成绩不合格,记为"F"。
时间限制:1000
内存限制:65536
输入
一个整数s,表示这门课的分数.(0 ≤ s ≤ 100)
输出
如果成绩合格,输出字母P,否者输出字母F。
样例输入
59
样例输出
F
#include <bits/stdc++.h>
using namespace std;
int main() {
int s;
scanf("%d", &s);
if (s >= 60) {
printf("P");
} else {
printf("F");
}
return 0;
}简单排序
依次输入3个整数a、b、c,将他们从小到大的顺序输出。
时间限制:1000
内存限制:65536
输入
一行3个整数a、b、c,以空格分隔。 0 < a,b,c < 108
输出
一行3个整数,即将a、b、c从小到大排序的3个整数,整数之间以一个空格分隔。
样例输入
10 5 20
样例输出
5 10 20
#include <bits/stdc++.h>
using namespace std;
int main() {
int a[3];
scanf("%d%d%d", &a[0], &a[1], &a[2]);
sort(a, a + 3); // 从小到大排序
printf("%d %d %d", a[0], a[1], a[2]);
return 0;
}数字求和
给定一个正整数a,以及另外的5个正整数,问题是:这5个整数中,小于a的整数的和是多少?
时间限制:3000
内存限制:65536
输入
输入一行,只包括6个小于100的正整数,其中第一个正整数就是a。
输出
输出一行,给出一个正整数,是5个数中小于a的数的和。
样例输入
10 1 2 3 4 11
样例输出
10
#include <bits/stdc++.h>
using namespace std;
int main() {
int a;
scanf("%d", &a);
int sum = 0;
for (int i = 0; i < 5; i++) {
int t;
scanf("%d", &t);
if (t < a) {
sum = sum + t;
}
}
printf("%d", sum);
return 0;
}数1的个数
给定一个十进制正整数n,写下从1到n的所有整数,然后数一下其中出现的数字“1”的个数。
例如当n=2时,写下1,2。这样只出现了1个“1”;当n=12时,写下1,2,3,4,5,6,7,8,9,10,11,12。这样出现了5个“1”。
时间限制:1000
内存限制:65536
输入
正整数n。1 <= n <= 10000。
输出
一个正整数,即“1”的个数。
样例输入
12
样例输出
5
#include <bits/stdc++.h>
using namespace std;
// 把数字转字符串,统计字符串中有多少个'1'的字符
int count_1(int x) {
char m[20];
int r = 0;
int num = sprintf(&m[0], "%d", x);
for (int i = 0; i < num; i++) {
if (m[i] == '1') {
r = r + 1;
}
}
return r;
}
int main() {
int sum = 0;
int max_x = 0;
scanf("%d", &max_x);
for (int i = 1; i <= max_x; i++) {
sum = sum + count_1(i);
}
printf("%d", sum);
return 0;
}红与黑
有一间长方形的房子, 地上铺了红色、 黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上, 只能向相邻的黑色瓷砖移动。 请写一个程序, 计算你总共能够到达多少块黑色的瓷砖。
时间限制: 1000
内存限制: 65536
输入
包括多个数据集合。每个数据集合的第一行是两个整数W和H,分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中,每行包括W个字符。每个字符表示一块瓷砖的颜色,规则如下 1)‘.’:黑色的瓷砖; 2)‘#’:白色的瓷砖; 3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。 当在一行中读入的是两个零时,表示输入结束。
输出
对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
样例输入
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 0 0
样例输出
45
//解法1:深搜
#include <bits/stdc++.h>
using namespace std;
#define N 25
char mp[N][N];//地图
int w, h, ct;//h:行数,w:ct:结果计数
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向数组
bool vis[N][N];
void dfs(int sx, int sy)
{
for(int i = 0; i < 4; ++i)
{
int x = sx + dir[i][0], y = sy + dir[i][1];
if(x >= 1 && x <= h && y >= 1 && y <= w && vis[x][y] == false && mp[x][y] != '#')
{
ct++;
vis[x][y] = true;
dfs(x, y);
}
}
}
int main()
{
int stx, sty;//起始位置
while(true)
{
cin >> w >> h;
if(w == 0 && h == 0)
return 0;
for(int i = 1; i <= h; ++i)
for(int j = 1; j <= w; ++j)
{
cin >> mp[i][j];
if(mp[i][j] == '@')
stx = i, sty = j;
}
memset(vis, 0, sizeof(vis));//多组数据,注意状态还原
ct = 1;
vis[stx][sty] = true;
dfs(stx, sty);
cout << ct << endl;
}
return 0;
}//解法2:广搜
#include <bits/stdc++.h>
using namespace std;
#define N 25
struct Node
{
int x, y;
Node(){}
Node(int a, int b):x(a),y(b){}
};
char mp[N][N];//地图
int w, h;//w:列数 h:行数
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向数组
bool vis[N][N];
int bfs(int sx, int sy)//传入起始位置
{
queue<Node> que;
vis[sx][sy] = true;
que.push(Node(sx, sy));
int ct = 1;//计数,看可以到达几个黑色格子
while(que.empty() == false)
{
Node u = que.front();
que.pop();
for(int i = 0; i < 4; ++i)
{
int x = u.x + dir[i][0], y = u.y + dir[i][1];
if(x >= 1 && x <= h && y >= 1 && y <= w && vis[x][y] == false && mp[x][y] != '#')
{
vis[x][y] = true;
que.push(Node(x, y));
ct++;
}
}
}
return ct;
}
int main()
{
int stx, sty;
while(true)
{
cin >> w >> h;
if(w == 0 && h == 0)
return 0;
for(int i = 1; i <= h; ++i)
for(int j = 1; j <= w; ++j)
{
cin >> mp[i][j];
if(mp[i][j] == '@')
stx = i, sty = j;
}
memset(vis, 0, sizeof(vis));
cout << bfs(stx, sty) << endl;
}
return 0;
}//解法3:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 1001
using namespace std;
int m,n;
char ch;
int maps[N][N];
int vis[N][N];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int cnt;
void dfs(int x,int y)
{
for(int i=0;i<4;i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&vis[nx][ny]==0&&maps[nx][ny]==1)
{
vis[nx][ny]=1;
cnt++;
dfs(nx,ny);
}
}
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF&&m&&n)
{
int x,y;
cnt=1;
memset(vis,0,sizeof(vis));
memset(maps,0,sizeof(maps));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>ch;
if(ch=='@')
{
x=i;
y=j;
maps[i][j]=1;
}
if(ch=='.')
maps[i][j]=1;
if(ch=='#')
maps[i][j]=0;
}
vis[x][y]=1;
dfs(x,y);
cout<<cnt<<endl;
}
return 0;
}迷宫问题
定义一个二维数组:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫, 其中的 1 表示墙壁, 0 表示可以走的路, 只能横着走或竖着走, 不能斜着走, 要求编程序找出从左上角到右下角的最短路线。
时间限制: 1000
内存限制: 65536
输入
一个 5 × 5 的二维数组, 表示一个迷宫。 数据保证有唯一解。
输出
左上角到右下角的最短路径, 格式如样例所示。
样例输入
0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
样例输出
(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)
/*#include <iostream>*/
#include <bits/stdc++.h>
using namespace std;
const int idata = 50 + 5;
int maps[idata][idata];
bool judge[idata][idata];
int change[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int nx, ny;
int x[idata], y[idata];
int show[30];
bool flag;
void print(int tail) {
if (show[tail])
print(show[tail]);
cout << "(" << x[tail] << ", " << y[tail] << ")" << endl;
}
int main() {
int head, tail;
register int i, j;
for (i = 0; i < 5; i++) {
for (j = 0; j < 5; j++) {
cin >> maps[i][j];
if (maps[i][j] == 1)
judge[i][j] = 1;
}
}
head = 0;
tail = 1;
judge[0][0] = 1;
show[tail] = head;
while (tail > head) {
head++;
for (i = 0; i < 4; i++) {
nx = x[head] + change[i][0];
ny = y[head] + change[i][1];
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && !judge[nx][ny]) {
tail++;
x[tail] = nx;
y[tail] = ny;
judge[nx][ny] = 1;
show[tail] = head;
if (nx == 4 && ny == 4) {
flag = 1;
print(tail);
break;
}
}
}
if (flag)
break;
}
return 0;
}二叉树的深度
给定一棵二叉树,求该二叉树的深度
二叉树深度定义:从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的节点个数为树的深度
时间限制:1000
内存限制:65535
输入
第一行是一个整数n,表示二叉树的结点个数。二叉树结点编号从1到n,根结点为1,n <= 10 接下来有n行,依次对应二叉树的n个节点。 每行有两个整数,分别表示该节点的左儿子和右儿子的节点编号。如果第一个(第二个)数为-1则表示没有左(右)儿子
输出
输出一个整型数,表示树的深度
样例输入
3 2 3 -1 -1 -1 -1
样例输出
2
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 7;
struct node {
int left, right;
} t[MAXN];
int n;
void build() {
for (int i = 1; i <= n; i++) {
cin >> t[i].left >> t[i].right;
}
}
#define rep1(i, n) for (int i = 1; i <= n; i++)
inline int dfs(int x) {
if (x == -1)
return 0;
return max(dfs(t[x].left), dfs(t[x].right)) + 1;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
build();
cout << dfs(1);
return 0;
}//题解2
#include <algorithm>
#include <iostream>
using namespace std;
int meng[102][30]; /*a[i][0]表示节点i的左孩子节点编号,
a[i][1]表示节点i的右孩子节点编号,a[i][2]表示i节点的父节点编号。*/
int a, b;
int dfs(int root) {
if (meng[root][0] == -1 && meng[root][1] == -1)
return 1;
else {
int left = 0, right = 0;
if (meng[root][0] >= 0)
left = dfs(meng[root][0]);
/*如果该节点满足不为-1证明它有父节点,
递归回去去证明它的父节点上面是否也有父节点*/
if (meng[root][1] >= 0) {
right = dfs(meng[root][1]);
}
return max(right, left) + 1;
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a >> b;
// 二维是为了更好的判断左孩子还是右孩子,父节点
meng[i][0] = a; // i的左孩子是a
meng[i][1] = b; // i的右孩子是b
}
cout << dfs(1) << endl;
return 0;
}表达式· 表达式树· 表达式求值
众所周知, 任何一个表达式, 都可以用一棵表达式树来表示。 例如,
表达式 a+b*c, 可以表示为如下的表达式树:
+
/ \
a *
/ \
b c
现在, 给你一个中缀表达式, 这个中缀表达式用变量来表示(不含数字), 请你将这个中缀表达式用表达式二叉树的形式输出出来。
时间限制: 1000
内存限制: 65535
输入
输入分为三个部分。 第一部分为一行,即中缀表达式(长度不大于50)。中缀表达式可能含有小写字母代表变量(a-z),也可能含有运算符(+、-、*、/、小括号),不含有数字,也不含有空格。 第二部分为一个整数n(n < 10),表示中缀表达式的变量数。 第三部分有n行,每行格式为C x,C为变量的字符,x为该变量的值。
输出
输出分为三个部分,第一个部分为该表达式的逆波兰式,即该表达式树的后根遍历结果。占一行。 第二部分为表达式树的显示,如样例输出所示。如果该二叉树是一棵满二叉树,则最底部的叶子结点,分别占据横坐标的第1、3、5、7……个位置(最左边的坐标是1),然后它们的父结点的横坐标,在两个子结点的中间。如果不是满二叉树,则没有结点的地方,用空格填充(但请略去所有的行末空格)。每一行父结点与子结点中隔开一行,用斜杠(/)与反斜杠(\)来表示树的关系。/出现的横坐标位置为父结点的横坐标偏左一格,\出现的横坐标位置为父结点的横坐标偏右一格。也就是说,如果树高为m,则输出就有2m-1行。 第三部分为一个整数,表示将值代入变量之后,该中缀表达式的值。需要注意的一点是,除法代表整除运算,即舍弃小数点后的部分。同时,测试数据保证不会出现除以0的现象。
样例输入
a+b*c 3 a 2 b 7 c 5
样例输出
abc*+ + / \ a * / \ b c 37
#include <cmath>
#include <cstring>
#include <iostream>
#include <stack>
#include <string>
#define OK 1
#define ERROR 0
#define MAXSIZE 50
using namespace std;
struct number {
char ch;
int value;
};
number a[10];
// 定义二叉树类型
typedef struct BiNode {
char date;
struct BiNode *lchild, *rchild;
} BiNode;
// 定义栈类型
typedef struct SqStack {
char *base;
char *top;
int stacksize;
} SqStack;
// 初始化栈
int InitStack(SqStack &S) {
S.base = new char[MAXSIZE];
if (!S.base)
exit(ERROR);
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
// 出栈
char Pop(SqStack &S) {
if (S.top == S.base)
return ERROR;
char e = *(--S.top);
return e;
}
// 入栈
int Push(SqStack &S, char e) {
if (S.top - S.base == S.stacksize)
return ERROR;
*(S.top++) = e;
return OK;
}
// 将中缀表达式转化为后缀表达式
string Change(string str) {
// str为中缀表达式,str2为后缀表达式
string str2 = "";
char ch, e; // e用于保存栈中弹出的元素
SqStack S1; // S1用于存放操作符(为辅助栈),S用于存放后续表达式
InitStack(S1);
for (int i = 0; i < str.size(); i++) {
ch = str[i];
if (ch >= 'a' && ch <= 'z') {
str2 += ch;
}
if (ch == '(')
Push(S1, ch);
if (ch == ')') {
while (*(S1.top - 1) != '(') {
e = Pop(S1);
str2 += e;
}
Pop(S1); // 左括号出栈但不入S2栈中
}
// 遇到+或-时
// 栈空/栈顶为左括号:直接入栈
// 否则一直出栈,直到栈空/栈顶为左括号,再入栈
if (ch == '+' || ch == '-') {
while (*(S1.top - 1) != '(' && S1.base != S1.top) {
e = Pop(S1);
str2 += e;
}
Push(S1, ch);
}
// 遇到*或/时
// 栈空/栈顶为左括号/栈顶操作符为+ or -:直接入栈
// 否则一直出栈,直到满足上述条件,再入栈
if (ch == '*' || ch == '/') {
while (S1.base != S1.top && *(S1.top - 1) != '(' &&
*(S1.top - 1) != '-' && *(S1.top - 1) != '+') {
e = Pop(S1);
str2 += e;
}
Push(S1, ch);
}
}
// 中缀表达式遍历完成,还需检查栈中是否有未输出字符
// 判断栈空,非空则直接出栈
while (S1.base != S1.top) {
e = Pop(S1);
if (e != '(')
str2 += e;
}
return str2;
}
struct BiNode *s[MAXSIZE]; // 定义栈,该栈用于存放树
int top = -1;
// 建立二叉树
BiNode *CreatTree(string str) {
// str为后缀表达式
BiNode *T, *T2;
SqStack S;
BiNode *e1, *e2;
int i;
InitStack(S);
for (i = 0; i < str.size() - 1; i++) {
if (str[i] >= 'a' && str[i] <= 'z') {
T = new BiNode;
T->date = str[i];
T->lchild = T->rchild = NULL;
s[++top] = T;
} else {
T = new BiNode;
T->date = str[i];
e1 = s[top--];
e2 = s[top--];
T->lchild = e2;
T->rchild = e1;
s[++top] = T;
}
}
T = new BiNode;
T->date = str[i];
T->rchild = s[top--];
T->lchild = s[top--];
s[++top] = T;
T2 = new BiNode;
T2 = s[top];
return T2;
}
int Seek(char e, int n) {
for (int i = 0; i < n; i++) {
if (a[i].ch == e)
return a[i].value;
}
}
int Count(string str, int n) {
// str为后缀表达式数组,n变量个数
int sum = 0;
stack<int> S;
int x, x1, x2;
for (int i = 0; i < n; i++) {
cin >> a[i].ch >> a[i].value;
}
for (int i = 0; i < str.size(); i++) {
if (str[i] >= 'a' && str[i] <= 'z') {
x = Seek(str[i], n);
S.push(x);
} else {
x2 = S.top();
S.pop(); // 左操作数
x1 = S.top();
S.pop(); // 右操作数
switch (str[i]) {
case '+':
sum = x1 + x2;
break;
case '-':
sum = x1 - x2;
break;
case '*':
sum = x1 * x2;
break;
case '/':
sum = x1 / x2;
break;
}
S.push(sum);
}
}
sum = S.top();
return sum;
}
char arr[1000][1000];
// 打印二叉树
void PrintTree(int tag, BiNode *T, int x, int m, int y) {
arr[2 * tag - 1][(x + m) / 2] = T->date;
if (tag != 1) {
if (y == 1)
arr[2 * tag - 2][m] = '/';
else
arr[2 * tag - 2][x] = '\\';
}
if (T->lchild != NULL)
PrintTree(tag + 1, T->lchild, x, (x + m) / 2 - 1, 1);
if (T->rchild != NULL)
PrintTree(tag + 1, T->rchild, (x + m) / 2 + 1, m, 0);
}
// 计算二叉树的深度
int Depth(BiNode *T) {
int m, n;
if (T == NULL)
return 0;
else {
m = Depth(T->lchild);
n = Depth(T->rchild);
if (m > n)
return (m + 1);
else
return (n + 1);
}
}
bool Judge(int i, int j, int n) {
for (int k = j + 1; k <= n; k++) {
if (arr[i][k] != ' ')
return 1;
}
return 0;
}
int main() {
string str1; // 中序表达式
cin >> str1;
int n; // 变量个数
cin >> n;
string str2 = Change(str1); // str2为后序表达式
BiNode *T = CreatTree(str2);
int sum = Count(str2, n);
int dp = Depth(T);
cout << str2 << endl;
memset(arr, ' ', sizeof(arr));
PrintTree(1, T, 1, pow(2.0, dp) - 1, 0);
for (int i = 1; i <= 2 * dp - 1; i++) {
for (int j = 1; j <= pow(2.0, dp) - 1; j++) {
cout << arr[i][j];
if (arr[i][j] != ' ') {
if (Judge(i, j, pow(2.0, dp) - 1))
continue;
else
break;
}
}
cout << endl;
}
cout << sum << endl;
return 0;
}多项式相加
我们经常遇到两多项式相加的情况, 在这里, 我们就需要用程序来模拟实现把两个多项式相加到一起。 首先, 我们会有两个多项式,每个多项式是独立的一行, 每个多项式由系数、 幂数这样的多个整数对来表示。
如多项式 2x20- x17+ 5x9- 7x7+ 16x5+ 10x4 + 22x2- 15
对应的表达式为: 2 20 -1 17 5 9 - 7 7 16 5 10 4 22 2 -15 0。
为了标记每行多项式的结束, 在表达式后面加上了一个幂数为负数的整数对。
同时输入表达式的幂数大小顺序是随机的。我们需要做的就是把所给的两个多项式加起来。
时间限制: 1000
内存限制: 65536
输入
输入包括多行。 第一行整数 n,表示有多少组的多项式需要求和。 (1 <n < 100) 下面为 2n 行整数, 每一行都是一个多项式的表达式。 表示 n组需要相加的多项式。 每行长度小于 300。
输出
输出包括 n 行, 每行为 1 组多项式相加的结果。 在每一行的输出结果中, 多项式的每一项用“[x y]” 形式的字符串表示, x 是该项的系数、 y 是该项的幂数。 要求按照每一项的幂从高到低排列, 即先输出幂数高的项、 再输出幂数低的项。 系数为零的项不要输出。
样例输入
2 -1 17 2 20 5 9 -7 7 10 4 22 2 -15 0 16 5 0 -1 2 19 7 7 3 17 4 4 15 10 -10 5 13 2 -7 0 8 -8 -1 17 2 23 22 2 6 8 -4 7 -18 0 1 5 21 4 0 -1 12 7 -7 5 3 17 23 4 15 10 -10 5 13 5 2 19 9 -7
样例输出
[ 2 20 ] [ 2 19 ] [ 2 17 ] [ 15 10 ] [ 5 9 ] [ 6 5 ] [ 14 4 ] [ 35 2 ] [ -22 0 ] [ 2 23 ] [ 2 19 ] [ 2 17 ] [ 15 10 ] [ 6 8 ] [ 8 7 ] [ -3 5 ] [ 44 4 ] [ 22 2 ] [ -18 0 ]
提示
第一组样例数据的第二行末尾的 8 -8, 因为幂次-8 为负数, 所以这一行数据结束, 8 -8 不要参与计算。
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
for (int i = 0; i != n; ++i) {
map<int, int> ploy;
int index, value, over = 0;
while (cin >> value >> index) {
if (index < 0)
over++;
else {
pair<map<int, int>::iterator, bool> ret =
ploy.insert(make_pair(index, value));
if (!ret.second)
ret.first->second += value;
}
if (over == 2)
break;
}
for (map<int, int>::reverse_iterator riter = ploy.rbegin();
riter != ploy.rend(); ++riter) {
if (riter->second != 0)
cout << "[ " << riter->second << ' ' << riter->first << " ] ";
}
cout << endl;
}
return 0;
}
扩号匹配问题
在某个字符串(长度不超过 100)中有左括号、 右括号和大小写字母;规定(与常见的算数式子一样) 任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。 写一个程序, 找到无法匹配的左括号和右括号, 输出原来字符串, 并在下一行标出不能匹配的括号。 不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.
时间限制: 3000
内存限制: 65536
输入
输入包括多组数据, 每组数据一行, 包含一个字符串, 只包含左右括号和大小写字母, 字符串长度不超过 100
输出
对每组输出数据, 输出两行, 第一行包含原始输入字符, 第二行由"$","?"和空格组成, "$"和"?"表示与之对应的左括号和右括号不能匹配。
样例输入
((ABCD(x) )(rttyy())sss)(
样例输出
((ABCD(x) $$ )(rttyy())sss)( ? ?$
// 就近原则匹配:栈
// 遍历字符串
// 遇到左括号,将其下标入栈
// 右括号则先判断栈内元素情况
// 1.空,则将其下表记录到数组中
// 2.非空,则栈顶元素弹出(匹配到了)
// 将字符串便遍历后,将栈内元素记录入另一个数组
// 用两数组内的对应下标分别改成对应字符
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
string s;
char ans[N]; // 第二排的输出数组
stack<int> st;
int a[N], cnt = 1; // 未匹配的右括号的下标存储
int b[N], cnn = 1; // 未匹配的左括号的下标存储
int main() {
while (getline(cin, s)) { // 输入不结束
memset(ans, 0, sizeof(ans));
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
cnt = 1;
cnn = 1; // 数据初始化
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') {
st.push(i); // 左括号统一入栈
}
if (s[i] == ')') {
if (!st.empty()) {
st.pop(); // 若栈非空,则可以匹配
} else {
a[cnt++] = i; // 否则无法匹配,记录
}
}
}
if (!st.empty())
while (!st.empty()) {
b[cnn++] = st.top();
st.pop();
} // 栈内数据(下标)的出栈
for (int i = 1; i < cnn; i++) {
ans[b[i]] = '$'; // 在ans内标记
}
for (int i = 1; i < cnt; i++) {
ans[a[i]] = '?'; // 在ans内标记
}
cout << s << endl;
for (int i = 0; i < s.size(); i++) {
if (ans[i] == 0)
cout << " ";
if (ans[i] == '$')
cout << "$";
if (ans[i] == '?')
cout << "?"; // 格式转化
}
cout << endl;
}
return 0;
}//解法2:递归
#include <bits/stdc++.h>
using namespace std;
#define N 105
char s[N], sign[N];
int si, len;
void find()//找下一个右括号 如果找到,si指向右括号 如果没找到,做标记
{
int lp = si;//当前左括号的下标
si++;
while(si < len)
{
if(s[si] == ')')
return;
else if(s[si] == '(')
find();
si++;
}
sign[lp] = '$';//没有找到右括号,左括号的位置标记为$
}
int main()
{
while(cin >> s)
{
len = strlen(s);
for(int i = 0; i < len; ++i)//初始化sign字符串为空格
sign[i] = ' ';
sign[len] = '\0';
si = 0;
while(si < len)
{
if(s[si] == ')')//右括号的位置标记为?
sign[si] = '?';
else if(s[si] == '(')
find();
si++;
}
cout << s << endl << sign << endl;
}
return 0;
}拼写检查
现在有一些英语单词需要做拼写检查, 你的工具是一本词典。 需要检查的单词, 有的是词典中的单词, 有的与词典中的单词相似, 你的任务是发现这两种情况。 单词 A 与单词 B 相似的情况有三种:
1、 删除单词 A 的一个字母后得到单词 B;
2、 用任意一个字母替换单词 A 的一个字母后得到单词 B;
3、 在单词 A 的任意位置增加一个字母后得到单词 B。
你的任务是发现词典中与给定单词相同或相似的单词。
时间限制: 2000
内存限制: 65536
输入
第一部分是词典中的单词, 从第一行开始每行一个单词, 以"#"结束。
词典中的单词保证不重复, 最多有 10000 个。 第二部分是需要查询的单词, 每行一个, 以"#"结束。 最多有 50 个需要查询的单词。 词典中的单词和需要查询的单词均由小写字母组成, 最多包含 15 个字符。
输出
按照输入的顺序, 为每个需要检查的单词输出一行。 如果需要检查的单词出现在词典中, 输出“?x is correct", ?x 代表需要检查的单词。
如果需要检查的单词没有出现在词典中, 则输出"?x: ?x1 ?x2 ...?xn",其中?x 代表需要检查的单词, ?x1...?xn 代表词典中与需要检查的单词相似的单词, 这些单词中间以空格隔开。 如果没有相似的单词, 输出"?x:"即可。
样例输入
i is has have be my more contest me too if award # me aware m contest hav oo or i fi mre #
样例输出
me is correct aware: award m: i my me contest is correct hav: has have oo: too or: i is correct fi: i mre: more me
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
using namespace std;
bool IsSame(string a, string b) {
char drop;
// a短
int mi = min(a.length(), b.length());
string a1 = a;
string b1 = b;
sort(a1.begin(), a1.end());
sort(b1.begin(), b1.end());
bool exis = false;
for (int i = 0; i < mi; i++) {
if (a1[i] != b1[i]) {
drop = b1[i];
exis = true;
break;
}
}
if (!exis) {
drop = b1[b1.length() - 1];
}
string ti;
bool ex = false;
for (int i = 0; i < a.length(); i++) {
if (a[i] != b[i]) {
ex = true;
ti = a.substr(0, i);
ti = ti + drop;
ti = ti + a.substr(i, 1000);
break;
}
}
if (!ex) {
ti = a + drop;
}
if (ti != b) {
return false;
} else {
return true;
}
}
int main() {
string dictionary[10010];
string words[60];
string a, b;
int dic = 0;
int m = 0;
while (1) {
cin >> a;
if (a == "#") {
break;
} else {
dictionary[dic++] = a;
}
}
while (1) {
cin >> b;
if (b == "#") {
break;
} else {
words[m++] = b;
}
}
for (int i = 0; i < m; i++) {
bool you = false;
for (int j = 0; j < dic; j++) {
if (dictionary[j] == words[i]) {
cout << words[i] << " is correct" << endl;
you = true;
break;
}
} // 判断是否完全相同。
if (you != true) {
cout << words[i] << ": ";
for (int j = 0; j < dic; j++) {
int somewhat = words[i].length() - dictionary[j].length();
if (somewhat == 0) {
for (int k = 0; k < words[i].length(); k++) {
if (words[i][k] != dictionary[j][k]) {
string tishen = words[i];
tishen[k] = dictionary[j][k];
if (tishen == dictionary[j]) {
cout << dictionary[j] << " ";
}
}
}
}
if (abs(somewhat) == 1) {
if (words[i].length() > dictionary[j].length()) {
if (IsSame(dictionary[j], words[i])) {
cout << dictionary[j] << " ";
}
} else {
if (IsSame(words[i], dictionary[j])) {
cout << dictionary[j] << " ";
}
}
}
}
cout << endl;
}
}
system("pause");
}利用队列进行数字排序
对于 N 个数字, 有人提出了如下的排序策略:
例如, 对于数字 53、 47、 85、 38、 64、 23
先建立 10 个队列(0 到 9) , 用于存放数字的大小, 将这 N 个数字依个位存放入各自的队列之中, 然后再按队列 0 到队列 9 依次出队。
例如, 对于上面的数字, 依次进队后, 结果如下:
队列 3: 53、 23 队列 4: 64 队列 5: 85 队列 7: 47 队列 8: 38
将其依次出队后, 结果为 53,23,64,85,47,38
然后, 再将方才出队后的队对, 依照十位放入各自的队列之中, 然后再按队列 0 到队列 9 依次出队
例如, 对于上面刚刚出队的序列 53,23,64,85,47,38, 将其依次进队,结果如下:
队列 2: 23 队列 3: 38 队列 4: 47 队列 5: 53 队列 6: 64 队列 8: 85
将其依次出队后, 结果为 23,38,47,53,64,85.因为这组数字最大只是两位数, 所以排序结束。
如果还有更大的数字, 那么, 接下来就是其百位、 千位……(如果位数不够, 就补 0.比如最大的数字是四位数, 那么数字 23 就当成 0023处理)
请根据上述算法, 对这些数字进行排序
时间限制: 1000
内存限制: 65535
输入
分为两行, 第一行为一个数字 N(1 <= N <= 1000), 表示数字的个数第二行为 N 个数字(都是非负数) , 以空格相隔, 最大的数字不超过9999
输出
输出两个部分 第一个部分为第一次进队出队的结果, 先显示一行:Step1. 之后用Queue0:...表示, 共 10 行, 结果用空格分隔, 下同 之后为第二次进队出队的结果(如果需要第二次进队出队的话) , 先显示一行: Step2. 之后仍然用 Queue0:...表示, 共 10 行 之后如果需要的话, 则分别显示第三次、 第四次的进队出队结果 第二部分为一行,即将数字排序后的结果(升序排序)
样例输入
20 41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36
样例输出
Step1. Queue0:0 Queue1:41 81 61 91 Queue2:62 42 Queue3: Queue4:34 24 64 Queue5:5 45 95 Queue6:36 Queue7:67 27 27 Queue8:78 58 Queue9:69 Step2. Queue0:0 5 Queue1: Queue2:24 27 27 Queue3:34 36 Queue4:41 42 45 Queue5:58 Queue6:61 62 64 67 69 Queue7:78 Queue8:81 Queue9:91 95 0 5 24 27 27 34 36 41 42 45 58 61 62 64 67 69 78 81 91 95
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define MaxSize 2000
typedef struct ss {
ElemType data[MaxSize];
int front, rear;
} SqQueue;
void InitQueue(SqQueue *&q) {
q = (SqQueue *)malloc(sizeof(SqQueue));
q->front = q->rear = -1;
}
void DestoryQueue(SqQueue *&q) { free(q); }
bool QueueEmpty(SqQueue *q) { return (q->front == q->rear); }
bool enQueue(SqQueue *&q, ElemType e) {
if (q->rear == MaxSize - 1)
return false;
q->rear++;
q->data[q->rear] = e;
return true;
}
bool deQueue(SqQueue *&q, ElemType &e) {
if (q->rear == q->front)
return false;
q->front++;
e = q->data[q->front];
return true;
}
int Num(int h) // 返回h的位数
{
int i = 0;
if (h == 0)
return 1;
while (h > 0) {
i++;
h /= 10;
}
return i;
}
int data(int g, int num) // 返回num的第g位数字
{
int result, i = 1;
int k = Num(num); // 获取位数
if (num == 0 || g > k)
return 0;
else if (num <= 9 && g == 1)
return num;
while (num >= 10 && i < g) {
num /= 10;
i++;
}
result = num % 10;
return result;
}
int main() {
int n, i = 0, j, a[100], max = 0, k = 0, e, t = 0;
scanf("%d\n", &n);
SqQueue *q[10];
for (i = 0; i < 10; i++) {
InitQueue(q[i]);
}
for (i = 0; i < n; i++) {
if (i != n - 1)
scanf("%d ", &a[i]);
else
scanf("%d", &a[i]);
} // a[i]='\0';
for (i = 0; i < n; i++) // 找出最大值
{
k = Num(a[i]);
if (k > max)
max = k;
}
// printf("%d\n",max);
for (i = 1; i <= max; i++) //
{
printf("Step%d.\n", i);
for (j = 0; j < 10; j++) { // 建立0-9的队对应的数字并输出
for (k = 0; k < n; k++) {
if (data(i, a[k]) == j)
enQueue(q[j], a[k]);
}
}
t = 0;
for (j = 0; j < 10; j++) {
printf("Queue%d:", j);
while (!QueueEmpty(q[j])) {
deQueue(q[j], e);
a[t++] = e;
printf("%d ", e);
}
printf("\n");
}
// printf("\n");
}
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
system("pause");
return 0;
}数字变换
给定一个包含 5 个数字(0-9)的字符串, 例如 “02943”, 请将“12345”变换到它。 你可以采取 3 种操作进行变换
1. 交换相邻的两个数字
2. 将一个数字加 1。 如果加 1 后大于 9, 则变为 0
3. 将一个数字加倍。 如果加倍后大于 9,则将其变为加倍后的结果除以 10 的余数。
最多只能用第 2 种操作 3 次, 第 3 种操作 2 次 求最少经过多少次操作可以完成变换。
时间限制: 1000
内存限制: 65536
输入
有最多 100,000 组数据 每组数据就是包含 5 个数字的字符串
输出
对每组数据, 输出将"12345"变换到给定字符串所需要的最少操作步数。 如果无法变换成功, 输出-1
样例输入
12435 99999 12374
样例输出
1 -1 3
提示
由于测试数据太多, 如果对每组数据都从头进行搜索, 就会超时。 建议先做预处理, 即以“12345” 作为初始状态做一遍彻底的广搜, 找出“12345” 经合法变换能够到达的所有字符串, 并记录到达这些字符串各需要多少步操作。 然后对读入的每组数据, 在上述预处理记录的结果中进行查询即可。
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
#define _init(x, v) memset(x, v, sizeof(x))
int rcd[100000];
bool vis[100000][5][5];
struct node {
int a[5], d, o2, o3;
};
queue<node> q;
void in() {
_init(rcd, -1);
node s = {1, 2, 3, 4, 5, 0, 3, 2};
q.push(s);
vis[12345][3][2] = 1;
rcd[12345] = 0;
}
int toNum(node &n) {
int t = 0;
for (int i = 0; i < 5; ++i) {
t *= 10;
t += n.a[i];
}
return t;
}
void bfs() {
while (!q.empty()) {
node s = q.front();
int t = toNum(s);
if (rcd[t] == -1 || rcd[t] > s.d)
rcd[t] = s.d;
// printf("n = %d, d = %d, o2 = %d, o3 = %d\n", toNum(s), s.d, s.o2, s.o3);
++s.d;
q.pop();
for (int i = 0; i < 5; ++i) {
// o1
if (i < 4 && s.a[i] != s.a[i + 1]) {
swap(s.a[i], s.a[i + 1]);
if (!vis[toNum(s)][s.o2][s.o3]) {
vis[toNum(s)][s.o2][s.o3] = 1;
q.push(s);
}
swap(s.a[i], s.a[i + 1]);
}
// o2
if (s.o2 > 0) {
--s.o2;
s.a[i] = (s.a[i] + 1) % 10;
if (!vis[toNum(s)][s.o2][s.o3]) {
vis[toNum(s)][s.o2][s.o3] = 1;
q.push(s);
}
s.a[i] = (s.a[i] + 10 - 1) % 10;
++s.o2;
}
// o3
if (s.o3 > 0) {
--s.o3;
int bak = s.a[i];
s.a[i] = (2 * s.a[i]) % 10;
if (!vis[toNum(s)][s.o2][s.o3]) {
vis[toNum(s)][s.o2][s.o3] = 1;
q.push(s);
}
s.a[i] = bak;
++s.o3;
}
}
}
}
int main() {
in();
bfs();
int n;
while (cin >> n) {
cout << rcd[n] << endl;
}
system("pause");
return 0;
}寻找边缘
给定一张 R*C 的地图, 由 "X" 和 "O" 组成。
现在需要重新处理这张地图, 找到地图边缘的那些 "O"。 你需要将这些地图边缘上的 "O" 保留下来, 然后将其他的 "O" 全部替换为 "X"。
地图边缘的 "O" 指的是那些处于第一行/列或最后一行/列上的 "O",以及从这些 "O" 的相邻位置(上下左右) 延伸出去的 "O"。
时间限制: 1000
内存限制: 65536
输入
第一行是一个正整数 T, 表示一共有 T 组数据。 对于每组数据, 其第一行是两个正整数 R 和 C, 表示地图的大小, 用一个空格分开。 接下来的 R 行, 每行包含了 C 个字符, 分别是 "X" 或 "O"。 其中,0 < T <= 10, 0 < R, C <= 500。
输出
对于每组数据, 输出 R 行, 每行包含了 C 个字符, 分别是 "X" 或"O"。 每组数据之间需要额外输出一个空行。
样例输入
2 2 3 OXX XXO 5 5 XXXOX XXXOX XOOXX XXOXX XOXXX
样例输出
OXX XXO XXXOX XXXOX XXXXX XXXXX XOXXX
#include <cstring>
#include <iostream>
using namespace std;
int r, c;
char a[505][505];
int dirx[4] = {0, 0, 1, -1};
int diry[4] = {1, -1, 0, 0};
void dfs(int x, int y) {
for (int i = 0; i < 4; i++) {
int nx = x + dirx[i];
int ny = y + diry[i];
if (a[nx][ny] == 'O') {
a[nx][ny] = '?';
dfs(nx, ny);
}
}
}
int main() {
int t;
cin >> t;
while (t--) {
memset(a, 0, sizeof(a));
cin >> r >> c;
int i, j;
for (i = 1; i <= r; i++)
for (j = 1; j <= c; j++)
cin >> a[i][j];
for (i = 1; i <= r; i++) {
if (a[i][1] == 'O') {
a[i][1] = '?';
dfs(i, 1);
}
if (a[i][c] == 'O') {
a[i][c] = '?';
dfs(i, c);
}
}
for (i = 1; i <= c; i++) {
if (a[1][i] == 'O') {
a[1][i] = '?';
dfs(1, i);
}
if (a[r][i] == 'O') {
a[r][i] = '?';
dfs(r, i);
}
}
for (i = 1; i <= r; i++) {
for (j = 1; j <= c; j++) {
if (a[i][j] == '?')
cout << 'O';
else
cout << 'X';
}
cout << endl;
}
cout << endl;
}
return 0;
}42 点
42 是:
· 组合数学上的第 5 个卡特兰数
· 字符'*'的 ASCII 码
· 钼的原子序数
· 6 与 9 的乘积结果的 13 进制表示
· 生命、 宇宙以及任何事情的终极答案
· 以及……表达式(1+5)/2*(6-4)*7 的值
因此, 小机器人 Marvin 发明了这个叫 42 点的小游戏。在这个游戏中,玩家会获得 n 个数。 玩家需要使用'+'、 '-'、 '*'、 '/'、 '('、 ')'以及这 n 个数构成一个合法的中缀表达式, 并使得该表达式的值为 42。 n 个数之间的顺序可以改变。 表达式运算过程中只能出现整数。
由于过于抑郁, Marvin 无力完成这个游戏, 于是来找你帮忙。 你的任务是对于给定的 n 个数, 判断他们是否能根据上述游戏规则算出 42。
时间限制: 1000
内存限制: 65536
输入
第一行为一个数 n, 1<=n<=6。 第二行为 n 个数, 每个数均为[1,13]范围内的整数。
输出
输出一行, 若可以算出 42 则输出“YES”, 否则输出“NO”(注意大小写)。
样例输入
6 1 5 2 6 4 7
样例输出
YES
#include <iostream>
using namespace std;
bool dfs(int a[], int n) {
if (n == 1) {
return a[0] == 42;
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int b[10];
int m = 0;
for (int k = 0; k < n; ++k) {
if (k == i || k == j)
continue;
b[m++] = a[k];
}
++m;
b[m - 1] = a[i] + a[j];
if (dfs(b, m))
return 1;
b[m - 1] = a[i] - a[j];
if (dfs(b, m))
return 1;
b[m - 1] = a[j] - a[i];
if (dfs(b, m))
return 1;
b[m - 1] = a[i] * a[j];
if (dfs(b, m))
return 1;
if (a[j] != 0)
b[m - 1] = a[i] / a[j];
if (dfs(b, m))
return 1;
if (a[i] != 0)
b[m - 1] = a[j] / a[i];
if (dfs(b, m))
return 1;
}
}
return 0;
}
int main() {
int n;
int a[10];
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
if (dfs(a, n))
cout << "YES" << endl;
else
cout << "NO" << endl;
system("pause");
return 0;
}Project Summer 游戏
小 I 和小 B 最近沉迷一款叫做《Project Summer》 的游戏, 小 I 扮演这个游戏中需要逃生的无辜者(Innocent), 小 B 扮演这个游戏中抓住无辜者, 阻止其逃生的背叛者(Betrayer)。
这个游戏的地图是一个 N 行 M 列 的矩形, 每个格点表示一个位置。
'#' 表示地图中的障碍物, '.' 表示地图中的空地, 此外, 地图中还有只有背叛者才能使用的传送门, 用小写字母 'a' - 'z' 标记, 它们在地图上成对出现。
角色可以花费 1 单位的时间从一个格子走到上下左右相邻的 4个空地中的另一个格子(不可以走出地图边界或者走到障碍物上)。此外, 当小 B 扮演的背叛者走到一个传送门上时, 他可以花费 1 单位的时间从当前格子传送到与当前格子相同字母的另一个传送门处(他也可以选择不传送, 此时没有花费任何时间, 待在原地不动)。
传送是双向的。 比如, 现在小 B 走到了标记为 'a' 的格子上, 那么他可以选择花费一单位的时间传送到另一个标记为 'a' 的格子上, 也可以选择不传送, 那么他就待在原地不动。
现在, 小 I 被小 B 的陷阱困住了, 无法移动。 给出地图上小 B 和小 I 所在的格子(他们都站在空地上), 求小 B 最少需要花费多少时间才能走到小 I 所在的格子抓住他。 如果小 I 无法抓住小 B, 输出 -1
时间限制: 1000
内存限制: 65536
输入
第一行一个数字 T, 表示数据组数。 接下来描述 T 组数据, 每组数据最开始是两个正整数 N, M 表示地图是 N 行 M 列的矩形。 接下来 N 行, 每行 M 个字符, 表示地图。 在地图上, 用 '.' 表示空地,'#' 表示障碍物, 'a'-'z' 表示传送门, 'B' 表示小 B 的初始位置, 'I' 表示小 I 的初始位置。 对于每组数据, 保证在地图上标记相同的传送
门恰好出现两次。 T,N,M <= 100
输出
T 行, 第 i 行输出 'Case #i: t', 表示第 i 组数据的答案是 t. 小 B 最少需要 t 单位时间才能走到小 I 所在的格子。 如果小 I 无法抓住小B, 输出 -1
样例输入
3 5 5 Bx#.. #a.#. ..... ##..# .x.aI 5 5 BIa.a x#.x. .#.## ..... ##### 2 2 B# #I
样例输出
Case #1: 4 Case #2: 1 Case #3: -1
提示
对于第一组数据, 假设行从上到下标号 1 到 5, 列从左到右标号 1到 5, 小 B 初始在 (1, 1)。 小 B 的最优路线是: (1, 1) -> (1, 2) -> (2,2) -> (5, 4) -> (5, 5)。 也就是走到标记为 x 的传送门时忽略传送门, 走到标记为 a 的传送门时使用传送门。 对于第二组数据, 小 B 直接花费 1 单位时间向右走一格就可以抓住小 I, 故输出 1。 对于第三组数据, 小 B 无法走到小 I 所在的位置上, 故输出 -1。
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
int T, N, M;
int ii, jj;
int directs[4][2]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
char a[100][100];
int visited[100][100];
struct Data {
int i, j, t;
Data(int _i, int _j, int _t) : i(_i), j(_j), t(_t) {}
};
Data gogogo(const Data &d) {
char c = a[d.i][d.j];
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
if (a[i][j] == c && !(d.i == i && d.j == j)) {
return Data(i, j, d.t + 1);
}
}
}
return d;
}
int main() {
cin >> T;
for (int t = 1; t <= T; ++t) {
cin >> N >> M;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
cin >> a[i][j];
if (a[i][j] == 'B') {
ii = i;
jj = j;
}
}
}
queue<Data> q;
memset(visited, -1, sizeof(visited));
q.push(Data(ii, jj, 0));
visited[ii][jj] = 0;
bool flag = 0;
while (!q.empty()) {
Data cur = q.front();
if (a[cur.i][cur.j] == 'I') {
flag = 1;
break;
}
q.pop();
int ni, nj, nt;
for (int d = 0; d < 4; ++d) {
ni = cur.i + directs[d][0];
nj = cur.j + directs[d][1];
nt = cur.t + 1;
if (ni >= 0 && ni < N && nj < M && nj >= 0 && a[ni][nj] != '#' &&
(visited[ni][nj] == -1 || nt < visited[ni][nj])) {
visited[ni][nj] = nt;
q.push(Data(ni, nj, nt));
}
}
// 气!isalpha函数在OJ上会被判错
if (a[cur.i][cur.j] <= 'z' && a[cur.i][cur.j] >= 'a') {
Data nd = gogogo(cur);
if (visited[nd.i][nd.j] == -1 || nd.t < visited[nd.i][nd.j]) {
visited[nd.i][nd.j] = nd.t;
q.push(nd);
}
}
}
cout << "Case #" << t << ": " << ((flag) ? q.front().t : -1) << endl;
}
}拦截导弹
某国为了防御敌国的导弹袭击, 发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷: 虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。 某天, 雷达捕捉到敌国的导弹来袭。 由于该系统还在试用阶段, 所以只有一套系统, 因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度(雷达给出的高度数据是不大于 30000 的正整数) , 计算这套系统最多能拦截多少导弹。
时间限制: 1000
内存限制: 65536
输入
第一行是一个整数 N(不超过 15) , 表示导弹数。 第二行包含 N 个整数, 为导弹依次飞来的高度(雷达给出的高度数据是不大于 30000的正整数) 。
输出
一个整数, 表示最多能拦截的导弹数。
样例输入
8 389 207 155 300 299 170 158 65
样例输出
6
#include <algorithm>
#include <bits/stdc++.h>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n[2002], t = 1, f;
int b1[2002], b2[2002], r1, r2;
int main() {
int c;
cin >> c;
for (int i = 1; i <= c; i++) {
cin >> n[i];
}
b1[1] = n[1];
r1 = 1;
for (int i = 2; i <= c; i++) {
if (b1[r1] >= n[i]) {
b1[++r1] = n[i];
} else {
*upper_bound(b1 + 1, b1 + r1 + 1, n[i], greater<int>()) = n[i];
}
}
cout << r1 << endl;
}神奇的数列
一个正整数数列, 可以将它切割成若干个数据段, 每个数据段由值相同的相邻元素构成。 该数列的神奇之处在于, 每次切除一个数据段后,该数据段前后的元素自动连接在一起成为邻居。 例如从数列“2 8 9 77 6 9 4” 中切除数据段“7 7 ” 后, 余下的元素会构成数列“2 8 9 6 94”
请问若要将该数列切割成若干个数据段, 则至少会切出来几个数据段?
样例: 按下列顺序切割数列“2 8 9 7 7 6 9 4” , 只要切割成 6 段
切割出“7 7” , 余下 “2 8 9 6 9 4”
切割出 “6” , 余下 “2 8 9 9 4”
切割出 “9 9” , 余下 “2 8 4”
切割出 “2” , 余下 “8 4”
切割出 “8” , 余下 “4”
时间限制: 1000
内存限制: 65536
输入
第一行是一个整数, 示共有多少组测试数据。 每组测试数据的输入包括两行: 第一行是整数 N, N<=200,表示数列的长度, 第二行是 N 个正整数。
输出
每个测试案例的输出占一行, 是一个整数。 格式是: Case n: x n 是测试数据组编号, x 是答案
样例输入
2 8 2 8 9 7 7 6 9 4 16 2 8 9 7 7 6 9 4 4 2 8 4 2 7 6 9
样例输出
Case 1: 6 Case 2: 11
#include <cstring>
#include <iostream>
using namespace std;
int score[202][202];
int N;
int num[202];
int main() {
int T;
// cin >> T;
// freopen("C:\\Users\\csctest\\Desktop\\slin.txt", "r", stdin);
// freopen("C:\\Users\\csctest\\Desktop\\sloutx.txt", "w", stdout);
scanf("%d", &T);
int T0 = T;
while (T--) {
/*for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
score[i][j] = 256;
}
}*/
memset(score, 1, sizeof(score));
memset(num, 0, sizeof(num));
int N;
scanf("%d", &N); // cin >> N;
for (int i = 0; i < N; ++i) {
scanf("%d", &num[i]); // cin >> num[i];
score[i][i] = 1;
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < i; ++j) {
score[i][j] = 0;
}
}
for (int i = 0; i < N - 1; ++i) {
if (num[i] == num[i + 1])
score[i][i + 1] = 1;
else
score[i][i + 1] = 2;
}
for (int i = N - 2; i >= 0; --i) {
for (int j = i + 1; j < N; ++j) {
for (int k = i; k < j; ++k) {
if (num[k] == num[j]) {
score[i][j] = min(score[i][j], score[i][k] + score[k + 1][j - 1]);
}
score[i][j] = min(score[i][j], score[i][k] + score[k + 1][j]);
}
}
}
/*
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (score[i][j] < 10000 ) printf("%d ", score[i][j]);//cout
<< score[i][j] << " "; else printf("%d ", -1); //cout << -1 << " ";
}
printf("\n");//cout << endl;
}*/
printf("Case %d: %d\n", T0 - T, score[0][N - 1]);
// cout << "Case " << T0-T << ": " <<score[0][N-1] << endl;
}
return 0;
}硬币
宇航员 Bob 有一天来到火星上, 他有收集硬币的习惯。 于是他将火星上所有面值的硬币都收集起来了, 一共有 n 种, 每种只有一个: 面值分别为 a1,a2… an。 Bob 在机场看到了一个特别喜欢的礼物, 想买来送给朋友 Alice, 这个礼物的价格是 X 元。 Bob 很想知道为了买这个礼物他的哪些硬币是必须被使用的, 即 Bob 必须放弃收集好的哪些硬币种类。 飞机场不提供找零, 只接受恰好 X 元。
时间限制: 1000
内存限制: 262144
输入
第一行包含两个正整数 n 和 x。 (1 <= n <= 200, 1 <= x <= 10000)
第二行从小到大为 n 个正整数 a1, a2, a3 … an (1 <= ai <= 10000)
输出
第一行是一个整数, 即有多少种硬币是必须被使用的。 第二行是这些必须使用的硬币的面值(从小到大排列) 。
样例输入
5 18 1 2 3 5 10
样例输出
2 5 10
提示
输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付 X元。 如果不存在必须被使用的硬币, 则第一行输出 0, 第二行输出空行。
#include <iostream>
using namespace std;
int val[210] = {0};
int ways[10000] = {0};
int ans[210] = {0};
int cal(int x, int y) {
if (x < 0)
return 0;
return ways[x] - cal(x - y, y);
}
int main() {
int N, Max;
cin >> N >> Max;
for (int i = 1; i <= N; ++i)
cin >> val[i];
ways[0] = 1;
for (int i = 1; i <= N; ++i)
for (int j = Max; j >= val[i]; --j)
ways[j] += ways[j - val[i]];
int cnt = 0;
for (int i = 1; i <= N; ++i)
if (cal(Max, val[i]) == 0)
ans[cnt++] = val[i];
cout << cnt << endl;
if (cnt == 0)
cout << ' ' << endl;
else {
cout << ans[0];
for (int i = 1; i < cnt; ++i)
cout << ' ' << ans[i];
}
return 0;
}公共子序列
我们称序列 Z = < z1, z2, ..., zk >是序列 X = < x1, x2, ..., xm >的子序列当且仅当存在 严格上升 的序列< i1, i2, ..., ik >, 使得对 j = 1, 2, ... ,k, 有xij = zj。 比如 Z = < a, b, f, c > 是 X = < a, b, c, f, b, c >的子序列。 现在给出两个序列 X 和 Y, 你的任务是找到 X 和 Y 的最大公共子序列, 也就是说要找到一个最长的序列 Z, 使得 Z 既是 X 的子序列也是 Y 的子序列。
时间限制: 3000
内存限制: 65536
输入
输入包括多组测试数据。 每组数据包括一行, 给出两个长度不超过200 的字符串, 表示两个序列。 两个字符串之间由若干个空格隔开。
输出
对每组输入数据, 输出一行, 给出两个序列的最大公共子序列的长度。
样例输入
abcfbc abfcab programming contest abcd mnp
样例输出
4 2 0
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
if (a > b)
return a;
else
return b;
}
int main() {
char s1[201], s2[201];
while (scanf("%s %s", s1, s2) != EOF) {
int dp[201][201];
memset(dp, 0, sizeof(dp));
int m = strlen(s1), n = strlen(s2);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
printf("%d\n", dp[m][n]);
}
return 0;
}