T1一千万零一只斑点狗

解决方案

将a~z看着26进制数，题目是1-26，需要偏移一位到0~25具体一个简单的递归，只需要将n不停%10并÷10，每个字符就是'a'+n%10，最后把他们拼接起来并反转。

T2金字塔

解决方案

先使用Point结构体存储每个点的x坐标、y坐标和高度h‌，对于给定的中心点(cx,cy)和高度h，验证所有点的高度是否符合公式$h - |x-cx| - |y-cy|‌$。

T3走迷宫

解决方案

起点终点任意，枚举所有的可行坐标作为起点和终点，求所有起点和终点的 最短路，取一个最大值。使用二维数组maze[N][N]存储迷宫地图，‌dist[N][N]数组记录每个点到起点的最短距离，初始值为-1‌方向数组dx/dy表示上右下左四个移动方向。从起点(nx,ny)开始广度优先搜索‌使用队列queue<pair<int,int>>实现BFS遍历‌每次扩展四个方向的相邻格子，更新可达点的距离并记录最大值‌.

T4划分问题

问题描述

问题描述 小圆为编程竞赛制作了N道题目。题目编号为1到N，第i道题目的难度用一个整数$di$表示（数值越大，难度越高）。 他通过选择一个整数K，将题目划分为两类，具体如下：

• 难度大于等于K的题目将用于提高组。
• 难度小于K的题目将用于普及组。 有多少个整数K的选择，可以使用于提高组的题目数量和用于普及组的题目数量相同？

约束条件

• $2≤N≤10^5$
• N是一个偶数。
• $1≤di≤10^5$
• 所有输入值均为整数。

解决方案

简单数学问题，要把数组排序后答案为中间两个数的差即为答案。

错误原因

把简单题目复杂化，也没有找到题目中的数学关系,总结为先找到方法或数学关系再下笔，不要着急。

正确代码

#include <bits/stdc++.h>
using namespace std;
int n,d[100001];
int main(){
    //freopen("hf.in","r",stdin);
    //freopen("hf.out","w",stdout);
    cin>>n;
    for(int i=0;i<n;i++) cin>>d[i];
    sort(d,d+n);
    cout<<d[n/2]-d[n/2-1];
    return 0;
}

T5序列查询

问题描述

我们有一个空序列A。给定Q个查询，按顺序处理它们。每个查询是以下三种类型之一：

• 1 x：将x插入A。
• 2 x k：在A中小于等于x的元素中，输出第k大的值。（k不超过5）如果A中小于等于x的元素不足k个，则输出−1。
• 3 x k：在A中大于等于x的元素中，输出第k小的值。（k不超过5）如果A中大于等于x的元素不足k个，则输出−1。

约束条件

• $1≤Q≤2×10^5$
• $1≤x≤10^9×10^9$
• $1≤k≤5$
• 输入中的所有值均为整数。

解决方案

用multiset进行有序序列的维护,分类讨论

整理知识点:

multiset常用操作：

multiset<int> s;
(1)插入一个数x到多重集合中：s.insert(x)
(2)删除多重集合中的所有x：s.erase(x)
(3)删除多重集合中的一个x：s.erase(s.find(x))
(4)s.lower_bound(x) 返回 >= x的第一个元素迭代器
(5)s.upper_bound(x) 返回 > x 的第一个元素迭代器
(6)s.begin()  指向第一个元素的迭代器
(7)s.end()    指向最后一个元素后一位的迭代器

迭代器可以理解为数组下标，但实际上他是一个地址，所以 要取得迭代器对应的值，需要用 * 解除引用。

正确代码

#include <bits/stdc++.h>
using namespace std;
long long opt,q,x,k;
multiset<long long> s;
int main(){
    //freopen("list.in","r",stdin);
    //freopen("list.out","w",stdout);
    cin>>q;
    while(q--){
        cin>>opt;
        if(opt==1){
            cin>>x;
            s.insert(x);
        }else if(opt==2){
            cin>>x>>k;
            auto it=s.upper_bound(x);
            bool f=1;
            for(long long i=1;i<=k;i++){
                if(it == s.begin()){
                    f=0;
                    break;
                }
                it --;
            }
            if(f) cout<<*it<<endl;
            else cout<<-1<<endl;
        }else{
            cin>>x>>k;
            auto it=s.lower_bound(x);
            bool f=1;
            for(long long i=1;i<k;i++){
                if(it==s.end()){
                    f=0;
                    break;
                }
                it++;
            }
            if(f&&it!=s.end()) cout<<*it<<endl;
            else cout<<-1<<endl;
        }
    }
}

注：所有freopen已注释