爱奇艺比赛-算法英雄复赛-writeup
最难的题目的难度和初赛第三题差不多，其他两题只不过是代码长了一些，令人感动……
手头有事，只扯关键点和贴代码了。
（为什么我编辑框里选了C/C++，可是高亮和缩进都丢了啊？令人感动）
A：2遍bfs就行了。
吐槽：似乎说了水能从高格子向低格子流，但是可流动的方向呢？我没太仔细读，没找到，于是默认当4向写，过了的……
如果能瞬移/8向流动就感人了……
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <limits.h> #include <ctype.h> #include <algorithm> #include <queue> using namespace std; typedef long long ll; int n,m; int a[105][105]; bool visa[105][105]; bool visb[105][105]; const int di[4][2]={{-1,0},{1,0},{0,1},{0,-1}}; struct Point{ int x,y; Point(int a=0,int b=0):x(a),y(b){} Point go(int i){ return Point(x+di[i][0],y+di[i][1]); } bool check(){ return x>=1&&y>=1&&x<=n&&y<=m; } }; void bfs(queue<Point>& q,bool vis[105][105]){ while(!q.empty()){ Point x=q.front();q.pop(); for(int i=0;i<4;i++){ Point y=x.go(i); if(y.check()&&(!x.check()||(x.check()&&a[x.x][x.y]<=a[y.x][y.y]))){ if(vis[y.x][y.y])continue; vis[y.x][y.y]=1; q.push(y); } } } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); } } queue<Point> q; for(int i=1;i<=n;i++){ q.push(Point(i,0)); } for(int i=1;i<=m;i++){ q.push(Point(n+1,i)); } bfs(q,visa); while(!q.empty())q.pop(); for(int i=1;i<=n;i++){ q.push(Point(i,m+1)); } for(int i=1;i<=m;i++){ q.push(Point(0,i)); } bfs(q,visb); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(visa[i][j]&&visb[i][j]){ printf("%d %d\n",i-1,j-1); } } } return 0; }
B：单调栈的经典应用。之前什么陈利人的新浪微博发过，感兴趣可以去学一下。
数据范围有点意思，1e6个数，高度最高1e4，刚好爆int，开long long躲就行了。
写过才知道，说用个数据结构就行，那是不够的，有些细节你会犯错的。
内存限制10MB……然后开1e6*2的int数组MLE了……然后换成vector，就过了？黑人问号脸。
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <limits.h> #include <ctype.h> #include <algorithm> #include <vector> using namespace std; typedef long long ll; struct Pt{ int x; int len; }; int main(){ int n; scanf("%d",&n); ll ans=0; vector<Pt> stk; for(int i=0;i<n;i++){ Pt tmp; scanf("%d",&tmp.len); tmp.x=i; while(stk.size()>0&&stk[stk.size()-1].len>tmp.len){ Pt& x=stk[stk.size()-1]; ans=max(ans,(ll)(x.len)*(ll)(i-x.x)); tmp.x=x.x; stk.pop_back(); } stk.push_back(tmp); } for(int i=0;i<stk.size();i++){ ans=max(ans,(ll)(stk[i].len)*(ll)(n-stk[i].x)); } printf("%lld\n",ans); return 0; }
C：……为什么是按规则排序的题啊……
反正就是，写好比较规则，扔进set里去方便快速修改其中一个/找最小。
本来想考缓存系统+最近最少使用的那种平衡树+源数据表，相互之间指针指来指去吧？
……可是，10w的范围，用基于红黑树的set+数组下标就搞定了啊……
缓存区容量为0的时候有点坑，小心一点就行了。
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <limits.h> #include <ctype.h> #include <algorithm> #include <set> using namespace std; typedef long long ll; struct Record{ int freq; int write_time; int id; bool operator<(const Record& b)const{ if(freq!=b.freq)return freq<b.freq; return write_time<b.write_time; } }; int pos[100001]; Record info[100001]; int d,q; int get_num(int& a,int& b){ char tmp[50]; gets(tmp); return sscanf(tmp,"%d%d",&a,&b); } set<Record> s; int query(int x){ if(pos[x]!=-1){ set<Record>::iterator it=s.find(info[x]); s.erase(it); info[x].freq++; s.insert(info[x]); } return pos[x]; } void update(int x,int data,int write_time){ if(d==0)return; if(pos[x]!=-1){ pos[x]=data; }else{ info[x].freq=0; info[x].id=x; info[x].write_time=write_time; pos[x]=data; if(s.size()>=d){ set<Record>::iterator it=s.begin(); int remove_id=it->id; pos[remove_id]=-1; s.erase(it); } s.insert(info[x]); } } int main(){ memset(pos,-1,sizeof(pos)); get_num(d,q); for(int i=0;i<q;i++){ int a,b; int ret=get_num(a,b); if(ret==1){ printf("%d\n",query(a)); }else{ update(a,b,i); } } return 0; }
查看8道真题和解析