当前位置： 代码迷 >> 综合 >> [赛后总结]G2022 Regular Contest 07总结
  详细解决方案

[赛后总结]G2022 Regular Contest 07总结

热度：121   发布时间：2023-10-22 20:54:04.0

这场比赛的题很Educational，给出题人点赞!
Educational的意思就是题目都不怎么会做…
相信下下场的题目一定会更Educational的

赛时

有时间再更…

题解

T1-贸易(business)

CF724E Goods Transportation
tag:网络流-最小割+dp

题面

[赛后总结]G2022 Regular Contest 07总结

题解

算法1:30分

显然可以用网络流暴力建模。

算法2:100分

啊啊啊…我又把最小割给忘了。
我们利用最小割定理把原题转化为割图问题，然后对于每个点我们都有属于SSS部和属于TTT部两种可能。然后你就会发现可以直接用二维dp解决这个问题了。
具体地，对于属于SSS部的点iii，需要割掉它与1?(i?1)1-(i-1)1?(i?1)之间容量为ccc的边，以及iii与TTT之间的边，对于属于TTT部的点iii，只需要割掉它与SSS之间的边即可。
复杂度:O(n2)O(n^2)O(n2)

Other

出题人为什么习惯把暴力分给这么少。
这道题最好的骗分方式是30分网络流+?分贪心乱搞。虽然最终结果是由于数据随机生成被贪心乱搞骗了75分…

T2-中位数(median)

ARC101B Median of Medians
tag:二分答案+树状数组
比较简单的一道题，略。

T3-山楂(hawthorn)

51nod 1577 异或凑数
tag:线性基

题面

[赛后总结]G2022 Regular Contest 07总结

题解

算法1:25分

线段树暴力维护线性基即可。

算法2:40分

注意到线性基中的每个元素都是原数组中的一个数(说个笑话其实我一其实一直都不知道)。所以我们可以维护包含前iii个数的线性基BiB_iBi?，且这个线性基满足插入的位置最靠后。这样我们每次查询就在BrB_rBr?中判断线性基中pos>=lpos>=lpos>=l的元素是否能够组成vvv即可。
对于这个数据规模我们可以直接从后往前暴力插入BiB_iBi?即可。
复杂度:O(nk2)O(nk^2)O(nk2)。

算法3:100分

考虑从Bi?1B_{i-1}Bi?1?推到BiB_iBi?，注意到线性基的相同位置的等效性，我们可以直接将新插入的数为111的位置和原位置的数交换，这样同样可以维持线性基的性质。
复杂度:O(nk)O(nk)O(nk)。

Other

没想到是直接以lemon上的时间为准，再加上我没算复杂度，以为线段树暴力维护线性基可以直接过=_=。
看来还是我太天真了qwq。
这道题目需要深入地理解线性解才行。
Emmm…这种东西其实可以叫可持久化线性基吧qwq…

实现

T1-business

30pts

/*Lower_Rating*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
using namespace std;#define LL long long
#define DB double
#define MOD 1000000007
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 10000
#define MAXM 200000
#define eps 1e-10
#define INF 1000000000
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(LL a,int b){
    return a*b%MOD;}int n,c,S,T;LL ans;
int dep[MAXN+5],ecnt;int head[MAXN+5],cur[MAXN+5];
struct edge{
    int to,nxt,cap;
}e[MAXM+5];
void link(int u,int v,int cap){
    e[++ecnt]=(edge){
    v,head[u],cap};head[u]=ecnt;e[++ecnt]=(edge){
    u,head[v],0};head[v]=ecnt;
}queue<int> Q;
bool BFS(){
    mem(dep,0),mem(cur,0);dep[S]=1,Q.push(S);while(!Q.empty()){
    int x=Q.front();Q.pop();for(int i=head[x];i;i=e[i].nxt){
    int v=e[i].to;if(dep[v]||!e[i].cap)continue;dep[v]=dep[x]+1;Q.push(v);}}return dep[T];
}
int dinic(int x,int flow){
    int nf=flow;if(x==T)return flow;if(!cur[x])cur[x]=head[x];for(int &i=cur[x];i;i=e[i].nxt){
    int v=e[i].to;if(dep[x]+1!=dep[v]||!e[i].cap)continue;int tmp=dinic(v,min(e[i].cap,nf));e[i].cap-=tmp,e[i^1].cap+=tmp;nf-=tmp;if(!nf)break;}return flow-nf;
}int main(){
    freopen("business.in","r",stdin);freopen("business.out","w",stdout);n=read(),c=read(),ecnt=1;if(c==0){
    for(int i=1;i<=n;i++)dep[i]=read();for(int i=1;i<=n;i++)ans+=min(dep[i],(int)read());printf("%lld",ans);return 0;}S=0,T=n+1;for(int i=1;i<=n;i++){
    int p=read();link(S,i,p);}for(int i=1;i<=n;i++){
    int s=read();link(i,T,s);}for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)link(i,j,c);while(BFS())ans+=dinic(S,INF);printf("%lld",ans);
}

100pts

/*Lower_Rating*/
/*Ex*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
using namespace std;#define LL long long
#define DB double
#define MOD 1000000007
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 10000
#define MAXM 200000i
#define eps 1e-10
#define INF 10000000000000
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(LL a,int b){
    return a*b%MOD;}int n,p;LL c;
LL dp[2][MAXN+5],ans;
int s[MAXN+5],t[MAXN+5];int main(){
    n=read(),c=read(),ans=INF;for(int i=1;i<=n;i++)s[i]=read();for(int i=1;i<=n;i++)t[i]=read();for(int i=1;i<=n;i++,p^=1){
    mem(dp[p^1],0);dp[p^1][0]=dp[p][0]+s[i];dp[p^1][i+1]=INF;for(int j=i;j>=1;j--)dp[p^1][j]=min(dp[p][j-1]+t[i],dp[p][j]+c*j+s[i]);}for(int i=0;i<=n;i++)ans=min(ans,dp[p][i]);printf("%lld",ans);
}

T2-median

/*Lower_Rating*/
/*Ex*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
using namespace std;#define LL long long
#define DB double
#define MOD 1000000007
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 100000
#define eps 1e-10
#define INF 1000000000000
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(LL a,int b){
    return a*b%MOD;}int n,a[MAXN+5],p[MAXN+5];struct BIT{
    int C[(MAXN<<1)+5];int lowbit(int x){
    return x&(-x);}void Init(){
    mem(C,0);}void Insert(int x,int v){
    while(x<=(MAXN<<1)){
    C[x]+=v;x+=lowbit(x);}}int Query(int x){
    int res=0;while(x){
    res+=C[x];x-=lowbit(x);}return res;}
}T;bool check(int val){
    int sum=0;LL res=0,tot=1LL*n*(n+1)/2;T.Init();T.Insert(MAXN,1);for(int i=1;i<=n;i++){
    if(a[i]>=val)sum++;else sum--;res+=T.Query(sum+MAXN);T.Insert(sum+MAXN,1);}return res>=(tot-res);
}
int main(){
    freopen("median.in","r",stdin);freopen("median.out","w",stdout);n=read();for(int i=1;i<=n;i++)a[i]=read(),p[i]=a[i];sort(p+1,p+n+1);int l=1,r=n,ans=0;while(l<=r){
    int mid=(l+r)>>1;if(check(p[mid]))l=mid+1,ans=mid;else r=mid-1;}printf("%d",p[ans]);
}

T3-hawthorn

25pts

/*Lower_Rating*/
/*Ex*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
using namespace std;#define LL long long
#define DB double
#define MOD 1000000007
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 500000
#define MAXK 30
#define eps 1e-10
#define INF 1000000000000
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(LL a,int b){
    return a*b%MOD;}struct Base{
    int d[MAXK+2];void Init(){
    mem(d,0);}void Insert(int x){
    for(int i=MAXK-1;i>=0;i--)if(x&(1<<i)){
    if(d[i])x^=d[i];else{
    d[i]=x;break;}}}bool Query(int v){
    for(int i=MAXK-1;i>=0;i--)if((v>>i)&1)v^=d[i];return v==0;}
}p[(MAXN<<2)+5],tmp;int n,q,a[MAXN+5];
struct Seg_tree{
    #define lc (x<<1)#define rc (x<<1|1)#define mid (l+r>>1)void merge(Base &x,Base &y){
    //鏆村姏鍚堝苟...for(int i=0;i<MAXK;i++)if(y.d[i])x.Insert(y.d[i]);}void Build(int x,int l,int r){
    if(l==r){
    p[x].Insert(a[l]);return ;}Build(lc,l,mid),Build(rc,mid+1,r);merge(p[x],p[lc]),merge(p[x],p[rc]);}void Query(int x,int l,int r,int L,int R){
    if(r<L||R<l)return ;if(L<=l&&R>=r){
    merge(tmp,p[x]);return ;}Query(lc,l,mid,L,R),Query(rc,mid+1,r,L,R);}
}T;int main(){
    freopen("hawthron.in","r",stdin);freopen("hawthron.out","w",stdout);n=read();for(int i=1;i<=n;i++)a[i]=read();T.Build(1,1,n);q=read();while(q--){
    tmp.Init();int l=read(),r=read();LL k=read();T.Query(1,1,n,l,r);printf("%s\n",tmp.Query(k)?"Koyi":"Budexin");}
}

100pts

/*Lower_Rating*/
/*Ex*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
using namespace std;#define LL long long
#define DB double
#define MOD 1000000007
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 500000
#define MAXK 30
#define eps 1e-10
#define INF 1000000000000
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(LL a,int b){
    return a*b%MOD;}int n,q,a[MAXN+5];struct Base{
    Pr d[MAXK+2];void Insert(int x,int pos){
    Pr cur=make_pair(x,pos);for(int i=MAXK-1;i>=0;i--)if(cur.X&(1<<i)){
    if(!d[i].X){
    d[i]=cur;break;}if(d[i].Y<cur.Y)swap(d[i],cur);cur.X^=d[i].X;}}bool Query(int v,int l){
    for(int i=MAXK-1;i>=0;i--)if(((v>>i)&1)&&d[i].Y>=l)v^=d[i].X;return v==0;}
}B[MAXN+5];int main(){
    //freopen("hawthorn.in","r",stdin);//freopen("hawthorn.out","w",stdout);n=read();for(int i=1;i<=n;i++){
    a[i]=read();B[i]=B[i-1];B[i].Insert(a[i],i);}q=read();while(q--){
    int l=read(),r=read(),v=read();printf("%s\n",B[r].Query(v,l)?"YES":"NO");}
}
  相关解决方案

代码迷 - 您身边的软件异常，代码异常，编程异常助手（发现，解决，分享）
Copyright © 2009-2013 DAIMAMI.COM. All rights reserved.