A.一千万零一只斑点狗
输入N，将a~z看着26进制数，转换为“26”进制输出，这样，这道题就是一道简简单单的进制转换题；
注意：n/26之前，一定一定要n--。
错因：没有n--。
代码：
#include<bits/stdc++.h>
using namespace std;
long long n,ys;
stack<int> a;
int main(){
freopen("dog.in","r",stdin);
freopen("dog.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
while(n){
n--;
ys=n%26;
n/=26;
a.push(ys);
}
while(!a.empty()){
char x=a.top()+97;
a.pop();
cout<<x;
}
return 0;
}
B. 金字塔
当时只读了一遍题目，没有往下思考，而是去思考其他题目，并没写着道题目。后来听了老师的讲解写出。
找到一个hi!=0的xi,yi,hi，使用公式：ch=hi+abs(xi-cx)+abs(yi-cy)，随后枚举Cx和Cy的值，算出ch的值，验证剩下n-1条信息的hi是否成立。使用公式：hi=max(ch-abs(xi-cx)-abs(yi-cy), 0)。
代码：
#include<bits/stdc++.h>
using namespace std;
struct wc{
int x,y,h;
};
int n;
vector<wc>q;
int main(){
freopen("tower.in","r",stdin);
freopen("tower.out","w",stdout);
cin>>n;
for(int i=0;i<n;i++){
int x,y,h;
cin>>x>>y>>h;
q.push_back({x,y,h});
}
for(int cx=0;cx<=100;cx++){
for(int cy=0;cy<=100;cy++){
int HH=-1;
for(const auto t:q){
if(t.h>0){
int hh=t.h+abs(t.x-cx)+abs(t.y-cy);
if(HH==-1) HH=hh;
else if(HH!=hh){
HH=-1;
break;
}
}
}
if(HH==-1) continue;
bool f=1;
for(const auto t:q){
int hi=max(HH-abs(t.x-cx)-abs(t.y-cy),0);
if(hi!=t.h) {
f=0;
break;
}
}
if(f){
cout<<cx<<" "<<cy<<" "<<HH<<endl;
return 0;
}
}
}
return 0;
}
}
C. 走迷宫
鹅鹅鹅，本来有100的，思路想到了，想对了，枚举也对啦，但是我的bfs的初始化q[x][y]=0写错了，写成q[1][1]=0了。呃呃~~
正常迷宫+枚举起点与终点。
bfs的模板题，但是需要加上枚举起点与终点，取最大值输出即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
char a[50][50];
int dist[50][50];
int vis[50][50];
int dx[5]={0,1,0,-1};
int dy[5]={1,0,-1,0};
bool ch(int nx,int ny){
if(nx>0 && ny>0 && nx<n+1 && ny<m+1 && !vis[nx][ny] && a[nx][ny]!='#'){
return 1;
}
return 0;
}
void bfs(int qx,int qy,int zx,int zy){
queue< pair<int,int> > q;
q.push({qx,qy});
vis[qx][qy]=1;
dist[qy][qx]=0;
while(q.size()){
auto t=q.front();
q.pop();
int x=t.first;
int y=t.second;
if (x==zx && y==zy) {
ans=max(ans,dist[x][y]);
return;
}
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if (ch(nx,ny)){
vis[nx][ny]=1;
q.push({nx,ny});
dist[nx][ny]=dist[x][y] + 1;
}
}
}
}
int main(){
freopen("maze.in","r",stdin);
freopen("maze.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]!='#'){
for(int k=1;k<=n;k++){
for(int e=1;e<=m;e++){
if(a[i][j]!='#'){
memset(dist, 0, sizeof dist);
memset(vis, 0, sizeof vis);
bfs(i,j,k,e);
}
}
}
}
}
}
cout<<ans;
return 0;
}
}
D. 划分问题
没有想到正解，想到了暴力解，未想暴力的时间复杂度，导致超时。
一道十分简单的数学题，只需sort排序，在多组样例的观察中发现答案等于两个中间值相减的绝对值，输出两个中间值相减的绝对值即可。
代码：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=2e5;
ll n,cnt;
ll d[N];
int main(){
freopen("hf.in","r",stdin);
freopen("hf.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>d[i];
}
sort(d+1,d+n+1);
cnt=abs(d[n/2]-d[n/2+1]);
cout<<cnt;
return 0;
}
}
E. 序列查询
鹅鹅鹅，又是一道会的题，还是没做对。当时想到了set，也想到了 multiset set,但是！我忘记multiset怎么写了。
使用multiset进行有序序列进行维护，这题便十分简单。
注意:s.lower_bound(x)与s.upper_bound(x)返回的是s的迭代器，并不是下标，输出需要用*解除引用，还有multiset set是不能用下标访问的，必须用迭代器访问。
代码：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=3e5;
multiset<ll> a;
ll Q;
int main(){
freopen("list.in","r",stdin);
freopen("list.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>Q;
while(Q--){
ll s;
ll x=0,k=0,cnt=0;
cin>>s>>x;
if(s==1) a.insert(x);
if(s==2){
cin>>k;
auto it=a.upper_bound(x);
bool f=1;
for(int i=1;i<=k;i++){
if(it==a.begin()){
f=0;
break;
}
it--;
}
if(f) cout<<*it<<endl;
else cout<<-1<<endl;
}
if(s==3){
cin>>k;
auto it=a.lower_bound(x);
while(--k && it!=a.end()) it++;
if(it==a.end()) cout<<-1<<endl;
else cout<<*it<<endl;
}
}
return 0;
}
}
