CSDN周赛第一期题解

一、题目名称:小艺的英文名

时间限制:1000ms内存限制:256M

题目描述

小艺酱想给自己起—个英文名字。小艺酱想要装的自己学识渊博。所以她想要自己英文名字必须满足:

1.只有字母表中前k个小写字母。

2必须是回文串。

3.前k个小写字母每个字母至少出现—次。

小艺酱已经自己完成了部分空余的字母部分用’?’代替。

请你帮她完成她的英文名字。

输入描述:

第一行输入一个整数k。(1第二行输入小艺酱的英文名字name。(1

输出描述:

如果小艺的名字不存在输出“QAQ"，如果存在多组解,输出字典序最小的一个解。

示例

输入

2

a??a

输出

abba

 字符串处理，给一个不完整的字符串，要求用前k个字母补满使之成为字典序最小的回文串。

既然要回文串，且字典序最小，容易想到从字符串中间向两边，字母由大到小，对称进行填充，这样可以保证结果为字典序最小的回文串。

所以思路为：

用一个map或数组used[i]，来存第i个字母是否使用过

1. 从中间字符开始，同时检查对称的两个字母，会出现三种情况：

        （1）两个都是字母，如果相同则标记为used后继续，若不相同则不满足条件，输出“QAQ”

        （2）一个字母一个"?"，那"?"就用字母表示即可，标记used后继续

        （3）两个“?”，那么我们从第k个字母往a遍历，找到第一个used[i]为false的，替换到两个"?"，标记为used后继续；若所有字母都用过了，用“a”填充即可，这样保证字典序最小

这样处理完整个字符串后，检查used数组是否还有没用过的，如果有说明字母没用完，输出“QAQ”返回，如果都用过了，则输出处理后的字符串。

#include 
using namespace std;

int main()
{
    int k;
    string name;
    cin>>k;
    cin>>name;
    int length = name.length();
    bool letter[30] = {false};
    for(int i = 0; i < length; i++)
    {
        letter[name[i] - 'a'] = true;
    }
    for(int i = (length+1) / 2 - 1; i >= 0; i--)
    {
        if(name[i] != '?' && name[length-i-1] != '?')
        {
            if(name[i] != name[length-i-1])
            {
                cout<<"QAQ"<= 0; j--)
            {
                if(letter[j] == false)
                {
                    name[i] = j + 'a';
                    name[length-i-1] = j + 'a';
                    letter[j] = true;
                    assign = true;
                    break;
                }
            }
            if(!assign)
            {
                name[i] = 'a';
                name[length-i-1] = 'a';
            }
        }
    }
    for(int i = 0; i < length; i++)
    {
        if(name[i] == '?')
        {
            cout<<"QAQ"< 
 
二、题目名称:分层遍历二叉树
 
时间限制:1000ms 内存限制:256M
 
题目描述
 
给定一棵二叉树,节点定义如下:
 
structNode{
 Node "pLeft:
 
Node "pRight:
 
int data;
 
};
 
要求按分层遍历该二叉树,即从上到下按层次访问该二叉树(每一层将单独输出—行),每一层要求访问的顺序为从左到右，并将节点依次编号。下面是一个例子:
 
输入描述:
 
输入—行字符串。1(2)表示2是1的子树。(1<=strlen(str)< =1000)
 
输出描述:
 
输出二叉树的层次。每层占—行。
 
示例
 
输入
 
 
 
1(2(4,5(7,8)),3(6))
 
 
输出
 
 
 
1
 
 
2 3
 
 
4 5 6
 
 
7 8
 
 
 看起来像树，实际也是字符串处理。
 
由于输入格式是用()表示子树，所以每多一层括号相当于树的深度+1，做判断即可。
 
输入范围最多为1000，则树深度不超过1000，用一个数组string tree[1010]来存每层的节点数字，用count来记录当前深度，tmpstr保存当前节点内容
 
count=0; tmpstr=""; 遍历输入字符串s，若s[i]
 
        （1）是数字，则tmpstr+=s[i]
 
        （2）是"("，
 
                （a）若tree[count]为空，则tree[count]+=tmpstr; count++; tmpstr="";
 
                （b）不为空，则tree[count]+=" " + tmpstr; count++; tmpstr="";
 
        （3）是")"，tree[count]+=" " + tmpstr; count--; tmpstr="";
 
        （4）是","，
 
                （a）若tmpstr不为空，说明前面是数字，tree[count]+=" " + tmpstr; tmpstr="";
 
                （b）若tmpstr为空，说明前面是“)”，continue
 
最后遍历tree，按层输出所有不为空的就可以了。
 
#include 
#include
using namespace std;

int main()
{
    string s;
    cin>>s;
    int length = s.length();
    string result[1100] = {""};
    string tmp = "";
    int count = 0;
    for(int i=0; i 
 
三、题目名称:查找整数
 
时问限制:1000ms 内存限制:256M
 
题目描述
 
给定—个非降序的整数数组,数组中包含重复数字(重复数字很多),给定任意整数,对数组进行二分查找，返回数组正确的位置,始出函数实现。
 
a.连续相同的数字,返回最后一个匹配的位置
 
b.如果数字不存在返回-1。(测试用例仅做参考,我们会根据代码质量进行评分)
 
输入描述:
 
第一行给定数组长度n,目标值tar。(1第二行给出n个整数a.(1
 
输出描述:
 
按题目描述输出。
 
示例
 
输入
 
 
 
7 4
 
 
1 2 2 3 4 4 10
 
 
输出
 
 
 
5
 
 
 二分查找，找到最后一个值为tar的元素位置，二分基础上做个变形即可，在判断mid == tar的时候，不要立刻return mid，增加判断
 
 
 
if(mid == len-1) return mid;
 
 
if(mid < len-1 && a[mid+1] != tar) return mid;
 
 
low = mid + 1;
 
 
这样保证找到的为最后一个值为tar的元素下标。
 
#include 
using namespace std;

int main()
{
    int n;
    int tar;
    int a[10100];
    cin>>n>>tar;
    for(int i=0; i>a[i];
    }
    int low = 0;
    int high = n-1;
    while(low <= high)
    {
        int mid = low + (high - low)/2;
        if(tar < a[mid])
        {
            high = mid - 1;
        }
        else if(tar > a[mid])
        {
            low = mid + 1;
        }
        else
        {
            if(mid == n - 1)
            {
                cout<