Scratch编程一级 题库
序列排序
对于给定的正整数序列,按照每个数的各位数和从大到小排序,各位数和相同的按照本身大小排序,大的在前,小的在后。
时间限制:1000
内存限制:65536
输入
第一行1个整数n,表示序列的大小。( 0 < n ≤ 1000) 第二行n个正整数,表示序列的每个数,每个数不大于100000000。
输出
输出按照题目要求排序后的序列
样例输入
6 17 26 9 13 88 10
样例输出
88 9 26 17 13 10
#include <iostream>
using namespace std;
int sum(int n) {
int s = 0;
while (n > 0) {
s += n % 10;
n /= 10;
}
return s;
}
int main() {
int i, j, t, n, a[1000], b[1000];
cin >> n;
for (i = 0; i < n; i++) {
cin >> a[i];
b[i] = sum(a[i]);
}
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if ((b[j] < b[j + 1]) || ((b[j] == b[j + 1]) && (a[j] < a[j + 1]))) {
t = b[j];
b[j] = b[j + 1];
b[j + 1] = t;
t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
}
for (i = 0; i < n; i++)
cout << a[i] << " ";
return 0;
}单词的长度
输入一行单词序列,相邻单词之间由1个或多个空格间隔,请对应地计算各个单词的长度。
注意,如果有标点符号(如连字符,逗号),标点符号算作与之相连的词的一部分。没有被空格间开的符号串,都算作单词。
时间限制:1000
内存限制:65536
输入
一行单词序列,最少1个单词,最多300个单词,单词之间用至少1个空格间隔。单词序列总长度不超过1000。
输出
依次输出对应单词的长度,之间以逗号间隔。
样例输入
She was born in 1990-01-02 and from Beijing city.
样例输出
3,3,4,2,10,3,4,7,5
#include <bits/stdc++.h>
using namespace std;
string s, ch;
int main() {
cin >> s;
cout << s.size();
while (cin >> ch) {
cout << "," << ch.size();
}
return 0;
}扫雷游戏地雷数计算
扫雷游戏是一款十分经典的单机小游戏。它的精髓在于,通过已翻开格子所提示的周围格地雷数,来判断未翻开格子里是否是地雷。
现在给出n行m列的雷区中的地雷分布,要求计算出每个非地雷格的周围格地雷数。
注:每个格子周围格有八个:上、下、左、右、左上、右上、左下、右下。
时间限制:1000
内存限制:65536
输入
第一行包含两个整数n和m,分别表示雷区的行数和列数。1 <= n <= 100, 1 <= m <= 100。 接下来n行,每行m个字符,‘*’表示相应格子中是地雷,‘?’表示相应格子中无地雷。字符之间无任何分隔符。
输出
n行,每行m个字符,描述整个雷区。若相应格中是地雷,则用‘*’表示,否则用相应的周围格地雷数表示。字符之间无任何分隔符。
样例输入
3 3 *?? ??? ?*?
样例输出
*10 221 1*1
#include <bits/stdc++.h>
using namespace std;
char a[102][102];
int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
int main() {
int n, m, sum;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == '*') {
cout << a[i][j];
continue;
} else {
sum = 0;
for (int k = 0; k < 8; k++) {
if (a[i + dx[k]][j + dy[k]] == '*')
sum++;
}
cout << sum;
}
}
cout << endl;
}
return 0;
}古代密码
古罗马帝国有一个拥有各种部门的强大政府组织。其中一个部门就是保密服务部门。为了保险起见,在省与省之间传递的重要文件中的大写字母是加密的。当时最流行的加密方法是替换和重新排列。
替换方法是将所有出现的字符替换成其它的字符。有些字符会替换成它自己。例如:替换规则可以是将'A' 到 'Y'替换成它的下一个字符,将'Z'替换成 'A',如果原词是 "VICTORIOUS" 则它变成 "WJDUPSJPVT"。
排列方法改变原来单词中字母的顺序。例如:将顺序例如将顺序 < 2 1 5 4 3 7 6 10 9 8 > 应用到 "VICTORIOUS" 上,则得到"IVOTCIRSUO"。
人们很快意识到单独应用替换方法或排列方法加密,都是很不保险的。但是如果结合这两种方法,在当时就可以得到非常可靠的加密方法。所以,很多重要信息先使用替换方法加密,再将加密的结果用排列的方法加密。用两种方法结合就可以将"VICTORIOUS" 加密成"JWPUDJSTVP"。
考古学家最近在一个石台上发现了一些信息。初看起来它们毫无意义,所以有人设想它们可能是用替换和排列的方法被加密了。人们试着解读了石台上的密码,现在他们想检查解读的是否正确。他们需要一个计算机程序来验证,你的任务就是写这个验证程序。
时间限制:1000
内存限制:65536
输入
输入有两行。第一行是石台上的文字。文字中没有空格,并且只有大写英文字母。第二行是被解读出来的加密前的文字。第二行也是由大写英文字母构成的。 两行字符数目的长度都不超过100。
输出
如果第二行经过某种加密方法后可以产生第一行的信息,输出 "YES",否则输出"NO"。
样例输入
JWPUDJSTVP VICTORIOUS
样例输出
YES
#include <stdio.h>
#include <string.h>
// 记录字母出现次数
int ans[26];
int test[26];
// 记录字符串
char strA[105];
char strT[105];
int main() {
while (1) {
// 注意初始化
memset(ans, 0, sizeof(ans));
memset(test, 0, sizeof(test));
if (scanf("%s", strA) == EOF) {
return 0;
}
int lenA = strlen(strA);
// 求出现次数
for (int k = 0; k < lenA; k++) {
ans[strA[k] - 'A']++;
}
scanf("%s", strT);
int lenT = strlen(strT);
for (int m = 0; m < lenT; m++) {
test[strT[m] - 'A']++;
}
int flag = 0;
int i;
for (i = 0; i < 26; i++) {
flag = 0;
// 等于0时代表没有出现,跳过
if (test[i] == 0) {
continue;
}
for (int j = 0; j < 26; j++) {
if (test[i] == ans[j]) {
// 匹配了就把ans置零
ans[j] = 0;
flag = 1;
break;
}
}
if (flag == 0) {
printf("NO\n");
break;
} else {
continue;
}
}
// 等于26代表所有字母都能有匹配
if (i == 26) {
printf("YES\n");
}
}
return 0;
}双精度浮点数的输入输出
输入一个双精度浮点数,保留8位小数,输出这个浮点数。
时间限制:1000
内存限制:65536
输入
只有一行,一个双精度浮点数。
输出
一行,保留8位小数的浮点数。
样例输入
3.1415926535798932
样例输出
3.14159265
#include <cstdio>
using namespace std;
int main() {
double a;
scanf("%lf", &a);
printf("%.8lf", a);
return 0;
}足球联赛积分
在足球联赛里,一个球队赢下一场比赛得到3个积分,打平一场比赛得到1个积分,输掉比赛得到0分。
现已知一个球队在整个联赛里的比赛情况,求该球队最终的积分。
时间限制:1000
内存限制:65536
输入
三个整数x,y,z,以空格分开,分别表示这个球队赢下的比赛场数,打平的比赛场数,输掉的比赛场数。(0 ≤ x,y,z ≤ 40)
输出
一个整数,表示该球队最终的积分。
样例输入
19 6 4
样例输出
63
提示
63=19*3+6*1+4*0
#include <iostream>
using namespace std;
int main() {
int x, y, z, a = 0;
cin >> x >> y >> z;
a = x * 3 + y;
cout << a;
return 0;
}小写字母的判断
输入一个字符,判断是否是英文小写字母,即是否是a-z中的一个。
时间限制:1000
内存限制:65536
输入
一个字符。
输出
如果是英文小写字母,则输出yes,否者输出no。
样例输入
k
样例输出
yes
#include <iostream>
using namespace std;
int main() {
char name;
cin >> name;
if (name >= 'a' && name <= 'z')
cout << "yes";
else
cout << "no";
return 0;
}足球联赛积分2
一场足球比赛中,两支参赛队A,B,如果A队的进球数大于B队,则A赢,A积3分B积0分,如果A队的进球数等于B队,则两队打平,各积1分,如果A队的进球数小于B队,则A输,A积0分B积3分。
现有一个球队一个赛季的比赛情况,请计算该球队的积分。
时间限制:1000
内存限制:65536
输入
第一行一个整数n(0 < n ≤ 40) 接下来n行,每行两个非负整数,表示一场该球队的进球数以及对手球队的进球数。
输出
一个整数,表示该球队的赛季积分。
样例输入
5 3 1 0 0 1 2 3 2 3 3
样例输出
8
提示
该球队5场比赛的结果分别为赢,平,输,赢,平,总计2赢2平1输,积分为8分。
#include <iostream>
using namespace std;
int main() {
int n, a, b, c = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a >> b;
if (a > b)
c = c + 3;
else if (a = b)
c = c + 1;
}
cout << c;
return 0;
}与7无关的数
一个正整数,如果它能被7整除,或者它的十进制表示法中某一位上的数字为7,则称其为与7相关的数.现求所有小于等于n(n < 100)的与7无关的正整数的平方和.
时间限制:1000
内存限制:65536
输入
输入为一行,正整数n(n < 100)
输出
输出一行,包含一个整数,即小于等于n的所有与7无关的正整数的平方和。
样例输入
21
样例输出
2336
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int m = 0;
for (int i = 1; i <= n; i++) {
if (i % 7 != 0 && i / 10 % 10 != 7 && i % 10 != 7) {
m = m + i * i;
}
}
cout << m;
return 0;
}道路
N个以 1 … N 标号的城市通过单向的道路相连:。每条道路包含两个参数:道路的长度和需要为该路付的通行费(以金币的数目来表示)
Bob and Alice 过去住在城市 1.在注意到Alice在他们过去喜欢玩的纸牌游戏中作弊后,Bob和她分手了,并且决定搬到城市N。他希望能够尽可能快的到那,但是他囊中羞涩。我们希望能够帮助Bob找到从1到N最短的路径,前提是他能够付的起通行费。
时间限制:1000
内存限制:65536
输入
第一行包含一个整数K, 0 <= K <= 10000, 代表Bob能够在他路上花费的最大的金币数。第二行包含整数N, 2 <= N <= 100, 指城市的数目。第三行包含整数R, 1 <= R <= 10000, 指路的数目. 接下来的R行,每行具体指定几个整数S, D, L 和 T来说明关于道路的一些情况,这些整数之间通过空格间隔: S is 道路起始城市, 1 <= S <= N D is 道路终点城市, 1 <= D <= N L is 道路长度, 1 <= L <= 100 T is 通行费 (以金币数量形式度量), 0 <= T <=100 注意不同的道路可能有相同的起点和终点。
输出
输入结果应该只包括一行,即从城市1到城市N所需要的最小的路径长度(花费不能超过K个金币)。如果这样的路径不存在,结果应该输出-1。
样例输入
5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2
样例输出
11
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
struct Road {
int d, L, t;
};
int N, K, R;
vector<vector<Road>> G(110); // 用二维数组表示临界表,G[s]表示和s邻接的路
int minLen; // 全局变量,记录最短的路径长度
int totalCost; // 当前状态的花费
int totalLen; // 当前状态的长度
int visited[110];
int minL[110][10010]; // minL[i][j]的意义是当到达i点是花费为j时的最短路径
void Dfs(int s) {
if (s == N) {
minLen = min(minLen, totalLen);
return;
}
int len = G[s].size();
for (int i = 0; i < len; i++) // 枚举和s相邻接额情况
{
Road r = G[s][i];
if (!visited[r.d]) // 如果没有被走过
{
/*下面三个if语句是三条剪枝条件*/
if (totalCost + r.t > K) // 如果当前花销大于K了
continue;
if (totalLen + r.L >=
minLen) // 如果当前的路径已经超过了已存在的最短路径,那就没必要往后dfs了
continue;
// 如果存在两种方式都到达同一点并且花销相同,但是如果当前的长度大于另一种方式的长度,则continue
if (totalLen + r.L > minL[r.d][totalCost + r.t])
continue;
minL[r.d][totalCost + r.t] = totalLen + r.L;
visited[r.d] = 1;
totalCost += r.t;
totalLen += r.L;
Dfs(r.d);
visited[r.d] =
0; // 因为可能存在多种方式的dfs的路径,所以每次dfs之后都要还原到之前的状态
totalCost -= r.t;
totalLen -= r.L;
}
}
}
int main() {
cin >> K >> N >> R;
for (int i = 0; i < R; i++) {
int s;
Road r;
cin >> s;
cin >> r.d >> r.L >> r.t;
G[s].push_back(r);
}
totalCost = 0;
totalLen = 0;
minLen = 1 << 30; // 无穷大
memset(visited, 0, sizeof(visited));
for (int i = 1; i <= N; i++)
for (int j = 0; j < 10010; j++)
minL[i][j] = 1 << 30;
visited[1] = 1;
Dfs(1);
if (minLen < (1 << 30))
cout << minLen << endl;
else
cout << -1 << endl;
return 0;
}控制公司
有些公司是其他公司的部分拥有者,因为他们获得了其他公司发行的股票的一部分。例如,福特公司拥有马自达公司12%的股票。据说,如果至少满足了以下条件之一,公司A就可以控制公司B了:
l 公司A = 公司B。
l 公司A拥有大于50%的公司B的股票。
l 公司A控制K(K >= 1)个公司,记为C1, …, CK,每个公司Ci拥有xi%的公司B的股票,并且x1+ … + xK > 50%。(ps:A可以控制自己,即Ci可以为A)
你将被给予一系列的三对数(i,j,p),表明公司i拥有公司j的p%的股票。计算所有的数对(h,s),表明公司h控制公司s。
写一个程序读入三对数(i,j,p),并且找出所有的数对(h,s),使得公司h控制公司s。
时间限制:1000
内存限制:65536
输入
第一行: N,表明接下来三对数的数量。 第二行到第N+1行:每行三个整数作为一个三对数(i,j,p),如上文所述。 I,J≤100,N,P≤100
输出
输出零个或更多个的控制其他公司的公司。每行包括两个整数表明序号为第一个整数的公司控制了序号为第二个整数的公司。将输出的每行以第一个数字升序排列(并且第二个数字也升序排列来避免并列)。请不要输出控制自己的公司。
样例输入
3 1 2 80 2 3 80 3 1 20
样例输出
1 2 1 3 2 3
#include <bits/stdc++.h>
using namespace std;
unsigned long long int n, gf[1000][1000], mp[1000][1000];
void jf(int x, int y) // x公司加上i公司股票
{
for (int i = 1; i <= 100; i++) {
if (gf[x][i] + gf[y][i] > 100)
gf[x][i] = 100; // 判断
else
gf[x][i] += gf[y][i];
}
return;
}
void find(int x) // 递归
{
for (int i = 1; i <= 100; i++) {
if (gf[x][i] >= 50 && mp[x][i] == 0 && x != i) {
mp[x][i] = 1; // 标记 x公司可以控制i公司
jf(x, i);
find(x); // 加上以后再找一遍
return;
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int a, b, c;
cin >> a >> b >> c;
gf[a][b] = c;
}
int t = 1;
while (t <= 100) // 枚举每一个公司
{
find(t);
t++;
}
for (int i = 1; i <= 100; i++) {
for (int j = 1; j <= 100; j++) {
if (mp[i][j] == 1)
cout << i << " " << j << endl;
}
}
}发现它,抓住它
一个城市中有两个犯罪团伙A和B,你需要帮助警察判断任意两起案件是否是同一个犯罪团伙所为,警察所获得的信息是有限的。假设现在有N起案件(N<=100000),编号为1到N,每起案件由团伙A或团伙B所为。你将按时间顺序获得M条信息(M<=100000),这些信息分为两类:
D [a] [b]
其中[a]和[b]表示两起案件的编号,这条信息表明它们属于不同的团伙所为
A [a] [b]
其中[a]和[b]表示两起案件的编号,这条信息需要你回答[a]和[b]是否是同一个团伙所为
注意你获得信息的时间是有先后顺序的,在回答的时候只能根据已经接收到的信息做出判断。
时间限制:1000
内存限制:65536
输入
第一行是测试数据的数量T(1<=T<=20)。 每组测试数据的第一行包括两个数N和M,分别表示案件的数量和信息的数量,其后M行表示按时间顺序收到的M条信息。
输出
对于每条需要回答的信息,你需要输出一行答案。如果是同一个团伙所为,回答"In the same gang.“,如果不是,回答"In different gangs.”,如果不确定,回答”Not sure yet."。
样例输入
1 5 5 A 1 2 D 1 2 A 1 2 D 2 4 A 1 4
样例输出
Not sure yet. In different gangs. In the same gang.
#include <bits/stdc++.h>
using namespace std;
template <class T> struct DisjointSet {
int *parent;
T *data;
map<T, int> m;
int capacity;
int size;
DisjointSet(int max = 1000) {
capacity = max;
size = 0;
parent = new int[max + 1];
data = new T[max + 1];
}
~DisjointSet() {
delete[] parent;
delete[] data;
}
bool insert(T x) {
if (size == capacity)
return false;
size++;
data[size] = x;
parent[size] = -1;
m[x] = size;
return true;
}
int getIndex(T x) {
for (int i = 1; i <= size; i++)
if (data[i] == x)
return i;
return -1;
}
int find(T x) {
typename map<T, int>::iterator it;
it = m.find(x);
if (it == m.end())
return -1;
int i, rt;
i = rt = it->second;
while (parent[rt] > 0)
rt = parent[rt];
return rt;
}
void unionSet(T x, T y) {
int rx, ry;
rx = find(x);
ry = find(y);
if (rx == -1 || ry == -1)
return;
if (rx == ry)
return;
if (parent[rx] < parent[ry]) {
parent[rx] += parent[ry];
parent[ry] = rx;
} else {
parent[ry] += parent[rx];
parent[rx] = ry;
}
find(x);
find(y);
}
};
int main() {
int t;
cin >> t;
while (t--) {
DisjointSet<int> s;
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
s.insert(i);
for (int i = 1; i <= m; i++) {
int a, b;
char c;
cin >> c >> a >> b;
if (c == 'D')
s.unionSet(a, b);
else {
if (s.find(a) != s.find(b))
cout << "Not sure yet.";
else if (s.parent[a] == s.parent[b])
cout << "In the same gang.";
else
cout << "In different gangs.";
cout << endl;
}
}
}
return 0;
}青蛙的约会
两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
时间限制:1000
内存限制:65536
输入
输入只包括一行5个整数x,y,m,n,L,其中x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。
输出
输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行"Impossible"
样例输入
1 2 3 4 5
样例输出
4
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
ll gcd = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return gcd;
}
ll inv(ll a, ll b, ll c) {
ll x, y;
ll gcd = exgcd(a, b, x, y);
if (c % gcd != 0)
return -1;
x *= c / gcd; // 得到当前情况下的一个x
b /= gcd; // 根据通解x = x0 + (b * t) / gcd 所以b = b / gcd
b = abs(
b); // 为了得到正数解,所以要abs,而且要在上一步/gcd之后,因为gcd可能是负的
ll ans = x % b;
if (ans < 0)
ans += b;
return ans;
}
int main() {
ll x, y, n, m, L;
cin >> x >> y >> m >> n >> L;
ll res = inv(m - n, L, y - x);
if (res == -1)
cout << "Impossible";
else
cout << res;
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;
}迷宫
一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由n * n的格点组成,每个格点只有2种状态,.和#,前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上,Extense想要从点A走到点B,问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#),则看成无法办到。
时间限制:3000
内存限制:65536
输入
第1行是测试数据的组数k,后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 <= n <= 100),表示迷宫的规模是n * n的。接下来是一个n * n的矩阵,矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb,描述A处在第ha行, 第la列,B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。
输出
k行,每行输出对应一个输入。能办到则输出“YES”,否则输出“NO”。
样例输入
2 3 .## ..# #.. 0 0 2 2 5 ..... ###.# ..#.. ###.. ...#. 0 0 4 0
样例输出
YES NO
#include <queue>
#include <stdio.h>
#include <string.h>
int m;
char c[100][100];
int xa, ya, xb, yb;
bool vis[100][100];
int dir[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
struct node {
int x;
int y;
int step;
} q[10000];
void bfs(int xa, int ya, int xb, int yb) {
int head = 1, tail = 1;
memset(vis, 0, sizeof(vis));
q[tail].x = xa;
q[tail].y = ya;
q[tail].step = 0;
tail++;
vis[xa][ya] = 1;
int flag = 1;
while (head < tail) {
int x = q[head].x;
int y = q[head].y;
int step = q[head].step;
if (x == xb && y == yb) {
flag = 0;
printf("YES\n");
break;
}
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < m && c[nx][ny] == '.' &&
vis[nx][ny] == 0) {
vis[nx][ny] = 1;
q[tail].x = nx;
q[tail].y = ny;
q[tail].step = step + 1;
tail++;
}
}
head++;
}
if (flag == 1) {
printf("NO\n");
}
}
int main() {
int n;
scanf("%d", &n);
while (n--) {
scanf("%d", &m);
for (int i = 0; i < m; i++) {
scanf("%s", c[i]);
}
scanf("%d%d%d%d", &xa, &ya, &xb, &yb);
bfs(xa, ya, xb, yb);
}
return 0;
}Sequence
给定m个数字序列,每个序列包含n个非负整数。我们从每一个序列中选取一个数字组成一个新的序列,显然一共可以构造出nm个新序列。接下来我们对每一个新的序列中的数字进行求和,一共会得到nm个和,请找出最小的n个和
时间限制:3000
内存限制:65536
输入
输入的第一行是一个整数T,表示测试用例的数量,接下来是T个测试用例的输入 每个测试用例输入的第一行是两个正整数m(0 < m <= 100)和n(0 < n <= 2000),然后有m行,每行有n个数,数字之间用空格分开,表示这m个序列 序列中的数字不会大于10000
输出
对每组测试用例,输出一行用空格隔开的数,表示最小的n个和
样例输入
1 2 3 1 2 3 2 2 3
样例输出
3 3 4
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int> que;
int a[2005];
int b[2005]; // 用作中间数组
int main() {
int T;
cin >> T;
int m, n;
while (T--) {
cin >> m >> n;
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
sort(a, a + n); // 用a做总的和数组
for (int i = 1; i < m; i++) // 轮接下来的序列
{
for (int j = 0; j < n; j++) {
scanf("%d", &b[j]);
que.push(a[0] + b[j]);
}
for (int j = 1; j < n; j++) {
for (int k = 0; k < n; k++) {
if (a[j] + b[k] < que.top()) {
que.pop();
que.push(a[j] +
b[k]); // 比最大值小就顶了它,想要得到ab两个里面最小的n个数
}
}
}
for (int i = 0; i < n; i++) {
a[n - i - 1] = que.top(); // 由于是最大值堆,要反过来让a有序
que.pop(); // 队列已经被清空了,轮下一次
}
}
for (int i = 0; i < n - 1; i++)
printf("%d ", a[i]);
printf("%d\n", a[n - 1]);
}
return 0;
}priority queue练习题
我们定义一个正整数a比正整数b优先的含义是:
*a的质因数数目(不包括自身)比b的质因数数目多;
*当两者质因数数目相等时,数值较大者优先级高。
现在给定一个容器,初始元素数目为0,之后每次往里面添加10个元素,每次添加之后,要求输出优先级最高与最低的元素,并把该两元素从容器中删除。
时间限制:2500
内存限制:131072
输入
第一行: num (添加元素次数,num <= 30)
下面10*num行,每行一个正整数n(n < 10000000).
输出
每次输入10个整数后,输出容器中优先级最高与最低的元素,两者用空格间隔。
样例输入
1 10 7 66 4 5 30 91 100 8 9
样例输出
66 5
#include <cmath>
#include <iostream>
#include <set>
using namespace std;
// 判断一个数是否为质数
bool isPrime(int iVal) {
for (int i = 2; i <= sqrt((float)iVal); i++) {
if (iVal % i == 0)
return false;
}
return true;
}
// 得到一个数的质因数数目
int getFactor(int a) {
int sum = 0;
int k = 0;
for (int i = 2; i <= sqrt((float)a); i++) {
if (a % i == 0) // 即a/i = k,无余数
{
k = a / i;
if (i != k && isPrime(k))
sum += 1;
if (isPrime(i)) {
sum += 1;
}
}
}
return sum;
}
// 函数对象,判断大小
class Compare_Class_Up {
public:
bool operator()(const int &a, const int &b) {
int sumA = 0, sumB = 0;
sumA = getFactor(a);
sumB = getFactor(b);
if (sumA == sumB) {
if (a < b) {
return true;
} else
return false;
} else if (sumA > sumB) {
return false;
} else
return true;
}
};
int main() {
set<int, Compare_Class_Up> queue;
int n = 0;
cin >> n;
while (n--) {
int num;
for (int i = 0; i < 10; i++) {
cin >> num;
queue.insert(num);
}
int min = *(queue.begin());
int max = *(queue.rbegin());
queue.erase(max);
queue.erase(min);
cout << max << ' ' << min << endl;
}
return 0;
}stack or queue
栈和队列都是常用的线性结构,它们都提供两个操作:
Push:加入一个元素。
Pop:弹出一个元素。
不同的是,栈是”先进后出”,而队列则是”先进先出”。
给出一个线性结构的进出顺序,判定这个结构是栈还是队列。
时间限制:1000
内存限制:65535
输入
第一行输入一个整数t,代表有t组测试数据 对于每组测试数据,第一行输入一个整数n,代表操作的次数。 随后输入n行,每行包含两个整数 type val。 当type = 1时,表示该次操作为push操作,val表示进入的数字。当type=2时,表示该次操作为pop操作,val代表出来的数字。 3<=n<=2000
输出
每组测试数据输出一行。 输出该组数据对应的线性结构,”Stack” 或者 “Queue”。 题目保证是栈或者队列的一种。
样例输入
2 6 1 1 1 2 1 3 2 3 2 2 2 1 4 1 1 1 2 2 1 2 2
样例输出
Stack Queue
#include <deque>
#include <iostream>
using namespace std;
int main() {
int t;
scanf("%d", &t);
deque<int> ds; // imitating stack
for (int i = 0; i < t; i++) {
int n;
bool tag = false;
scanf("%d", &n);
for (int j = 0; j < n; j++) {
int type, val;
scanf("%d%d", &type, &val);
if (tag)
continue;
if (type == 1) {
ds.push_back(val);
} else {
int s = ds.back();
ds.pop_back();
if (s != val) {
printf("Queue\n");
tag = true;
}
}
}
if (!tag)
printf("Stack\n");
ds.clear();
}
}栈的基本操作
栈是一种重要的数据结构,它具有push k和pop操作。push k是将数字k加入到栈中,pop则是从栈中取一个数出来。
栈是后进先出的:把栈也看成横向的一个通道,则push k是将k放到栈的最右边,而pop也是从栈的最右边取出一个数。
假设栈当前从左至右含有1和2两个数,则执行push 5和pop操作示例图如下:
push 5 pop
1
栈 1 2 -------> 1 2 5 ------> 1 2
现在,假设栈是空的。给定一系列push k和pop操作之后,输出栈中存储的数字。若栈已经空了,仍然接收到pop操作,则输出error。
时间限制:1000
内存限制:65536
输入
第一行为m,表示有m组测试输入,m<100。 每组第一行为n,表示下列有n行push k或pop操作。(n<150) 接下来n行,每行是push k或者pop,其中k是一个整数。 (输入保证同时在栈中的数不会超过100个)
输出
对每组测试数据输出一行。该行内容在正常情况下,是栈中从左到右存储的数字,数字直接以一个空格分隔,如果栈空,则不作输出;但若操作过程中出现栈已空仍然收到pop,则输出error。
样例输入
2 4 push 1 push 3 pop push 5 1 pop
样例输出
1 5 error
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 1000
typedef struct {
int num[M];
int top;
} stack;
void push(stack *p, int i) {
if (p->top == M - 1)
return;
else {
p->num[++(p->top)] = i;
return;
}
}
int pop(stack *p) {
if (p->top == -1) {
return 0;
} else
return (p->num[(p->top)--]);
}
int main() {
int m, n, i, j;
char s[5];
stack *p;
scanf("%d", &m);
while (m--) {
int t = 0;
p = (stack *)malloc(sizeof(stack));
p->top = -1;
scanf("%d", &n);
while (n--) {
scanf("%s", s);
if (strcmp(s, "push") == 0) {
scanf("%d", &i);
push(p, i);
} else {
if (p->top == -1)
t = 1;
pop(p);
}
}
if (t == 1)
printf("error\n");
else {
if (p->top != -1) {
for (j = 0; j < (p->top); j++)
printf("%d ", p->num[j]);
printf("%d\n", p->num[p->top]);
}
}
}
return 0;
}发型糟糕的一天
农夫John 的N(1 ≤ N ≤ 80,000)只奶牛中,有一些也许正在经历发型糟糕的一天。每只奶牛对自己乱糟糟的发型都有自知之明,农夫John想知道所有奶牛能看到其他奶牛头顶的数量之和。
任意奶牛i身高记为 hi (1 ≤ hi ≤ 1,000,000,000),所有奶牛面向东方(本题示意图的右面)依次站成一条线。因此,奶牛i能够看到在它前面的(奶牛i+1,i+2…)所有身高比它低的奶牛,直到被一头比它高的奶牛挡住
考虑如下的例子:
=
= =
= - = Cows facing right ->
= = =
= - = = =
= = = = = =
1 2 3 4 5 6 奶牛#1 可以看见奶牛#2, 3, 4的头顶
奶牛#2 无法看到任何奶牛的头顶
奶牛#3可以看见奶牛#4的头顶
奶牛#4无法看到任何奶牛的头顶
奶牛#5可以看见奶牛#6的头顶
奶牛#6无法看到任何奶牛的头顶!
用ci表示奶牛i能够看到头顶的奶牛个数;请计算c1 至cN的和。对于上面这个例子,其和为:3 + 0 + 1 + 0 + 1 + 0 = 5。
时间限制:2000
内存限制:65536
输入
第1行:奶牛数N第2行至N+1行:第i+1行包含一个整数,表示奶牛i的高度
输出
第1行:c1 至cN的累加和
样例输入
6 10 3 7 4 12 2
样例输出
5
#include <iostream>
#include <stack>
using namespace std;
int main() {
long long n, h, sum = 0;
cin >> n;
stack<int> s;
cin >> h;
s.push(h);
n -= 1;
while (n--) {
cin >> h;
while (!s.empty() && h >= s.top()) {
s.pop();
}
sum += s.size();
s.push(h);
}
cout << sum << endl;
return 0;
}