前言
牙疼，最近有点上火，两个后槽牙都得补了。再一次羡慕红唇皓齿的人。
第一题
题目： B - Distance Between Tokens (atcoder.jp)
题意：
给一个h行w列的图，图中有两个 o ，问从一个 o 到另一个 o 最少需要多少步。
输入格式
第一行是两个整数h和w。
接下来h行，每行都是w个字符的字符串。
数据范围
2 ≤ H, W ≤ 100
输出格式
输出一个整数。
输入样例：
5 4
-o--
----
----
----
-o--输出样例：
4思路：
- BFS模板题。用队列记录当前走到了哪里，用两个数组分别记录是否走到过该点和走到该点的距离。
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
string s[150];
int st[150][150],d[150][150];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i)
cin >> s[i];
int x, y;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
{
if (s[i][j] == 'o')
x = i, y = j;
}
queue<pair<int, int>>q;
q.push({ x,y });
memset(d, 0x3f, sizeof d);
d[x][y] = 0;
st[x][y] = 1;
int res = 0;
int dx[] = { 0,0,-1,1 }, dy[] = { 1,-1,0,0 };
while (q.size())
{
auto t = q.front();
q.pop();
if (s[t.first][t.second] == 'o'&&d[t.first][t.second]!=0)
{
res = d[t.first][t.second];
break;
}
for (int i = 0; i <= 3; ++i)
{
int xx = t.first + dx[i], yy = t.second + dy[i];
if (xx >= 0 && xx < n && yy >= 0 && yy < m && st[xx][yy] == 0)
{
st[xx][yy] = 1;
q.push({ xx,yy });
d[xx][yy] = min(d[xx][yy],d[t.first][t.second] + 1);
}
}
}
cout << res << endl;
return 0;
}第二题
题目： C - Max - Min Query (atcoder.jp)
题意：
我们有一个空集，对这个集合做n次操作，每次对集合有三种操作，1代表插入一个整数x，2代表删除集合中min(x的数量，c)个x，3代表求出当前集合的最大值和最小值的差。
输入格式
第一行是一个整数n。
接下来有n行，每行都是 1 x ，2 x c 或者 3 的形式。
输出格式
对于每个 3 的询问，输出一个整数。
数据范围
1 ≤ t ≤ 2 × 104
1 ≤ n ≤ 2 × 105
1 ≤ ai ≤ n
输入样例：
8
1 3
1 2
3
1 2
1 7
3
2 2 3
3输出样例：
1
5
4思路：
- 用unordered_map记录当前集合中的数，用两个优先队列分别记录最大值和最小值。
- 在求最大值和最小值之差时，要注意判断集合中是否还有当前这个数。
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstring>
#include<unordered_map>
using namespace std;
unordered_map<int, int>p;
priority_queue<int>k;//最大值
priority_queue<int,vector<int>,greater<int>>g;//最小值
int main()
{
int n;
cin >> n;
while (n--)
{
int t;
cin >> t;
if (t == 3)
{
while (k.size() != 0 && p[k.top()] == 0)k.pop();
while (g.size() != 0 && p[g.top()] == 0)g.pop();
cout << k.top() - g.top() << endl;
}
else if (t == 1)
{
int u;
cin >> u;
p[u]++;
if(k.size()==0||k.top()!=u)k.push(u);
if(g.size()==0||g.top()!=u)g.push(u);
}
else
{
int w, e;
cin >> w >> e;
p[w] -= min(p[w], e);
}
}
return 0;
}第三题
题目： D - FizzBuzz Sum Hard (atcoder.jp)
题意:
给我们三个整数n，a，b，询问1~n中，不是a的倍数，也不是b的倍数的数之和。
输入格式
输入只有三个整数，n，a，b。
输出格式
每个样例如果能找到符合条件的 n/2 对整数，则每行输出一对，共 n/2 行。否则输出 -1 。
数据范围
1 ≤ N, A, B ≤ 109
输入样例：
1000000000 314 159输出样例：
495273003954006262思路：
- 可以先求出1n所有数的和，然后减去1n中所有a的倍数，减去1n中所有b的倍数，最后再加上1n中a和b的最小公倍数的所有倍数就是所求整数。
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstring>
#include<unordered_map>
using namespace std;
#define ll long long
ll gcd(ll a, ll b)
{
if (a == 0)return b;
return gcd(b % a, a);
}
int main()
{
ll n, a, b;
cin >> n >> a >> b;
if (a > b)swap(a, b);
ll sum = 0;
if (n & 1)sum = (1 + n)/2 *n;
else sum = n / 2 * (1 + n);
ll u = n / a;
if (u & 1)sum -= (1 + u) / 2 * u * a;
else sum -= u / 2 * (1 + u) * a;
u = n / b;
if (u & 1)sum -= (1 + u) / 2 * u * b;
else sum -= u / 2 * (1 + u) * b;
b = a*b/gcd(a, b);
if (b <= n)
{
u = n / b;
if (u & 1)sum += (1 + u) / 2 * u * b;
else sum += u / 2 * (1 + u) * b;
}
cout << sum;
return 0;
}
