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