VP记录:Codeforces Round 857 (Div. 2) A~D

传送门:CF

A题 Likes:

这道题的题意很变态,十分的难懂,简直就是一坨shit,这场比赛最后被骂是有原因的

简单来说就是对于一个项目,每一个人都能对此加一或者减一,最后问你这个项目每一时刻最大和最小是多少.题目中只说明了只能点赞后才能取消,并没有解释存在取消操作必存在点赞操作(在数据那里悄悄的提了一嘴),但是仍然会造成理解困难

看懂题目之后解决方法很简单,对于最大,我们只要先全部都进行点赞,然后再取消即可
对于最小,我们只要先点赞然后随即取消即可(数据保证取消操作必有一个点赞操作与之对应)

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int T;
vector<int>a,b;
int main() {T=read();while(T--) {int n=read();a.clear();b.clear();for(int i=1;i<=n;i++) {int x=read();if(x>0) a.push_back(x);else b.push_back(x);}int cnt=0;for(int i=0;i<a.size();i++) {printf("%d ",++cnt);}for(int i=0;i<b.size();i++) {printf("%d ",--cnt);}cnt=0;cout<<endl;int pos=0;for(int i=0;i<a.size();i++) {printf("%d ",++cnt);if(pos<b.size()) {printf("%d ",--cnt);pos++;}}while(pos<b.size()) {printf("%d ",--cnt);}cout<<endl;}return 0;
}

B题 Settlement of Guinea Pigs:

题目理解起来也十分的变态,样例也十分的难以理解,只能活该被骂,做起来十分难受

对于每一次查询性别之前,也就是每一个2出现之前记录1的个数,假设我们的1的个数是偶数的话,那么此时我们需要的鸟笼就是$(n-2)/2+2$,对于我们1的个数是奇数的时候,我们需要的鸟笼的数量就是$n/2+1$,接下来来解释一下:

显然我们会发现我们的情况会随着4的余数而进行变化(下面将1,2作为雌雄):
当我们是4的倍数的时候,最坏情况是1,2,1,2…11,12.也就是说对于最后的四个猪,我们的情况并不是1,2,1,2,而应该是11,12,这样才是最坏的情况,此时我们的答案就是(n-2)/2+2
当我们是4的倍数余1时,此时最坏情况是1,2,1,2…1,2,1,2,1,也就是说此时的情况就是n/2+1
当我们是4的倍数余2时,此时最坏的情况是1,2,1,2…1,2,1,2,1,2,此时也还是(n-2)/2+2
当我们是4的倍数余3时,此时最坏的情况是1,2,1,2,…1,2,1,2,1,此时也还是n.2+1

并且注意本题有一个坑点就是在中途过程中我们可能需要很多个鸟笼,虽然可能这些鸟笼在最后可能是空的,但是为了安放好猪,我们依旧需要购买,所以我们需要记录过程中的最大值而不是直接查询最终结果!!

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int main() {int T=read();while(T--) {int n=read();int sum1=0,sum2=0;int ans=0;for(int i=1;i<=n;i++) {int x=read();if(x==1) sum1++;else {if(sum1==0) continue;if(sum1&1) {sum2+=sum1/2;sum1=1;}else {sum2+=(sum1-2)/2;sum1=2;}}ans=max(ans,sum1+sum2);}cout<<ans<<endl;}return 0;	
}

C题 The Very Beautiful Blanket:

本题的题面还是比较简明易懂的,做起来的感觉比前两题要爽

由于是一道构造题,所以假设想不到构造的那一个点上本题做起来还是比较痛苦的
我们需要保证每4*4的区间就要满足左上2*2异或和要等于右下2*2异或和,如何保证我们这个做法比较舒服呢.要知道CF上对于这种构造题肯定不会很麻烦的,所以我们大胆猜测,能不能直接保证异或和都等于0呢,这样我们就可以轻易的保证满足题目条件了.而且等于0这个值也比较特殊,大概率是突破口.
那么此时我们就需要保证每2*2的矩阵异或和等于即可,考虑从0开始填矩阵,我们先填满矩阵的第一行,$0,1,2,3,4,....m-1$,因为我们需要保证最后的异或和等于0,那么就意味着我们的第二行的两个数字必须包括上一行的二进制位.我们不妨对于第一行的数字加上一个只有首位的值.例如对于$0,1$来说,我们第二行构造出$1000+0,1000+1$,这样的话就可以满足异或和等于0了.对于每一个左右相邻数字,我们异或出来最终剩下的就是第一行相邻的数字,再于上下相邻异或,最终都是0

但是此时我们加上这一个二进制位必须比原数字的最高位高才行也就是不能破坏原来的第一行的数字.此时我们第一行数字最大也就是200,所以此时我们采用$2^8$即可

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int T;
int a[maxn];
int main() {T=read();while(T--) {int n=read(),m=read();cout<<n*m<<endl;for(int i=1;i<=m;i++) {a[i]=i-1;printf("%d ",a[i]);}printf("\n");for(int i=2;i<=n;i++) {for(int j=1;j<=m;j++) {a[j]+=pow(2,8);printf("%d ",a[j]);}printf("\n");}}return 0;
}

D题: Buying gifts

本题题意也比较清明.理解题意十分简单.

对于本题,n的范围为500000,不难感觉应该是一个$nlogn$算法

考虑对数对<ai,bi>按照ai的大小从小到大进行排序
我们可以考虑枚举A组最大的数字.那么对于A组后面的所有数对,因为当前我们最大值是Ai,所以对于Ai后面的所有数对我们肯定都是选择Bi.对于Ai前面的数对我们可以随意选择,

此时我们的目的是需要max(b)-ai最小.那么对于$i$后面的所有bj来说,此时我们可以记录后缀最大值来轻松的找出最大值.那么此时我们只需要找到前缀最大值即可.对于$i$前面的所有数对我们进行分类讨论
因为不知道我们的bi的最大值是不是大于ai,所以我们需要找到$i$前面所有$bj$中恰好大于和小于$ai$的数,该操作使用$set$进行,$set$可以轻松进行插入和二分查找操作
如果存在比ai大的数字,那么此时我们将其后面的最大值进行比较,因为最终的答案需要选出最大的那个数减去ai,我们后面的所有数字又是必选的,所以假如后面的数字比较大,我们此时答案只能是是后面最大值减去ai(选更大的肯定更不优),反之我们选择考虑选择前面的那么查询出来的值.因为此时的值更为贴近我们的ai.(注意此时我们只是选了一下,因为存在一种可能就是后面的最大值才是最贴近的,所以在最后还需要比较一下)

如果存在比ai小的数字,我们的讨论方法类似,此处就不再赘述了

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int T;
vector<pair<int,int> >v;
set<int>se;
int per_mx[maxn];
int main() {T=read();while(T--) {int n=read();v.clear();se.clear();for(int i=0;i<=n+1;i++) {per_mx[i]=0;}for(int i=1;i<=n;i++) {int a=read(),b=read();v.push_back({a,b});}sort(v.begin(),v.end());for(int i=n-1;i>=0;i--) {if(i==n-1) per_mx[i]=v[i].second;else per_mx[i]=max(per_mx[i+1],v[i].second);}int ans=int_INF;for(int i=0;i<=n-1;i++) {int c=int_INF;auto pos=se.lower_bound(v[i].first);if(pos!=se.end()) {if(per_mx[i+1]>=*pos) {c=min(c,abs(v[i].first-per_mx[i+1]));}else {c=min(c,abs(v[i].first-*pos));}}if(pos!=se.begin()) {pos--;if(per_mx[i+1]>=*pos) {c=min(c,abs(v[i].first-per_mx[i+1]));}else {c=min(c,abs(v[i].first-*pos));}}if(i!=n-1) c=min(c,abs(v[i].first-per_mx[i+1]));se.insert(v[i].second);ans=min(ans,c);}cout<<ans<<endl;}return 0;
}