2018年58春招编程题

//题意：给定一个串：aabccdddeefgghhggg 任给一个数字n整数，判断长度为n的连续的串并输出出来那个元素和其下标例如：a(1,2) c(4,5) e(9,10)g(12,13)h(14,15)大概就是这么个意思，可能输出稍微有差别但不影响

//大水题可惜当时时间感觉好紧没有思路

/*思路：将原来的串加入队列，每次将队头弹出并判断当前元素是否和队列中的队头元素是否不等，当然每次弹出都记录次数，
若当前元素与队头元素不等且弹出次数等于所给的串的连续个数 n那么输出，从新记录弹出次数，或者当弹出元素不等于剩余队列中的
队头元素时且弹出次数不等于所给的n那么从新记录弹出次数*/

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int main()
{
    int n;
    while(cin >> n){
        string s;
        cin >> s;
        queue <char> q;
        int lens = s.length();
        for(int i = 0; i < lens; i++)
            q.push(s[i]);
        int j = 1;
        int cnt = n;
        char c;
        while(!q.empty()){
            j++;
            c = q.front();
            cnt--;
            q.pop();
            if(c != q.front() && cnt == 0){
                cout << c << "(" << j - n << "," << j-1 << ")" <<endl;
                cnt = n;
            }
            if(c != q.front() && cnt != 0){
                cnt = n;
            }
        }
    }
    return 0;
}

//第二题同样是水题但是也可以用dp思想写，后悔啊为什么当时做题那么慢

/*题意：给你一个数字串，求出连续的串最大的整数和例如：3,5,-7,6,8,9,-10球最大的连续整数和*/

//思路：记录每个状态下的和，将最大值输出即可

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

int a[1000];
int dp[1000];

int main()
{
    int n;
    while(cin >> n){
        memset(dp, 0, sizeof(dp));
        memset(a, 0, sizeof(a));
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        int maxx = dp[0] = a[0];
        for(int i = 1; i < n; i++){
            dp[i] = dp[i-1] + a[i];
            if(dp[i] > a[i]){
                maxx = max(dp[i], maxx);
            } else {
                dp[i] = a[i];
                maxx = max(dp[i], maxx);
            }
        }
        cout << maxx << endl;
    }
    return 0;
}