前言
本人菜鸡，难以言喻。第一题居然写了一个小时，就因为打错了一个符号。我决定自闭。。。o(╥﹏╥)o
题目就不打了，<h3>标题为传送门。
A Jelly
第一题就是简单的bfs
操作操作：
- 三维数组作为地图（mp数组）保存题目信息，建立一个已访问数组（visited数组）保存节点的访问信息，保证每个节点不被重复访问。
- 用队列对地图进行遍历。先将起点进队，然后访问起点可以到达的所有节点（地图外和禁止区域当然就不让访问了）
- 然后依次类推，每次将队首节点拿出来访问，直到访问到终点。
- 因为我们队列保存的是结构体，每个节点自带步数。（步数自然等于访问他的节点+1）所以输出该节点的步数就好了。
代码
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int MAX = 1e2 + 7;
//代码预处理
int walk[6][3] = { {1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1} };//三轴移动
int visited[MAX][MAX][MAX], mp[MAX][MAX][MAX], n;//已访问数组，地图，大小
typedef struct {
int x, y, z, eat;//坐标与吃的数量
} Node;
int judge(Node next);//判断接下来访问的节点是否是合法位置（墙或者不能走的格子）
int dfs();//广度优先遍历
int main() {
js;
cin >> n;
memset(mp, -1, sizeof(mp));
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
char ch; cin >> ch;
if (ch == '.') mp[i][j][k] = 0;
}
//初始化地图数组
cout << dfs() << endl;
return 0;
}
int judge(Node next) {
if (mp[next.x][next.y][next.z]) return 0;//判墙或者不能走的节点
if (visited[next.x][next.y][next.z]) return 0;//判是否走过
return 1;
}
int dfs() {
memset(visited, 0, sizeof(visited));
visited[1][1][1] = 1;
Node top; top.x = 1; top.y = 1; top.z = 1; top.eat = 1;
queue<Node> que; que.push(top);
//队列与访问数组初始化
while (!que.empty()) {
top = que.front(); que.pop();
if (top.x == n && top.y == n && top.z == n) return top.eat;
//抵达终点则有数量返回，否则最后会全部出队返回-1
for (int i = 0; i < 6; i++) {
Node next;
next.x = top.x + walk[i][0];
next.y = top.y + walk[i][1];
next.z = top.z + walk[i][2];
next.eat = top.eat + 1;
//得到下一个节点
if (judge(next)) {
que.push(next);
visited[next.x][next.y][next.z] = 1;
}
//可走则进队
}
}
return -1;
}
B 「木」迷雾森林
这道题一看题型就能发现是dp。（我一开始还看成了是到终点的步数，我是瞎了吗）
- 我们知道，dp的基本操作就是递推！
所以我们只要知道了递推公式就完美了。
- 因为这道题题目也告诉了我们，我们只能往上面和右边走。
- 这么说不就是在告诉我们：当前点的方法数=下面点的方法数+左边节点的方法数。
- 总结出来递推公式就是dp[i][j] = dp[i+1][j] + dp[i][j - 1]。
那么操作就是：
- 先初始化地图数组（mp数组）。
- 将第一行和第一列设置为1作为递推的根（因为单纯按行或按列走只有一种情况）。
同时注意从起点向上和向右遇到了障碍就要停下来，因为我们没办法向下和左走，所以永远不可能到达。 - 然后从离起点最近的地方，一层一层的遍历完整个数组，我们就可以知道每个位置的可能数了。
- 最后把要的节点输出来就好了。
代码
#include <iostream>
using namespace std;
const int MOD = 2333;
const int MAX = 3e3 + 7;
//代码预处理
int mp[MAX][MAX], dp[MAX][MAX];
inline void read(int& res);
int main() {
int n, m; read(n); read(m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
read(mp[i][j]);
//初始化地图
for (int i = n; i >= 1; i--)
if (mp[i][1]) break;
else dp[i][1] = 1;
//第1列初始化
for (int i = 1; i <= m; i++)
if (mp[n][i]) break;
else dp[n][i] = 1;
//第n行初始化
for (int i = n - 1; i >= 1; i--)
for (int j = 2; j <= m; j++)
if (mp[i][j]) dp[i][j] = 0;
else dp[i][j] = (dp[i + 1][j] + dp[i][j - 1]) % MOD;
//可能数=行可能数+列可能数
cout << dp[1][m] << endl;
return 0;
}
inline void read(int& res) {
char c; int flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
C 小雨坐地铁
分层图最短路径问题（现学）+ Dijkstra
个人觉得题目挺难的。。也是第一次写，煎熬的写（看+问）了好几个小时。真的是辛苦细心教我的大佬了。
首先来讲一下分层图最短路径：
- 简单来说就是将图分层：每一层放一组自己要的东西，然后不同组之间额外用一层连接起来（称作超级源点层），根据需要，超级源点可以和其他节点之间无权值。
转载大网上大佬的图片。- 我们从某一点作为起点向外拓展，每次选取最小边进行操作（为了省时间和方便可以用优先队列），并用一个数组（mp数组）保存到达每个节点的最小值。
这两个概念都简单介绍过之后：
- 先初始化我们的数组，这道题根据我刚刚说的，操作都好说，但是建立图形难。（我们以下用n表示地铁站数，用m表示地铁线数）
- 我们可以用一个链式表来模拟一个三维结构（vector<Node> subway）：数组每n个位置为一组，每个位置可以链接节点，然后有i层。加上超级源点层数组长度就是n*(m+1)。
- 根据以上，我们就能知道，第i层的第k个节点就是i * n + k。我们便以此来索引位置。
- 下面就是赋值了，我们只要每一层都将c个数顺序连起来就行了，正反都要连，权值依照输入。（这里要注意地铁换线：进入超级源点层。进地铁花钱，出地铁不花钱）
- 初始化完了我们就再建立一个地图（mp数组）来进行Dijkstra就行了。
- 详情看代码。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MAX = 1e6 + 7;
//代码预处理
struct Node {
ll to, cost;//抵达站的坐标，花费的价格
int operator < (const Node& b) const {
return cost > b.cost;
}//优先队列，花费小优先。
};
vector<Node> subway[MAX];
ll n, m, s, t;//表示车站个数，地铁线数，起点站和终点站
ll mp[MAX];//作为地图，记录每个车站的最短路径
template<class T>inline void read(T& res);//整型快读函数
void dijkstra();//最短路径
int main() {
js;
read(n); read(m); read(s); read(t);
for (ll i = 0; i < m; i++) {
ll a, b, c; read(a); read(b); read(c);
//坐i号线的价格，i号线每坐一站多花的价格，i号线车站个数
ll last = 0;
for (ll j = 0; j < c; j++) {
ll u; read(u);//i号线有u号车站
if (j) {
subway[i * n + u].push_back({ i * n + last, b });
subway[i * n + last].push_back({ i * n + u, b });
}
//与同一条线的上一个节点连起来
subway[i * n + u].push_back({ m * n + u, 0 });
subway[m * n + u].push_back({ i * n + u, a });
//进出超级源点（进要花钱，出不花钱）
last = u;
}
}
dijkstra();
if (mp[m * n + t] == INF) printf("-1\n");
else printf("%lld\n", mp[m * n + t]);
return 0;
}
template<class T>inline void read(T& res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
void dijkstra() {
memset(mp, INF, sizeof(mp));
//fill(mp, mp + MAX, INF);
mp[n * m + s] = 0;
priority_queue<Node> que;
que.push({ n * m + s, mp[n * m + s] });
while (!que.empty()) {
Node top = que.top(); que.pop();
if (top.cost > mp[top.to]) continue;
//如果到该节点花的钱比以前记录的还多，就直接跳过
for (auto it : subway[top.to])
if (mp[it.to] > top.cost + it.cost) {
mp[it.to] = top.cost + it.cost;
que.push({ it.to, mp[it.to] });
}
//如果花的钱更少了就替换上去
}
}
D 表达式求值
栈的基本操作题，就简单说一下思路吧（虽然也没人看）
- 毋庸置疑，存下字符串。
- 按顺序遍历字符串，建立两个栈，遇到数字就读入数字栈，遇到运算符就判断。（我在字符串后面加一个'+'为了防止最后一次计算的特判，加'+'是因为他优先级最低）
- 判断啥呢？：后面的运算符的优先级小于或等于前面运算符的优先级才能进行计算。
而且为了防止前面有因为优先级跳过的运算，所以循环到字符栈中没有字符或优先级较低了为止。最后再把要进栈的字符进栈了。 - 直到最后数字栈的栈顶元素就是答案了。
代码
#include <iostream>
#include <string>
#include <stack>
using namespace std;
#define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int MOD = 1e4;
//代码预处理
int compare(char a, char b);//运算符优先级比较函数,0为a大，1为b大，2为相等
int compute(string s);//表达式计算函数
int main() {
js;
string s; cin >> s;
int ans = compute(s);
cout << ans << endl;
return 0;
}
int compare(char a, char b) {
if (a == '*' && b == '+') return 0;
if (a == '+' && b == '*') return 1;
return 2;
}
int compute(string s) {
s += '+';
int len = s.length();
stack<int> num; stack<char> ch;
for (int i = 0; i < len;)
if (s[i] == '+' || s[i] == '*')
if (ch.empty()) ch.push(s[i++]);
else if (!compare(s[i], ch.top())) ch.push(s[i++]);
else {
while (!ch.empty() && compare(s[i], ch.top())) {
char t = ch.top(); ch.pop();
int u = num.top(); num.pop();
int v = num.top(); num.pop();
if (t == '+') num.push((u + v) % MOD);
else num.push((u * v) % MOD);
}
ch.push(s[i++]);
}
else if ('0' <= s[i] && s[i] <= '9') {
string t;
while ('0' <= s[i] && s[i] <= '9')
t += s[i++];
num.push(stoi(t) % MOD);
}
return num.top();
} 比我快6ms短300b的大佬代码
E Sunscreen
一群非要晒黑又不想晒死的牛的故事
贪心算法求解：
- 我们先用结构体数组储存每头牛牛的信息。map映射乳液。
- 那么最重要的就是贪心思路了：我们首先肯定要对数组进行有序摆放，因为最小值越***液越难找，所以就按最小值倒序摆放。
- 排序后，每头牛的最小值一定有最大值，我们按顺序遍历，取该牛能使用的距离最大值最近的乳液。（原因见点4）
- 原因：因为当前牛的最小值是牛牛里面最大的。所以我们选取其中的最大值，使得具有更小的最小值的牛牛可以使用前面的。
可能你会说（其实就是我），这样最大值比他大的可能没法用了怎么办？没关系，因为如果有更大的他自然能选，如果只能是这瓶，不也就是极限一换一吗，数量还是一样的。
最小值比他小的也是同理，不过就是极限一换一而已。 - 其他基本操作详情看代码
代码
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int MAX = 3e3 + 7;
//代码预处理
typedef struct Node {
int min, max;
int operator < (const Node& b) const {
return min > b.min;
}
} Node;
Node cow[MAX];
map<int, int> mp;
template<class T>inline void read(T& res);//快读函数
int main() {
int C, L; read(C); read(L);
for (int i = 1; i <= C; i++) {
read(cow[i].min); read(cow[i].max);
}
mp[0] = 0;//添加一个不被使用的特例，防止mp为空
for (int i = 1; i <= L; i++) {
int key, value; read(key); read(value);
mp[key] += value;
}
//初始化牛的特征，乳液特征
int cnt = 0;//符合条件的牛计数
sort(cow + 1, cow + 1 + C);//最小值降序
for (int i = 1; i <= C; i++) {
auto t = --mp.upper_bound(cow[i].max);
if (t->first >= cow[i].min) {
cnt++;
t->second--;
if (!t->second)
mp.erase(t->first);
}
}
printf("%d\n", cnt);
return 0;
}
template<class T>inline void read(T& res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
} 
京公网安备 11010502036488号