2021年3月30 天梯赛训练部分试题

7-8 取取取数 (20 分)

这天，Keven突然想和zwg玩一个游戏，游戏规则如下，有N个数字排成一列（保证N为偶数），Keven和zwg每次可以从数列的最左边或者最右边取一个数字，直到所有数字取完，最后谁的数字和最大谁就获胜。Keven先手。

输入格式:

输入在一行中给出一个正整数N（保证N为正偶数并且N<1000）。第二行给出N个绝对值小于1e10的正整数

输出格式:

如果Keven赢了或者平局就输出Keven tql!，如果Keven输了就输出zwg tql!。

输入样例:

在这里给出一组输入。例如：

2
5 5

输出样例:

在这里给出相应的输出。例如：

Keven tql!

思路：先手总是挑最大的数，或露出最小的数给对手

例如：5 6 3 3 6 5

第一轮：先手：5 ，后手取 6（后手可取5和6 ，这里假设取6）

第二轮：先手：3 ，后手取5

第三轮：先手取6 ，后手取3 （又一样了）

怎么取都是先手赢或平局

#include<bits/stdc++.h>
using namespace std;
int main(){
    
    cout<<"Keven tql!"<<endl;
    return 0;
}

有人问我，为啥没有输入，直接输出，OJ系统黑盒测试，只要结果

7-9 小江的密码 (15 分)

小江是一名哔哩哔哩网站控，因此他注册了无数的账号，但是账号的名字并不一定不相同。近期，他想知道某一个账号的名字。因为他已经改名字改到了吐血，他将会给你他的改名字的记录，希望你可以帮他查找出某一个账号现在的名字。

输入格式:

第一行一个整数n，代表修改信息的条数。（1<=n<=20000）

第二行到第n + 1行，每行两字符串a、b，a为名字，b为账号 ( 1 <= |a| ,|b|<= 20 , |s| 代表字符串s 的长度的意思 )

接下来一行一个数字m，为查询次数。（1<=m<=40000）

接下来m行，每行一个账号数据。

注：账号为一串数字组成，名字由数字，字母组成。

输出格式:

m行数据，代表每一个查询。输出格式："caseA:B",。A为序号，从0开始。

当答案存在时，b为答案，查询为空时，b为："no ID!"（无引号）

输入样例:

输出样例:

case0:jdb
case1:no ID!

思路：没什么思路吧，直接上map

#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n ;
    cin>>n;
    map<string,string> m;
    string name ,id;
    while(n--){
        cin>>name>>id;
        m[id] = name ;
    }    
    
    cin>>n;
    for(int i = 0 ; i < n ; i++){
        map<string,string>::iterator it;
        cin>>id;
        it = m.find(id);
        if(it != m.end()){
            cout<<"case"<<i<<":"<<m[id]<<endl;
        }
        else {
            cout<<"case"<<i<<":no ID!"<<endl;
        }
    }
    return 0;
}

7-10 打败迪奥 (25 分)

恶人的救世主迪奥又复活了，无敌的承太郎开始召集替身使者们，组队打败邪恶的迪奥，现在有n(1<=n<=2e5)个替身使者，他们每个人的能力是qi（1<=q[i]<=1e9),为了打败迪奥，承太郎需要选择能相差绝对值不超过5的团队，这样才能更好的协同合作，在由无敌的白金之星带领这个团队获得胜利。你能帮承太郎选择出最多人手的团队吗？（学出团队中任意两个人的能力值相差不超过5）

输入格式:

t组测试样例，每个测试样例第一行为一个n，下一行为n个数。

输出格式:

对于每个测试样例输出最大的团队人数，每个答案占一行。

输入样例:

在这里给出一组输入。例如：

3
6
1 2 3 4 5 6
7
2 2 2 2 2 2 2
5
1 10 20 30 40

输出样例:

在这里给出相应的输出。例如：

6
7
1

思路：这个是线性DP入门吧，我用了一个双指针暴力过了，本想写O(nlogn)的复杂度的，但是实际测试的时候好像退化成O(n^2)了，

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0); 
    int a ;
    cin>>a;
    while(a--){
        int n ;
        vector<int> vec;
        cin>>n;
        int temp;
        for(int i = 0 ; i < n ; i ++){
            cin>>temp;
            vec.push_back(temp);
        } 
        sort(vec.begin() , vec.end() ) ; // 要排序
        int p = 0 ; 
        int mark = vec[0];
        int sum = 0 ;
        int Max = -111;
        for(int i = 0; i < n ; i++){
            while(vec[i] - mark > 5){ // 控制能力差值 ， 超出范围了，就把前面的踢掉
                p++;
                sum--;
                mark = vec[p];
            }
            sum++;
            Max = max(Max , sum);
        }
        cout<<Max<<endl;
    }
    
    return 0;
}

7-11 Keven裂了 (20 分)

众所周知，

然后大家开始了愉快的做题之旅。

已知有

输入格式:

第一行是空格分隔的两个整数 $, ，表示有$

第二行有

输出格式:

输出一行一个整数表示Keven能做出的做多的题目数量

输入样例:

在这里给出一组输入。例如：

5 2
2 3 0 1 1

输出样例:

在这里给出相应的输出。例如：

思路： 简单贪心，排序一下就行了，刚开始还犹豫了是不是背包

#include<bits/stdc++.h>
using namespace std ;

int main(){
    int n , m ;
    cin>>n>>m ;
    vector<int> vec;
    int temp ;
    for(int i = 0 ; i < n ; i++){
        cin>>temp;
        vec.push_back(temp);
    }
    sort(vec.begin() , vec.end()) ;
    int sum = 0 ; 
    for(int i = 0 ; i < n ; i++){
        sum += vec[i];
        if(sum > m){
            cout<<i<<endl;
            return 0;
        }
        else if(sum == m){
            cout<<i+1<<endl;
            return 0;
        }
    }
    cout<<n<<endl;
    
    return 0 ;
}