A、Jelly
给定三维地图，并且给出不能走的位置）星号，问从 到
的最短路径是多长。
挺裸的 题目，这里提醒一下走图最好别用DFS会爆内存死的很惨。
规定移动方向，判断是否越界，在判断这个点是否走过，在判断这个点是不是不能走的位置，如果都不是，就把这个点进队，位移长度是前一个走法加一，一直到 ，因为是
，第一次到终点就是最短路了。直接
出循环。
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43532270
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
struct Node {
int x, y, z, s;
};
queue<Node> que;
char mp[N][N][N];
bool vis[N][N][N];
int dx[] = { 1,-1,0,0,0,0 };
int dy[] = { 0,0,1,-1,0,0 };
int dz[] = { 0,0,0,0,1,-1 };
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k)
cin >> mp[i][j][k];
if (mp[n][n][n] == '*') puts("-1");
else {
bool flag = false;
queue<Node> que;
que.push(Node{ 1,1,1,1 });
vis[1][1][1] = true;
while (!que.empty()) {
Node temp = que.front();
que.pop();
for (int i = 0; i < 6; ++i) {
int xx = temp.x + dx[i], yy = temp.y + dy[i], zz = temp.z + dz[i];
if (xx<1 || yy<1 || zz<1 || xx>n || yy>n || zz>n || mp[xx][yy][zz] == '*' || vis[xx][yy][zz])
continue;
que.push(Node{ xx,yy,zz,temp.s + 1 });
vis[xx][yy][zz] = true;
if (xx == n && yy == n && zz == n) {
printf("%d\n", temp.s + 1);
flag = true;
break;
}
}
}
if (!flag) puts("-1");
}
return 0;
}
B、「木」迷雾森林
又是一个走图题，不过这次问的是路径数，不是最短路径，我们从（n,1）走到（1，m），只能向上和向右，很浅显的一个动态规划题目。我们使用 表示出发点走到
的方法数。从出发点开始看起，沿着出发点，一路向上只有一种走法，一路向右也只有一种走法，所以，如果这个地方可以走，那么就把这个地方的方法数规定成1。那么其他位置，要么是从
过来，要么是从
过来，把两种方案数累加就是
的方案数。
所以我们得到状态转移方程
1、第n行中不是1的点，dp[n][j]=1;
2、第1列中不是1的点，dp[i][1]=1;
3、其余位置不是1的点，dp[i][j]=dp[i-1][j]+dp[i][j-1];
4、剩下1的点，dp[i][j]=0;
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43532258
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
const int N = 3001;
const int MOD = 2333;
int mp[N][N];
int dp[N][N];
int main() {
int n = read(), m = read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
mp[i][j] = read();
for (int i = n; i >= 1; --i)
if (!mp[i][1]) dp[i][1] = 1;
else break;
for (int i = 1; i <= m; ++i)
if (!mp[n][i]) dp[n][i] = 1;
else break;
for (int i = n - 1; i >= 1; --i)
for (int j = 2; j <= m; ++j) {
if (mp[i][j]) {
dp[i][j] = 0;
continue;
}
else dp[i][j] = (dp[i + 1][j] + dp[i][j - 1]) % MOD;
}
printf("%d\n", dp[1][m]);
return 0;
} C、小雨坐地铁
分层建图，求单源最短路，不带负权边。
如果单看最短路，不带负权边，很容易想到迪杰斯特拉算法，那么还有一个主要问题就是这个图怎么建立了。
我们知道对于一条地铁线，存在最大N个结点，如果不够也没关系，我们对这一条地铁线上的点进行建边，假设第一条地铁线在第一层，花费为地铁一站的花费，那么第二条地铁线在第二层，这层地铁线可能也用到了第一层某个站点，我们就要对应在M+1层开一个超级源点，从站点去超级源点假设花费为0，那么从超级源点去往某一条地铁线中的点就是转线或者上地铁了，花费记作上地铁的花费。
那么我们的迪杰斯特拉算法就变成了，从超级源点中的起点，去往超级源点中的终点。存在的最短路，直接求解即可，判断是否小于等于初始化的INF，直接输出答案就OK了。
vector相比于前向星码量小，适合我这种懒人，卡vector的 坑爹 良心出题人想让我们多用用更好的方案
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43533955
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
const int N = 5e5+3e3; //节点数
const int M = 5e5 + 7; //路径数
const ll INF = 1e18;
ll d1[N];//d1正向图
struct Node {
int v;
ll cost;
bool operator < (Node b)const {
return cost > b.cost;
}
};
vector<Node> e[N];
int n, m, st, ed;
void dijkstra(int s, ll d[]) {
priority_queue<Node> pq;
fill(d, d + N, INF);
d[m * n + s] = 0;
pq.push(Node{ m * n + s,0 });
while (!pq.empty()) {
Node x = pq.top();
pq.pop();
if (d[x.v] < x.cost) continue; //原先这个节点花费更少 跳过
for (auto it : e[x.v]) {
if (d[it.v] > x.cost + it.cost) {
d[it.v] = x.cost + it.cost;
pq.push(Node{ it.v,d[it.v] });
}
}
}
}
int main() {
n = read(), m = read(); st = read(), ed = read();
for (int i = 0; i < m; ++i) {
int a = read(), b = read(), c = read(), x = read();
e[i * n + x].push_back(Node{ m * n + x, 0 });
e[m * n + x].push_back(Node{ i * n + x, a });
while (--c) {
int y = read();
e[i * n + x].push_back(Node{ i * n + y, b });
e[i * n + y].push_back(Node{ i * n + x, b });
e[i * n + y].push_back(Node{ m * n + y, 0 });
e[m * n + y].push_back(Node{ i * n + y, a });
x = y;
}
}
dijkstra(st, d1);
if (d1[m * n + ed] == INF) puts("-1");
else printf("%lld\n", d1[m * n + ed]);
return 0;
} D、表达式求值
挺简单的模拟题，我的做法是开一个加法栈，把最终需要加的元素放在里面，一个个对字符串处理，把第一个数字直接放进加法栈，其余位置如果是乘号，取出加法栈的栈顶，与乘号后面的元素进行乘法，再进栈。如果是加号，直接读到后面一个运算符号的时候把读到的数放进栈。最后通过把栈中元素全部累加就可以得出最终答案。
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43532725
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
stack<int> st;
string s;
cin >> s;
int len = s.length(), res = 0, m = 0;
while (!st.empty())
st.pop();
for (int i = 0; i < len; ++i) {
if (s[i] >= '0' && s[i] <= '9')
res = res * 10 + s[i] - '0';
else {
res = res % 10000;
if (!m || m == 1) {
st.push(res);
}
else {
int temp = st.top();
st.pop();
st.push((temp % 10000 * res % 10000) % 10000);
}
if (s[i] == '*')
m = 2;
else
m = 1;
res = 0;
}
}
res %= 10000;
if (!m || m == 1) {
st.push(res);
}
else {
int temp = st.top();
st.pop();
st.push((temp % 10000 * res % 10000) % 10000);
}
int ans = 0;
while (!st.empty()) {
ans += st.top();
ans %= 10000;
st.pop();
}
cout << ans << endl;
return 0;
} Python作弊代码，调用eval（）函数，注意调整一下递归深度Py写起来就是爽。
import sys sys.setrecursionlimit(150000)# 调整递归深度，默认900多，表达式运算符过多，需要手动调一下，不然80分 print(eval(input())%10000)
E、Sunscreen
英文题面，简单说下题面意思，给定N头牛M种防晒霜，下面给出每头牛的最低值和最高值，再给出防晒霜的能力值和数量，我们给牛用了防晒霜，牛的能力值就变成防晒霜的能力值，我们要让牛位于它最大值和最小值中间，这头牛就会高兴，问最大可以让多少头牛高兴。
我们如果把全部的牛，按照最小值降序排下序，再把防晒霜按能力值升序排个序。
一个贪心思路，如果当前的牛，找到的最接近最大值要求的防晒霜，不能用来契合自己的最小值，那么后面最小值比你小的牛说不定可以。如果当前牛找不到最契合最大值的防晒霜，那么这头牛也不能高兴了。那么最小值比你小的牛，说不定最大值比你大，指不定可以找到防晒霜。综合来看，最小值比你小的牛，比你更容易找到可行的防晒霜，所以优先处理难处理的最小值大的牛，可以保证局部最优，最终结果就是整体达到最优解。
这里我再说一个错误的贪心思路，如果我们按照最小值升序排序，防晒霜也按照能力值升序排序，从最小值最小开始找第一个符合最小值要求的防晒霜，如果这头牛使用了这个防晒霜，后面的牛最大值又比你小，说不定就不能找到合适的防晒霜使用。所以不一定要使用最接近最小值的防晒霜。
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43536253
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
const int N = 2505;
struct Node {
int mini, maxi;
bool operator < (const Node b)const {
return mini < b.mini;
}
}a[N];
map<int, int> mp;
int main() {
int n = read(), m = read();
for (int i = 1; i <= n; ++i) {
a[i].mini = read();
a[i].maxi = read();
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= m; ++i) {
int spf = read(), cnt = read();
mp[spf] += cnt;
}
int ans = 0;
mp[0] = n; //哨兵保证没有防晒霜不会出异常
for (int i = n; i; --i) {
auto it = mp.upper_bound(a[i].maxi);
--it;
if (it->first >= a[i].mini) {
++ans;
it->second -= 1;
if (it->second == 0)
mp.erase(it);
}
}
printf("%d\n", ans);
return 0;
} 
京公网安备 11010502036488号