Scratch编程一级 题库
找和最接近但不超过K的两个元素
在一个长度为n(1 < n < 1000)的整数(0至1000之间)序列中,选出两个元素使得它们的和最接近但不超过K(0 <= K < 2000)。保证一定存在不超过K的两元素和。<n<1000)的整数(0至1000之间)序列中,选出两个元素使得它们的和最接近但不超过k(0<=k<2000)。保证一定存在不超过k的两元素和。<n<1000)的整数(0至1000之间)序列中,选出两个元素使得它们的和最接近但不超过k(0<=k<2000)。保证一定存在不超过k的两元素和。
<n<1000)的整数(0至1000之间)序列中,选出两个元素使得它们的和最接近但不超过k(0<=k<2000)。保证一定存在不超过k的两元素和。
时间限制:1000
内存限制:65536
输入
第一行输入一个整数n 第二行输入一个整数K 第三行输入序列,用空格分开
输出
最接近但不超过K的和
样例输入
4 7 1 2 2 8
样例输出
4
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
int a[10005];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
int l = 0, r = n - 1;
int ans = a[0] + a[1];
while (l < r) {
int sum = a[l] + a[r];
if (sum <= k) {
if (k - sum < k - ans)
ans = sum;
}
if (sum == k) {
cout << k << endl;
return 0;
} else if (sum < k)
l++;
else
r--;
}
cout << ans << endl;
}数根
树根可以通过把一个数的各个位上的数字加起来得到。如果得到的数是一位数,那么这个数就是数根。如果结果是两位数或者包括更多位的数字,那么再把这些数字加起来。如此进行下去,直到得到是一位数为止。比如,对于24来说,把2和4相加得到6,由于6是一位数,因此6是24的数根。再比如39,把3和9加起来得到12,由于12不是一位数,因此还得把1和2加起来,最后得到3,这是一个一位数,因此3是39的数根。
输入
一个正整数(小于10^1000)
输出
一个数字,即输入数字的数根
样例输入
24
样例输出
6
#include <bits/stdc++.h>
using namespace std;
int sg(int n) {
int sum = 0;
while (n) {
sum += n % 10;
n /= 10;
}
if (sum >= 10)
return sg(sum);
return sum;
}
int main() {
string s;
int len, ans = 0;
cin >> s;
len = s.size();
for (int i = 0; i < len; i++) {
ans = ans + s[i] - '0';
}
cout << sg(ans);
return 0;
}迷信的病人
医院为了方便对患者进行建档和管理,引入了9位整数ID号来标识每个病人。最近医院入住了一个迷信的病人,他认为ID号的好坏直接决定了自己的命运。他对ID号x有如下要求:
(1)x的前三位数构成的整数是素数
(2)x的后三位数构成的整数是平方数(所谓平方数,是指它是某一个正整数的平方,e.g. 1,4,9,16...)
(3)x中不包含"13"
为了避免不必要的医患矛盾,医院须尽量满足他的需求。现给定正整数区间[m,n],请你判断存在几个满足病人需求的ID号。
时间限制:1000
内存限制:65536
输入
两个正整数m,n,以空格隔开。(999999999>=n>=m>=111111111)
输出
一个整数(满足要求的ID的个数)。
样例输入
157689476 157689687
样例输出
5
提示
存在5个满足要求的ID:157689484,157689529,157689576,157689625,157689676
#include <bits/stdc++.h>
using namespace std;
bool su(int x) {
for (int i = 2; i < x; i++) {
if (x % i == 0)
return false;
}
return true;
}
bool pf(int x) {
int n = sqrt(x);
if (n * n == x)
return true;
return false;
}
int main() {
int m, n, ans = 0;
cin >> m >> n;
for (int i = m; i <= n; i++) {
int q, h;
q = i / 1000000;
h = i % 1000;
int flag = 0, k = i;
while (k) {
if (k % 10 == 3 && k / 10 % 10 == 1)
flag = 1;
k /= 10;
}
if (flag == 0 && su(q) && pf(h))
ans++;
}
cout << ans;
return 0;
}算24
给出4个小于10个正整数,你可以使用加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。现在的问题是,是否存在一种方式使得得到的表达式的结果等于24。 这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致(这里的除法定义是实数除法)。 比如,对于5,5,5,1,我们知道5 * (5 – 1 / 5) = 24,因此可以得到24。又比如,对于1,1,4,2,我们怎么都不能得到24。
时间限制:6000
内存限制:65536
输入
输入数据包括多行,每行给出一组测试数据,包括4个小于10个正整数。最后一组测试数据中包括4个0,表示输入的结束,这组数据不用处理。
输出
对于每一组测试数据,输出一行,如果可以得到24,输出“YES”;否则,输出“NO”。
样例输入
5 5 5 1 1 1 4 2 0 0 0 0
样例输出
YES NO
#include <bits/stdc++.h>
#include <cmath>
#include <iostream>
#define EPS 1e-6
using namespace std;
bool iszero(double c) {
if (fabs(c) <= EPS)
return 1;
else
return 0;
}
bool suan24(double *a, int k) {
if (k == 1 && iszero(a[0] - 24))
return 1;
double b[5];
for (int i = 0; i < k - 1; i++)
for (int j = i + 1; j < k; j++) {
int z = 0;
for (int xx = 0; xx < k; xx++)
if (xx != i && xx != j)
b[z++] = a[xx];
b[z] = a[i] + a[j];
if (suan24(b, k - 1))
return 1;
b[z] = a[i] - a[j];
if (suan24(b, k - 1))
return 1;
b[z] = a[j] - a[i];
if (suan24(b, k - 1))
return 1;
b[z] = a[i] * a[j];
if (suan24(b, k - 1))
return 1;
if (a[j] != 0) {
b[z] = a[i] / a[j];
if (suan24(b, k - 1))
return 1;
}
if (!iszero(a[i])) {
b[z] = a[j] / a[i];
if (suan24(b, k - 1))
return 1;
}
}
return 0;
}
int main() {
while (1) {
double a[6];
int sum = 0;
for (int i = 0; i < 4; ++i) {
cin >> a[i];
sum += a[i];
}
if (sum == 0)
break;
bool flag = suan24(a, 4);
if (flag == 1)
cout << "YES" << endl;
else
cout << "NO" << endl;
// cout<<flag<<endl;
}
return 0;
}//解法2 深搜
#include <bits/stdc++.h>
using namespace std;
double a[5];
bool fig(double a[],int n){
double b[5];
int i,j,k,m;
if(fabs(a[0]-24)<1e-6 && n==1) return 1;
if(n==1) return 0;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++){
m=0;
for(k=0;k<n;k++)
if(k!=i&&k!=j) b[++m]=a[k];
b[0]=a[i]+a[j];if(fig(b,n-1)) return 1;
b[0]=a[i]-a[j];if(fig(b,n-1)) return 1;
b[0]=a[j]-a[i];if(fig(b,n-1)) return 1;
b[0]=a[i]*a[j];if(fig(b,n-1)) return 1;
b[0]=a[i]/a[j];if(fig(b,n-1)) return 1;
b[0]=a[j]/a[i];if(fig(b,n-1)) return 1;
}
return 0;
}
int main() {
while(1){
for(int i=0;i<4;i++) cin>>a[i];
if(a[0]==0&&a[1]==0&&a[2]==0&&a[3]==0) break;
if(fig(a,4)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}倒序输出
依次输入4个整数a、b、c、d,将他们倒序输出,即依次输出d、c、b、a这4个数。
时间限制:1000
内存限制:65536
输入
一行4个整数a、b、c、d,以空格分隔。 0 < a,b,c,d < 108
输出
一行4个整数d、c、b、a,整数之间以一个空格分隔。
样例输入
1 2 3 4
样例输出
4 3 2 1
#include <bits/stdc++.h>
using namespace std;
int a, b, c, d;
int main() {
cin >> a >> b >> c >> d;
cout << d << ' ' << c << ' ' << b << ' ' << a;
return 0;
}最小的数
依次输入3个整数a、b、c,将a、b、c中的最小值输出。
时间限制:1000
内存限制:65536
输入
一行3个整数a、b、c,以空格分隔。 0 < a,b,c < 108
输出
1个整数,即3个整数的最小值。
样例输入
2 3 2
样例输出
2
#include <bits/stdc++.h>
using namespace std;
long long a, b, c, ss;
int main() {
cin >> a >> b >> c;
ss = min(a, b);
ss = min(ss, c);
cout << ss;
return 0;
}开关灯
假设有N盏灯(N为不大于5000的正整数),从1到N按顺序依次编号,初始时全部处于开启状态;有M个人(M为不大于N的正整数)也从1到M依次编号。
第一个人(1号)将灯全部关闭,第二个人(2号)将编号为2的倍数的灯打开,第三个人(3号)将编号为3的倍数的灯做相反处理(即,将打开的灯关闭,将关闭的灯打开)。依照编号递增顺序,以后的人都和3号一样,将凡是自己编号倍数的灯做相反处理。
请问:当第M个人操作之后,哪几盏灯是关闭的,按从小到大输出其编号,其间用逗号间隔。
时间限制:1000
内存限制:65536
输入
输入正整数N和M,以单个空格隔开。
输出
顺次输出关闭的灯的编号,其间用逗号间隔。
样例输入
10 10
样例输出
1,4,9
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[5010];
int i, j;
int flag = 1;
int main() {
cin >> n >> m;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
if (j % i == 0)
a[j] = !a[j];
for (i = 1; i <= n; i++) {
if (a[i]) {
if (flag)
flag = 0;
else
cout << ",";
cout << i;
}
}
cout << endl;
return 0;
}字符串插入
有两个字符串str和substr,str的字符个数不超过10,substr的字符个数为3。(字符个数不包括字符串结尾处的'\0'。)将substr插入到str中ASCII码最大的那个字符后面,若有多个最大则只考虑第一个。
时间限制:1000
内存限制:65536
输入
输入包括若干行,每一行为一组测试数据,格式为 str substr
输出
对于每一组测试数据,输出插入之后的字符串。
样例输入
abcab eee 12343 555
样例输出
abceeeab 12345553
#include <cstring>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef char ElemType;
const int M = 14;
typedef struct {
ElemType data[M];
int length;
} SqList;
void lnitList(SqList &L) { L.length = 0; }
void f(SqList &s1, SqList s2) {
ElemType maxc = s1.data[0];
int index = 0;
int j = 0;
for (int i = 0; i < s1.length; i++) {
if (maxc < s1.data[i]) {
index = i;
maxc = s1.data[i];
}
}
s1.data[s1.length] = 0;
s1.data[s1.length + 3] = '\0';
for (int i = s1.length; i > index; i--) {
s1.data[i + 3] = s1.data[i];
}
for (int i = index + 1; i <= index + 3; i++) {
s1.data[i] = s2.data[j++];
}
s1.length += 3;
}
int main() {
SqList s1, s2;
while (cin >> s1.data >> s2.data) {
lnitList(s1);
lnitList(s2);
s1.length = strlen(s1.data);
s2.length = strlen(s2.data);
f(s1, s2);
cout << s1.data << endl;
}
return 0;
}栈基本操作
依次读入序列元素1,2,...,n进栈,每进一个元素,机器可要求下一个元素进栈或弹栈,如此进行。给定一个输入序列,判断栈空时弹出的元素构成的序列是否可能等于给定的序列,如果是则输出栈的操作过程,否则输出“NO”。
时间限制:1000
内存限制:65535
输入
输入分两行 第一行为n的值(即序列元素个数) 第二行为给定的输入序列(序列元素均为整型)
输出
如果输入序列能够由题目规定的操作得到,则输出对栈的操作过程 否则直接输出“NO”
样例输入
7 4 5 3 6 2 7 1
样例输出
PUSH 1 PUSH 2 PUSH 3 PUSH 4 POP 4 PUSH 5 POP 5 POP 3 PUSH 6 POP 6 POP 2 PUSH 7 POP 7 POP 1
提示
给定序列中有可能有不在1...n之间的数字
#include <bits/stdc++.h>
using namespace std;
const int MAXL = 100010;
vector<int> v;
int n;
int visited[MAXL];
bool isLegal() {
stack<int> sk;
int idx = 1;
int k = 0;
while (idx <= n) {
sk.push(idx++);
while (!sk.empty() && sk.top() == v[k]) {
sk.pop();
k++;
}
}
return sk.empty() && k == n;
}
int main() {
// 数据的输入和非法输入判断
cin >> n;
for (int i = 0; i < n; i++) {
int tmp;
cin >> tmp;
if (visited[tmp] || tmp <= 0 || tmp > n) {
cout << "NO" << endl;
system("pause");
return 0;
}
v.push_back(tmp);
visited[tmp] = 1;
}
// 判断是否合法
if (!isLegal()) {
cout << "NO" << endl;
system("pause");
return 0;
}
// 模拟栈
stack<int> sk;
int i = 0; // i是出栈的指针
int j = 1; // j是入栈的指针
while (i < n) { // 最后一个操作是出栈
if (!sk.empty() && sk.top() == v[i]) {
cout << "POP " << v[i] << endl;
sk.pop();
i++;
} else {
cout << "PUSH " << j << endl;
sk.push(j);
j++;
}
}
system("pause");
}书架
John最近买了一个书架用来存放奶牛养殖书籍,但书架很快被存满了,只剩最顶层有空余。
John共有N头奶牛(1 ≤ N ≤ 20,000),每头奶牛有自己的高度Hi(1 ≤ Hi ≤ 10,000),N头奶牛的总高度为S。书架高度为B(1 ≤ B ≤ S < 2,000,000,007).
为了到达书架顶层,奶牛可以踩着其他奶牛的背,像叠罗汉一样,直到他们的总高度不低于书架高度。当然若奶牛越多则危险性越大。为了帮助John到达书架顶层,找出使用奶牛数目最少的解决方案吧。
时间限制:10000
内存限制:65536
输入
第1行:空格隔开的整数N和B 第2~N+1行:第i+1行为整数Hi
输出
能达到书架高度所使用奶牛的最少数目
样例输入
6 40 6 18 11 13 19 11
样例输出
3
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define INF 999999999
#define N 20001
using namespace std;
int a[N];
void qsort(int x, int y) {
int i = x, j = y, mid = a[(x + y) / 2];
while (i <= j) {
while (a[i] > mid)
i++;
while (a[j] < mid)
j--;
if (i <= j) {
swap(a[i], a[j]);
i++;
j--;
}
}
if (x < j)
qsort(x, j);
if (i < y)
qsort(i, y);
}
int main() {
int n, b;
int sum = 0;
int i;
cin >> n >> b;
for (i = 1; i <= n; i++)
cin >> a[i];
qsort(1, n);
for (i = 1; i <= n; i++) {
sum += a[i];
if (sum >= b)
break;
}
cout << i << endl;
;
return 0;
}课程表
现在你总共有n门课需要选,记为0到n-1。在选修某些课程之前需要一些先修课程。例如,想要学习课程0,你需要先完成课程1,我们用一个匹配来表示他们:[0, 1]。给定课程总量以及它们的先决条件,判断是否可能完成所有课程的学习?
时间限制:1000
内存限制:65536
输入
多组数据。每组数据第一行是n和m,n表示有n门课程,m表示有m组依赖关系,接下来的m行是依赖关系的具体信息a b,表示第a门课程依赖第b门课程。 0<=n <=1000,0 <= m <= 4000 两组数据之间可能有空行
输出
对每组数据,能完成输出 True,不能完成输出 False
样例输入
2 1 1 0 2 2 1 0 0 1
样例输出
True False
提示
示例2解释: 总共有2门课程。学习课程1之前,你需要先完成课程0;并且学习课程0之前,你还应先完成课程1。这是不可能的。
// 拓扑排序:Kahn算法+邻接表+栈
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[1005][1005]; // 邻接点
int rd[1005], cd[1005]; // 入度 出度
int main() {
int r, c, num, i, j, k;
stack<int> st;
while (cin >> n >> m) {
memset(a, 0, sizeof(a));
memset(rd, 0, sizeof(rd));
memset(cd, 0, sizeof(cd));
while (!st.empty())
st.pop();
for (i = 1; i <= m; i++) {
cin >> r >> c;
rd[c]++;
cd[r]++;
a[r][cd[r]] = c;
}
for (i = 0; i <= n - 1; i++)
if (rd[i] == 0) {
st.push(i);
}
num = 0;
while (!st.empty()) {
i = st.top();
st.pop();
num++;
for (j = 1; j <= cd[i]; j++) {
k = a[i][j];
rd[k]--;
if (rd[k] == 0)
st.push(k);
}
}
if (num == n)
cout << "True" << endl;
else
cout << "False" << endl;
}
return 0;
}拯救公主
多灾多难的公主又被大魔王抓走啦!国王派遣了第一勇士阿福去拯救她。
身为超级厉害的术士,同时也是阿福的好伙伴,你决定祝他一臂之力。你为阿福提供了一张大魔王根据地的地图,上面标记了阿福和公主所在的位置,以及一些不能够踏入的禁区。你还贴心地为阿福制造了一些传送门,通过一个传送门可以瞬间转移到任意一个传送门,当然阿福也可以选择不通过传送门瞬移。传送门的位置也被标记在了地图上。此外,你还查探到公主所在的地方被设下了结界,需要集齐K种宝石才能打开。当然,你在地图上也标记出了不同宝石所在的位置。
你希望阿福能够带着公主早日凯旋。于是在阿福出发之前,你还需要为阿福计算出他最快救出公主的时间。
地图用一个R×C的字符矩阵来表示。字符S表示阿福所在的位置,字符E表示公主所在的位置,字符#表示不能踏入的禁区,字符$表示传送门,字符.表示该位置安全,数字字符0至4表示了宝石的类型。阿福每次可以从当前的位置走到他上下左右四个方向上的任意一个位置,但不能走出地图边界。阿福每走一步需要花费1个单位时间,从一个传送门到达另一个传送门不需要花费时间。当阿福走到宝石所在的位置时,就视为得到了该宝石,不需要花费额外时间。
时间限制:1000
内存限制:65536
输入
第一行是一个正整数T(1 <= T <= 10),表示一共有T组数据。 每一组数据的第一行包含了三个用空格分开的正整数R、C(2 <= R, C <= 200)和K,表示地图是一个R×C的矩阵,而阿福需要集齐K种宝石才能够打开拘禁公主的结界。 接下来的R行描述了地图的具体内容,每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。$的数量不超过10个。宝石的类型在数字0至4范围内,即不会超过5种宝石。
输出
对于每一组数据,输出阿福救出公主所花费的最少单位时间。若阿福无法救出公主,则输出“oop!”(只输出引号里面的内容,不输出引号)。每组数据的输出结果占一行。
样例输入
1 7 8 2 ........ ..S..#0. .##..1.. .0#..... ...1#... ...##E.. ...1....
样例输出
11
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define N 210
using namespace std;
int dir[2][4] = {{1, 0, 0, -1}, {0, 1, -1, 0}};
int dp[N][N][1 << 5 - 1], trans[20][2], n, m, k, tot, num, T, x, y, ans;
char map[N][N];
struct node {
int x, y, step, key;
node(int xx, int yy, int ss, int kk) : x(xx), y(yy), step(ss), key(kk){};
};
bool check(int key) {
int cnt = 0;
for (int i = 0; i <= 5; i++)
if ((key >> i) & 1)
cnt++; // 位运算 统计这条路上可获不同种类的宝石数量
if (cnt >= k)
return 1;
return 0;
}
int bfs(int x, int y) {
queue<node> que; // 根据结构体 定义队列que
dp[x][y][0] = 1;
node now(x, y, 0, 0); // 相当于 定义了now这个结构体变量
que.push(now); // 进队
while (!que.empty()) // 当队列不为空时 .empty()-->若队列为空返回1;
{
now = que.front(); // 把队头的值赋给now这个结构体上
que.pop(); // 弹出队首
for (int i = 0; i < 4; i++) // 上下左右四个执行方案
{
int xx = now.x + dir[0][i]; // 具体变动
int yy = now.y + dir[1][i];
int step = now.step; // 步数
int key = now.key; //
if (xx < 0 || xx >= n || yy < 0 || yy >= m)
continue; // 判断边界
if (dp[xx][yy][key])
continue; // 若在队中 不走
if (map[xx][yy] == '#')
continue; // 禁区 不走
if (map[xx][yy] == 'E' && check(key)) // 既到达营救点 且 宝石够数
{
return step + 1; // 返回步数 //结束遍历
}
if (isdigit(map[xx][yy])) //
{
dp[xx][yy][key] = 1; // 标记 相当于vis
key = key | (1 << (map[xx][yy] - '0')); // 记录宝石
que.push(node(xx, yy, step + 1, key)); // 进队
}
if (map[xx][yy] == '.') // 普通地带
{
dp[xx][yy][key] = 1; // 标记
que.push(node(xx, yy, step + 1, key));
}
if (map[xx][yy] == '$') // 传送门
{
dp[xx][yy][key] = 1; // 标记
que.push(node(xx, yy, step + 1, key)); // 进队
for (int j = 1; j <= tot; j++) // 遍历 方案
{
xx = trans[j][0], yy = trans[j][1];
if (!dp[xx][yy][key]) {
dp[xx][yy][key] = 1; // 标记
que.push(node(xx, yy, step + 1, key)); // 进队
}
}
}
}
}
return -1; // 若遍历完还没返回 就说明没有可行方案
}
main() {
cin >> T; // 组数
while (T--) {
memset(dp, 0, sizeof(dp));
tot = 0;
num = 0; // 初始化
scanf("%d%d%d", &n, &m, &k);
// cin>>n>>m>>k;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
cin >> map[i][j];
// scanf("%c",&map[i][j]);还是没搞明白为什么不能用scanf和getchar
// map[i][j]=getchar();
if (map[i][j] == 'S')
x = i, y = j, map[i][j] = '.'; // 标记起点
if (map[i][j] == '$')
trans[++tot][0] = i, trans[tot][1] = j; // 记录传送门
if (isdigit(map[i][j]))
num++; // 判断是否是宝石(数字)
}
if (k > num) {
printf("oop!\n");
continue;
} // 没有足够的宝石
ans = bfs(x, y);
if (ans == -1)
printf("oop!\n");
else
printf("%d\n", ans);
}
}最长公共子上升序列
给定两个整数序列,写一个程序求它们的最长上升公共子序列。 当以下条件满足的时候,我们将长度为N的序列S1 , S2 , . . . , SN 称为长度为M的序列A1 , A2 , . . . , AM 的上升子序列: 存在 1 <= i1 < i2 < . . . < iN <= M ,使得对所有 1 <= j <=N,均有Sj = Aij,且对于所有的1 <= j < N,均有Sj < Sj+1。
时间限制:10000
内存限制:65536
输入
每个序列用两行表示,第一行是长度M(1 <= M <= 500),第二行是该序列的M个整数Ai (-231 <= Ai < 231 )
输出
在第一行,输出两个序列的最长上升公共子序列的长度L。在第二行,输出该子序列。如果有不止一个符合条件的子序列,则输出任何一个即可。
样例输入
5 1 4 2 5 -12 4 -12 1 2 4
样例输出
2 1 4
#include <bits/stdc++.h>
using namespace std;
#define N 505
int dp
[N]
[N]; // dp[i][j]:x前i个元素与y前j个元素构成的以x[i]为结尾的最长公共上升子序列的长度
int x[N], y[N];
vector<int> seq
[N]; // seq[i]:当j为某确定值时,x前i个元素与y前j个元素构成的以x[i]为结尾的最长公共上升子序列
int main() {
int xn, yn;
cin >> xn;
for (int i = 1; i <= xn; ++i)
cin >> x[i];
cin >> yn;
for (int i = 1; i <= yn; ++i)
cin >> y[i];
for (int j = 1; j <= yn; ++j)
for (int i = 1; i <= xn; ++i) {
if (x[i] == y[j]) {
dp[i][j] = 1;
seq[i] = vector<int>();
for (int k = 1; k < i; ++k) {
if (x[k] < x[i] && dp[k][j - 1] + 1 > dp[i][j]) {
dp[i][j] = dp[k][j - 1] + 1;
seq[i] = seq[k];
}
}
seq[i].push_back(x[i]);
} else
dp[i][j] = dp[i][j - 1];
}
int mxi = 1;
for (int i = 1; i <= xn; i++) {
if (dp[i][yn] > dp[mxi][yn])
mxi = i;
}
cout << dp[mxi][yn] << endl;
for (int i = 0; i < seq[mxi].size(); ++i)
cout << seq[mxi][i] << ' ';
return 0;
}技能树
设二叉树中每个节点的子节点数为0或2,求有N个节点高度为M的不同的二叉树有多少个
(输出 mod 9901 后的结果)。
时间限制:10000
内存限制:131072
输入
两个空格分开的整数, N和K。
输出
第 1 行: 一个整数,表示可能的技能树的个数除以9901的余数。
样例输入
5 3
样例输出
2
提示
有5个节点,高为3的两个不同的技能树。约定:n在[3,300]间,m在(1,100)间
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
#define N 310
#define M 110
#define mod 9901
int f[M][N], sum[N][M];
int main() {
int n, m;
scanf("%d%d", &n, &m);
f[1][1] = sum[1][1] = 1;
for (int j = 2; j <= n; j++)
f[1][j] = sum[1][j] = 0;
for (int i = 2; i <= m; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = 0;
for (int k = 1; k < j; k++)
f[i][j] = (f[i][j] + (2 * f[i - 1][k] * sum[i - 1][j - k - 1] -
f[i - 1][k] * f[i - 1][j - k - 1]) %
mod) %
mod;
sum[i][j] = (sum[i - 1][j] + f[i][j]) % mod;
}
}
printf("%d\n", f[m][n]);
return 0;
}温度统计
现有一段时间的温度数据,请统计指定温度出现的次数。
时间限制:1000
内存限制:65536
输入
第一行一个整数n,表示温度数据的个数。(0 < n ≤ 200) 第二行n个整数,以空格分隔,每个整数表示一个温度,温度的范围大于等于0,小于等于40。 第三行一个整数,表示需要查询的温度t。(0 ≤ t ≤ 40)
输出
输出一个整数,表示温度t出现的次数。
样例输入
10 18 19 21 17 20 18 21 21 22 21 21
样例输出
4
#include <bits/stdc++.h>
using namespace std;
int a[202];
int main() {
int n, t, ans;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
cin >> t;
ans = 0;
for (int i = 1; i <= n; i++)
if (a[i] == t)
ans++;
cout << ans << endl;
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;
}与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;
}发现它,抓住它
一个城市中有两个犯罪团伙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;
}