VP的时候坐了大牢。。。

但题目质量还是挺不错的

A

考虑开两个set,每个set里存的是相同price的物品

每次遍历小的set里的元素求答案

#include <set>
#include <cstdio>
#include <algorithm>
using namespace std;
#define IT set<data>::iterator
const int N=500010;
struct data{
	int p,h,id;
	bool operator < (const data &a)const{
		return h<a.h;
	}
}p[N],q[N];
multiset<data>S1,S2;
int i,j,k,n,m,x,y,t;
int nx1[N],nx2[N];
int ans1[N],ans2[N];
bool cmp(const data&a,const data&b){
	return a.p<b.p;
}
int main(){
	//p:front;q:back
	//nx1:front;nx2:back
	scanf("%d",&n);
	for (i=1;i<=n;i++)scanf("%d",&q[i].p);
	for (i=1;i<=n;i++)scanf("%d",&q[i].h);
	for (i=1;i<=n;i++)p[i].id=i;
	for (i=1;i<=n;i++)scanf("%d",&p[i].p);
	for (i=1;i<=n;i++)scanf("%d",&p[i].h);
	for (i=1;i<=n;i++)q[i].id=i;
	sort(p+1,p+1+n,cmp);
	sort(q+1,q+1+n,cmp);
	nx1[n]=n+1;for (i=n-1;i>=1;i--)if (p[i].p==p[i+1].p)nx1[i]=nx1[i+1];else nx1[i]=i+1;
	nx2[n]=n+1;for (i=n-1;i>=1;i--)if (q[i].p==q[i+1].p)nx2[i]=nx2[i+1];else nx2[i]=i+1;
	int l1=1,l2=1;
	while (l1<=n&&l2<=n){
		if (S1.empty()){
			for (i=l1;i<nx1[l1];i++){p[i].h=-p[i].h;S1.insert(p[i]);p[i].h=-p[i].h;}
		}
		if (S2.empty()){
			for (i=l2;i<nx2[l2];i++){S2.insert(q[i]);}
		}
		if (S1.size()<=S2.size()){
			for (IT it1=S1.begin();it1!=S1.end();it1++){
				data t1=*it1;t1.h=-t1.h;
				IT t2=(S2.upper_bound(t1));
				if (t2==S2.end()){
					printf("impossible");
					return 0;
				}
				ans1[l1]=t1.id;ans2[l1]=(*t2).id;
				S2.erase(t2);
				l1++;
			}
			S1.clear();
			l2=l1;
		}
		else{
			for (IT it1=S2.begin();it1!=S2.end();it1++){
				data t1=*it1;t1.h=-t1.h;
				IT t2=(S1.upper_bound(t1));
				if (t2==S2.end()){
					printf("impossible");
					return 0;
				}
				ans1[l2]=(*t2).id;ans2[l2]=t1.id;
				S1.erase(t2);
				l2++;
			}
			S2.clear();
			l1=l2;
		}
	}
	for (i=1;i<=n;i++)printf("%d ",ans2[i]);printf("\n");
	for (i=1;i<=n;i++)printf("%d ",ans1[i]);printf("\n");
	return 0;
}

D

我的方法是对于每种括号线段树判断每个循环是否满足条件,再用树状数组来统计答案,复杂度NlogN

#include <cstdio>
#include <vector>
#include <algorithm>
#define pb push_back
using namespace std;
const int N=1000010;
struct data1{
    int l,r,ans,lazy;
}T[N*8];
struct gene{
    int id,index,type;
}p[N];
vector<gene>v[N];
int i,j,k,n,m,x,y,t,s[N*2],num,ans[N*2];
bool cmp(const gene&a,const gene&b){
    if (a.id!=b.id)return a.id<b.id;
    return a.index<b.index;
}
void pushdown2(int i){
    T[i*2].ans+=T[i].lazy;T[i*2+1].ans+=T[i].lazy;
    T[i*2].lazy+=T[i].lazy;T[i*2+1].lazy+=T[i].lazy;
    T[i].lazy=0;
}
void build2(int i,int l,int r){
    T[i]=(data1){l,r,s[l]};
    if (l==r)return;
    int mid=l+r>>1;
    build2(i*2,l,mid);build2(i*2+1,mid+1,r);
    T[i].ans=min(T[i*2].ans,T[i*2+1].ans);
}
int check(int i,int l,int r){
    if (T[i].l==l&&T[i].r==r)return T[i].ans;
    pushdown2(i);
    int mid=T[i].l+T[i].r>>1;
    if (r<=mid)return check(i*2,l,r);
    else if (l>mid)return check(i*2+1,l,r);
    else return min(check(i*2,l,mid),check(i*2+1,mid+1,r));
}
void update(int l,int r){
    for (int i=l;i<=n*2;i+=(i&-i))
        ans[i]++;
    for (int i=r+1;i<=n*2;i+=(i&-i))
        ans[i]--;
}
int getans(int x){
    int t=0;
    for (int i=x;i;i-=(i&-i))
        t+=ans[i];
    return t;
}
void modify(int i,int l,int r,int t){
    if (T[i].l==l&&T[i].r==r){
        T[i].ans+=t;
        T[i].lazy+=t;
        return;
    }
    pushdown2(i);
    int mid=T[i].l+T[i].r>>1;
    if (r<=mid)modify(i*2,l,r,t);
    else if (l>mid)modify(i*2+1,l,r,t);
    else{
        modify(i*2,l,mid,t);
        modify(i*2+1,mid+1,r,t);
    }
    T[i].ans=min(T[i*2].ans,T[i*2+1].ans);
}
int main(){
    scanf("%d",&n);
    for (i=1;i<=n;i++){
        char ch=getchar();
        while (ch!='s'&&ch!='e')ch=getchar();
        scanf("%d",&x);
        p[i]=(gene){x,i,ch=='s'};
    }
    sort(p+1,p+1+n,cmp);
    for (i=1;i<=n;i++){
        if (p[i].id!=p[i-1].id)++num;
        v[num].pb(p[i]);
    }
    for (i=1;i<=num;i++){
        k=v[i].size();
        for (j=0;j<k;j++){
            gene tmp=v[i][j];tmp.index+=n;
            v[i].pb(tmp);
        }
    }
    for (i=1;i<=num;i++){
        for (k=1;k<=v[i].size();k++)s[k]=s[k-1]+(v[i][k-1].type==1?1:-1);
        // for (k=1;k<=v[i].size();k++)printf("%d ",s[k]);printf("\n");
        if (s[v[i].size()]!=0)continue;
        // for (k=0;k<v[i].size();k++)printf("%d %d %d\n",v[i][k].id,v[i][k].type,v[i][k].index);
        // printf("===\n");
        build2(1,1,v[i].size());
        int len=v[i].size()/2;
        for (k=len;k<len*2;k++){
            int l=check(1,k-len+1,k);
            // printf("-->%d\n",l);
            // for (int t1=k-len+1;t1<=k;t1++)printf("%d ",check(1,t1,t1));printf("\n");
            if (l==0&&check(1,k,k)==0){
                // printf("$$$%d %d %d\n",k,v[i][k-1].index,v[i][k].index-1);
                update(v[i][k-1].index+1,v[i][k].index);
            }
            if (v[i][k-len].type==0){
                modify(1,k-len+2,len*2,1);
            }
            else{
                modify(1,k-len+2,len*2,-1);
            }
        }
    }
    int ANS1=0,ANS2=1;
    for (i=n+1;i<=n*2;i++){
        int tmp=getans(i)+getans(i-n);
        // printf("###%d %d\n",i,tmp);
        if (tmp>ANS1){
            ANS1=tmp;
            ANS2=i-n;
        }
    }
    printf("%d %d\n",ANS2,ANS1);
}

E

对边双缩点,然后分开考虑是树上全是单点还是有缩过的点,分类讨论一下

#include <map>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#define mp make_pair
using namespace std;
const int N=1000010;
int i,j,k,n,m,x,y,t,ned[N];
int mark[N];
int a[N*2],fi[N],ne[N*2],la[N*2],is[N*2],d[N],fr[N],fir[N];
int dfn[N],low[N],s[N],in[N],tim,cnt,id[N],num[N],fa[N],ok[N];
vector<int>v[N],V[N];
map<pair<int,int>,pair<int,int> >Mp;
void add(int x,int y){
    k++;a[k]=y;fr[k]=x;
    if (fi[x]==0)fi[x]=k;else ne[la[x]]=k;
    la[x]=k;
}
void tarjan(int x,int fa){
    low[x]=dfn[x]=++tim;s[++s[0]]=x;mark[x]=1;
    for (int i=fi[x];i;i=ne[i]){
        int j=a[i];
        if (!dfn[j]){
            tarjan(j,x);
            low[x]=min(low[x],low[j]);
            if (dfn[x]<low[j])is[i]=is[i^1]=1;
        }
        else if (j!=fa)low[x]=min(low[x],dfn[j]);
    }
    if (dfn[x]==low[x]){
        ++cnt;
        int y;
        do{
            y=s[s[0]--];
            id[y]=cnt;num[cnt]++;
        }while (y!=x);
    }
}
void ADD(int x,int y,int X,int Y){
    // printf("%d %d %d %d\n",x,y,X,Y);
    fir[x]=y;fir[y]=x;
    v[x].push_back(y);v[y].push_back(x);
    Mp[mp(x,y)]=mp(X,Y);
    Mp[mp(y,x)]=mp(Y,X);
    d[x]++;d[y]++;
}
int ans;
pair<int,int> Ans[N];
bool dfs(int x,int fa){
    mark[x]=1;int need=0;
    if (v[x].size()==1)return num[x]==1;
    for (int i=0;i<v[x].size();i++)
        if (v[x][i]!=fa){
            if (dfs(v[x][i],x)){
                need=1;
                if (num[x]>1){
                    Ans[++ans]=Mp[mp(x,v[x][i])];
                }
                else if (fa==-1){
                    Ans[++ans]=Mp[mp(x,v[x][i])];
                }
            }
        }
    return (need==1&&num[x]==1);
}
void PRE(int x){
    mark[x]=1;s[++s[0]]=x;
    for (int i=0;i<v[x].size();i++)
        if (!mark[v[x][i]]){
            PRE(v[x][i]);
        }
}
bool dfs1(int x,int fa){
    int flag=1;
    for (int i=0;i<v[x].size();i++)
        if (v[x][i]!=fa){
            flag&=dfs1(v[x][i],x);
        }
    if (num[x]>1)flag=0;
    return ok[x]=flag;
}
void dfs2(int x,int fa){
    for (int i=0;i<v[x].size();i++)
        if (v[x][i]!=fa){
            dfs2(v[x][i],x);
            if (ok[v[x][i]]&&!ok[x]){
                Ans[++ans]=Mp[mp(x,v[x][i])];
            }
        }
}
int main(){
    scanf("%d%d",&n,&m);
    k=1;
    for (i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    for (i=1;i<=n;i++)
        if (!mark[i]){
            tarjan(i,-1);
        }
    for (i=1;i<=k;i+=2)
        if (is[i]){
            ADD(id[fr[i]],id[a[i]],fr[i],a[i]);
        }
    memset(mark,0,sizeof mark);
    for (i=1;i<=n;i++)
        if (!mark[i]){
            s[0]=0;
            PRE(i);int rt=-1;
            for (k=1;k<=s[0];k++)
                if (num[s[k]]!=1){
                    rt=s[k];
                }
            if (rt==-1){
                for (k=1;k<=s[0];k++)
                    if (d[s[k]]==1){
                        // printf("!!!%d %d\n",s[k],fir[s[k]]);
                        Ans[++ans]=Mp[mp(s[k],fir[s[k]])];
                    }
            }
            else{
                dfs1(rt,-1);
                dfs2(rt,-1);
            }
        }
    printf("%d\n",ans);
    sort(Ans+1,Ans+1+ans);
    for (i=1;i<=ans;i++)printf("%d %d\n",Ans[i].first,Ans[i].second);
    return 0;
}


告别纷扰,去寻找生活的宝藏。