Codeforces Round #500 (Div. 2) [based on EJOI]
https://codeforces.com/contest/1013
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][]))<<" ";
}
}
