T1 一千万零一只斑点狗
题意：
有1-10000001只狗，每只狗都有自己的编号，给定一个N，让我们求这个数对应的编号。
思路：
根据这个题意，可以推公式，大概意思是将这个数除以26，取余，然后如果这个新得到的数大于26，继续除以26.
代码：
#include<bits/stdc++.h>
using namespace std;
string d(long long N){
string r;
while(N>0){
N--;
char c='a'+(N%26);
r+=c;
N/=26;
}
reverse(r.begin(),r.end());
return r;
}
int main(){
freopen("dog.in","r",stdin);
freopen("dog.out","w",stdout);
long long N;
cin>>N;
cout<<d(N)<<endl;
return 0;
}
T2 金字塔
题意：
根据这个金字塔的信息，可以求出中心坐标和高度。
思路：
向外每移动一格，海拔减1。已知点N的坐标和海拔高度进行反推求出其他值。若 hi=0，则 H≤∣xi−CX∣+∣yi−CY∣。但是CX,CY范围比较小，可以枚举。检查所有点是否满足条件，如果满足则输出结果。
代码：
#include<bits/stdc++.h>
using namespace std;
struct P{
int x,y,h;
};
int main(){
freopen("tower.in","r",stdin);
freopen("tower.out","w",stdout);
int N;
cin>>N;
vector<P>p(N);
for(int i=0;i<N;i++){
cin>>p[i].x>>p[i].y>>p[i].h;
}
for(int cx=0;cx<=100;cx++){
for(int cy=0;cy<=100;cy++){
int H=-1;
for(const auto & t:p){
if(t.h>0){
int e=t.h+abs(t.x-cx)+abs(t.y-cy);
if(H==-1){
H=e;
}else if(H!=e){
H=-1;
break;
}
}
}
if(H==-1) continue;
bool d=true;
for(const auto & t:p){
int c=max(H-abs(t.x-cx)-abs(t.y-cy),0);
if(c!=t.h) {
d=false;
break;
}
}
if(d){
cout<<cx<<" "<<cy<<" "<<H<<endl;
return 0;
}
}
}
return 0;
}
T3 走迷宫
题意：
给定一个N×M的网格迷宫，其中#表示墙,.表示可通行的路。允许在相邻的上下左右四个方向移动，但不能穿过墙或走出迷宫边界。要求找到所有可能的起点和终点组合中，最短路径的最大步数1。
思路：
迷宫的最短路径问题通常使用广度优先搜索解决，因为BFS能保证找到最短路径,而且DFS时间复杂度太高。本题需要枚举所有可能的起点和终点，计算它们之间的最短路径，并取其中的最大值。对每个可通行的点作为起点，执行计算到其他所有点的最短距离。在每次完成后，更新全局的最大步数。
代码：
#include<bits/stdc++.h>
using namespace std;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
int main(){
freopen("maze.in","r",stdin);
freopen("maze.out","w",stdout);
int N,M;
cin>>N>>M;
vector<string> d(N);
for(int i=0;i<N;i++){
cin>>d[i];
}
int m=0;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(d[i][j]=='.'){
vector<vector<int>> t(N,vector<int>(M,-1));
queue<pair<int,int>>q;
q.push({i,j});
t[i][j]=0;
while(!q.empty()){
auto[x,y]=q.front();
q.pop();
for(int k=0;k<4;k++){
int nx=x+dx[k];
int ny=y+dy[k];
if(nx>=0 && nx<N && ny>=0 && ny<M && d[nx][ny]=='.' && t[nx][ny]==-1){
t[nx][ny]=t[x][y]+1;
q.push({nx,ny});
m=max(m,t[nx][ny]);
}
}
}
}
}
}
cout<<m<<endl;
return 0;
}
T4 划分问题
题意：
给定N道题目（N为偶数），每道题目的难度用整数d表示。需要选择一个整数K，将题目划分为两组：难度大于等于K的题目和普及组两组题目数量相等（各占一半）。求满足条件的整数K的个数。
思路：
划分后两组数量相等，即提高组题目数=普及组题目数=N/2。
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("hf.in","r",stdin);
freopen("hf.out","w",stdout);
int N;
cin>>N;
vector<int>d(N);
for(int i=0;i<N;i++){
cin>>d[i];
}
sort(d.begin(),d.end());
int f=N/2;
int k=d[f-1]+1;
int K=d[f];
if(k>K){
cout<<0<<endl;
}else{
cout<<K-k+1<<endl;
}
return 0;
}
T5 序列查询
题意：
给定一个初始为空的序列A，处理q个查询，每个查询是以下三种类型之一：将元素x插入序列A。在A中小于等于x的元素中，输出第k大的值（若不足k个则输出-1）。在A中大于等于x的元素中，输出第 k小的值（若不足k个则输出-1）。
思路：
由于需要高效处理插入和查询操作，选择平衡二叉搜索树（如multiset）来维护序列A。使用 upper_bound(x) 找到第一个大于x的元素位置。通过迭代器遍历小于等于x的元素，取第k个。使用lower_bound(x) 找到第一个大于等于x的元素位置。正向迭代遍历大于等于x的元素，取第k个。
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("list.in","r",stdin);
freopen("list.out","w",stdout);
multiset<long long>s;
int q;
cin>>q;
while(q--){
long long p,x,k;
cin>>p>>x;
if(p==1){
s.insert(x);
}
else if(p==2){
cin>>k;
auto t=s.upper_bound(x);
bool g=true;
while(k-- && t!=s.begin())t--;
if(k>=0 || t==s.end())g=false;
cout<<(g?*t:-1)<<endl;
}
else{
cin>>k;
auto t=s.lower_bound(x) ;
while(--k && t!=s.end())t++;
if(t==s.end())cout<<-1<<endl;
else cout<<*t<<endl;
}
}
return 0;
}
