牛客算法周周练3
A、
题意：Nancy往六个方向走，会吃掉'.'，遇到'*'就返回，问他能吃到多少糖果，他想少吃表明到了终点后就不会在找了，三维迷宫。
思路：
明显的BFS，题目描述的很明确了，开个结构体记录当前坐标以及吃的果冻数量，再用队列去BFS模拟一遍。刚开始没懂题意用了DFS，又超时又wa。
Code：
#include <bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int read(){
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
void print(int x){
if(x>=10) print(x/10);
putchar(x%10+'0');
}
bool vis[105][105][105];
struct node{
int x,y,z,cnt;
};
queue<node>q;
char a[105][105][105];
int dir[][3] = {{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}},n;
int main() {
js;
cin>>n;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) cin>>a[i][j]+1;
q.push({1,1,1,1});
while(!q.empty()) {
node ans=q.front(); q.pop();
if(ans.x==n&&ans.y==n&&ans.z==n) {
cout<<ans.cnt<<endl;
return 0;
}
for(int i=0;i<6;++i) {
int x=ans.x+dir[i][0],y=ans.y+dir[i][1],z=ans.z+dir[i][2];
if(x<1||y<1||z<1||x>n||y>n||z>n||a[x][y][z]=='*'||vis[x][y][z]) continue;
vis[x][y][z]=true;
q.push({x,y,z,ans.cnt+1});
}
}
cout<<"-1\n";
} B、
题意：走迷宫，只能向右或者向上走，1是树木不可以走，0可以走，从起点到终点有多少方案。
思路：
动态规划，状态dp[i][j]表示走到第i行第j列的方案数，它的状态去决与左边和下边状态的方案数之和。
状态转移方程：dp[i][j]=dp[i+1][j]+dp[i][j-1]。起点的方案数是1，所以可以初始化dp[n][0]或者dp[n+1][1]为0.
注意：因为起点是左下角，所以最终的答案是dp[1][m]，起点是dp[n][1]，别搞错了。
Code：
#include<bits/stdc++.h>
using namespace std;
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 dp[3005][3005],n,m,a[3005][3005];
int main() {
read(n),read(m);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) read(a[i][j]);
dp[n][0]=1;
for(int i=n;i;--i) {
for(int j=1;j<=m;++j) {
if(a[i][j]) continue;
dp[i][j]=dp[i+1][j]+dp[i][j-1];
if(dp[i][j]>=2333) dp[i][j]-=2333;
}
}
cout<<dp[1][m]%2333<<endl;
} C、
思路：
分层建图，求单源最短路。
想到求最短路，不带负权边，很容易想到迪杰斯特拉算法，但是这并不是给你n个点m条边让你建好图再问你最短路，这里最难想到的就是怎么建图化为求最短路的一般情况。
将每条地铁线看作一层图，因为每层之间可能公用了一些节点，所以我们对每个车站建立一个超级源点放在第m+1层， 车站到超级源点的花费是0, 超级源点往车站的花费是上地铁的花费，因为从源点到车站表示第一次上地铁，而从车站到超级源点表示他要转地铁（转地铁的搭配是车站到超级源点再到其它层的该车站）。
每一层假设有n个结点（有强迫症你可以这一层有几个就放几个，但是在连这一层的该车站到超级源点的边时，超级源点的取值又不知道，反正又不浪费多少空间），第i层第j个车站的编号就是(i-1)*n+a[j]。
因为取了m+1层，每层n个单位，所以最多有有(m+1) * n个不重复的编号.
注意：到起点最短的结点集合是A，集合A的邻居放进集合B。集合B里可能有两个一样的邻居，但是有一个邻居是要去掉的。必须要存放进去的邻居和它连起来的最短路，比如集合B里有两个一样的邻居u=2,dis=5和u=2,dis=4，这里邻居u=2,dis=5是要去掉的，所以要用优先队列存集合，并重载'<'，使距离起点最小的邻居出队，再标记已经出队的邻居（找到最短路了），这样在遇到距离大一点的邻居u=2,dis=5时判断已经出队然后就可以抛弃了。
Code：
#include<bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int maxn=501005;
int head[maxn],Next[maxn<<1],to[maxn<<1],tot,val[maxn<<1];
void add(int x,int y,int c) {
to[++tot]=y;
val[tot]=c;
Next[tot]=head[x];
head[x]=tot;
}
struct node{
int v,dis;
bool operator<(const node&a) const{
return dis>a.dis;
}
};
int n,m,dis[maxn];
bool done[maxn];//done[i]=true表示到结点i的最短路径已经找到
void dijkstra(int s) {
fill(dis, dis + maxn, 0x3f3f3f3f);
dis[s]=0; //起点到自己的距离是0
priority_queue<node>q;//优先队列，存结点的信息
q.push(node{s,0});//起点进栈
while(!q.empty()) {
node u=q.top();
q.pop();
if(done[u.v]) continue;//丢弃已经找到最短路径的结点，即集合A中的结点
done[u.v]=true;
for(int i=head[u.v];i;i=Next[i]) {
int y=to[i];
if(done[y]) continue;
if(dis[y]>val[i]+u.dis) {
dis[y]=val[i]+u.dis;
q.push(node{y,dis[y]});
}
}
}
}
int s,t,num,x,last,a,b;
int main() {
js;
cin>>n>>m>>s>>t;
for(int i=0;i<m;++i) {
cin>>a>>b>>num;
for(int j=1;j<=num;++j) {
cin>>x;
if(j!=1) {
add(i*n+x,i*n+last,b);
add(i*n+last,i*n+x,b);
}
add(i*n+x,n*m+x,0);
add(n*m+x,i*n+x,a);
last=x;
}
}
dijkstra(n*m+s);
if(dis[n*m+t]==0x3f3f3f3f) cout<<"-1\n";
else cout<<dis[n*m+t]<<endl;
} D、
题意：给一个只包含数字和'+'、'*'的表达式，给出结果的后四位，前导0不需要输出。
思路：
模拟计算机运算，把输入的数字压栈，遇到乘号出栈，再将乘积压栈，最后将栈内的元数求和输出。复杂度---不好算，我怕超时，但是没有超时。
Code：
#include <bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int read(){
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
void print(int x){
if(x>=10) print(x/10);
putchar(x%10+'0');
}
char ch;
int x,y,temp;
long long ans;
stack<int>s;
int main() {
scanf("%d",&x);
s.push(x%10000);
while((ch=getchar())!='\n') {
scanf("%d",&y);
y%=10000;
if(ch=='*') {
temp=s.top()*y%10000;
s.pop();
s.push(temp);
}
else s.push(y);
}
while(!s.empty()) {
ans+=s.top();
s.pop();
}
printf("%lld\n",ans%10000);
}
E、
题意：n头牛因为想黑又不想死，宁愿死也要黑，给出n头牛在晒黑的前提下需要的防晒霜强度范围，然后是m个防晒霜的信息，分别是强度和数量。输出有几头牛可以不死。
思路：
l值表示防晒霜最小需求，r值表示最大需求
如果先考虑l值最小的，选第一个大于等于l值的防晒霜，反例：
2 2
2 3
1 5
3 1
4 1
如果先考虑l值最小的，选第一个小于等于r值的防晒霜，反例：
2 2
3 5
1 5
3 1
2 1
给一个牛选防晒霜，如果防晒霜的强度要逼近r值，那么这个防晒霜强度要满足后面没有比当前的l值还逼近它的；如果防晒霜的强度要逼近l值，那么这个防晒霜强度要满足后面没有比当前的r值还逼近它的。总结一下就是这个防晒霜的强度要最切合这个舒适范围。
如果上面一段话没明白就当是废话吧，我觉得局部最优不能光想着逼近r值或者l值，应该都要考虑。
所以考虑到局部最优，我们可以把皮最薄的牛（需要的防晒霜最小值最大）用满足条件的最小强度的防晒霜给它涂，接着处理皮更厚的（需要的防晒霜最小值更小的）。这样在保证了选的防晒霜最接近r值的同时又最接近l值。
Code：
#include <bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
int read(){
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
struct Node {
int mini, maxi;
bool operator < (const Node b)const {
return mini < b.mini;
}
}a[2505];
map<int, int> mp;
int ans;
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;
}
mp[0] = mp[1001] = 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;
} 
