SDUT-数据结构-第一次机测

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];
  }
}
如果对您有帮助的话,能否支持一下博主?
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇