第36次ccf-csp题解（思维）
[*]比赛链接 https://sim.csp.thusaac.com/contest/36/home
[*]比赛感受
这会刚打完上海icpc，比起区域赛的题，这个简单太多了。
感受还不错，写的很顺手。除了第3题，其他3题都是一发过。
刷题得长期刷。
[*]A题 移动
题意：f : y+1 ; b : y-1 ; l : x-1 ; r : x+1
一个简单的模拟，若当前操作使机器人移出场地，那么使机器人移回来就好
#include <bits/stdc++.h>#define int long longusing namespace std;void ooo(int x){ cout<<x<<'\n';}signed main(){ int n, k;cin>>n>>k; for(int i=1;i<=k;i++){ int x, y;cin>>x>>y; string s;cin>>s; int len=s.size(); for(int j=0;j<len;j++){ if(s=='f')y+=1; else if(s=='b')y-=1; else if(s=='l')x-=1; else x+=1; if(y>n)y--; if(y<1)y++; if(x>n)x--; if(x<1)x++; } cout<<x<<' '<<y<<'\n'; } return 0;}
[*]B题 梦境巡查
这个题不算太难，有点思维，对码力要求不高。
它假设当bi为0时求初始时要带的最小补给。
关键在于怎样维护bi=0时，全程中所拥有补给的最小量（为负数表示还需要多少补给）所以就是一个单点修改，以bi为分界处，维护前半段和后半段最小值，对两段最小值取最小值，为负数则取绝对值，为非负数则为0。
#include <bits/stdc++.h>#define int long longusing namespace std;const int xmmm=2e5+10;int a, b;int c;int sum;int pmi, lmi;int ans;void ooo(int x){ cout<<x<<'\n';}signed main(){ int n;cin>>n; for(int i=0;i<=n;i++){ cin>>a; c=0-a; } for(int i=1;i<=n;i++){ cin>>b; c=b; } pmi=lmi=0-1e10; for(int i=1;i<=2*n+1;i++){ sum=sum+c; } for(int i=1;i<=2*n+1;i++){ if(i==1)pmi=sum; else pmi=min(pmi, sum); } for(int i=2*n+1;i>=1;i--){ if(i==2*n+1)lmi=sum; else lmi=min(lmi, sum); } for(int i=1;i<=n;i++){ int pos=i*2; int t1=pmi; int t2=lmi-b; ans=min(t1, t2); } for(int i=1;i<=n;i++){ if(ans<0)cout<<0-ans<<' '; else cout<<0<<' '; } return 0;}/*35 5 5 50 100 03 9 4 6 29 4 6*/
[*]D题 跳房子
这个题感觉还没有C题难。
这其实是一个很简单的图遍历的问题
建完边还是只有一个前驱的这种，简单版的迪杰斯特拉。
处理出b数组，每个点只入队列一次。
#include <bits/stdc++.h>//#define int long longusing namespace std;void ooo(int x){ cout<<x<<'\n';}struct p{ int id, num;};const int xmmm=2e5+10;int a, b, k;int dis;bool vis;signed main(){ int n;cin>>n; for(int i=1;i<=n;i++){ cin>>a; b=i-a; } for(int i=1;i<=n;i++)cin>>k; int pos=0; queue<p>q; //q.clear(); q.push(p{1, 0}); int ans=-1; while(!q.empty()){ p t=q.front();q.pop(); if(vis)continue; vis=1; if(t.id==n){ ans=t.num;break; } int x=t.id; if(x+k<=pos)continue; if(x+k>=n){ q.push(p{n, t.num+1}); continue; } for(int i=max(pos+1, x+1);i<=min(n, x+k);i++){ q.push(p{b, t.num+1}); } pos=max(pos, x+k); } cout<<ans<<'\n'; return 0;}/*50 1 2 3 03 4 4 10 15100 1 1 1 1 3 1 0 3 02 4 5 4 1 4 1 3 5 3*/
[*]C题 缓存模拟
一个大模拟按他的要求来就好了，详细的可以看注释
#include <bits/stdc++.h>#define int long longusing namespace std;const int xxx=3e5;const int xx=7e4;int head,nnum;// m组里有多少个struct p{ int x, y;};vector<p>ans;void ooo(int x){ cout<<x<<'\n';};struct node { int id, num; bool operator<(const node &a)const {return a.num<num;}};priority_queue<node>qq;unordered_map<int, int>a, vis; // 位置//是否修改signed main(){ int n, m, q;cin>>n>>m>>q; for(int i=1;i<=q;i++){ int x, y;cin>>x>>y; if(a){ / /判断是否命中 int pos=(y / n ) %m; head++; qq.push(node{y, head}); a=head; if(x==0)x=x; else { vis=1; //判断是否改写 } } else { int pos=( y / n )%m; //位置 if(nnum==n){ //如果已经满了 while(!qq.empty()){ node tt=qq.top();qq.pop(); if(a!=tt.num)continue; if(vis){ //cout<<"pos"<<tt.id<<' '<<tt.num<<' '<<a<<'\n'; ans.push_back(p{(int)1, tt.id}); vis=0; } head++; a=head; if(x)vis=1; qq.push(node{y, head}); ans.push_back(p{(int)0, y}); a=0;break; } } else { head++; a=head; nnum++; qq.push(node{y, head}); if(x)vis=1; ans.push_back(p{(int)0, y}); } } } int len=ans.size(); for(int i=0;i<len;i++){ cout<<ans.x<<' '<<ans.y<<'\n'; } return 0;}/*4 8 80 00 11 20 11 00 321 330 341 1 31 01 10 2*/
[*]自我总结
这次写题的顺序是1243，再写一点点。
页:
[1]