CF每日5题（1400）

感觉1400的题练的差不多了？也可能是今天盲抽到很多水题。
明天练1500，今晚上早点睡觉。

1-799B 模拟 优先队列

• 使用优先队列找最便宜的衣服 根据衣服上的颜色分队列
• 如何确定衣服已经卖出？维护一个vis数组，判断卖出了就把它弹出队列。

const int N=2e5+10;
struct ts{int p,a,b,id;bool operator<(const ts&x)const{//优先队列默认是大顶堆，所以小于号要变成大于号return p>x.p;}
}t[N];
int vis[N];
priority_queue<ts>q[4];
void buy(int i){bool fg=0;//能不能买到while (!q[i].empty()){ts tp=q[i].top();if(vis[tp.id])q[i].pop();//之前买过了else{//没买过vis[tp.id]=1;q[i].pop();fg=1;return cout<<tp.p<<' ',void();}}if(fg==0)cout<<-1<<' ';
}
void solve(){int n;cin>>n;forr(i,1,n)cin>>t[i].p;forr(i,1,n)cin>>t[i].a;forr(i,1,n)cin>>t[i].b;forr(i,1,n){t[i].id=i;if(t[i].a==t[i].b)q[t[i].a].push(t[i]);else{q[t[i].a].push(t[i]);q[t[i].b].push(t[i]);}}int m;cin>>m;forr(i,1,m){int x;cin>>x;buy(x);}
}

2-416A 水题 模拟

const int N=2e9;
map<string,string>op={{">=","<"},{"<",">="},{"<=",">"},{">","<="}};
void solve(){int l=-N,r=N;int n;cin>>n;forr(i,1,n){string s,jud;int num;cin>>s>>num>>jud;if(jud=="N"){s=op[s];//变成反向符号}if(s==">=")l=max(num,l);if(s==">")l=max(num+1,l);if(s=="<")r=min(num-1,r);if(s=="<=")r=min(num,r);// cout<<l<<' '<<r<<endl;}if(l<=r)cout<<l;else cout<<"Impossible"<<endl;
}

3- 710B 水 排序

• 注意是找距离相同时最左边的数
• 考虑$a,b$两数，对任意$x,a\le x\le b$，到$a,b$两点距离和一样，但是题意要求输出$a$

void solve(){int n;cin>>n;vector<int>a(n);forr(i,1,n)cin>>a[i-1];sort(a.begin(),a.end());int ans;if(n%2==0)ans=a[n/2-1];else ans=a[n/2];cout<<ans<<endl;
}

4- 377B 水 数学

void solve(){int a,b,c,d;cin>>a>>b>>c>>d;// if(a*d==b*c)return cout<<0<<endl,void();int ma=max(a*d,b*c),mi=min(a*d,b*c);int u=ma-mi,dd=ma;int g=__gcd(u,dd);cout<<u/g<<'/'<<dd/g<<endl;
}

5- 1130C 搬砖水题 bfs 暴力

const int N=55;
char mp[N][N];
int vis[N][N];
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
int n;
struct pos{int x,y;};
inline bool jud_in(int x,int y){return x>=1&&x<=n&&y>=1&&y<=n;
}
void solve(){cin>>n;int r1,c1,r2,c2;cin>>r1>>c1>>r2>>c2;forr(i,1,n){string s;cin>>s;forr(j,1,n){mp[i][j]=s[j-1];}}queue<pos>q;vector<pos>bg,ed;q.push({r1,c1});bg.push_back({r1,c1});vis[r1][c1]=1;while (!q.empty()){int qx=q.front().x,qy=q.front().y;q.pop();forr(i,0,3){int nx=qx+dx[i],ny=qy+dy[i];if(jud_in(nx,ny)&&mp[nx][ny]=='0'&&vis[nx][ny]==0){if(nx==r2&&ny==c2)return cout<<0<<endl,void();vis[nx][ny]=1;q.push({nx,ny});bg.push_back({nx,ny});}}}q.push({r2,c2});ed.push_back({r2,c2});vis[r2][c2]=1;while (!q.empty()){int qx=q.front().x,qy=q.front().y;q.pop();forr(i,0,3){int nx=qx+dx[i],ny=qy+dy[i];if(jud_in(nx,ny)&&mp[nx][ny]=='0'&&vis[nx][ny]==0){vis[nx][ny]=1;q.push({nx,ny});ed.push_back({nx,ny});}}}int ans=50*50*2+5;for(auto b:bg){for(auto e:ed){ans=min(ans,(e.x-b.x)*(e.x-b.x)+(e.y-b.y)*(e.y-b.y));}}cout<<ans<<endl;
}