在$CF$水题の记录

CF1158C

题意:有排列p, 令(nxt_i)为(p_i)右侧第一个大于(p_i)的数的位置，若不存在则(nxt_i=n+1)

现在整个p和nxt的一部分丢失了，请根据剩余的nxt，构造出一个符合情况的p，输出任意一解。

---

使有解的充要条件是对于每一个i不存在(jin(i,nex_i))满足(nex_j>nex_i)

也就是说对于每个(i)向(nxt_i)连一条边，然后没有两条边相交

对于点(i)向(nex_i)和满足(j<i wedge nex_j>nex_i)的最小的j连边

这样的话就是一个拓扑图

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define M 2100001
#define N 500010
using namespace std;
int n,m,k,a[N],d[M],s[N],ver[N],t[N],T,B;
queue<int> q;
void ins(int now,int l,int r,int k,int x)
{
if(l==r)
{
d[now]=k;
return;
}
int mid=(l+r)>>1;
if(x<=mid) ins(now*2,l,mid,k,x);
else ins(now*2+1,mid+1,r,k,x);
d[now]=1;
}
int ask(int now,int l,int r,int L)
{
if(l==r) return d[now];
int mid=(l+r)>>1, k=0;
if(L<=mid && d[now*2]) k=ask(now*2,l,mid,L);
if(!k)return ask(now*2+1,mid+1,r,L);
return k;
}
void rb(int now,int l,int r)
{
if(!d[now]) return ;
d[now]=0;
if(l==r) return ;
int mid=(l+r)>>1;
rb(now*2,l,mid);
rb(now*2+1,mid+1,r);
}
int main()
{
scanf("%d",&T);
for(T;T;T--)
{
B=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]==-1) a[i]=i+1;
}
for(int i=1;i<=n;i++)
{
k=ask(1,1,n+1,i+1);
if(k && a[k]<a[i])
{
B=1;
break;
}
ins(1,1,n+1,i,a[i]);
s[a[i]]++;
if(!k) continue;
ver[i]=k; s[k]++;
}
if(!B)
{
for(int i=1;i<=n;i++) if(!s[i]) q.push(i);
k=0;
while(q.size())
{
int x=q.front(); q.pop();
s[ver[x]]--; s[a[x]]--;
if(!s[ver[x]]) q.push(ver[x]);
if(!s[a[x]]) q.push(a[x]);
t[x]=++k;
}
if(k!=n+1) B=1;
}
if(B) printf("-1");
else for(int i=1;i<=n;i++) printf("%d ",t[i]);
printf("n");
for(int i=1;i<=n+1;i++) t[i]=s[i]=ver[i]=a[i]=0;
rb(1,1,n+1);
}
}

---

CF1163E

首先存在p的要求是能建一个满的线性基而且线性基用到的数不能大于等于(2^x)

这很好解决，只要把所有数排序后从小到大的插进线性基，然后每次删掉所有原数大于(2^x)的数并调整x

至于输出p，由于能插进线性基里的数都是线性不相关的，随便输出一下就行

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int M = 410001;
int n,m,k,a[M],d[30],fr[30],b[M];
void ins(int x,int t)
{
for(int i=20;i>=0;i--)
{
if(!((x>>i)&1)) continue;
if(!d[i]){fr[i]=t, d[i]=x; k++; return;}
x^=d[i];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+1+n);
for(int i=1;i<=n;i++) ins(a[i],a[i]);
k=0;
while(d[k]) k++;
while(1 && k)
{
int B=1;
for(int i=0;i<k;i++)
if(fr[i]>=1<<k)
{
B=0; k=i;
break;
}
if(B) break;
}
printf("%dn",k);
int x=0;
for(int i=1;i<=1<<k;i++)
{
printf("%d ",x); b[x]=1;
for(int j=0;j<k;j++) if(!b[x^fr[j]])
{
x=x^fr[j];
break;
}
}
}

---

update after CF1173

很好，我！expert！掉rating了！！
成为pupil指日可待==

CF1173C

由于牌堆只能从最后插牌，所以插牌方法非常显然

首先特判一下牌堆有没有一个合法的后缀，如果有的话再判断一下手中的牌和合法后缀之前的牌的排列顺序能不能有效的继续续下去

然后排除了以上情况就可以直接找(max(i-b_i))就是最早在哪个时刻开始往里按顺序加牌构造递增序列

#include<iostream>
#include<cstdio>
using namespace std;
int w,n,m,k,a[1000001],b[1000001],c[300001];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++) scanf("%d",&a[i]), c[a[i]]=i;
int B=0;
k=n;
while(k && a[k-1]==a[k]-1) k--;
if(a[k]==1 || a[k]==0) B=1;
if(a[n]==0) B=1;
if(B)
{
for(int i=1;i<k;i++)
if(a[i] && i-a[i]+a[n]+1>0) B=0;
if(B)
{
printf("%d",n-a[n]);
return 0;
}
}
B=0;
for(int i=1;i<=n;i++) if(a[i])B=max(B,i-a[i]+1);
printf("%d",B+n);
}

---

CF1173D

边不交叉的条件是每棵子树都要在一段连续的位置

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int M = 1000001;
const int P = 998244353;
int x,y,n,m,k, ver[M], nex[M], edge[M],cnt,A[M],head[M];
void add(int x,int y)
{
ver[++cnt]=y, nex[cnt]=head[x], head[x]=cnt;
ver[++cnt]=x, nex[cnt]=head[y], head[y]=cnt;
}
int dfs(int x,int fa)
{
int s=1, d=1;
for(int i=head[x];i;i=nex[i])
{
if(ver[i]==fa) continue;
d=(LL)d*dfs(ver[i],x)%P;
s++;
}
if(x!=1)return (LL)A[s]*d%P;
return (LL)A[s-1]*d%P;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
}
A[0]=1;
for(int i=1;i<=n;i++) A[i]=(LL)A[i-1]*i%P;
printf("%d",(LL)n*dfs(1,0)%P);
}

---

比赛的时候前三道题写的过于缓慢（尤其还读错题了什么的浪费提交次数==

导致sb题D的调试时间Tle了2min（就是10:07才写出来qaq

下次要记得合理安排时间==

惨惨

ps.一道题都没写的(asuldb)排名比窝和慎老师还高，然后还嘲讽窝掉rating?? 他合格考稳了

---

CF1179D

树形dp

基环树上的不在环上的每棵子树内的两个节点间只有一条路径，其他的是两条

然后就可以dp的找环上路径

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int M = 1100001;
const LL inf= 9999999999999999ll;
int head[M],n,m,k,cnt,x,y,ver[M],edge[M],nex[M],s[M],fr[M][2];
LL d[M][2],res=inf;
void add(int x,int y)
{
ver[++cnt]=y, nex[cnt]=head[x], head[x]=cnt;
ver[++cnt]=x, nex[cnt]=head[y], head[y]=cnt;
}
void dfs_(int x,int fa)
{
s[x]=1;
for(int i=head[x];i;i=nex[i])
{
if(ver[i]==fa) continue;
dfs_(ver[i],x);
s[x]+=s[ver[i]];
}
}
void dfs(int x,int fa)
{
if(s[x]==1) return;
d[x][0]=d[x][1]=inf;
for(int i=head[x];i;i=nex[i])
{
if(ver[i]==fa) continue;
dfs(ver[i],x);
LL k=d[ver[i]][0]+((LL)s[x]-s[ver[i]]-1)*((LL)s[x]-s[ver[i]])/2;
if(k<d[x][1])
{
d[x][1]=k;
fr[x][1]=ver[i];
}
if(d[x][1]<d[x][0])
{
swap(d[x][1],d[x][0]);
swap(fr[x][1],fr[x][0]);
}
}
res=min(res,d[fr[x][0]][0]+d[fr[x][1]][0]+((LL)n-s[fr[x][0]]-s[fr[x][1]])*((LL)n-s[fr[x][0]]-s[fr[x][1]]-1)/2);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
}
dfs_(1,0);
dfs(1,0);
printf("%I64d",(LL)n*n-n-res);
}