Codeforces Round #541 (Div. 2) 题解
分类:
IT文章
•
2025-01-15 16:44:07
Codeforces Round #541 (Div. 2)
题目链接：https://codeforces.com/contest/1131
A. Sea Battle
题意：
给出两个矩形的宽和高，满足第一个矩形的左上顶点为(0,0)，右下顶点为(w1,-h1)；第二个矩形的坐下顶点为(0,0)，右上顶点为(w2,h2)。然后求围绕这两个矩形一圈的格子个数为多少。
题解：
利用二维前缀和的思路推导一下公式就行了，公式也有很多吧==我当时就是大概模拟了一下。。
代码如下：
![]()
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll w1,h1,w2,h2;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>w1>>h1>>w2>>h2;
ll ans = 0;
ans+=(h1+h2+2)*(max(w1,w2)+2);
ll now=min(w1,w2);
ll tmp=max(w1,w2)-now;
if(w1<w2) ans-=h1*tmp;
else ans-=h2*tmp;
ans-=(w1*h1+w2*h2);
cout<<ans;
return 0;
}
View Code
B. Draw!
题意：
给出n次两个人的比分，每次给出xi,yi代表两个人的比分，然后问这两个人最多平局的多少次。
题解：
假设这两个人在比分为p的时候平局，对于xi,yi,xi+1,yi+1来说，肯定满足max(xi,yi)<=p<=min(xi+1,yi+1)的，然后就借用这个式子来算。注意一下xi==yi这种特殊情况，可能会被计算多次，处理一下就好了。
原谅我代码对不上上面的题解。。懒得改了，我感觉我的做题思路还没有抽象化，上面一题也是，基本都是采用模拟的方法来做的，没有很好地进行数学建模。
代码如下：
![]()
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10005;
int n;
int a[N],x[N],y[N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>n;
ll ans = 1;
for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
ans+=min(x[1],y[1]);
for(int i=2;i<=n;i++){
if(x[i]>y[i]){
int dx=x[i]-x[i-1],dy=y[i]-y[i-1];
if(y[i]<x[i-1]) continue ;
if(y[i-1]<x[i-1]) ans+=(y[i]-x[i-1]+1);
else if(y[i-1]>x[i-1]) ans+=dy+1;
else ans+=min(dx,dy);
}else{
int dx=x[i]-x[i-1],dy=y[i]-y[i-1];
if(x[i]<y[i-1]) continue ;
if(x[i-1]<y[i-1]) ans+=(x[i]-y[i-1]+1);
else if(x[i-1]>y[i-1]) ans+=dx+1;
else ans+=min(dx,dy);
}
}
cout<<ans;
}
View Code
C. Birthday
题意：
n个人，每个人都有对应的身高ai，然后这n个人站成一个圈，问怎样的站法，能够使相邻两个人的身高差最小，最后任意输出一种方法即可。
题解：
考虑贪心的做法(为啥这题的数据为100啊...)，先对所有的数排个序，然后从前往后依次放奇数位置的人，从后往前依次放偶数位置的人。
题解的证明用到了哈密顿回路，我们这种做法得到的答案为max(ai+2-ai)，然后只需要证明不可能存在max(ai+1-ai)这样的答案就行了，证明这个在直观上面还是比较好理解的，很容易得证。
代码如下：
![]()
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
int a[N],ans[N];
int n;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
int fir=1,last=n;
for(int i=1;i<=n;i++){
if(i&1){
ans[fir++]=a[i];
}else ans[last--]=a[i];
}
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
return 0;
}
View Code
![]()
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
int n,m,cnt,tot;
char mp[N][N];
int f[N<<1],num[N<<1],head[N<<1],in[N<<1],ans[N<<1];
struct Edge{
int u,v,next;
}e[N*N<<1];
int find(int x){
return f[x]==x?f[x]:f[x]=find(f[x]);
}
void Union(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy) return ;
f[fx]=fy;
}
void adde(int u,int v){
e[tot].v=v;e[tot].next=head[u];head[u]=tot++;
}
int topsort(){
queue <int> q;
int tot=0;
for(int i=1;i<=cnt;i++) if(!in[i]) q.push(i),tot++,ans[i]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i!=-1;i=e[i].next){
int v=e[i].v;
if(--in[v]==0){
ans[v]=ans[u]+1;
q.push(v);
tot++;
}
}
}
return tot==cnt;
}
int main(){
scanf("%d%d",&n,&m);
int flag=0;
for(int i=1;i<=n+m;i++) f[i]=i;
for(int i=1;i<=n;i++){
scanf("%s",mp[i]+1);
for(int j=1;j<=m;j++){
if(mp[i][j]=='=') Union(i,j+n);
else flag=1;
}
}
for(int i=1;i<=n+m;i++){
int f=find(i);
if(!num[f]) num[f]=++cnt;
}
if(cnt==1 && flag){
cout<<"No";
return 0;
}
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int u=num[find(i)],v=num[find(j+n)];
if(u==v&&mp[i][j]!='='){
cout<<"No";
return 0;
}
if(mp[i][j]=='<') adde(u,v),in[v]++;
else if(mp[i][j]=='>') adde(v,u),in[u]++;
}
}
int f=topsort();
if(!f) cout<<"No";
else{
puts("Yes");
for(int i=1;i<=n+m;i++){
int fx=find(i);
cout<<ans[num[fx]]<<" ";
if(i==n) cout<<'
';
}
}
return 0;
}
