20/04/03
感觉自己做思维题的能力还是太差了，所以决定从今天开始从cf500场开始补div2/3的题，一天一场一直到开学吧。（希望大三前的时候有机会上个紫！
A. Piles With Stones
一开始把数量看成编号了..
#include<bits/stdc++.h>
using namespace std;
int a[10010],b[10010];
int main(){
int n;
cin>>n;
int suma=0,sumb=0;
for(int i=1,x;i<=n;++i){
cin>>x;
suma+=x;
}
for(int i=1,x;i<=n;++i){
cin>>x;
sumb+=x;
}
if(suma<sumb) cout<<"No";
else cout<<"Yes";
return 0;
}
B. And
给n个数字，每个数都可以被&运算，一次&记作一次费用，求n个数中被构造出至少有两个数相等的最少费用。
一个数字最多被&一次后就不会有变化了，因为a&x=a&x&x。直接开两个map存一下所有可以得到数，费用最少最好（例如当前数是a，首先查看费用为0的可能即m1中有没有a，费用为1的可能即再看m2中有没有a和m1中有没有a&x，最后查看费用为2的可能即m2中有没有a&x；把a存到m1，a&x存到m2
#include<bits/stdc++.h>
using namespace std;
map<int,int> m1,m2;
int main(){
int n,x;
cin>>n>>x;
int f=3;
for(int i=1,a;i<=n;++i){
cin>>a;
if(m1[a]>0) f=0;
else if((m1[a&x]>0||m2[a]>0)&&f!=0) f=1;
if(m2[a&x]>0&&f!=0&&f!=1) f=2;
m2[a&x]++;
m1[a]++;
}
if(f==3) cout<<"-1
";
else cout<<f<<endl;
return 0;
}
C. Photo of The Sky
给出随意排列的2*n个数字，求重新排列成二维平面的n个点的(x,y)，包含这n个点最小矩形面积。
一开始只想到了排序后取前n个数字为一类坐标，后n个为另一类坐标，看了一下发现并不只是这样的。例如排序后得到(a,b,c,d)，取(b-a)*(d-c)一定是小于(c-a)*(d-b)的，因为(b-a)小于(c-a)，(d-c)小于(d-b)；可以总结出:当选择一类坐标时，中间跳过一个，不如把这个点补上这样左右端的差距就能减小。所以尽量先选择一类连续的，另一类就是剩下的数字，这样的所有情况取个最小
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
long long a[N];
int main(){
int n;
cin>>n;
n+=n;
for(int i=1;i<=n;++i) cin>>a[i];
sort(a+1,a+1+n);
long long ans=max(0ll,1ll*(a[n/2]-a[1])*1ll*(a[n]-a[n/2+1]));
for(int i=2;i+n/2-1<=n;++i){
ans=min(1ll*ans,(a[n]-a[1])*(a[i+n/2-1]-a[i]));
}
cout<<ans<<endl;
return 0;
}
D. Chemical table
对于一个n*m的方格，当有(r1,c1),(r1,c2),(r2,c1)三个点,就会产生一个新点(r2,c2)，除了产生点还可以用一次花费产生一个新点，求最少的花费可以使得图上满点
很有意思的并查集应用：一个点对应的行和列都有关系，所以我们可以把这个点想象成它连接了它所在的行和列，三个格子自动生成第四个格子，显然可以想象为这个矩形所在的两行两列是有交集，所以拥有所有点就是使得每一行和每一列都有交集，利用并查集对每个点连接的行和列放到一个集合中，一个点都没有时有n+m个集合，满点时有1个集合，所以最后统计一下还差多少合并
#include<bits/stdc++.h>
using namespace std;
const int N=200100*2;
int fa[N];
int Find(int x){
return fa[x]==x? x:fa[x]=Find(fa[x]);
}
int main(){
int n,m,q;
cin>>n>>m>>q;
int ans=n+m-1;
for(int i=1;i<=n+m;++i) fa[i]=i;
while(q--){
int a,b;
cin>>a>>b;
b+=n;
int f1=Find(a),f2=Find(b);
if(f1!=f2){
fa[f1]=f2;
ans--;
}
}
cout<<ans<<endl;
return 0;
}