这场打的时候一点状态都没有 就签了个到就跑了 /吐血
A、Jelly
这就是一个三维bfs的签到题（不信邪的写dfs加剪枝 我还是没有过 最后只能改成bfs
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll const N=110;
ll n,s[N][N][N],dd,v[N][N][N];
struct T
{
ll a,b,c,d;
};
queue<T>q;
string z;
int main()
{
cin>>n;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
cin>>z;
for(int k=0;k<z.length();++k)
{
if(z[k]=='.') s[i][j][k+1]=1;
}
}
}
T t;
t.a=1,t.b=1,t.c=1,t.d=1;q.push(t);
while(!q.empty())
{
T t=q.front();q.pop();
ll i=t.a,j=t.b,k=t.c,d=t.d;
if(i==n&&j==n&&k==n)
{
dd=d;
break;
}
t.d=d+1;
if(s[i][j][k+1]&&k+1<=n&&!v[i][j][k+1]) {v[i][j][k+1]=1;t.c=k+1;q.push(t);t.c=k;}
if(s[i][j][k-1]&&k-1>0&&!v[i][j][k-1]) {v[i][j][k-1]=1;t.c=k-1;q.push(t);t.c=k;}
if(s[i][j+1][k]&&j+1<=n&&!v[i][j+1][k]) {v[i][j+1][k]=1;t.b=j+1;q.push(t);t.b=j;}
if(s[i][j-1][k]&&j-1>0&&!v[i][j-1][k]) {v[i][j-1][k]=1;t.b=j-1;q.push(t);t.b=j;}
if(s[i+1][j][k]&&i+1<=n&&!v[i+1][j][k]) {v[i+1][j][k]=1;t.a=i+1;q.push(t);t.c=i;}
if(s[i-1][j][k]&&i-1>0&&!v[i-1][j][k]) {v[i-1][j][k]=1;t.a=i-1;q.push(t);t.c=i;}
}
if(dd) cout<<dd<<endl;
else cout<<-1<<endl;
return 0;
}B、「木」迷雾森林
一个简单的dp 一个点只能从左边或者下面到达（推出方程）
不用快读还超时了....
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, neg = 1; char op = getchar();
while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
return neg * x;
}
const int maxn = 3050;
int m,n,a[maxn][maxn];
int dp[maxn][maxn];
const int mod = 2333;
signed main() {
m = read(),n = read();
for(int i=1;i<=m;++i)
{
for(int j=1;j<=n;++j) a[i][j] = read();
}
dp[m][1] = 1;
for(int i = m ;i >= 1 ; i--)
{
for(int j = 1; j <= n; j++)
{
if(a[i][j] == 1) continue;
if(i + 1 <= m) dp[i][j] += dp[i + 1][j];
dp[i][j] %= mod;
if(j - 1 >= 1) dp[i][j] += dp[i][j - 1];
dp[i][j] %= mod;
}
}
cout << dp[1][n] % mod << endl;
return 0;
}C、小雨坐地铁
又是不会的图论而且是这场里面最难的 经过对大佬们的题解和ac代码的学习 我整出了这一份我的理解
首先这是一个分层图最短路 每一条路线建一层图 每个车站建一个超级源点
这样题目要求的最少代价变成了超级源点a到超级源点b的最少花费
其他理解写在了代码里
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e6 + 5;
const ll inf = 1e18;
int a[N], b[N];
struct Edge {///前向星
int v, nextz;
ll w;
}edge[N << 1];
int tot, head[N];
struct qnode {
int v;
ll cost;
qnode(int _v = 0, ll _cost = 0): v(_v), cost(_cost) {}
bool operator < (const qnode &s)const {
return cost > s.cost;
}///花费小优先
};
void addedge(int u, int v, ll w) {
edge[tot].v = v;
edge[tot].w = w;
edge[tot].nextz = head[u];
head[u] = tot++;
}
ll dist[N];
bool vis[N];
void Dijkstra(int start)
{///最短路基础
for(int i = 1; i <= 1e6; i++) dist[i] = inf;
priority_queue<qnode> q;
q.push(qnode(start, 0));
dist[start] = 0;
while(!q.empty())
{
qnode tmp = q.top();
q.pop();
int u = tmp.v;
if(vis[u]) continue;///原先这个节点花费更少 跳过
vis[u] = 1;
for(int i = head[u]; ~i; i = edge[i].nextz)
{
ll cost = edge[i].w;
int v = edge[i].v;
if(!vis[v] && dist[v] > dist[u] + cost)
{
dist[v] = dist[u] + cost;
q.push(qnode(v, dist[v]));
} ///如果花的钱更少了就替换上去
}
}
}
int main() {
memset(head, -1, sizeof(head));
int n, m, s, t;
cin >> n >> m >> s >> t;
for(int i = 1; i <= m; i++)
{
int num;
cin >> a[i] >> b[i] >> num;
int x = 0, last = 0;
for(int j = 1; j <= num; j++)
{///一条线建一层图 每个点建一个超级源点
cin >> x;
if(j != 1)
{ ///与同一条线的上一个节点连起来
addedge((i - 1) * n + x, (i - 1) * n + last, b[i]);
addedge((i - 1) * n + last, (i - 1) * n + x, b[i]);
}
addedge((i - 1) * n + x, (m + 1) * n + x, 0);
addedge((m + 1) * n + x, (i - 1) * n + x, a[i]); ///进出超级源点 进不花钱 出花钱
last = x;
}
}
Dijkstra((m + 1) * n + s);///跑dij最短路 从超级源点到超级源点
ll ans=dist[(m + 1) * n + t];
if(ans>=inf) cout << -1 << endl;///是否能够到达
else cout << ans << endl;
return 0;
}D、表达式求值
简单的模拟 建一个栈把要加的数放入 如果判断到是乘法就处理成被加的 然后压入栈
最后把栈中的数全部加起来
#include <bits/stdc++.h>
using namespace std;
stack<int>a;
string s;
int main()
{
ios::sync_with_stdio(false);
cin >> s;
int l=s.length(),ins=0,flag=0;
for (int i=0;i<l;++i)
{
if(s[i] >= '0' && s[i] <= '9' )ins = ins*10 + s[i] - '0';
else
{
ins %= 10000;
if(!flag)a.push(ins);///判断这里是加还是乘
else
{
int temp = a.top();
a.pop();
a.push((temp%10000*ins%10000)%10000);
}
if (s[i] == '*' )flag = 1;
else flag = 0;
ins = 0;
}
}
ins %= 10000;
if(!flag)a.push(ins);
else
{
int temp = a.top();
a.pop();
a.push((temp%10000*ins%10000)%10000);
}
int ans = 0;
while(!a.empty())
{
ans += a.top();
ans %= 10000;
a.pop();
}
cout << ans << endl;
return 0;
}E、Sunscreen
这是一个贪心题 我们将牛以r升序排 防晒霜spf值升序排 首先满足右边界小的牛的需求
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
const int N = 2505;
int c,l;
struct cow {int l, r;}C[N];
struct lu {int p, num;}L[N];
bool cmp1(cow a,cow b){return a.r<b.r;};
bool cmp2(lu a,lu b){return a.p<b.p;};
int main(){
cin >> c >> l;
for(int i = 1; i <= c; i++)cin >> C[i].l >> C[i].r;
for(int i = 1; i <= l; i++)cin >> L[i].p >> L[i].num;
sort(C + 1, C + 1 + c,cmp1);
sort(L + 1, L + 1 + l,cmp2);
int ans = 0;
for(int i = 1; i <= c; i++)///先满足右边界小的牛
{
for(int j = 1; j <= l; j++)
{
if(L[j].p >= C[i].l && L[j].p <= C[i].r && L[j].num)
{
L[j].num--;ans++;break;
}
}
}
cout << ans << endl;
return 0;
}
看到最后的彩蛋 推荐轻音乐：Fall
京公网安备 11010502036488号