Scratch编程一级 题库
输出整数部分
输入一个双精度浮点数f, 输出其整数部分。
时间限制:1000
内存限制:65536
输入
一个双精度浮点数f(0 < f < 100000000)。
输出
一个整数,表示浮点数的整数部分。
样例输入
3.8889
样例输出
3
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
double a;
cin >> a;
int b;
b = a;
cout << b;
return 0;
}疫情集中隔离
A同学12月初从国外回来,按照防疫要求,需要进行14天集中隔离,请你实现一个程序,根据回国的时间计算集中隔离结束的日期。
比如,12月1号回来,1号当天开始隔离,14号是隔离的最后一天,因此14号是集中隔离结束的日期。
时间限制:1000
内存限制:65536
输入
一个整数x,表示A同学12月x号回国。(1 ≤ x ≤ 15)
输出
一个整数y,表示A同学结束集中隔离的日期(即12月y号A结束集中隔离)。
样例输入
1
样例输出
14
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
int a, b = 1, c = 1;
cin >> a;
if (a <= 18) {
b = a + 13;
} else {
b = a - 18;
}
cout << b;
return 0;
}字符判断
对于给定的字符,如果该字符是大小写字母或者数字,输出YES, 否则输出NO
时间限制:1000
内存限制:65536
输入
一个字符
输出
按照题目要求输出YES或者NO
样例输入
样例1输入
A
样例2输入
a
样例3输入
1
样例4输入
*
样例输出
样例1输出
YES
样例2输出
YES
样例3输出
YES
样例4输出
NO
提示
【样例输入】、【样例输出】里的多组数据只是给大家提供尽量多的参考,”样例1输入“、”样例1输出“等提示文字也只是为了区别不同的数据,输入输出中不会出现。输入输出的格式按照题目里【输入】【输出】的描述为准。
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
char a;
cin >> a;
if (a >= 'A' && a <= 'Z') {
cout << "YES";
} else if (a >= 'a' && a <= 'z') {
cout << "YES";
} else if (a >= '0' && a <= '9') {
cout << "YES";
} else {
cout << "NO";
}
return 0;
}统计数
给定一个数的序列S,以及一个区间[L, R], 求序列中介于该区间的数的个数,即序列中大于等于L且小于等于R的数的个数。
时间限制:1000
内存限制:65536
输入
第一行3个整数n、L、R,分别表示序列的长度,区间的左端点,区间的右端点。(0 < n ≤ 10000, 1 ≤ L ≤ R ≤ 1000000) 第二行n个正整数,表示序列里的每一个数,每个数小于等于10000000
输出
输出一个整数,表示序列中大于等于L且小于等于R的数的个数。
样例输入
5 1 10 11 8 1 10 16
样例输出
3
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
int a, b, c, d, e, g = 0;
cin >> a >> b >> c;
for (e = 1; e <= a; e++) {
cin >> d;
if (d >= b && d <= c) {
g++;
}
}
cout << g;
return 0;
}最大质因子
质因子是指能整除给定正整数的质数。而最大质因子是指一个整数的所有质因子中最大的那个。
比如30的质因子有2,3, 5,所以最大质因子就是5。
时间限制:1000
内存限制:65536
输入
一个整数N( 2 ≤ N ≤ 10000)
输出
N的最大质因子
样例输入
30
样例输出
5
提示
质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
int a;
bool b = true;
cin >> a;
for (int i = a; i >= 1; i--) {
if (a % i == 0) {
for (int j = 2; j < i; j++) {
if (i % j == 0)
b = false;
}
if (b == true) {
cout << i;
break;
} else {
b = true;
}
}
}
return 0;
}双端队列
定义一个双端队列,进队操作与普通队列一样,从队尾进入。出队操作既可以从队头,也可以从队尾。编程实现这个数据结构。
时间限制:1000
内存限制:65535
输入
第一行输入一个整数t,代表测试数据的组数。 每组数据的第一行输入一个整数n,表示操作的次数。 接着输入n行,每行对应一个操作,首先输入一个整数type。
当type=1,进队操作,接着输入一个整数x,表示进入队列的元素。
当type=2,出队操作,接着输入一个整数c,c=0代表从队头出队,c=1代表从队尾出队。
n <= 1000
输出
对于每组测试数据,输出执行完所有的操作后队列中剩余的元素,元素之间用空格隔开,按队头到队尾的顺序输出,占一行。如果队列中已经没有任何的元素,输出NULL。
样例输入
2 5 1 2 1 3 1 4 2 0 2 1 6 1 1 1 2 1 3 2 0 2 1 2 0
样例输出
3 NULL
//解法1
//用deque模拟一下即可
#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
int n,m,type,x;
cin>>n;
for(int i=1;i<=n;i++){
cin>>m;
deque<int> q;
for(int j=1;j<=m;j++){
cin>>type>>x;
if(type==1){
q.push_back(x);
}else {
if(x==0)q.pop_front();
else q.pop_back();
}
}
if(q.empty()){
cout<<"NULL";continue;
}
while(!q.empty()){
cout<<q.front()<<" ";
q.pop_front();
}
cout<<endl;
}
return 0;
}//解法2
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
int n, t, type, c;
int a[1005] = {0};
int Top = 0, Back = 0;
int main() {
cin >> t;
while (t--) {
Top = 0;
Back = 0;
cin >> n;
while (n--) {
cin >> type >> c;
if (type == 1) {
a[Back++] = c;
} else {
if (c == 0) {
Top++;
} else {
Back--;
}
}
}
if (Top == Back) {
cout << "NULL" << endl;
} else {
for (int i = Top; i < Back; ++i) {
cout << a[i] << " ";
}
cout << endl;
}
}
return 0;
}区间合并
给定 n 个闭区间 [ai; bi],其中i=1,2,...,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如,[1;2] 和 [2;3] 可以合并为 [1;3],[1;3] 和 [2;4] 可以合并为 [1;4],但是[1;2] 和 [3;4] 不可以合并。
我们的任务是判断这些区间是否可以最终合并为一个闭区间,如果可以,将这个闭区间输出,否则输出no。
时间限制:1000
内存限制:65536
输入
第一行为一个整数n,3 ≤ n ≤ 50000。表示输入区间的数量。 之后n行,在第i行上(1 ≤ i ≤ n),为两个整数 ai 和 bi ,整数之间用一个空格分隔,表示区间 [ai; bi](其中 1 ≤ ai ≤ bi ≤ 10000)。
输出
输出一行,如果这些区间最终可以合并为一个闭区间,输出这个闭区间的左右边界,用单个空格隔开;否则输出 no。
样例输入
5 5 6 1 5 10 10 6 9 8 10
样例输出
1 10
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
int t, n, min1, max1;
struct node {
int x, y;
} a[101000];
int N;
int cmp(const node &w, const node &e) {
if (w.x > e.x)
return 0;
return 1;
}
bool f(int i) {
min1 = a[1].x;
if (i == t)
return 1;
if (a[i + 1].x >= a[i].x && a[i + 1].x <= max1) {
max1 = max(max1, a[i + 1].y);
f(i + 1);
} else
return 0;
}
int main() {
int i = 1;
cin >> n;
t = n;
while (n--) {
cin >> a[i].x >> a[i].y;
i++;
}
sort(a + 1, a + t + 1, cmp);
max1 = a[1].y;
if (f(1))
printf("%d %d\n", min1, max1);
else
printf("no\n");
return 0;
}奇怪的括号
某天小A和同学在课堂上讨论到:“栈这种数据结构真是太优美了,既简单用途又广泛。”小B仰慕小A许久,于是他拿出了自己在网上抄写的一道题问小A,如何判断括号是否匹配呢
时间限制:1000
内存限制:65536
输入
多组数据,每组数据占一行,且都是由(、)、[、]、*、/这六种字符组成。
输出
每组数据输出一行,如果括号能匹配成功,输出True,否则输出False。括号匹配规则是: ( 和 ) 匹配 [ 和 ] 匹配 /* 和 */ 匹配 如果含有冗余字符也算匹配失败,例如 /***/ 是匹配失败的因为中间多了一个*。
样例输入
()/*[()]*/ */**/
样例输出
True False
#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
while (cin >> s) {
stack<char> st;
for (int i = 0; i < s.size(); i++) {
if (st.empty()) {
st.push(s[i]);
} else {
if (s[i] == ')' && st.top() == '(')
st.pop();
else if (s[i] == ']' && st.top() == '[')
st.pop();
else if (s[i] == '/' && st.top() == '*' && st.size() >= 3) {
st.pop();
char a = st.top();
st.pop();
char b = st.top();
st.pop();
if (!(a == '*' && b == '/')) {
st.push(b);
st.push(a);
st.push('*');
}
} else
st.push(s[i]);
}
}
if (st.empty())
cout << "True" << endl;
else
cout << "False" << endl;
}
return 0;
}合法出栈序列
给定一个由不同小写字母构成的长度不超过8的字符串x,现在要将该字符串的字符依次压入栈中,然后再全部弹出。
要求左边的字符一定比右边的字符先入栈,出栈顺序无要求。
再给定若干字符串,对每个字符串,判断其是否是可能的x中的字符的出栈序列。
时间限制:1000
内存限制:65536
输入
第一行是原始字符串x 后面有若干行,每行一个字符串
输出
对除第一行以外的每个字符串,判断其是否是可能的出栈序列。如果是,输出"YES",否则,输出"NO"
样例输入
abc abc bca cab
样例输出
YES YES NO
#include <bits/stdc++.h>
using namespace std;
string a, b;
int main() {
cin >> a;
while (cin >> b) {
stack<char> st;
int j = 0;
for (int i = 0; i < a.size(); i++) {
if (!st.empty())
if (st.top() == b[j]) {
st.pop();
j++;
}
st.push(a[i]);
}
while (!st.empty() && st.top() == b[j] && j < b.size()) {
st.pop();
j++;
}
if (st.empty())
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}抓牛
农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两种移动方式:
1、从X移动到X-1或X+1,每次移动花费一分钟
2、从X移动到2*X,每次移动花费一分钟
假设牛没有意识到农夫的行动,站在原地不动。农夫最少要花多少时间才能抓住牛?
时间限制:2000
内存限制:65536
输入
两个整数,N和K
输出
一个整数,农夫抓到牛所要花费的最小分钟数
样例输入
5 17
样例输出
4
#include <bits/stdc++.h>
using namespace std;
int b[200100];
int a[10];
queue<int> q;
int n, k;
void bfs(int x) {
q.push(x);
b[x] = 1;
while (!q.empty()) {
int s = q.front();
a[1] = s - 1;
a[2] = s + 1;
a[3] = 2 * s;
for (int i = 1; i < 4; i++) {
if (b[a[i]] == 0 && a[i] >= 0 && a[i] < 100100) {
b[a[i]] = b[s] + 1;
q.push(a[i]);
if (a[i] == k) {
cout << b[k] - 1 << endl;
}
}
}
q.pop();
}
}
int main() {
cin >> n >> k;
bfs(n);
return 0;
}泳池
学校是 N x N 的坐标方格 grid 中,每一个方格的值 grid(i,j)表示在位置 (i,j) 的高度。现在开始下雨了。当时间为 t 时,此时雨水导致方格中任意位置的水位为 t 。你可以从一个方格游向四周相邻的任意一个方格,但是前提是此时水位必须同时淹没这两个方格。假定小C的游动是不耗时的。
现在小C从坐标方格的左上(0,0)出发。最少耗时多久他才能到达坐标方格的右下平台 (N-1, N-1)?
时间限制:1000
内存限制:65536
输入
第一行有一个整数N,以下是一个N*N的方阵,代表各处的高度。
输入范围:
2 ≤ N ≤ 300
0 ≤ Height ≤ 10000000
输出
输出一个整数,代表最少等待时间T
样例输入
样例输入1:
2 0 2 1 3
样例输入2:
5 0 1 2 3 4 24 23 22 21 5 12 13 14 15 16 11 17 18 19 20 10 9 8 7 6
样例输出
样例输出1:
3
样例输出2:
16
提示
样例1:时间为3时,才可以游向平台(1,1),此时水位为3。 样例2:时间为16时,水位为16,此时才能保证(0,0)和(4,4)是联通的(请自行找出一条通路)。
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
int maze[305][305];
bool reach[305][305];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int N;
struct point {
int x, y;
point(int a, int b) : x(a), y(b) {}
};
bool canreach(int t) {
if (maze[0][0] > t)
return false;
memset(reach, 0, sizeof(reach));
reach[0][0] = 1;
queue<point> myqueues;
myqueues.push(point(0, 0));
while (!myqueues.empty()) {
point top = myqueues.front();
myqueues.pop();
if (top.x == N - 1 && top.y == N - 1)
return true;
for (int i = 0; i < 4; i++) {
int tx = top.x + dx[i];
int ty = top.y + dy[i];
if (tx < 0 || tx >= N || ty < 0 || ty >= N)
continue;
if (reach[tx][ty])
continue;
if (maze[tx][ty] > t)
continue;
reach[tx][ty] = 1;
myqueues.push(point(tx, ty));
}
}
return false;
}
int main() {
memset(maze, 0, sizeof(maze));
cin >> N;
int L = 10000000, R = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> maze[i][j];
L = min(maze[i][j], L);
R = max(maze[i][j], R);
}
}
int result = 10000000;
while (L <= R) {
int mid = (L + R) / 2;
if (canreach(mid)) {
R = mid - 1;
result = min(result, mid);
} else
L = mid + 1;
}
cout << result << endl;
return 0;
}问题求解
给定一个正整数N,求最小的M满足比N大且M与N的二进制表示中有相同数目的1。
举个例子,假如给定N为78,二进制表示为1001110,包含4个1,那么最小的比N大的并且二进制表示中只包含4个1的数是83,其二进制是1010011,因此83就是答案。
时间限制:1000
内存限制:65536
输入
输入若干行,每行一个数N(1 ≤ N ≤ 1000000),如果这行为0表示输入结束。
输出
对于每个N,输出对应的M。
样例输入
1 2 3 4 78 0
样例输出
2 4 5 8 83
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define INF 999999999
#define N 1001
using namespace std;
int main() {
int n;
while (scanf("%d", &n) != EOF && n) {
int cnt = 0;
int temp = n;
while (temp > 0) {
if (temp % 2)
cnt++;
temp /= 2;
}
int sum = 0;
while (1) {
temp = ++n;
while (temp > 0) {
if (temp % 2)
sum++;
temp /= 2;
}
if (cnt == sum) {
cout << n << endl;
break;
}
sum = 0;
}
}
return 0;
}//解法2 样例代码 枚举
using namespace std;
int n; // 定义变量 n
int tj(int x) {
int ans = 0; // 定义变量 ans
while (x) { // 当 x 不为0循环执行
if (x &)
ans++; // 如果 x 的最低位为1,则将 ans 加1
x >>= 1; // 将 x 右移1位,即将 x 的二进制表示向右移动一位
}
return ans; // 返回 ans
}
int main() {
while (1) { // 无限循环
cin >> n; // 从标准输入读取一个整数 n
if (!n)break; 如果 n 为0,则结束循环
int t = tj(n); // 调用函数 tj 计算 n 的二进制中的1的个数,并将结果赋值给 t
for (int i = n + 1;; i++) { // 从 n+1 开始递增遍历整数 i
if (t == tj(i)) {
cout << i << endl; // 输出第一个满足条件的整数 i,即其二进制表示中的1的个数与 t 相等
break; // 结束循环
}
}
}
return 0; // 返回 0,表示程序正常结束
}交易市场
市场里面一共有n种物品,有m种交易途径,每个交易途径可以由(x,y,z)表示,意思是可以用第x种物品换成第y种物品,并且得到z元的收益(z均大于0)。最开始你只有第一种物品,请问最多可以赚取多少收益。
时间限制:1000
内存限制:65536
输入
第一行两个正整数n和m(n ≤ 1000,m ≤ 4000) 接下来m行,每行三个正整数x, y, z,意思是可以用第x种物品换成第y种物品,并且得到z元的收益。(1 ≤ x,y ≤ n, 1 ≤ z ≤ 100)
输出
一个整数表示最大收益,如果可以赚取无穷多的收益则输出1000000000
样例输入
3 3 1 2 2 2 3 3 1 3 4
样例输出
5
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define INF 1000000000
using namespace std;
struct exchangeTo {
int target;
int p;
exchangeTo(int a, int b) : target(a), p(b) {}
};
struct path {
int pre;
int val;
} dp[1005];
map<int, vector<exchangeTo>> tables;
bool inPath(int n, int k) {
while (k != -1) {
if (n == k)
return true;
k = dp[k].pre;
}
return false;
}
int main() {
memset(dp, -1, sizeof(dp));
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y, z;
cin >> x >> y >> z;
tables[x].push_back(exchangeTo(y, z));
}
dp[1].val = 0, dp[1].pre = 0;
bool done = false;
int result = 0;
queue<int> myqueues;
myqueues.push(1);
while (!myqueues.empty()) {
int top = myqueues.front();
myqueues.pop();
if (!tables[top].empty()) {
vector<exchangeTo>::iterator ii;
for (ii = tables[top].begin(); ii != tables[top].end(); ii++) {
if (inPath(ii->target, top)) {
result = INF;
done = true;
break;
}
if (dp[top].val + ii->p > dp[ii->target].val) {
dp[ii->target].val = dp[top].val + ii->p;
dp[ii->target].pre = top;
myqueues.push(ii->target); // 注意这里的更新
}
result = max(result, dp[ii->target].val);
}
if (done)
break;
}
}
cout << result << endl;
return 0;
}最佳路径
如下所示的由正整数数字构成的三角形:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。
注意:路径上的每一步只能从一个数走到下一层上和它最近的下边(正下方)的数或者右边(右下方)的数。
时间限制:1000
内存限制:65536
输入
第一行为三角形高度100>=h>=1,同时也是最底层边的数字的数目。 从第二行开始,每行为三角形相应行的数字,中间用空格分隔。
输出
最佳路径的长度数值。
样例输入
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
样例输出
30
#include <bits/stdc++.h>
using namespace std;
int n, a[1001][1001] = {};
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> a[i][j];
}
}
for (int i = n; i >= 1; i--) {
for (int j = i; j >= 1; j--) {
a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
}
}
cout << a[1][1];
return 0;
}数字构造
火山宝打算造一个 n 位的十进制数字出来。
对于 1 到 n 中的每一个 i,火山宝可以从 xi,1, ..., xi,ki 这 ki 个 0-9 的数字中选择一个作为 ai。
在选择结束后,a1a2...an 形成了一个 n 位的十进制数——这就是火山宝造出来的数。
你需要帮火山宝计算他能造出的数中,有多少个是 3 的倍数。
时间限制:1000
内存限制:65536
输入
第一行输入一个整数 n(1 ≤ n ≤ 18),表示数字的位数。 接下来 n 行,每行第一个整数 ki (1 ≤ ki ≤ 10),表示第 i 中候选的数字数量。接着是 ki 个两两不同的 0-9 范围内的数字 xi,1, ..., xi,ki。 输入保证 0 不是第一位的可选项。
输出
你需要输出一行一个整数,表示火山宝能造出的数字中,3 的倍数的数量。
样例输入
样例输入1:
2 5 5 6 7 8 9 5 0 1 2 3 4
样例输入2:
5 9 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9
样例输出
样例输出1:
9
样例输出2:
30000
提示
样例1能造出来的 3 的倍数有 51, 54,60,63,72,81,84,90, 93。
#include <cstring>
#include <iostream>
using namespace std;
int num[20][10];
int k[20];
int mod[20][3] = {};
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> k[i];
for (int j = 0; j < k[i]; j++) {
cin >> num[i][j];
mod[i][num[i][j] % 3]++;
}
}
long result[3] = {};
for (int i = 0; i < 3; i++)
result[i] = mod[0][i];
for (int i = 1; i < n; i++) {
long temp0 = result[0], temp1 = result[1], temp2 = result[2];
result[0] = temp0 * mod[i][0] + temp1 * mod[i][2] + temp2 * mod[i][1];
result[1] = temp0 * mod[i][1] + temp1 * mod[i][0] + temp2 * mod[i][2];
result[2] = temp0 * mod[i][2] + temp1 * mod[i][1] + temp2 * mod[i][0];
}
cout << result[0] << endl;
return 0;
}奶牛散步
从一个无限大的矩阵的中心点出发,一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法?
输入
一个数字,代表N,N<=1000
输出
输出有多少方案数模12345
样例输入
2
样例输出
7
// 上一步向上走,下一步可以向左、右、上
// 上一步向左走,下一步可以向左、上
// 上一步向右走,下一步可以向右、上
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long lr = 2, up = 1;
int i = 0;
long long tmplr = 0, tmpup = 0;
if (n == 1) {
cout << 3;
} else {
for (i = 2; i <= n; i++) {
tmplr = lr;
tmpup = up;
lr = (tmpup * 2 + tmplr) % 12345;
up = (tmpup + tmplr) % 12345;
}
cout << (up + lr) % 12345;
}
return 0;
}吃奶酪
Jerry准备偷吃Tom的奶酪。所有的奶酪排成了一条直线,每块奶酪都有不同的美味程度。然而,如果有相邻两块奶酪都被Jerry偷吃,Tom就会发现这一点并迅速抓住Jerry。Jerry当然希望在不被Tom发现的条件下吃到的奶酪美味度总和最大。当然,他也可以选择一块奶酪都不吃。请你帮助他规划一下偷吃的方案,告诉他最多能偷吃到多少的美味度吧。
时间限制:1000
内存限制:65536
输入
第一行一个整数T (T<=100),表示测试数据组数。 接下来,每组测试数据包含两行。其中,第一行一个整数n (1 <= n <= 100,000) ,表示奶酪的数量;第二行n个整数,表示这一排直线上奶酪的美味程度,请注意,美味度保证能够被int类型存储,且可能是负数。
输出
对于每组测试数据,输出一个整数,表示Jerry可以吃到的最大美味度总和。请注意,美味度总和可能超过int存储范围
样例输入
2 4 1 2 3 1 5 2 7 9 3 1
样例输出
4 12
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
long long d[100005];
int a[100005];
int main() {
int t;
cin >> t;
while (t--) {
int n;
memset(d, 0, sizeof(d));
memset(a, 0, sizeof(a));
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
d[1] = max(0, a[1]);
d[2] = max(int(d[1]), a[2]);
for (int i = 3; i <= n; i++) {
d[i] = max(d[i - 1], a[i] + d[i - 2]);
}
cout << d[n] << endl;
}
return 0;
}余数相同问题
已知三个正整数 a,b,c。
现有一个大于1的整数x,将其作为除数分别除a,b,c,得到的余数相同。
请问满足上述条件的x的最小值是多少?
数据保证x有解。
输入
一行,三个不大于1000000的正整数a,b,c,两个整数之间用一个空格隔开。
输出
一个整数,即满足条件的x的最小值。
样例输入
300 262 205
样例输出
19
#include <iostream>
using namespace std;
int min(int a, int b, int c) {
int min = a;
if (b < min)
min = b;
if (c < min)
min = c;
return min;
}
int ys(int a, int b, int c) {
int i;
for (i = 2; i <= min(a, b, c); i++) {
int y1 = a % i, y2 = b % i, y3 = c % i;
if (y1 == y2 && y1 == y3 && y2 == y3)
break;
}
return i;
}
int main() {
int a, b, c;
cin >> a >> b >> c;
cout << ys(a, b, c) << endl;
}生成括号
Paul是一名数学专业的同学,在课余选修了C++编程课,现在他能够自己写程序判断判断一个给定的由'('和')'组成的字符串是否是正确匹配的。可是他不满足于此,想反其道而行之,设计一个程序,能够生成所有合法的括号组合,请你帮助他解决这个问题。
时间限制:1000
内存限制:65536
输入
输入只有一行N,代表生成括号的对数(1 ≤ N ≤ 10)。
输出
输出所有可能的并且有效的括号组合,按照字典序进行排列,每个组合占一行。
样例输入
3
样例输出
((())) (()()) (())() ()(()) ()()()
#include <bitset>
#include <ctime>
#include <iostream>
using namespace std;
int N;
bool judge(bitset<20> temp) {
int numL = 0, numR = 0; // numL 表0 左括号数 numR表1 右括号数
for (int i = 2 * N - 1; i >= 0; i--) {
if (temp[i])
numR++;
else
numL++;
if (numL - numR < 0)
return false; // 在任何一个位置所得的前缀中0的个数不少于1的个数。
}
if (numL != numR)
return false; // 有相同个数的0和1,都是N个
return true;
}
int main() {
cin >> N;
int max = 1 << (2 * N - 1); // 2的2*N-1次方
// cout<<max<<endl;
for (int i = 1; i <= max; i++) {
bitset<20> temp;
// 开始枚举每种可能
for (int j = 0; j < 2 * N; j++) {
temp[j] = (i >> j) & 1; // 这里是反着取的 如000111,先取个位的1
}
// 对每种可能进行判断
if (judge(temp)) {
for (int j = 2 * N - 1; j >= 0; j--) {
if (temp[j])
cout << ")"; // 所以这要反过来输出
else
cout << "(";
}
cout << endl;
}
}
return 0;
}课程冲突
小 A 修了 n 门课程, 第 i 门课程是从第 ai 天一直上到第 bi 天。
定义两门课程的冲突程度为 : 有几天是这两门课程都要上的。
例如 a1=1,b1=3,a2=2,b2=4 时, 这两门课的冲突程度为 2。
现在你需要求的是这 n 门课中冲突程度最大的两门课的冲突程度。
时间限制:1000
内存限制:65536
输入
第一行一个正整数 n 表示课程数量。 接下来 n 行,每行两个正整数 ai,bi。 2 ≤ n≤ 1000, 1 ≤ ai ≤ bi ≤ 1000。
输出
输出一个整数表示最大的冲突程度
样例输入
3 1 3 2 4 5 5
样例输出
2
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct project {
int start;
int end;
project(int a, int b) : start(a), end(b) {}
bool operator<(const project A) const {
if (start == A.start)
return end < A.end;
else
return start < A.start;
}
};
int main() {
int n;
cin >> n;
vector<project> alls;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
alls.push_back(project(a, b));
}
sort(alls.begin(), alls.end());
int result = 0;
for (int i = 0; i < n; i++) {
if (alls[i].end - alls[i].start < result) // 剪枝
continue;
for (int j = i + 1; j < n; j++) {
if (alls[j].start > alls[i].end)
break;
int t = min(alls[i].end, alls[j].end) - alls[j].start + 1;
result = max(t, result);
}
}
cout << result << endl;
return 0;
}