T1.一千万零一只斑点狗
思路：
将看成进制数，但题目是，需要偏移一位，这样，这道题就是一道简简单单的进制转换题。 $\bcancel{他明明是1000000000000001只狗，标题上却是10000001只狗，这对么?}$
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string ans;
ll n;
char a;
int main ()
{
freopen("dog.in", "r", stdin);
freopen("dog.out", "w", stdout);
cin >> n;
while (n)
{
a = 'a';
int cnt = (n - 1) % 26; // 移位
a += cnt;
ans = a + ans; // 连接
n = (n - 1) / 26;
}
cout << ans;
return 0;
}
T2.金字塔
思路：
找到一个的，代入题目公式得： 枚举和的值，算出的值，用的值验证剩下条信息的是否成立，使用公式。
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll x[110], y[110], h[110], n;
int main ()
{
freopen("tower.in", "r", stdin);
freopen("tower.out", "w", stdout);
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> x[i] >> y[i] >> h[i];
if (h[i] > 0)
{
swap(h[1], h[i]);
swap(x[1], x[i]);
swap(y[1], y[i]);
}
}
for (int xn = 0; xn <= 100; xn++)
{
for (int yn = 0; yn <= 100; yn++)
{
ll hn, t = 0;
hn = h[1] + abs(x[1] - xn) + abs(y[1] - yn);
for (int i = 2; i <= n; i++)
{
if (!(hn - abs(x[i] - xn) - abs(y[i] - yn) >=0 && hn - abs(x[i] - xn) - abs(y[i] - yn) == h[i]))
{
t = 1;
break;
}
}
if (t == 0)
{
cout << xn << " " << yn << " " << hn;
return 0;
}
}
}
return 0;
}
T3.走迷宫
思路：
此题其实就是bfs的模板题，只不过多了一个枚举起点和终点，再取最大值输出即可。
代码：
#include <bits/stdc++.h>
using namespace std;
int n, m, ans;
char a[50][50];
int cnt[50][50], v[50][50], dx[5]={0, 1, 0, -1}, dy[5]={1, 0, -1, 0};
bool ch (int nx, int ny)
{
if(nx > 0 && ny > 0 && nx < n + 1 && ny < m + 1 && !v[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});
v[qx][qy] = 1;
cnt[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, cnt[x][y]);
return;
}
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (ch(nx,ny))
{
v[nx][ny] = 1;
q.push({nx, ny});
cnt[nx][ny] = cnt[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(cnt, 0, sizeof cnt);
memset(v, 0, sizeof v);
bfs(i, j, k, e);
}
}
}
}
}
}
cout << ans;
return 0;
}
T4.划分问题
思路：
一道十分简单的数学题，只需排序，在多组样例的观察中发现答案等于两个中间值相减的绝对值，输出两个中间值相减的绝对值即可。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], k, x, y;
int main ()
{
freopen("hf.in", "r", stdin);
freopen("hf.out", "w", stdout);
cin >> n;
k = n / 2;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
sort(a + 1, a + n + 1);
cout << a[k + 1] - a[k];
return 0;
}
T5.序列查询
思路：
用multiset进行有序序列进行维护
注意：a.lower_bound(x)与a.upper_bound(x)返回的是a的迭代器，并不是下标，输出需要用*解除引用，还有multiset是不能用下标访问的，必须用迭代器访问。
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
multiset<ll> a;
int q;
int main ()
{
freopen("list.in", "r", stdin);
freopen("list.out", "w", stdout);
cin >> q;
while (q--)
{
int n;
cin >> n;
if (n == 1)
{
ll x;
cin >> x;
a.insert(x);
}
else if (n == 2)
{
ll x, k;
cin >> x >> k;
auto ans = a.upper_bound(x);
bool f = 1;
while (k-- && ans != a.begin()) ans--;
if (k >= 0 || ans == a.end()) f = 0;
if (f) cout << *ans << "\n";
else cout << "-1\n";
}
else
{
ll x, k;
cin >> x >> k;
auto ans = a.lower_bound(x);
bool f = 1;
k--;
while (k-- && ans != a.end()) ans++;
if (k >= 0 || ans == a.end()) f = 0;
if (f) cout << *ans << "\n";
else cout << "-1\n";
}
}
return 0;
}
$$\red{\rm{8472690697868}}$$
$$\red{\rm{THE~~END}}$$
