Lvat_s Blog

直接Splay上

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int n,m,a[N];
 
struct Node{
int v,rev,siz;
Node *ch[2],*fa;
Node(){}
Node(int vx);
void Pushdown();
void Pushup();
}*root,*Null;
 
Node::Node(int vx){
v=vx;
siz=1;
rev=0;
ch[0]=ch[1]=fa=Null;
}
 
Node *GetNull(){
Node *p=new Node(0);
p->siz=0;
p->ch[0]=p->ch[1]=p->fa=p;
return p;
}
 
void Node::Pushdown(){
if(rev){
    rev=0;
    if(ch[0]!=Null)ch[0]->rev^=1;
    if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0]->ch[0],ch[0]->ch[1]);
    swap(ch[1]->ch[0],ch[1]->ch[1]);
}
}
 
void Node::Pushup(){
siz=ch[0]->siz+ch[1]->siz+1;
}
 
void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(z!=Null)z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}
 
void Splay(Node *x,Node *place){
while(x->fa!=place){
    Node *y=x->fa,*z=y->fa;
    if(z==place)Rotate(x,y->ch[0]==x);
    else {
        if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
        else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
        else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
        else {Rotate(y,0);Rotate(x,0);}
    }
}
if(place==Null)root=x;
}
 
Node *Find(Node *splay,int k){
splay->Pushdown();
if(splay->ch[0]->siz+1==k)return splay;
if(splay->ch[0]->siz>=k)return Find(splay->ch[0],k);
return Find(splay->ch[1],k-1-splay->ch[0]->siz);
}
 
Node *GetSeq(int l,int r){
Node *Tp1=Find(root,l);
Splay(Tp1,Null);
Node *Tp2=Find(root,r+2);
Splay(Tp2,root);
return Tp2->ch[0];
}
 
Node *Build(int l,int r){
if(l>r)return Null;
int mid=l+r>>1;
Node *splay=new Node(a[mid]);
splay->ch[0]=Build(l,mid-1);
if(splay->ch[0]!=Null)splay->ch[0]->fa=splay;
splay->ch[1]=Build(mid+1,r);
if(splay->ch[1]!=Null)splay->ch[1]->fa=splay;
splay->Pushup();
return splay;
}
 
void PrintTree(Node *rt){
if(rt==Null)return;
rt->Pushdown();
if(rt->ch[0]!=Null)PrintTree(rt->ch[0]);
if(rt->v)printf("%d ",rt->v);
if(rt->ch[1]!=Null)PrintTree(rt->ch[1]);
}
 
void Reverse(int l,int r){
Node *seq=GetSeq(l,r),*fat=seq->fa;
seq->rev^=1;
swap(seq->ch[0],seq->ch[1]);
fat->Pushup();
fat->fa->Pushup();
}
 
int main(){
freopen("3223.in","r",stdin);
freopen("3223.out","w",stdout);
scanf("%d %d",&n,&m);
Null=GetNull();
for(int i=1;i<=n;i++)a[i+1]=i;
root=Build(1,n+2);
for(int i=1;i<=m;i++){
    int l,r;
    scanf("%d %d",&l,&r);
    Reverse(l,r);
}
PrintTree(root);
return 0;
}

四边形不等式优化

我一开始直接写了一个旋转卡壳然后WA了

搜了一下题解，发现这样不对(有可能点会靠后一些)

需要优化

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=500005;
int n,T,ans[N];
 
struct Point{
long long x,y,id;
Point(){}
Point(long long sa,long long sb){x=sa;y=sb;}
friend Point operator+(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
friend Point operator-(Point A,Point B){return Point(A.x-B.x,A.y+B.y);}
friend Point operator*(Point A,long long B){return Point(A.x*B,A.y*B);}
friend long long operator*(Point A,Point B){return A.x*B.y-A.y*B.x;}
}poi[2*N];
 
long long Dist(Point A,Point B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}
 
bool cmp(int i,int j,int k){
long long x=Dist(poi[i],poi[j]),y=Dist(poi[i],poi[k]);
if(j<i || j>i+n)x=-x;
if(k<i || k>i+n)y=-y;
return x==y?poi[j].id>poi[k].id:x<y;
}
 
void Find(int l,int r,int L,int R){
if(l>r)return;
int mid=l+r>>1,M=L;
for(int i=L+1;i<=R;i++)if(cmp(mid,M,i))M=i;
ans[mid]=poi[M].id;
Find(l,mid-1,L,M);Find(mid+1,r,M,R);
}
 
int main(){
freopen("2739.in","r",stdin);
freopen("2739.out","w",stdout);
scanf("%d",&T);
while(T--){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld %lld",&poi[i].x,&poi[i].y),poi[i].id=i;
    if(n==1){puts("1");continue;}
    if(n==2){puts("2\n1");continue;}
    for(int i=n+1;i<=2*n;i++)poi[i]=poi[i-n];
    Find(1,n,1,n<<1);
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
}
return 0;
}

模版题

每个点只向每个象限里最近的点连边

离散化后树状数组维护就好了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const long long N=50005,LIMIT=1000000000,INF=210000000000000ll;
 
long long n,f[N],Fir[10*N],Sec[10*N],cnt,Line[10*N],Num[10*N],tot,ans;
 
struct Point{
long long x,y,id;
friend bool operator<(Point A,Point B){return (A.x<B.x)|(A.x==B.x && A.y<B.y);}
}poi[N];
 
struct Edge{
long long x,y,len;
Edge(){}
Edge(long long sa,long long sb,long long sc){x=sa;y=sb;len=sc;}
friend bool operator<(Edge A,Edge B){return A.len<B.len;}
}e[20*N];
 
long long Find(long long x){return f[x]==x?x:f[x]=Find(f[x]);}
void Union(long long x,long long y){if(x>y)f[x]=y;else f[y]=x;}
long long lowbit(long long x){return x&(-x);}
void AddBIT(long long x,long long y,long long z){while(x){if(Fir[x]>y){Fir[x]=y;Sec[x]=z;}x-=lowbit(x);}}
long long QueBIT(long long x){long long Mx=LIMIT*2,Ex=0;while(x<=n){if(Mx>Fir[x]){Mx=Fir[x];Ex=Sec[x];}x+=lowbit(x);}return Ex;}
long long Abs(long long x){return x>0?x:-x;}
long long Dist(Point A,Point B){return Abs(A.y-B.y)+Abs(A.x-B.x);}
 
int main(){
freopen("2177.in","r",stdin);
freopen("2177.out","w",stdout);
scanf("%lld",&n);
for(long long i=1;i<=n;i++){scanf("%lld %lld",&poi[i].x,&poi[i].y);poi[i].id=i;}
for(long long i=1;i<=4;i++){
    if(i==3)for(long long i=1;i<=n;i++)poi[i].x=LIMIT-poi[i].x;
    if(i==2 || i==4)for(long long i=1;i<=n;i++)swap(poi[i].x,poi[i].y);
    sort(poi+1,poi+n+1);
    for(long long i=1;i<=n;i++)Line[i]=poi[i].y-poi[i].x;
    sort(Line+1,Line+n+1);
    for(long long i=1;i<=n;i++)Num[i]=lower_bound(Line+1,Line+n+1,poi[i].y-poi[i].x)-Line;
    for(long long i=1;i<=n;i++)Fir[i]=INF;
    for(long long i=n;i>=1;i--){
        long long Set=QueBIT(Num[i]);
        if(Set)e[++cnt]=Edge(poi[i].id,poi[Set].id,Dist(poi[i],poi[Set]));
        AddBIT(Num[i],poi[i].y+poi[i].x,i);
    }
}
sort(e+1,e+cnt+1);
for(long long i=1;i<=n;i++)f[i]=i;
for(long long i=1;i<=cnt && tot<n-1;i++){
    if(Find(e[i].x)!=Find(e[i].y)){
        tot++;
        Union(Find(e[i].x),Find(e[i].y));
        ans+=1ll*e[i].len;
    }
}
printf("%lld\n",ans);
return 0;
}

图上进行概率DP

先BFSn次算出每个点的最优前进点

然后对于每种情况DFS算期望

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
 
const int N=1005;
 
int n,m,en,h[N],deg[N],Cat,Mouse,D[N][N],P[N][N];
double f[N][N];
queue<int> Q;
 
struct Edge{
int b,next;
}e[N*2];
 
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
deg[sa]++;
}
 
void BFS(int S){
Q.push(S);
D[S][S]=0;
while(!Q.empty()){
    int u=Q.front(),tmp=P[S][u];
    Q.pop();
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(D[S][v]==-1 || (D[S][u]+1==D[S][v] && tmp<P[S][v])){
            D[S][v]=D[S][u]+1;
            if(!tmp)P[S][v]=v;
            else P[S][v]=tmp;
            Q.push(v);
        }
    }
}
}
 
double DP(int Cat,int Mouse){
if(f[Cat][Mouse])return f[Cat][Mouse];
if(Cat==Mouse)return f[Cat][Mouse]=0;
if(P[Cat][Mouse]==Mouse || P[P[Cat][Mouse]][Mouse]==Mouse)return f[Cat][Mouse]=1;
double Sum=DP(P[P[Cat][Mouse]][Mouse],Mouse);
for(int i=h[Mouse];i;i=e[i].next)Sum+=DP(P[P[Cat][Mouse]][Mouse],e[i].b);
return f[Cat][Mouse]=Sum/(deg[Mouse]+1)+1;
}
 
int main(){
freopen("1415.in","r",stdin);
freopen("1415.out","w",stdout);
memset(D,-1,sizeof(D));
scanf("%d %d %d %d",&n,&m,&Cat,&Mouse);
for(int i=1;i<=m;i++){
    int sa,sb;
    scanf("%d %d",&sa,&sb);
    AddEdge(sa,sb);
    AddEdge(sb,sa);
}
for(int i=1;i<=n;i++)BFS(i);
printf("%.3lf\n",DP(Cat,Mouse));
return 0;
}

使用n!近似公式算一下就可以了

注意特判

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
 
const long double Pi=acos(-1),e=exp(1),eps=1e-10;
long long n,k;
 
long double log(long double a,long double b){return log(a)/log(b);}
 
int main(){
freopen("3000.in","r",stdin);
freopen("3000.out","w",stdout);
while(scanf("%lld %lld",&n,&k)!=EOF){
    double ans=0;
    if(n<=10000){
        for(int i=1;i<=n;i++)ans+=log(i);
        ans/=log(k);
        ans=ceil(ans+eps);
        printf("%.0lf\n",ans);
    }
    else printf("%lld\n",(long long)(0.5*log(2*Pi*n,k)+n*log(n,k)-n*log(e,k)+1));
}
return 0;
}

map直接上

其他同ZJOI2011 最小割

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<cstdlib>
using namespace std;
 
const int N=8505,P=855;
const long long INF=210000000000000ll;
 
int n,m,en,h[P],mark[P],cur[P],level[P],S,T,a[P],tmp[P],Ans;
long long ans[P][P];
queue<int> Q;
map<long long,int> Mp;
 
struct Edge{
int b,next,back;
long long f;
}e[N*4];
 
void AddEdge(int sa,int sb,long long sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}
 
int BFS(){
memset(level,0,sizeof(level));
level[S]=1;
Q.push(S);
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(level[v] || !e[i].f)continue;
        level[v]=level[u]+1;
        Q.push(v);
    }
}
return level[T];
}
 
long long DFS(int u,long long flow){
if(u==T)return flow;
long long f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b;
    long long fl;
    if(level[v]==level[u]+1 && e[i].f && (fl=DFS(v,min(f,e[i].f)))){
        e[i].f-=fl;
        e[e[i].back].f+=fl;
        f-=fl;
        if(f==0)return flow;
    }
}
return flow-f;
}
 
long long Dinic(){
long long ans=0;
while(BFS()){for(int i=1;i<=n;i++)cur[i]=h[i];ans+=DFS(S,INF);}
return ans;
}
 
void Rebuild(){
for(int i=1;i<=en;i+=2){
    e[i].f=e[i].f+e[i+1].f;
    e[i+1].f=0;
}
}
 
void dfs(int u){
mark[u]=1;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(e[i].f && !mark[v])dfs(v);
}
}
 
void Solve(int l,int r){
if(l==r)return;
Rebuild();S=a[l];T=a[r];
long long flow=Dinic();
int L=l,R=r;
memset(mark,0,sizeof(mark));
dfs(S);
for(int i=1;i<=n;i++){
    if(!mark[i])continue;
    for(int j=1;j<=n;j++){
        if(!mark[j])ans[i][j]=ans[j][i]=min(ans[i][j],flow);
    }
}
for(int i=l;i<=r;i++){if(mark[a[i]])tmp[L++]=a[i];else tmp[R--]=a[i];}
for(int i=l;i<=r;i++)a[i]=tmp[i];
Solve(l,L-1);Solve(R+1,r);
}
 
int main(){
scanf("%d %d",&n,&m);
memset(ans,127,sizeof(ans));
for(int i=1;i<=n;i++)a[i]=i;
for(int i=1;i<=m;i++){
    int sa,sb;
    long long sc;
    scanf("%d %d %lld",&sa,&sb,&sc);
    AddEdge(sa,sb,sc);
    AddEdge(sb,sa,sc);
}
Solve(1,n);
for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
        if(Mp[ans[i][j]]==0){
            Mp[ans[i][j]]=1;
            Ans++;
        }
    }
}
printf("%d\n",Ans);
return 0;
}

这题我写了很长很长时间。。。

SB错误1:无向图要建双向边，然而我只建了单向边……

SB"错误"2:要加当前弧优化！一开始偷懒没加，然后TLE了N次

分治最小割，直接上Gusfield算法

顺便庆祝lyz lyf wyx cjy大爷签了PKU一本线 太神了orzzzzzzzzzzzzz

我这种蒟蒻ZJOI完全不敢去……

要补一补ZJOI讲课的Gusfield和Stoer-wanger算法了

为什么重建边时直接均分流量是对的啊……我按照正常方法写的然后跑的奇慢无比

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;

const int N=3005,P=155;
const long long INF=210000000000000ll;

int n,m,en,h[P],q,level[P],S,T,a[P],mark[P],tmp[P],Data_Num,cur[P];
long long ans[P][P];
queue<int> Q;

struct Edges{
int a,b;
long long v;
}es[N];

struct Edge{
int b,next,back;
long long f;
}e[N*4];

void AddEdge(int sa,int sb,long long sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

int BFS(){
memset(level,0,sizeof(level));
Q.push(S);
level[S]=1;
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
    for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		if(level[v] || !e[i].f)continue;
        level[v]=level[u]+1;
        Q.push(v);
    }
}
return level[T];
}

long long DFS(int u,long long flow){
if(u==T)return flow;
long long f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b;
    long long fl;
    if(level[u]+1==level[v] && e[i].f && (fl=DFS(v,min(f,e[i].f)))){
		e[i].f-=fl;
		e[e[i].back].f+=fl;
        f-=fl;
        if(f==0)return flow;
    }
}
return flow-f;
}

long long Dinic(){
long long ans=0;
while(BFS()){for(int i=1;i<=n;i++)cur[i]=h[i];ans+=DFS(S,INF);}
return ans;
}

void dfs(int u){
mark[u]=1;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(e[i].f && !mark[v])dfs(v);
}
}

void Build(){
en=0;
memset(h,0,sizeof(h));
for(int i=1;i<=m;i++)AddEdge(es[i].a,es[i].b,es[i].v),AddEdge(es[i].b,es[i].a,es[i].v);;
}

void Rebuild(){
for(int i=1;i<=en;i+=2){e[i].f=e[i+1].f+e[i].f;e[i+1].f=0;}
}

void Solve(int l,int r){
if(l==r)return;
Rebuild();S=a[l];T=a[r];
long long flow=Dinic();
int L=l,R=r;
memset(mark,0,sizeof(mark));
dfs(S);
for(int i=1;i<=n;i++){
	if(!mark[i])continue;
	for(int j=1;j<=n;j++){
		if(!mark[j])ans[i][j]=ans[j][i]=min(ans[i][j],flow);
	}
}
for(int i=l;i<=r;i++){
	if(mark[a[i]])tmp[L++]=a[i];
	else tmp[R--]=a[i];
}
for(int i=l;i<=r;i++)a[i]=tmp[i];
Solve(l,L-1);Solve(R+1,r);
}

int main(){
freopen("2229.in","r",stdin);
freopen("2229.out","w",stdout);
scanf("%d",&Data_Num);
while(Data_Num--){
	memset(ans,127,sizeof(ans));
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d %d %lld",&es[i].a,&es[i].b,&es[i].v);
	for(int i=1;i<=n;i++)a[i]=i;
	Build();
	Solve(1,n);
	scanf("%d",&q);
	while(q--){
		int Ans=0;
		long long x;
		scanf("%lld",&x);
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				if(ans[i][j]<=x)Ans++;
			}
		}
		printf("%d\n",Ans);
	}
	puts("");
}
return 0;
}

这题我写+调了一晚上……代码能力太差

首先忘了LCT怎么维护生成树，看了半天以前的代码

然后写了1.5h。。然后过不了样例

调试

调试

调试

呀！原来这里写错了！改！

样例还是不对……

调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试

Splay写错了！改！

样例过了！

提交，AC了！

真心写不动题解了……Claris题解

现在才真正感受到wzf AHOI2016Day1考场写12k+代码AK的可怕……我写调了将近3h，然而这代码4k不到……

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int N=200005,INF=2100000000;

int n,m,T,cnt,in[N],on[N];

struct Line{int v;Line *next;Line(int ux=0){v=ux;next=NULL;}}*Sline[N],*Eline[N];
void AddLineS(int u,int v){Line *x=new Line(v);x->next=Sline[u];Sline[u]=x;}
void AddLineE(int u,int v){Line *x=new Line(v);x->next=Eline[u];Eline[u]=x;}

struct Edge{
int u,v,t;
}e[N];

struct Node{
int v,rev,sum,id;
Node *ch[2],*fa,*mne;
Node(){}
Node(int vx,int vy);
void Pushdown();
void Pushup();
}*tree[2*N],*Null;

Node::Node(int val,int vy){
v=val;
id=vy;
sum=id>n;
rev=0;
ch[0]=ch[1]=fa=Null;
mne=this;
}

void Node::Pushdown(){
if(rev){
	rev=0;
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0]->ch[0],ch[0]->ch[1]);
	swap(ch[1]->ch[0],ch[1]->ch[1]);
}
}

void Node::Pushup(){
mne=this;
sum=id>n;
if(ch[0]!=Null){if(mne->v>ch[0]->mne->v)mne=ch[0]->mne;sum+=ch[0]->sum;}
if(ch[1]!=Null){if(mne->v>ch[1]->mne->v)mne=ch[1]->mne;sum+=ch[1]->sum;}
}

bool Notroot(Node *x){return x->fa->ch[0]==x || x->fa->ch[1]==x;}
void Prepare(Node *x){if(Notroot(x))Prepare(x->fa);x->Pushdown();}
Node *GetNull(){Node *p=new Node(INF,0);p->v=INF;p->id=p->sum=p->rev=0;p->ch[0]=p->ch[1]=p->fa=p->mne=p;return p;}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y))Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else {Rotate(y,0);Rotate(x,0);}
	}
}
}

void Access(Node *x){for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}}
void Makeroot(Node *x){Access(x);Splay(x);x->rev^=1;swap(x->ch[0],x->ch[1]);}
void Link(Node *x,Node *y){Makeroot(x);x->fa=y;}
void Cut(Node *x,Node *y){Makeroot(x);Access(y);Splay(y);if(y->ch[0]==x){y->ch[0]=Null;x->fa=Null;}}
Node *Find(Node *x){Access(x);Splay(x);while(x->ch[0]!=Null)x=x->ch[0];return x;}
Node *ToLct(int x){return tree[x];}

void Add(int id){
int u=e[id].u,v=e[id].v;
if(u==v){cnt++;in[id]=1;return;}
if(Find(ToLct(u))!=Find(ToLct(v))){on[id]=1;Link(ToLct(u),ToLct(id+n));Link(ToLct(v),ToLct(id+n));}
else {
	Makeroot(ToLct(u));
	Access(ToLct(v));
	Splay(ToLct(v));
	int idx=ToLct(v)->mne->id-n;
    if(e[idx].t<e[id].t){
		if(ToLct(v)->sum&1^1){in[idx]=1;cnt++;}
		Cut(ToLct(e[idx].u),ToLct(idx+n));Cut(ToLct(e[idx].v),ToLct(idx+n));
		Link(ToLct(u),ToLct(id+n));Link(ToLct(v),ToLct(id+n));
		on[idx]=0;on[id]=1;
    }
    else if(ToLct(v)->sum&1^1){in[id]=1;cnt++;}
}
}

void Del(int id){
if(in[id]){in[id]=0;cnt--;}else if(on[id]){Cut(ToLct(e[id].u),ToLct(id+n));Cut(ToLct(e[id].v),ToLct(id+n));}
}

int main(){
freopen("4025.in","r",stdin);
freopen("4025.out","w",stdout);
scanf("%d %d %d",&n,&m,&T);
Null=GetNull();
for(int i=1;i<=n;i++)tree[i]=new Node(INF,i);
for(int i=1;i<=m;i++){
	int x;
	scanf("%d %d %d %d",&e[i].u,&e[i].v,&x,&e[i].t);
	AddLineS(x,i);
	AddLineE(e[i].t,i);
	tree[i+n]=new Node(e[i].t,i+n);
}
for(int i=0;i<T;i++){
	for(Line *j=Sline[i];j!=NULL;j=j->next)Add(j->v);
	for(Line *j=Eline[i];j!=NULL;j=j->next)Del(j->v);
	puts(cnt?"No":"Yes");
}
return 0;
}

这题真心神题……

首先我们直接考虑第i轮选择谁，那么明显是做不了的，就变成了暴力

我们需要一些独特的DP技巧

首先，我们无视掉m轮的限制，把m次选择全部放在同一轮里面

设$DP[i][j]$为$[i,n]$中的人被选择$j$次的概率

那么显然$DP[0][m]=1$，因为根本没有0号，所以0一定不会被选择

那么转移就变成了

$DP[i][j]=DP[i-1][j]*(1-P[i-1])^j+DP[i-1][j+1]*(1-(1-P[i-1])^{j+1})$

解释:

首先$DP[i-1][j]*(1-P[i-1])^j$表示的是向前面递推到i-1人(因为这一次这一轮没有结束，当前卡牌没有被选择)，同样还是j次机会，上一张卡发动技能的概率是$P[i-1]$(因为上一张卡如果发动了技能就跳到下一轮了),那么不发动技能的概率就是$1-P[i-1]$，j轮不发动技能的概率就是$(1-P[i-1])^j$,前面的$DP[i-1][j]$意思是上一张卡没有发动技能结束回合，这次机会留到这张卡

$DP[i-1][j+1]*(1-(1-P[i-1])^{j+1})$意思是上一张卡在第j轮不幸被选中发动技能了，那么下一次想要选到当前卡牌必须跳到下一轮(所以是$j+1$)，后面的概率意思是上一张卡在前$j+1$轮发动技能的概率(因为直接选中这张卡后会判断当前这张卡有没有发动技能，前面是发动了技能的概率)，那么这次将会跳过这张卡来到当前卡

所以来到当前卡的期望就是上面两者的和

然而答案怎么统计呢?答案因为要统计伤害的期望，那么根据期望的线性性，我们知道第$i$张卡能来到j轮的期望为$DP[i][j]$(来到的意思就是没有在前面发动过技能)

所以$ans=DP[i][j]*(1-(1-P[i])^j)*D[i]$,其中$D[i]$表示的是伤害

怎么找一篇详细的题解那么难。。大部分题解也就两句话，迫使我这样的蒟蒻花很长时间去思考，那些神犇的思维能力太强一句话题解就会做了orzorz

UPD:hzwer的题解比我的好多了。。十分清晰易懂

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=255;

long double dp[N][N],P[N],D[N],ans;
int n,m,T;

long double Qpow(long double x,int y){
long double ans=1.0;
while(y){
	if(y&1)ans=ans*x;
	x*=x;
	y>>=1;
}
return ans;
}

int main(){
freopen("4008.in","r",stdin);
freopen("4008.out","w",stdout);
scanf("%d",&T);
while(T--){
    scanf("%d %d",&n,&m);
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
		double x,y;
		scanf("%lf %lf",&x,&y);
		P[i]=x;D[i]=y;
    }
    dp[0][m]=1.0;
    ans=0.0;
    for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j]=dp[i-1][j]*Qpow(1-P[i-1],j)+dp[i-1][j+1]*(1-Qpow(1-P[i-1],j+1));
			ans+=dp[i][j]*(1-Qpow(1-P[i],j))*D[i];
		}
    }
    printf("%.10lf\n",(double)ans);
}
return 0;
}

简单的期望DP

分三种情况考虑就可以了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=300005;

int n;
double F[N],D[N];
char s[N];

int main(){
freopen("3450.in","r",stdin);
freopen("3450.out","w",stdout);
scanf("%d %s",&n,s+1);
for(int i=1;i<=n;i++){
    if(s[i]=='o'){F[i]=F[i-1]+D[i-1]*2+1;D[i]=D[i-1]+1;}
    if(s[i]=='x'){F[i]=F[i-1];D[i]=0;}
    if(s[i]=='?'){F[i]=F[i-1]+(D[i-1]*2+1)/2;D[i]=(D[i-1]+1)/2;}
}
printf("%.4lf\n",F[n]);
return 0;
}