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

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;
}


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