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];
}
}
