随便搞点什么吧3

shinbokuow posted @ 10 年前 in water , 1043 阅读

最近的状态非常爆炸,几乎所有题都不能想出第一步QwQ.

只能尽可能调整一下状态了.

bzoj3489

如果允许离线显然是水题.

强制在线的话我们用主席树维护就行啦.

bzoj1019

令 $f[i][j]$ 表示一开始在柱子 $i$ 上有 $j$ 个盘子,要移动到另外一个的最少步数.

令 $g[i][j]$ 表示一开始在柱子 $i$ 上有 $j$ 个盘子,在最小字典序意义下会移动到哪一个柱子.

转移就非常显然了.

bzoj1021

我又不会做的水题...

不同的钞票之间显然是独立的.

令 $f[i][j][k]$ 表示前 $i$ 种钞票,第一个人有 $j$ 元,第二个人有 $k$ 元的最小钞票数,简单dp即可.

bzoj1935

将询问转化为前缀相减并离线,离散化后利用树状数组维护即可.

bzoj2024

把所有男生女生都按照身高从小到大排序,令 $g[i][j]$ 表示排名前 $i$ 小的女生参与匹配,且至少存在 $j$ 对女大于男的方案数.

令 $num[i]$ 表示比排名第 $i$ 的女生身高矮的男生数目.

那么有转移: $g[i][j]=g[i-1][j]+g[i-1][j-1]\times{(num[i]-(j-1))}$ .

然后这样会有重复的方案,所以要容斥一下,然后就行了.

bzoj1020

一开始感觉是二分答案,然后将每个多边形都拓展出来一定的长度,然后判断折线是否被全部包含.

这样原来的夹角处就会变成一个弧形,看起来就十分难做了.

网上的题解用的是一种迭代的方法.

将所有没有被完全覆盖的线段取出,首先找到左端点的最近点 $pl$ ,再找到右端点的最近点 $pr$ ,容易发现线段上的每个点到这两个点的最小值是一个先增大后减小的单峰函数,我们用二分找出这个最大值.

首先利用这个值更新答案,然后跟已经出现过的答案进行比较,如果小于那个答案则这个线段显然对于答案不存在贡献.这是由于我们仅仅选取了两个端点作为估价,实际上要比这个距离更小.

如果这个线段对于答案有影响,我们就把这个线段二等分之后加入队列即可.

bzoj3562

将自始至终不会被删除的边缩到一起,这样边数和点数都是 $O(q)$ 级别的.

于是直接利用暴力算法即可.

bzoj2025

建一个最短路图然后随便跑跑应该就行了吧.

bzoj2620

显然是糖果传递.

bzoj1712

每进行一次变换,总和均乘以 $n-1$ ,然后再注意两个元素的差的规律就能做了.

bzoj1611

随便预处理一下每个格子能走的时间,然后随便spfa就行了.

bzoj1610

暴力把所有斜率都算出来.

bzoj1625

背包.

bzoj1609

傻逼dp.

bzoj1606

背包.

bzoj1599

暴力||dp.

bzoj1600

枚举两条边长,剩下的O(1)计算.

bzoj1617

O(n^2)dp.

闲着没事发现了一场水比赛from HackerRank.

EpicCode CodeSprint A

模拟即可.

EpicCode CodeSprint B

统计每种字符的数目,然后直接算.

EpicCode CodeSprint C

简单贪心即可.

EpicCode CodeSprint D

想FFT就完了.是一个类似于最大子段和的dp.

EpicCode CodeSprint E

题目大意是求出最多的一些区间使得任意两个区间之间没有包含关系.

做法是按照起点排序转化为终点的lis.

EpicCode CodeSprint F

差分后转化成维护

$iw_i$ 的形式.

EpicCode CodeSprint G

按照集合中的元素数目是否超过

$\sqrt{n}$ 分为两种.

剩下的细节就不想考虑啦.

EpicCode CodeSprint H

树链剖分直接上.

bzoj2720&&spoj COT5

首先维护一个关于键值的有序序列.

然后lca就是区间内权值的最小值对应的点.

然后一个点到根的链是由两部分组成的:就是从这个点开始分别向前和向后权值的单调递减序列.

我们维护一下区间从左端点开始向右的单调递减序列长度,以及右端点的序列长度,就知道一个点的深度了.

然后就能求出路径的长度了.

bzoj4025

动态二分图,允许离线.

lct直接上啊...

维护一个以边的删除时间为关键字的最大生成树.

然后如果弹出了边,并且加入的这条边在树上形成了奇环,就把弹出的那条边加入一个集合.

注意如果是自环的话直接加入集合.

删除的时候如果这条边在树上直接删(不加入集合),如果在集合中的话直接从集合中删除.

某个时刻如果集合中不存在边的话就是二分图.

正确性不想证明了...

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define inf 0x3f3f3f3f
 
#define N 100010
#define M 200010
 
int u[M],v[M],be[M],en[M];
 
struct Note{
    int t,type,lab;
    Note(){}
    Note(int _t,int _type,int _lab):t(_t),type(_type),lab(_lab){}
     
    bool operator<(const Note&B)const{
        if(t!=B.t)
            return t<B.t;
        return type>B.type;
    }
}S[M<<1];
int id;
 
#define ls ch[0]
#define rs ch[1]
struct Node{
    Node*ch[2],*pa;
    int size,minend,minlab,end,lab;
    bool rev;
    Node():size(0),minend(inf){}
     
    inline bool d(){
        return this==pa->rs;
    }
    inline void sc(Node*p,bool d){
        ch[d]=p;
        p->pa=this;
    }
    inline void revit(){
        rev^=1;
        swap(ls,rs);
    }
    inline void down();
    inline void up();
    inline bool isroot();
}mem[N+M],*G=mem,*V[N],*E[M],Tnull,*null=&Tnull;
inline Node*newnode(int lab){
    G->ls=G->rs=G->pa=null;
    G->size=(lab>0);
    G->minend=G->end=lab?en[lab]:inf;
    G->minlab=G->lab=lab?lab:0;
    G->rev=0;
    return G++;
}
inline void Node::down(){
    if(rev){
        if(ls!=null)
            ls->revit();
        if(rs!=null)
            rs->revit();
        rev=0;
    }
}
inline void Node::up(){
    size=ls->size+rs->size+(lab!=0);
    minend=end;
    minlab=lab;
    if(ls!=null&&ls->minend<minend){
        minend=ls->minend;
        minlab=ls->minlab;
    }
    if(rs!=null&&rs->minend<minend){
        minend=rs->minend;
        minlab=rs->minlab;
    }
}
inline bool Node::isroot(){
    return pa==null||(this!=pa->ls&&this!=pa->rs);
}
inline void Rot(Node*p){
    Node*fa=p->pa;
    bool d=p->d();
    p->pa=fa->pa;
    if(!fa->isroot())
        fa->pa->sc(p,fa->d());
    fa->sc(p->ch[!d],d);
    fa->up();
    p->sc(fa,!d);
}
inline void pushpath(Node*p){
    static Node*stack[N];
    int top=0;
    for(;p!=null;p=p->pa)
        stack[top++]=p;
    while(top)
        stack[--top]->down();
}
inline void Splay(Node*p){
    pushpath(p);
    while(!p->isroot()){
        if(p->pa->isroot())
            Rot(p);
        else
            Rot(p->d()==p->pa->d()?p->pa:p),Rot(p);
    }
    p->up();
}
inline void Access(Node*p){
    Node*q=null;
    while(p!=null){
        Splay(p);
        p->sc(q,1);
        p->up();
        q=p;
        p=p->pa;
    }
}
inline void Makeroot(Node*p){
    Access(p);
    Splay(p);
    p->revit();
}
inline void Link(Node*p,Node*q){
    Makeroot(p);
    p->pa=q;
}
inline void Cut(Node*p,Node*q){
    Makeroot(p);
    Access(q);
    Splay(q);
    q->ls=p->pa=null;
    q->up();
}
inline Node*findroot(Node*p){
    while(p->pa!=null)
        p=p->pa;
    return p;
}
inline int query(Node*p,Node*q){
    Makeroot(p);
    Access(q);
    Splay(q);
    return q->minlab;
}
inline int qlen(Node*p,Node*q){
    Makeroot(p);
    Access(q);
    Splay(q);
    return q->size&1;
}
bool inset[M];
int num=0;
bool ontree[M];
 
inline int getc(){
    static const int L=1<<15;
    static char buf[L],*S=buf,*T=buf;
    if(S==T){
        T=(S=buf)+fread(buf,1,L,stdin);
        if(S==T)
            return EOF;
    }
    return*S++;
}
inline int getint(){
    int c;
    while(!isdigit(c=getc()));
    int x=c-'0';
    while(isdigit(c=getc()))
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
 
int main(){
    //freopen("tt.in","r",stdin);
    int n,m,T;
    cin>>n>>m>>T;
    int i,j;
    for(i=1;i<=n;++i)
        V[i]=newnode(0);
    for(i=1;i<=m;++i){
        u[i]=getint(),v[i]=getint();
        be[i]=getint()+1,en[i]=getint()+1;
        S[++id]=Note(be[i],1,i);
        S[++id]=Note(en[i],-1,i);
        E[i]=newnode(i);
    }
    sort(S+1,S+id+1);
     
    j=1;
    for(i=1;i<=T;++i){
        for(;j<=id&&S[j].t==i;++j){
            if(S[j].type==1){
                if(u[S[j].lab]==v[S[j].lab]){
                    ++num;
                    inset[S[j].lab]=1;
                }
                else if(findroot(V[u[S[j].lab]])!=findroot(V[v[S[j].lab]])){
                    ontree[S[j].lab]=1;
                    Link(E[S[j].lab],V[u[S[j].lab]]);
                    Link(E[S[j].lab],V[v[S[j].lab]]);
                }
                else{
                    int _edge=query(V[u[S[j].lab]],V[v[S[j].lab]]);
                    int d=qlen(V[u[S[j].lab]],V[v[S[j].lab]]);
                    if(en[S[j].lab]>en[_edge]){
                        if(d==0){
                            ++num;
                            inset[_edge]=1;
                        }
                        ontree[_edge]=0;
                        Cut(E[_edge],V[u[_edge]]);
                        Cut(E[_edge],V[v[_edge]]);
                         
                        ontree[S[j].lab]=1;
                        Link(E[S[j].lab],V[u[S[j].lab]]);
                        Link(E[S[j].lab],V[v[S[j].lab]]);
                    }
                    else{
                        if(d==0){
                            ++num;
                            inset[S[j].lab]=1;
                        }
                    }
                }
            }
            else{
                if(ontree[S[j].lab]){
                    ontree[S[j].lab]=0;
                    Cut(E[S[j].lab],V[u[S[j].lab]]);
                    Cut(E[S[j].lab],V[v[S[j].lab]]);
                }
                else if(inset[S[j].lab]){
                    --num;
                    inset[S[j].lab]=0;
                }
            }
        }
        puts(num==0?"Yes":"No");
    }
     
    return 0;
}

由于出傻逼题被D,我还是决定好好补补字符串的姿势水平...

重量平衡树

比如Treap.

插入一个点的复杂度是期望 $O(logn)$ ,假设这个点经过旋转后到达了祖先 $k$ 的位置.那么大小为 $size_k$ 的子树都会进行重构,但这种情况发生当且仅当这个点的随机权值在 $size_k$ 个点中最小,概率为 $\frac{1}{size_k}$ ,因此期望代价为 $O(1)$ .

同时一个点最多有 $O(logn)$ 个祖先,因此重构期望代价为 $O(logn)$ ,期望影响的子树大小为 $O(logn)$ .

删除也是同理.

我们考虑给每个节点赋一个权值来快速比较两个节点的先后顺序.

假设每棵子树都有一个权值区间 $[l,r]$ ,那么根的权值就是 $\frac{l+r}{2}$ .

用Treap来维护这个权值,插入和删除的代价都是期望 $O(logn)$ .

后缀平衡树

对于一个字符串而言,维护了后缀之间的字典序关系的平衡树.

假设已经有字符串 $s$ 的后缀平衡树,我们已经计算出里面所有后缀的标号.

下面考虑如何得到 $cs$ 的后缀平衡树,只需要将后缀 $cs$ 插入后缀平衡树就行了.

首先我们可以直接得到 $cs$ 和任意一个之前后缀的字典序关系.这只需要 $O(1)$ ,若首字母相同,调用两个已经计算完毕的后缀的标号;否则比较完毕.这样直接期望 $O(logn)$ 插入就行了.

这样我们用 $O(nlogn)$ 就能构造一个串的后缀平衡树.

同时还支持在开头插入一个字符.

这一天感觉看了好多课件,但是却不知道都懂了什么...

最起码大概懂了凸壳合并吧...

这里的凸壳是以 $x$ 坐标为序的.

比如说两个上凸壳合并,如果都往里走,那么只有斜率大的走;否则如果有往外走的,都往外走;否则如果有往里走的都往里走.

这样最终得到两个点,他们连起来就得到公切线,合并的话直接上就行了.

两个下凸壳合并一样道理.

上下凸壳合并就是如果都往外走只有斜率大的走,否则优先往里走.

这两种规则我知道是对的,虽然不知道怎么出来的,不过记住就行了.

凸壳用平衡树来维护,这样 $O(logn)$ 就能合并.

这样的话完全动态凸包就能 $O(log^2n)$ 搞了.

看COT4的做法看得我要爆炸...

现在只管离线算法吧...

后缀数组和后缀树好像也有着一些联系,后缀树上的每一个节点都代表后缀数组上的一段连续区间.

先离线对于最终的S集合(一个Trie)建出后缀树.

每个T集合中的串,我们维护一下他在后缀树上是哪一个节点.对于在开头和末尾添加字符,我们都可以 $O(1)$ 找到变化之后是哪个节点.

关键是将两个字符串拼接起来形成的新字符串对应哪个节点呢?

让我们首先考虑后缀数组的算法吧.

考虑两个字符串 $s_1,s_2$ 分别对应后缀数组的区间为 $[l_1,r_1],[l_2,r_2]$ .

我们想通过二分得到串 $s_1+s_2$ 在后缀数组中的区间.

考虑我们需要比较 $s_1+s_2$ 和某个后缀 $T$ 的字典序大小.

若 $T$ 在 $[l_1,r_1]$ 中,那么只需 $O(1)$ 比较 $T$ 的后半部分在后缀数组中的位置与 $[l_2,r_2]$ 的关系即可.

若 $T$ 不在 $[l_1,r_1]$ 中,那么直接比较 $T$ 在后缀数组中的位置与 $[l_1,r_1]$ 的关系即可.

能够支持 $O(1)$ 比较大小关系,我们就能在 $O(logn)$ 之内得出新的区间.

然后在开头和末尾加一个字符也套用这个算法就行了.

得出一段区间的话,我们显然只需在区间中看有几个当前已经加入的后缀,这样就是答案了.

然而这个东西需要对于Trie树求出后缀数组.

我们回到后缀树.

容易发现建出后缀树之后,我们可以dfs一遍直接得到每个节点对应的(后缀数组中的)区间,这样直接套用后缀数组上的区间比较不就行了?

这样就行了吧QwQ.

bzoj2658

首先利用补集转化,然后简单维护一下,现在头痛就不多说了.

bzoj4154

首先搞出dfs序,利用线段树维护,每个线段树节点维护一颗以深度为关键字的线段树,上面存的是颜色以及覆盖时间.

这样空间 $O(nlog^2n)$ QAQ.

不知道能不能过啊...

里层如果用平衡树的话就能少一个log.但是那东西我可懒得写QwQ.

妈的Claris居然用Kdtree!

不过好像觉得也没什么不行的?

算了算了,有思路就可以了.

bzoj4155

第一问:最小割

第二问:考虑将点分配到两个集合中,令点 $i$ 的度数为 $deg_i$ ,那么分配到集合 $A$ 有 $\frac{1}{2}$ 的贡献,分配到集合 $B$ 则有 $-\frac{1}{2}$ 的贡献.想想发现是对的.于是直接背包就OK啦QwQ.

bzoj2557

动态加点最小费用最大流.

bzoj4153

将每一对夫妇用一个二元组 $(x_i,y_i)$ 表示, $x_i$ 表示并查集中男的根节点, $y_i$ 表示并查集中女的根节点.我们维护两个并查集,每个根节点维护一个集合表示里面所有的点.然后合并的时候就启发式合并,暴力修改.然后答案就是知道所有二元组都有多少人,然后搞搞就行了.这个我们在维护过程中顺便维护就行了.

bzoj2947

模拟.

bzoj2277

首先问题转化为选出gcd(seq[k],n)的一个约数x,使得x不是seq[1]~seq[k-1]中任何一个数的约数,并最大化n/x.

直接暴力做的话是\sqrt{n}k的.

我们可以对seq[i]对n取一个gcd,这样最多只剩下20000个数,直接暴力就行了.

前面那么快的是有什么黑科技吗QwQ.

bzoj2216

观察了一下发现每一次移动只有 $O(\sqrt{n})$ 个位置的值会发生改变.

于是就是 $O(n\sqrt{n})$ 感觉好像过不去...

结果题解是单调性dp啊...QwQ.

这道题比较鬼畜,直接用单调队列好像是不行的.因为没有单调性.

参考了一下1d1d优化的课件.

发现了下面这个梗:假设方程是这样的, $f_i=min_{j=1}^{i-1}f_j+w_{j,i}$ ,令 $g_i$ 表示状态 $i$ 的最优决策.

然后我们可以证明若对于任意 $j\leq{i}$ 均满足 $w_{j,i}+w_{j+1,i+1}\leq{w_{j+1,i}+w_{j,i+1}}$ ,则有对于任意 $j\leq{i}$ 满足 $g_j\leq{g_i}$ .

在这道题里面显然 $w_{i,j}=|i-j|$ ,简单证明一下发现是成立的.

这样我们套用用栈优化的技巧:

依次确定每个决策的对后面的影响区间,用栈维护一下 $g_j\leq{g_i}$ 的性质就行了.

这个结论我根本不知道是怎么回事QwQ.

bzoj4108

简单的上下界费用流.

问题在于题目要求每个地点只能去一遍...题里面好像没这么说?

(去掉注释的那行代码就Wa了,大家理解一下吧TAT)

100

101

102

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
 
#define inf 0x3f3f3f3f
struct Solver{
    static const int V=10010;
    static const int E=1000010;
    int head[V],next[E],end[E],flow[E],cost[E],ind;
    int d[V],lv[V],le[V];
    bool inq[V];
    queue<int>q;
    inline void reset(){
        ind=0;
        memset(head,-1,sizeof head);
    }
    inline void addedge(int a,int b,int f,int c){
        int q=ind++;
        end[q]=b;
        next[q]=head[a];
        head[a]=q;
        flow[q]=f;
        cost[q]=c;
    }
    inline void make(int a,int b,int f,int c){
        addedge(a,b,f,c);
        addedge(b,a,0,-c);
    }
    inline bool spfa(int s,int t){
        memset(d,0x3f,sizeof d);
        d[s]=0;
        inq[s]=1;
        q.push(s);
        while(!q.empty()){
            int i=q.front();
            q.pop();
            inq[i]=0;
            for(int j=head[i];j!=-1;j=next[j]){
                if(flow[j]&&d[end[j]]>d[i]+cost[j]){
                    d[end[j]]=d[i]+cost[j];
                    lv[end[j]]=i;
                    le[end[j]]=j;
                    if(!inq[end[j]]){
                        inq[end[j]]=1;
                        q.push(end[j]);
                    }
                }
            }
        }
        return d[t]!=inf;
    }
    inline int Mincost(int s,int t){
        int i,Min,res=0;
        while(spfa(s,t)){
            for(i=t,Min=inf;i!=s;i=lv[i])
                if(flow[le[i]]<Min)
                    Min=flow[le[i]];
            for(i=t;i!=s;i=lv[i])
                flow[le[i]]-=Min,flow[le[i]^1]+=Min;
            res+=Min*d[t];
        }
        return res;
    }
}g;
 
int in[110],out[110];
int main(){
    int n,k;
    cin>>n>>k;
    g.reset();
    int id=0;
    int s=0,ss=++id,t=++id,i,j;
    for(i=2;i<=n+1;++i)
        in[i]=++id,out[i]=++id;
    g.make(s,ss,k,0);
     
    int x;
    for(i=2;i<=n+1;++i){
        scanf("%d",&x);
        g.make(ss,in[i],inf,x);
    }
    for(i=2;i<=n+1;++i){
        for(j=i+1;j<=n+1;++j){
            scanf("%d",&x);
            g.make(out[i],in[j],inf,x);
        }
    }
    for(i=2;i<=n+1;++i){
        //g.make(in[i],out[i],inf,0);
        g.make(s,out[i],1,0);
        g.make(in[i],t,1,0);
    }
     
    cout<<g.Mincost(s,t)<<endl;
     
    return 0;
}
    

bzoj1344

傻逼背包=_=

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
bool f[100010];
int g[100010];
 
int main(){
    int n,i,j;
    cin>>n;
    int x,sum=0;
    f[0]=1;
    g[0]=0x3f3f3f3f;
    for(i=1;i<=n;++i){
        scanf("%d",&x);
        sum+=x;
        for(j=100000;j>=x;--j){
            if(f[j-x]){
                f[j]=1;
                g[j]=max(g[j],min(g[j-x],x));
            }
        }
    }
    int ans=0;
    for(i=1;i<=100000;++i)
        if(f[i]&&2*(i-g[i])<=sum)
            ans=i;
    cout<<ans<<endl;
    return 0;
}

bzoj2213

实际上我们转化为以下问题:枚举字母a,b,用所有区间中的 $num(a)-num(b)$ 更新答案,但前提是这两个东西都不能是0.

显然确定了这两种字母之后,就可以将它们分别看成1和-1,然后求有限制的最大子段和.

直接令 $f[i][0/1][0/1]$ 表示以 $i$ 为结尾,a出现状态为0/1,b出现状态为0/1的最大和.

这样 $O(1)$ 转移下去就行了.

但是这样是 $O(26^2n)$ 的会TLE.

脑补一下可以发现只枚举一个字母就行啦.

就可以过了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 1000010
char s[N];
int ch[N];
int f[26][2][2],_f[2][2];
 
int main(){
    //freopen("tt.in","r",stdin);
    int n;
    scanf("%d",&n);
    scanf("%s",s+1);
     
    int i,j,k;
    for(i=1;i<=n;++i)
        ch[i]=s[i]-'a';
 
    int ans=0;
    for(i=0;i<26;++i){
        memset(f,0xc0,sizeof f);
        for(j=0;j<26;++j)
            f[j][0][0]=0;
        for(j=1;j<=n;++j){
            if(ch[j]==i){
                for(k=0;k<26;++k)
                    if(k!=i){
                        memset(_f,0xc0,sizeof _f);
                        _f[1][0]=1+max(0,f[k][1][0]);
                        _f[1][1]=max(f[k][0][1],f[k][1][1])+1;
                        ans=max(ans,_f[1][1]);
                        memcpy(f[k],_f,sizeof _f);
                    }
            }
            else{
                memset(_f,0xc0,sizeof _f);
                _f[0][1]=-1;
                _f[1][1]=max(f[ch[j]][1][0],f[ch[j]][1][1])-1;
                ans=max(ans,_f[1][1]);
                memcpy(f[ch[j]],_f,sizeof _f);
            }
        }
    }
     
    cout<<ans<<endl;
     
    return 0;
}

bzoj3546

感觉上是先拿dinic跑出一组初始解,然后tarjan...回去再看看吧TAT

bzoj1666

手抖一下,ac+1.

bzoj2680

跟昨天一个题思路一样QwQ...结果我被jkxing的0ms吓尿了看了题解却发现是这种思路QwQ.

bzoj3270

很早之前就做过这个题,现在再深入理解一下.

现在有一个 $n^2\times{1}$ 的列向量 $A$ ,第 $i$ 行表示到达位置 $i$ 的概率.为什么有 $n^2$ 行呢?因为这里的位置是一个二元组包括了两个人的位置.

然后还有一个 $n^2\times{n^2}$ 的概率转移矩阵 $B$ .

容易发现我们要求的答案就是 $ans=A+B\times{A}+B^2\times{A}+...+B^{\infty}\times{A}$ .

注意到 $B^{\infty}$ 趋于0,我们不妨使用等比数列求和公式.

$ans=A\times{\frac{I}{I-B}}$

$(I-B)ans=A$

这东西就是高斯消元啊.直接做就行了.

时间复杂度 $O(n^6)$ .

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
 
int head[21],deg[21],next[510],end[510];
inline void addedge(int a,int b){
    static int q=1;
    end[q]=b;
    next[q]=head[a];
    head[a]=q++;
}
inline void make(int a,int b){
    addedge(a,b);
    addedge(b,a);
    ++deg[a];
    ++deg[b];
}
 
f2 A[510][510],p[21];
 
int lab[25][25];
 
inline void Gauss(int n){
    int i,j,k;
    f2 t;
    for(i=1;i<=n;++i){
        for(k=i,j=i+1;j<=n;++j)
            if(fabs(A[j][i])>fabs(A[k][i]))
                k=j;
        if(k!=i)
            for(j=i;j<=n+1;++j)
                swap(A[i][j],A[k][j]);
        for(k=i+1;k<=n;++k){
            t=-A[k][i]/A[i][i];
            A[k][i]=0;
            for(j=i+1;j<=n+1;++j)
                A[k][j]+=t*A[i][j];
        }
    }
    for(i=n;i>=1;--i){
        for(j=i+1;j<=n;++j)
            A[i][n+1]-=A[i][j]*A[j][n+1];
        A[i][n+1]/=A[i][i];
    }
}
 
int main(){
    int n,m,be,_be;
    cin>>n>>m>>be>>_be;
    int i,j,a,b;
    for(i=1;i<=m;++i){
        scanf("%d%d",&a,&b);
        make(a,b);
    }
    for(i=1;i<=n;++i){
        scanf("%lf",&p[i]);
        addedge(i,i);
    }
 
    int id=0;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            lab[i][j]=++id;
     
    for(i=1;i<=n;++i){
        for(j=1;j<=n;++j){
            if(i!=j){
                for(int _j=head[i];_j;_j=next[_j])
                    for(int __j=head[j];__j;__j=next[__j])
                        A[lab[end[_j]][end[__j]]][lab[i][j]]+=(i==end[_j]?p[i]:(1-p[i])*1.0/deg[i])*(j==end[__j]?p[j]:(1-p[j])*1.0/deg[j]);
            }
        }
    }
    for(i=1;i<=id;++i)
        for(j=1;j<=id;++j)
            A[i][j]=-A[i][j]+(i==j?1:0);
    A[lab[be][_be]][id+1]=1;
     
    Gauss(id);
     
    for(i=1;i<=n;++i)
        printf("%.6lf ",A[lab[i][i]][id+1]);
     
    return 0;
}

bzoj3159

用LCT来维护,每一条重链另外用一颗Splay来维护重链上的权值.

这是因为打翻转标记的话,不能够破坏原有的LCT的结构.

然后Access的时候简单维护一下就行啦!

时间复杂度 $O(nlog^2n)$ .

bzoj3155

跟上面的某个题目一样,差分之后维护 $iw_i$ 即可.

bzoj3157

利用二项式定理矩阵乘法.时间复杂度 $O(m^3logn)$ .

不过出题人说好像过不去?

正解是推个式子然后倍增QwQ.好像不难就不看了.

bzoj2759

感觉好傻逼的题啊Qwq.回去果断水一发!

ETT:

能在 $O(logn)$ 里面兹磁删边、加边,换根,子树修改查询.

23333

随便搞点什么吧3

search

lastest comments

friend links

visitor counter

随便搞点什么吧3

search

tags

lastest comments

friend links

visitor counter