1-1 sdut-C最大子列和问题
任务描述:
给定个整数组成的序列{ , , …, },“连续子列”被定义为{ , , …, },其中 。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 },其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序,计算给定整数序列的最大子列和。
本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下:
- 数据1:与样例等价,测试基本正确性;
- 数据2:102个随机整数;
- 数据3:103个随机整数;
- 数据4:104个随机整数;
- 数据5:105个随机整数;
输入格式:
输入第1行给出正整数 ();第2行给出个整数,其间以空格分隔。
输出格式:
在一行中输出最大子列和。如果序列中所有整数皆为负数,则输出0。
输入样例:
6 -2 11 -4 13 -5 -2
输出样例:
20
相关限制:
代码长度限制16KB 时间限制10000ms 内存限制64MB 栈限制8192KB
答案:
#include <bits/stdc++.h> using namespace std; int main() { int now=0,max=0; int k,i; cin>>k; int a[k]; for(i=0;i<k;i++) cin>>a[i]; for(i=0;i<k;i++) { now+=a[i]; if(now>max) max=now; if(now<0) now=0; } cout<<max<<endl; return 0; }
1-2 sdut-C两个有序链表序列的合并
任务描述:
给定2个非降序序列,要求把他们合并成1个非降序序列。假设所有元素个数为N,要求算法的时间复杂度为O(N)。
输入格式:
输入有4行。第1行是一个正整数m,表示第2行有m个整数,这些整数构成一个非降序序列,每个整数之间以空格隔开。第3行是一个正整数n,表示第4行有n个整数,这些整数也构成一个非降序序列,每个整数之间以空格隔开。
输出格式:
把第2行的m个整数和第4行的n个整数合并成一个非降序序列,输出这个整数序列。每个数之间隔1个空格。
输入样例:
6 1 3 6 6 8 9 4 2 4 5 7
输出样例:
1 2 3 4 5 6 6 7 8 9
相关限制:
代码长度限制16KB 时间限制100ms 内存限制64MB 栈限制8192KB
答案:
#include <bits/stdc++.h> using namespace std; int main() { int n,m,i,j,k; cin>>m; int a[m]; for(i=1;i<=m;i++) cin>>a[i]; cin>>n; int b[n]; for(j=1;j<=n;j++) cin>>b[j]; int c[m+n]; i=1;j=1;k=1; while(i<=m&&j<=n) { if(a[i]<b[j]) { c[k++]=a[i++]; } else c[k++]=b[j++]; } while(i<=m) c[k++]=a[i++]; while(j<=n) c[k++]=b[j++]; for(i=1;i<k;i++) cout<<c[i]<<" "; return 0; }
1-3 sdut-C单链表就地逆置
任务描述:
输入多个整数,以-1作为结束标志,顺序建立一个带头结点的单链表,之后对该单链表进行就地逆置(不增加新结点),并输出逆置后的单链表数据。
输入格式:
首先输入一个正整数T,表示测试数据的组数,然后是T组测试数据。每组测试输入多个整数,以-1作为该组测试的结束(-1不处理)。
输出格式:
对于每组测试,输出逆置后的单链表数据(数据之间留一个空格)。
输入样例:
1 1 2 3 4 5 -1
输出样例:
5 4 3 2 1
相关限制:
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案:
#include <bits/stdc++.h> using namespace std; int a[1000005]; int main () { int t,i,x,m; cin>>t; while(t--) { i=0; while(cin>>x) { if(x==-1) break; else { a[i++]=x; m=i; } } for(i=m-1;i>0;i--) cout<<a[i]<<" "; cout<<a[0]<<endl; } }
1-4 sdut-C求链式线性表的倒数第K项
任务描述:
给定一系列正整数,请设计一个尽可能高效的算法,查找倒数第K个位置上的数字。
输入格式:
输入首先给出一个正整数K,随后是若干非负整数,最后以一个负整数表示结尾(该负数不算在序列内,不要处理)。
输出格式:
输出倒数第K个位置上的数据。如果这个位置不存在,输出错误信息NULL
。
输入样例:
在这里给出一组输入。例如:
4 1 2 3 4 5 6 7 8 9 0 -1
输出样例:
7
相关限制:
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案:
#include <bits/stdc++.h> using namespace std; int a[1000005]; int main () { int n,x; cin>>n; int i=0; while(cin>>x) { if(x<0) break; else { a[i++]=x; } } if(i-n>=0) cout<<a[i-n]<<endl; else cout<<"NULL"; }
1-5 sdut-C银行业务队列简单模拟
任务描述:
设某银行有A、B两个业务窗口,且处理业务的速度不一样,其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时,B窗口处理完1个顾客。给定到达银行的顾客序列,请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔,并且当不同窗口同时处理完2个顾客时,A窗口顾客优先输出。
输入格式:
输入为一行正整数,其中第1个数字N(1000)为顾客总数,后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务,为偶数的顾客则去B窗口。数字间以空格分隔。
输出格式:
按业务处理完成的顺序输出顾客的编号。数字间以空格分隔,但最后一个编号后不能有多余的空格。
输入样例:
在这里给出一组输入。例如:
8 2 1 3 9 4 11 13 15
输出样例:
在这里给出相应的输出。例如:
1 3 2 9 11 4 13 15
相关限制:
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案:
#include <bits/stdc++.h> using namespace std; int a[1000005],b[100005],c[100005],N[100005]; int main () { int n,k=0,j=0,i; cin>>n; for(i=0;i<n;i++) { cin>>N[i]; if(N[i]%2!=0) a[j++]=N[i]; else b[k++]=N[i]; } int q=0,p=0,m=0; for(i=0;i<n;i++) { if(p<j) { c[m++]=a[p++]; c[m++]=a[p++]; } if(q<k) { c[m++]=b[q++]; } } for(i=0;i<m-1;i++) cout<<c[i]<<" "; cout<<c[m-1]<<endl; }
1-6 sdut-C行编辑器
任务描述:
一个简单的行编辑程序的功能是:接受用户从终端输入的程序或数据,并存入用户的数据区。由于用户在终端上进行输入时,不能保证不出差错,因此,若在编辑程序中,“每接受一个字符即存入用户数据区”的做法显然不是最恰当的。较好的做法是,设立一个输入缓冲区,用以接受用户输入的一行字符,然后逐行存入用户数据区。允许用户输入出差错,并在发现有误时可以及时更正。例如,当用户发现刚刚键入的一个字符是错的时,可补进一个退格符”#”,以表示前一个字符无效;如果发现当前键入的行内差错较多或难以补救,则可以键入一个退行符”@”,以表示当前行中的字符均无效。如果已经在行首继续输入’#’符号无效。
输入格式:
输入一个多行的字符序列。但行字符总数(包含退格符和退行符)不大于250。
输出格式:
按照上述说明得到的输出。
输入样例:
在这里给出一组输入。例如:
whli##ilr#e(s#*s)
输出样例:
在这里给出相应的输出。例如:
while(*s)
相关限制:
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案:
#include <bits/stdc++.h> using namespace std; string s; int main () { while(getline(cin,s)) { int i,cnt=0; char str[100]; for(i=0;i<s.size();i++) { if(s[i]=='#'&&cnt==0) continue; if(s[i]=='#') cnt--; else if(s[i]=='@') cnt=0; else str[cnt++]=s[i]; } for( i=0;i<cnt;i++) cout<<str[i]; } }