D – LRUD Instructions
题意：给一个棋盘，然后给出N个障碍，然后给出Q次移动，给出移动的方向和移动的距离，如果移动的过程中遇到墙或者障碍，就停止，问每次移动之后停下来的位置。
题解：数据是1e9很大，所以肯定不能遍历，但我们可以看到，实际上会出现的障碍只有2e5个，所以我们可以离散化一下，把数据缩小，然后每次二分查找有没有障碍即可。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const int N=2e5+5; const ll inf=1e18; const ll mod=998244353; ll n,m; vector<ll> p[N]; vector<ll> q[N]; unordered_map<ll,ll> l,r; ll cnt1,cnt2; signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); ll bx,by; cin>>n>>m>>bx>>by; ll t;cin>>t; while(t--){ ll x,y;cin>>x>>y; if(!l[x]) l[x]=++cnt1;//类似于离散化的操作 if(!r[y]) r[y]=++cnt2; p[l[x]].push_back(y); q[r[y]].push_back(x); } cin>>t; for(ll i=1;i<=cnt1;i++){p[i].push_back(0);p[i].push_back(m+1); sort(p[i].begin(),p[i].end());} for(ll i=1;i<=cnt2;i++){q[i].push_back(0);q[i].push_back(n+1); sort(q[i].begin(),q[i].end());} while(t--){ char s;ll x;cin>>s>>x; if(s=='L'){ if(!p[l[bx]].size()){ by=max(1ll,by-x); } else{ ll pt=*(lower_bound(p[l[bx]].begin(),p[l[bx]].end(),by)-1); by=max(pt+1,by-x); } } else if(s=='R'){ if(!p[l[bx]].size()){ by=min(m,by+x); } else { ll pt=*(lower_bound(p[l[bx]].begin(),p[l[bx]].end(),by));//找到第一个比它大的数 by=min(pt-1,by+x); } } else if(s=='U'){ if(!q[r[by]].size()){ bx=max(1ll,bx-x); } else { ll pt=*(lower_bound(q[r[by]].begin(),q[r[by]].end(),bx)-1);//找到第一个比它小的 bx=max(pt+1,bx-x); } } else { if(!q[r[by]].size()){ bx=min(n,bx+x); } else{ ll pt=*(lower_bound(q[r[by]].begin(),q[r[by]].end(),bx)); bx=min(pt-1,bx+x); } } cout<<bx<<" "<<by<<endl; } }
E – Notebook
题意：四种操作
- add：在序列尾加x
- delete：删除序列最后一个数
- save：将当前的序列保存到第x页
- load：用第x页的序列替换当前的序列
问每次操作结束之后当前序列的最后一个数字是多少，如果没有数字则输出” -1 “。
题解：放在树上操作，利用不同的枝来存储不同的序列。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const int N=5e5+5; const ll inf=1e18; const ll mod=998244353; vector<ll> ans; vector<ll> res; struct ss{ ll w,fa; ss(ll x,ll y){ w=x;fa=y; } }; unordered_map<ll,ll> mp; vector<ss> q; ll cnt; signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); ll n;cin>>n; q.push_back(ss(-1,0)); ll now=0; while(n--){ string s;cin>>s; ll x; if(s!="DELETE") cin>>x; if(s=="ADD"){ q.push_back(ss(x,now)); now=(ll)(q.size()-1); } else if(s=="DELETE"){ now=q[now].fa; } else if(s=="SAVE"){//将当前的节点存储 mp[x]=now; } else now=mp[x];//直接跳转到之前存储的节点 cout<<q[now].w<<" "; } }
F – Hammer 2
题意：给出两个数组，第一个数组表示墙的位置，第二个数组表示锤子的位置，对应的墙需要对应的锤子敲开，开始在0的位置，每次然后最后要到达一个点，问能否到达，不能到达输出-1，能到达输出需要走的最短路程。
题解：dp,可以把问题抽象化为，开始有2*n+2个点.其中2*n是墙的位置和锤子的位置，然后还有起点0和终点m的位置，然后我们每次都选择一个位置去，我们可以再把这些点排序去重离散化，最后得到的一个序列，找到其中0对应的位置，每次都选择一个位置去，然后利用一个l,一个r表示到达的最左边和最右边，用dp[l][r][x]表示最左边到达l,最右边到达r，然后x两个取值(0：上一次移动的方向是向左，也就是当前自身的位置在l ——— 1：上一次移动的方向是向右，也就是当前自身的位置在r）,dp[l][r][x]就是这种状态下的满足条件的最小路程。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e3+5; const ll inf=1e18; ll dp[N][N][2]; ll cnt; ll a[N],b[N],q[N]; ll vis[N]; signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); ll n,m;cin>>n>>m; for(ll i=1;i<=n;i++) cin>>a[i],q[++cnt]=a[i]; for(ll i=1;i<=n;i++) cin>>b[i],q[++cnt]=b[i]; q[++cnt]=0,q[++cnt]=m;//将所有点放到q数组中 sort(q+1,q+1+cnt);//排序 cnt=unique(q+1,q+1+cnt)-q-1;//去重 for(ll i=1;i<=n;i++) b[i]=lower_bound(q+1,q+1+cnt,b[i])-q;//离散化 for(ll i=1;i<=n;i++) a[i]=lower_bound(q+1,q+1+cnt,a[i])-q,vis[a[i]]=b[i];//注意这句话和上一句话的顺序，要先给锤子赋值，再给墙赋值，因为这里要用一个vis数字去记录每一个墙对应的锤子的位置 ll beg=lower_bound(q+1,q+1+cnt,0)-q;//找到开始0的位置 memset(dp,0x3f,sizeof(dp)); dp[beg][beg][0]=dp[beg][beg][1]=0; for(ll len=1;len<=cnt;len++)//遍历区间的长度 for(ll l=1;l<=cnt;l++){ ll r=l+len-1;//右端点 if(l>1){//要向左移动所以l>1 ll pt=vis[l-1];//判断左边的位置是不是墙，是墙的话钥匙在不在[l,r]内 if(!pt||(pt&&pt>=l&&pt<=r)){ dp[l-1][r][0]=min(dp[l-1][r][0],dp[l][r][0]+q[l]-q[l-1]); dp[l-1][r][0]=min(dp[l-1][r][0],dp[l][r][1]+q[r]-q[l-1]); } } if(r<cnt){ ll pt=vis[r+1];; if(!pt||(pt&&pt>=l&&pt<=r)){ dp[l][r+1][1]=min(dp[l][r+1][1],dp[l][r][0]+q[r+1]-q[l]); dp[l][r+1][1]=min(dp[l][r+1][1],dp[l][r][1]+q[r+1]-q[r]); } } } ll ans=inf; m=lower_bound(q+1,q+1+cnt,m)-q;//找到终点 for(ll i=1;i<=m;i++) for(ll j=m;j<=cnt;j++){//找到最小值 ans=min(min(ans,dp[i][j][0]),dp[i][j][1]); } if(ans==1e18) cout<<"-1"<<endl; else cout<<ans; }
原文地址：http://www.cnblogs.com/hhzp/p/16813874.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
