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