Codeforces Round #500 (Div. 2) [based on EJOI]

2022-11-30 12:10:50

Codeforces Round #500 (Div. 2) [based on EJOI]

A

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define IT set<node>::iterator

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 200005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<ll,ll>pll;

 typedef pair<ll,int> pli;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=1e9+;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int n,ans1,ans2;

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n;

     int x;

     for(int i=;i<=n;i++){

         cin>>x;

         ans1+=x;

     }

     for(int i=;i<=n;i++){

         cin>>x;

         ans2+=x;

     }

     if(ans1>=ans2) puts("YES");

     else puts("NO");

 }

B

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define IT set<node>::iterator

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 200005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<ll,ll>pll;

 typedef pair<ll,int> pli;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=1e9+;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int n,x;

 int a[];

 int b[];

 set<int>se1,se2,se3;

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n>>x;

     for(int i=;i<=n;i++){

         cin>>a[i];

         b[i]=a[i]&x;

         se1.insert(a[i]);

         se2.insert(b[i]);

     }

     if(se1.size()!=n){

         cout<<<<endl;

         return ;

     }

     for(int i=;i<=n;i++){

         se1.erase(a[i]);

         se1.insert(b[i]);

         if(se1.size()!=n){

             cout<<<<endl;

             return ;

         }

         se1.erase(b[i]);

         se1.insert(a[i]);

     }

     if(se2.size()!=n){

         cout<<<<endl;

         return ;

     }

     cout<<-<<endl;

 }

C

题意：给你2*n个值，组成n个点，问能覆盖这n个点的最小矩形面积

思路：枚举长度为n的区间,这段区间作为x坐标的范围,然后将这段区间的差值与剩下部分的差值相乘取最小值

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define IT set<node>::iterator

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 200005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<ll,ll>pll;

 typedef pair<ll,int> pli;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=1e9+;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int n;

 ll a[maxn];

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n;

     n*=;

     for(int i=;i<=n;i++) cin>>a[i];

     sort(a+,a+n+);

     ll ans=(a[n/]-a[])*(a[n]-a[n/+]);

     for(int i=;i<=n/+;i++){

         ans=min(ans,(a[n]-a[])*(a[i+n/-]-a[i]));

     }

     cout<<ans<<endl;

 }

D

题意：有一个n*m的矩形，一开始有q个格子上被标记。对于任意两行两列，如果交汇的四个格子中有三个被标记，那么第4个也会被标记。求至少需要手动标记几个格子，才能让整个矩形内的格子都被标记。

题意：当(x1,y1),(x1,y2),(x2,y1)被标记时,(x2,y2)也会被标记，所以用并查集维护,判断有多少个点是没有被标记的

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define IT set<node>::iterator

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 200005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<ll,ll>pll;

 typedef pair<ll,int> pli;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=1e9+;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int n,m,q;

 int fa[maxn*];

 int Find(int x){

     int r=x,y;

     while(x!=fa[x]){

         x=fa[x];

     }

     while(r!=x){

         y=fa[r];

         fa[r]=x;

         r=y;

     }

     return x;

 }

 void join(int x,int y){

     int xx=Find(x);

     int yy=Find(y);

     if(xx!=yy){

         fa[xx]=yy;

     }

 }

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n>>m>>q;

     int x,y;

     for(int i=;i<=n+m;i++) fa[i]=i;

     for(int i=;i<=q;i++){

         cin>>x>>y;

         join(x,y+n);

     }

     int ans=;

     for(int i=;i<=n+m;i++){

         if(fa[i]==i){

             ans++;

         }

     }

     cout<<ans-<<endl;

 }

E

题意：给你n个数，你一次操作可以把某一个数减一，使任意k个数严格大于它旁边的两个数，问最少需要几次操作。输出1<=k<=(n+1)/2时的答案。

思路：　dp[i][j][0]表示表示前i个数有j个满足条件，i、i-1都不满足条件的最少操作数

　　　　dp[i][j][1]表示表示前i个数有j个满足条件，i满足条件的最少操作数

　　　　dp[i][j][2]表示表示前i个数有j个满足条件，i-1满足条件的最少操作数

然后进行状态转移：

　　dp[i][j][2]=dp[i-1][j][1]+max(0,a[i]-a[i-1]+1);
　　dp[i][j][0]=min(dp[i-1][j][0],dp[i-1][j][2]);
　　dp[i][j][1]=min(dp[i-1][j-1][0]+max(0,a[i-1]-a[i]+1),dp[i-1][j-1][2]+max(0,min(a[i-1],a[i-2]-1)-a[i]+1));

dp[i][j][1]分为两种情况：

1、前两个都不满足条件，那么i-1就是原来的数，即没有被操作过，需要的操作数就是max(0,a[i-1]-a[i]+1)

2、i-2满足条件，那么i-1已经变成了min(a[i-1],a[i-2]-1)，还需要的操作数就是max(0,min(a[i-1],a[i-2]-1)-a[i]+1)

因为转移只用到了dp[i-1][j],dp[i-1][j-1],所以可以用滚动数组优化

参考博客：https://ouuan.blog.luogu.org/solution-cf1012c

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define IT set<node>::iterator

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 200005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<ll,ll>pll;

 typedef pair<ll,int> pli;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=1e9+;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int n;

 int dp[][];

 int a[];

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n;

     for(int i=;i<=n;i++) cin>>a[i];

     for(int i=;i<=;i++){

         for(int j=;j<=(n+)/;j++){

             dp[j][i]=0x3f3f3f3f;

         }

     }

     dp[][]=dp[][]=;

     for(int i=;i<=n;i++){

         for(int j=(i+)/;j>=;j--){

             dp[j][]=dp[j][]+max(,a[i]-a[i-]+);

             dp[j][]=min(dp[j][],dp[j][]);

             dp[j][]=min(dp[j-][]+max(,a[i-]-a[i]+),dp[j-][]+max(,min(a[i-],a[i-]-)-a[i]+));

         }

     }

     for(int i=;i<=(n+)/;i++){

         cout<<min(dp[i][],min(dp[i][],dp[i][]))<<" ";

     }

 }

码农公寓

Codeforces Round #500 (Div. 2) [based on EJOI]

A

B

C

D

E

相关文章