A
正常的bfs搜一下即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; char mp[105][105][105]; bool vis[105][105][105]; struct node{ int x,y,z; int num; }; int n; bool check(int x,int y,int z){ if(x>n || x<1 || y>n || y<1 || z>n || z<1 || vis[x][y][z]==1 ||mp[x][y][z]=='*' ) return 1; return 0; } int to[][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}}; int main() { cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> mp[i][j] + 1; } } queue<node> q; q.push({1,1,1,1}); vis[1][1][1]=1; while(!q.empty()){ node now=q.front(); q.pop(); if(now.x==n &&now.y==n&&now.z==n){ cout<<now.num; return 0; } for(int i=0;i<6;i++){ node next=now; next.x+=to[i][0]; next.y+=to[i][1]; next.z+=to[i][2]; if(check(next.x,next.y,next.z)) continue; next.num+=1; //cout<<next.x<<" "<<next.y<<" "<<next.z<<" "<<next.num<<endl; vis[next.x][next.y][next.z]=1; q.push(next); } } cout<<-1; return 0; }
B
简单的dp入门,注意起点是左下角不是左上角,a[i][j]=0,才进行转移
#include <bits/stdc++.h> using namespace std; typedef long long ll; int dp[3005][3005]; int a[3005][3005]; const int mod=2333; 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; } int main() { int n,m;read(n),read(m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) read(a[i][j]); } dp[n][1]=1; for(int i=n;i;i--){ for(int j=1;j<=m;j++){ if(a[i][j]==0){ dp[i][j]=(dp[i][j]+dp[i+1][j]+dp[i][j-1])%mod; } } } cout<<dp[1][m]; return 0; }
C
最短路分层图。
每一条路线都是一层,对于每条路线重复的点,暴力的话我们考虑m^2枚举每条路线,O(n)枚举点建边
这样的复杂度显然是不允许的,所以考虑建虚点。
虚点什么意思呢,顾名思义,并不是实际存在的点,而是人为创建的不存在的点,我们考虑建立一层虚点,把每条航线的每个点都连到虚点来,连到虚点的路径权值为0,把虚点到每条路线的每个点的路径权值为a,也就是乘坐的价钱。其实可以理解为在同一站点换乘另一路线,先到虚点这一层,这一层就是车站。这样建图复杂度只需要O(nm)
然后跑一次最短路。注意起点和终点位置应该在虚点的一层。
#include<bits/stdc++.h> using namespace std; typedef long long ll; int n, m,s,t; struct dijkstra { struct node { int to, cost; friend bool operator<(node a, node b) { return a.cost > b.cost; } }; struct Edge { int to, next; int v; } edge[1 << 21]; int head[1 << 20], tot; bool vis[1 << 20]; ll d[1 << 20]; void Init() { tot = 0; for (int i = 1; i <= 1000000; ++i) d[i] = -1, vis[i] = 0, head[i] = -1; } void add(int a, int b, int c) { edge[tot].to = b; edge[tot].v = c; edge[tot].next = head[a]; head[a] = tot++; } void dj(int x) { priority_queue<node> q; q.push({x, 0}); while (!q.empty()) { node now = q.top(); q.pop(); if (!vis[now.to]) { vis[now.to] = 1; d[now.to] = now.cost; for (int i = head[now.to]; i != -1; i = edge[i].next) { node next; next.to = edge[i].to; next.cost = now.cost + edge[i].v; if (!vis[next.to]) q.push(next); } } } } } d; int main() { d.Init();///初始化 cin>>n>>m>>s>>t; for(int i=1;i<=m;i++){ int a,b,c; cin>>a>>b>>c; int last; ///下面代码中 我的虚点建立在(m+1)*n与(m+2)*n之间 for(int j=1;j<=c;j++){ int x;cin>>x; if(j>1){///每一条路线相邻两个站点之间建边 d.add(i*n+last,i*n+x,b);///上一个点到当前点 d.add(i*n+x,i*n+last,b);///当前点到上一个点 } d.add(i*n+x,(m+1)*n+x,0);///当前点到虚点 d.add((m+1)*n+x,i*n+x,a);///虚点到当前点 last=x; } } d.dj((m+1)*n+s);//起点取虚点那一层图 ll mi=d.d[(m+1)*n+t];///终点取虚点那一层图 cout<<mi; return 0; }
D
只有加号和乘号,栈模拟完事,数字就一直加,加号把flag赋值为1,乘号把栈顶取出赋值给flag即可。
#include <bits/stdc++.h> using namespace std; typedef long long ll; char str[600005]; int main() { cin >> str; stack<ll> s; int len = strlen(str); ll sum = 0; int f = 1; for (int i = 0; i < len; i++) { if (str[i] >= '0' && str[i] <= '9') { sum = 0; while (str[i] >= '0' && str[i] <= '9') { sum = sum * 10 + str[i] - '0'; i++; } if(i==len) break; i--, s.push(f * sum % 10000); continue; } if (str[i] == '*') { f = s.top(); s.pop(); } if (str[i] == '+') f = 1; } s.push(f * sum % 10000); ll ans = 0; while (!s.empty()) ans = (ans + s.top()) % 10000, s.pop(); cout << ans << endl; return 0; }
E
贪心
对于牛的忍受值,按照最小值升序,最大值升序排序,对物品的值按照升序排序
枚举物品,如果牛的忍受值的最小值≤该物品的值,将牛的忍受值的最大值放入优先队列,维护一个小根堆,考虑一下,如果牛的忍受值最大值越大,说明它可以选择的范围更大,所以优先让最大值小的用,注意考虑牛的最大值是不是≥物品值,以及物品的个数是否够即可。
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int n,m;cin>>n>>m; pair<int,int> p[n],l[m]; for(int i=0;i<n;i++) cin>>p[i].first>>p[i].second; for(int i=0;i<m;i++)cin>>l[i].first>>l[i].second; sort(p,p+n),sort(l,l+m);///对牛的忍受值,物品值升序。 int ans=0,j=0; priority_queue<int> que; for(int i=0;i<m;i++){ ///将满足的牛的最大值压入堆中 while(j<n && p[j].first<=l[i].first) que.push(-p[j].second),j++; while(!que.empty() && l[i].second){ if(-que.top()>=l[i].first )ans++,l[i].second--;///看该物品是否满足牛的忍受值区间 que.pop(); } } cout<<ans; return 0; }