过去一年我都做了些什么呢...如果现在不记下来的话之后会不会完全忘记了呢？
如果写能够看懂的内容，反而有可能会造成成误解；这样来看不如写一些意义完全含混不清的内容吧！
Codeforces Goodbye2016 G New Year and Binary Tree Paths 数学+DP
Dec 31, 2016 08:38:02 PM
题目大意：给定一颗无穷大的完全二叉树，根节点的标号为$1$，对于每个节点若其标号为$x$，则其左儿子标号为$2x$，右儿子标号为$2x+1$。同时再给定$S$，求树上有多少条路径使得路径上节点的标号和恰为$S$。数据范围$S\leq{10^{15}}$。
本站改风格公告!
Aug 17, 2015 05:26:31 PM
意料之外的事情,居然NOI之后还没有滚粗...
其实这才是最大的侥幸吧...
我回忆起北大夏令营之后的我的心情,和现在的心情比较,真是一个天上,一个地下啊.
所以我以后做的每一道题目,都不会像前段时间那样仓促,而是尽量写详细的题解,贴上代码.
(当然是因为这些都是水题了啊!)
随便搞点什么吧3
Jun 20, 2015 10:36:10 PM
最近的状态非常爆炸,几乎所有题都不能想出第一步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直接上啊...
维护一个以边的删除时间为关键字的最大生成树.
然后如果弹出了边,并且加入的这条边在树上形成了奇环,就把弹出的那条边加入一个集合.
注意如果是自环的话直接加入集合.
删除的时候如果这条边在树上直接删(不加入集合),如果在集合中的话直接从集合中删除.
某个时刻如果集合中不存在边的话就是二分图.
正确性不想证明了...
#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)
#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
随便搞点什么吧2
Jun 16, 2015 06:10:59 PM
弱省胡策Round6 A
大意:首先注意到就是求出一个最大的循环串集合,使得集合中的任意两个循环串在模$a$意义下相等或者模$b$意义下相等.
思路:首先找出哪些循环串是模$a$相等的,哪些循环串是模$b$相等的,然后找出模$a$相等的最大集合,再找出模$b$相等的最大集合,取个最大值.
利用反证法易证这样是对的.
利用hash很容易实现,时间$O(n)$.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define N 1000010
int A[N<<1],B[N<<1];
struct Hash_system{
static const int mod1=1000000007;
static const int mod2=1000000009;
static const int seed1=200019;
static const int seed2=13131;
int f1[N<<1],f2[N<<1],pow1[N<<1],pow2[N<<1];
inline void init(){
int i;
for(pow1[0]=1,i=1;i<=2000000;++i)
pow1[i]=(ll)pow1[i-1]*seed1%mod1;
for(pow2[0]=1,i=1;i<=2000000;++i)
pow2[i]=(ll)pow2[i-1]*seed2%mod2;
}
inline void input(int A[],int n){
f1[n+1]=f2[n+1]=0;
for(int i=n;i>=1;--i){
f1[i]=((ll)f1[i+1]*seed1+A[i])%mod1;
f2[i]=((ll)f2[i+1]*seed2+A[i])%mod2;
}
}
pii gethash(int l,int r){
int h1=(f1[l]-(ll)f1[r+1]*pow1[r-l+1]%mod1+mod1)%mod1;
int h2=(f2[l]-(ll)f2[r+1]*pow2[r-l+1]%mod2+mod2)%mod2;
return make_pair(h1,h2);
}
}H;
pii seq[N];
int main(){
int T;
cin>>T;
int i,j;
H.init();
while(T--){
int n,a,b;
cin>>n>>a>>b;
for(i=1;i<=n;++i)
scanf("%d",&A[i]);
for(i=n+1;i<2*n;++i)
A[i]=A[i-n];
int ans=0;
for(i=1;i<2*n;++i)
B[i]=A[i]%a;
H.input(B,2*n-1);
for(i=1;i<=n;++i)
seq[i]=H.gethash(i,i+n-1);
sort(seq+1,seq+n);
for(i=1;i<=n;){
for(j=i;j!=n&&seq[j]==seq[j+1];++j);
ans=max(ans,j-i+1);
i=j+1;
}
for(i=1;i<2*n;++i)
B[i]=A[i]%b;
H.input(B,2*n-1);
for(i=1;i<=n;++i)
seq[i]=H.gethash(i,i+n-1);
sort(seq+1,seq+n);
for(i=1;i<=n;){
for(j=i;j!=n&&seq[j]==seq[j+1];++j);
ans=max(ans,j-i+1);
i=j+1;
}
cout<<(ans==1?0:ans)<<endl;
}
return 0;
}
弱省胡策Round6 B
思路:首先将树树链剖分,则任何一颗联通的子树都必定可以用一条链上的一段作为主链来表示,主链上的每个点会向下连出一些子链,我们仅需考虑子链的最大前缀和,若其$>0$,则加到这个点的点权中.然后再搞出这个链的最大子段和更新答案.
维护一个全局堆记录所有重链的最大子段和.
考虑修改,只需要修改这个点的权值,更新链的最大子段和,在堆中修改,然后更新父亲重链的点权,并以此类推就行了.
时间复杂度$O(log^2n)$.
我的代码在ch上不明所以的RE,本地可以AC.
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
multiset<int>s;
#define N 100010
#define l(x) S[x].l
#define r(x) S[x].r
struct Ans{
int lm,rm,sum,mx;
inline void add(int x){
lm+=x;
rm+=x;
sum+=x;
mx+=x;
}
};
struct Node{
int l,r;
Ans v;
}S[N<<1];
Ans merge(const Ans&l,const Ans&r){
Ans re;
re.lm=max(l.lm,l.sum+max(0,r.lm));
re.rm=max(r.rm,r.sum+max(0,l.rm));
re.sum=l.sum+r.sum;
re.mx=max(max(l.mx,r.mx),l.rm+r.lm);
return re;
}
int cnt;
inline int build(int tl,int tr){
int q=++cnt;
if(tl==tr)
return q;
int mid=(tl+tr)>>1;
l(q)=build(tl,mid);
r(q)=build(mid+1,tr);
return q;
}
inline void up(int x){
S[x].v=merge(S[l(x)].v,S[r(x)].v);
}
inline void add(int q,int tl,int tr,int ins,int v){
if(tl==tr){
S[q].v.add(v);
return;
}
int mid=(tl+tr)>>1;
if(ins<=mid)
add(l(q),tl,mid,ins,v);
else
add(r(q),mid+1,tr,ins,v);
up(q);
}
inline Ans Query(int q,int tl,int tr,int dl,int dr){
if(dl<=tl&&tr<=dr)
return S[q].v;
int mid=(tl+tr)>>1;
if(dr<=mid)
return Query(l(q),tl,mid,dl,dr);
else if(dl>mid)
return Query(r(q),mid+1,tr,dl,dr);
else
return merge(Query(l(q),tl,mid,dl,mid),Query(r(q),mid+1,tr,mid+1,dr));
}
int head[N],next[N<<1],end[N<<1];
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);
}
int v[N],_v[N];
int siz[N],son[N],id,p_id[N],id_p[N],dep[N],top[N],pa[N];
inline void dfs(int x,int fa){
siz[x]=1;
int Max_siz=0;
for(int j=head[x];j;j=next[j]){
if(end[j]!=fa){
dep[end[j]]=dep[x]+1;
pa[end[j]]=x;
dfs(end[j],x);
siz[x]+=siz[end[j]];
if(siz[end[j]]>Max_siz){
Max_siz=siz[end[j]];
son[x]=end[j];
}
}
}
}
int lab[N],num=1,_begin[N],_end[N];
inline void create(int x,int Top){
top[x]=Top;
p_id[x]=++id;
id_p[id]=x;
lab[id]=num;
if(son[x])
create(son[x],Top);
else
++num;
for(int j=head[x];j;j=next[j])
if(end[j]!=pa[x]&&end[j]!=son[x])
create(end[j],end[j]);
}
int n,m;
inline void Modify(int x,int y){
Ans tmp=Query(1,1,n,_begin[p_id[x]],_end[p_id[x]]);
int lastlm=tmp.lm,lastmx=tmp.mx,_lastlm,_lastmx;
int nowlm,nowmx;
add(1,1,n,p_id[x],-v[x]+y);
v[x]=y;
while(1){
tmp=Query(1,1,n,_begin[p_id[x]],_end[p_id[x]]);
nowlm=tmp.lm,nowmx=tmp.mx;
s.erase(s.find(lastmx)),s.insert(nowmx);
if(pa[top[x]]){
tmp=Query(1,1,n,_begin[p_id[pa[top[x]]]],_end[p_id[pa[top[x]]]]);
_lastlm=tmp.lm,_lastmx=tmp.mx;
if(lastlm<=0&&nowlm>0)
add(1,1,n,p_id[pa[top[x]]],nowlm);
else if(lastlm>0&&nowlm<=0)
add(1,1,n,p_id[pa[top[x]]],-lastlm);
else if(lastlm>0&&nowlm>0)
add(1,1,n,p_id[pa[top[x]]],-lastlm+nowlm);
x=pa[top[x]];
lastlm=_lastlm;
lastmx=_lastmx;
}
else
break;
}
}
int main(){
//freopen("tt.in","r",stdin);
cin>>n>>m;
int i,j,k;
for(i=1;i<=n;++i)
scanf("%d",&_v[i]);
int a,b;
for(i=1;i<n;++i){
scanf("%d%d",&a,&b);
make(a,b);
}
dep[1]=1;
dfs(1,-1);
create(1,1);
for(i=1;i<=n;){
for(j=i;j!=n&&lab[j]==lab[j+1];++j);
for(k=i;k<=j;++k)
_begin[k]=i,_end[k]=j;
i=j+1;
}
for(i=1;i<=num-1;++i)
s.insert(0);
build(1,n);
for(i=1;i<=n;++i)
Modify(i,_v[i]);
int qte,x,y;
while(m--){
scanf("%d",&qte);
if(qte==2){
multiset<int>::iterator it=s.end();
printf("%d\n",max(0,*(--it)));
}
else{
scanf("%d%d",&x,&y);
Modify(x,y);
}
}
return 0;
}
弱省胡策Round6 C
想了好长时间的性质,结果发现是暴力题,稍微加了一点可行性剪枝就过了.
出题人我@$#^$%&$%#@^%#$&$%&...
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
multiset<int>s;
#define N 2010
int a[N];
int main(){
//freopen("tt.in","r",stdin);
int T;
cin>>T;
int n,m,i,j;
while(T--){
cin>>n>>m;
int sum=0,Max=0;
for(i=1;i<=n;++i){
scanf("%d",&a[i]);
sum+=a[i];
Max=max(Max,a[i]);
}
int ans;
for(ans=max(Max,sum/m);ans<=sum;++ans){
int tim=0,last;
for(i=1;i<=n;++i)
s.insert(a[i]);
while(!(s.begin()==s.end())){
++tim;
last=ans;
while(1){
if(s.begin()==s.end())
break;
multiset<int>::iterator it=s.upper_bound(last);
if(it==s.begin()||last<*(--it))
break;
last-=*it;
s.erase(s.find(*it));
//for(multiset<int>::iterator it=s.begin();it!=s.end();++it)printf("%d ",*it);puts("");
}
}
//printf("%d ",tim);
if(tim<=m)
break;
}
cout<<ans<<endl;
}
return 0;
}
WC2014紫荆花之恋
orz jkxing!orz orz orz!
我现在终于明白正确的动态树分治是什么鬼啦...
我们并不是对于每个分治结构在里面维护每个子树的信息,而是直接把每个子树的信息维护到对应的子结构里面去就行啦!
还有,求每个点在分治结构中的贡献,用一个全局的lca倍增就行了,也不用单独在分治结构中维护!
一般来说,这种路径信息全局的lca应该都足以解决了.
于是我现在又要开动啦!
upd:现在一些恶心的点爆栈,剩下的还是都能过的,80分.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
#define ls ch[0]
#define rs ch[1]
#define N 100010
namespace Treap{
struct Node{
Node*ch[2];
int v,p,s;
Node():s(0){}
inline void up(){
s=ls->s+rs->s+1;
}
}mem[N*50],*G=mem,Tnull,*null=&Tnull;
stack<Node*>bin;
inline Node*newnode(int _v){
Node*re;
if(!bin.empty()){
re=bin.top();
bin.pop();
}
else
re=G++;
re->ls=re->rs=null;
re->v=_v;
re->p=rand();
re->s=1;
return re;
}
inline void Rot(Node*&p,bool d){
Node*q=p->ch[!d];
p->ch[!d]=q->ch[d];
q->ch[d]=p;
p->up();
q->up();
p=q;
}
inline void insert(Node*&p,int v){
if(p==null)
p=newnode(v);
else if(v<p->v){
insert(p->ls,v);
if(p->ls->p<p->p)
Rot(p,1);
}
else{
insert(p->rs,v);
if(p->rs->p<p->p)
Rot(p,0);
}
p->up();
}
inline int query(Node*p,int v){
if(p==null)
return 0;
if(v<p->v)
return 1+p->rs->s+query(p->ls,v);
else
return query(p->rs,v)+(p->v>=v);
}
inline void recover(Node*p){
if(p==null)
return;
if(p->ls!=null)
recover(p->ls);
if(p->rs!=null)
recover(p->rs);
bin.push(p);
}
void dfs(Node*p){
if(p->ls!=null)
dfs(p->ls);
printf("%d ",p->v);
if(p->rs!=null)
dfs(p->rs);
}
}
int head[N],next[N<<1],end[N<<1],len[N<<1];
inline void addedge(int a,int b,int l){
static int q=1;
end[q]=b;
next[q]=head[a];
head[a]=q;
len[q++]=l;
}
inline void make(int a,int b,int l){
addedge(a,b,l);
addedge(b,a,l);
}
int dep[N],_dep[N],pa[N][21];
inline int lca(int x,int y){
if(dep[x]<dep[y])
swap(x,y);
for(int i=20;i>=0;--i)
if(dep[pa[x][i]]>=dep[y])
x=pa[x][i];
if(x==y)
return x;
for(int i=20;i>=0;--i)
if(pa[x][i]!=pa[y][i])
x=pa[x][i],y=pa[y][i];
return pa[x][0];
}
inline int getdist(int x,int y){
return _dep[x]+_dep[y]-(_dep[lca(x,y)]<<1);
}
ll ans;
int r[N];
struct Array{
int t[N],a[N],tclock;
inline int operator[](const int&x){
if(t[x]!=tclock){
t[x]=tclock;
a[x]=0;
}
return a[x];
}
inline void ch(int x,int d){
t[x]=tclock;
a[x]=d;
}
}in;
namespace Dynamic_System{
struct Tnode{
Tnode*pa;
Treap::Node*root,*_root;
set<Tnode*>son;
int up,g,siz;
}mem[N],*G=mem,Tnull,*null=&Tnull,*ins[N];
stack<Tnode*>bin;
inline Tnode*newnode(){
Tnode*re;
if(!bin.empty()){
re=bin.top();
bin.pop();
}
else
re=G++;
re->pa=null;
re->root=Treap::null;
re->_root=Treap::null;
re->son.clear();
return re;
}
inline Tnode*sNode(int x){
Tnode*re=newnode();
re->g=re->up=x;
re->siz=1;
Treap::insert(re->root,r[x]);
return re;
}
inline void recover(Tnode*p){
for(set<Tnode*>::iterator it=p->son.begin();it!=p->son.end();++it)
recover(*it);
in.ch(p->g,1);
Treap::recover(p->root);
Treap::recover(p->_root);
p->son.clear();
bin.push(p);
}
inline Tnode*divide(int x,int pdis){
static int q[N],_pa[N],ms[N],siz[N],d[N];
//static int g,mins;
//static Tnode*re,*tmp;
static int fr,ta,g,mins;
int i,j;
static Tnode*tmp;
Tnode*re;
_pa[x]=0;
d[x]=0;
fr=ta=0;
q[ta++]=x;
re=newnode();
re->up=x;
while(fr!=ta){
i=q[fr++];
Treap::insert(re->_root,r[i]-(d[i]+pdis));
for(j=head[i];j;j=next[j])
if(end[j]!=_pa[i]&&in[end[j]]){
_pa[end[j]]=i;
d[end[j]]=d[i]+len[j];
q[ta++]=end[j];
}
}
mins=0x3f3f3f3f;
for(i=0;i<ta;++i)
siz[q[i]]=1,ms[q[i]]=0;
for(i=ta-1;i>=0;--i){
ms[q[i]]=max(ms[q[i]],ta-siz[q[i]]);
if(mins>ms[q[i]]){
mins=ms[q[i]];
g=q[i];
}
ms[_pa[q[i]]]=max(ms[_pa[q[i]]],siz[q[i]]);
siz[_pa[q[i]]]+=siz[q[i]];
}
ins[re->g=g]=re;
re->siz=ta;
_pa[g]=0;
d[g]=0;
fr=ta=0;
q[ta++]=g;
while(fr!=ta){
i=q[fr++];
Treap::insert(re->root,r[i]-d[i]);
for(j=head[i];j;j=next[j])
if(end[j]!=_pa[i]&&in[end[j]]){
_pa[end[j]]=i;
d[end[j]]=d[i]+len[j];
q[ta++]=end[j];
}
}
if(ta==1)
return re;
in.ch(g,0);
for(j=head[g];j;j=next[j])
if(in[end[j]]){
tmp=divide(end[j],len[j]);
tmp->pa=re;
re->son.insert(tmp);
}
return re;
}
inline void rebuild(Tnode*p){
Tnode*fa=p->pa;
if(fa!=null)
fa->son.erase(p);
++in.tclock;
recover(p);
Tnode*get=divide(p->up,fa==null?0:getdist(p->up,fa->g));
if(fa!=null){
get->pa=fa;
fa->son.insert(get);
}
}
inline void addnode(int x,int fa,int pdis){
dep[x]=dep[fa]+1;
_dep[x]=_dep[fa]+pdis;
pa[x][0]=fa;
for(int j=1;j<=20;++j)
pa[x][j]=pa[pa[x][j-1]][j-1];
make(x,fa,pdis);
ins[x]=sNode(x);
ins[x]->pa=ins[fa];
ins[fa]->son.insert(ins[x]);
Tnode*last=ins[x],*node=null;
for(Tnode*t=ins[fa];t!=null;t=t->pa){
int dis=getdist(t->g,x);
Treap::insert(t->root,r[x]-dis);
Treap::insert(last->_root,r[x]-dis);
ans+=Treap::query(t->root,dis-r[x])-Treap::query(last->_root,dis-r[x]);
if(last->siz/(double)(++t->siz)>0.75)
node=t;
last=t;
}
if(node!=null)
rebuild(node);
}
}
int main(){
//freopen("tt.in","r",stdin);
int n;
scanf("%*d%d",&n);
//scanf("%d",&n);
int pa,pdis;
for(int i=1;i<=n;++i){
scanf("%d%d%d",&pa,&pdis,&r[i]);
pa^=(ans%1000000000);
if(i==1){
dep[1]=1;
_dep[1]=0;
Dynamic_System::ins[1]=Dynamic_System::sNode(1);
}
else
Dynamic_System::addnode(i,pa,pdis);
//printf("%I64d\n",ans);
printf("%lld\n",ans);
}
return 0;
}
BZOJ3924
一样的动态树分治,对于每个分治结构维护所有点到根的加权距离以及所有点到父分治结构的根的加权距离,以及分治结构内部所有点的权值和.
计算答案时,每次向着答案更小的地方走就好了.
#include<cstdio>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
typedef long long ll;
#define mp make_pair
#define N 100010
int head[N],next[N<<1],end[N<<1],len[N<<1];
inline void addedge(int a,int b,int c){
static int q=1;
end[q]=b;
next[q]=head[a];
head[a]=q;
len[q++]=c;
}
inline void make(int a,int b,int c){
addedge(a,b,c);
addedge(b,a,c);
}
int seq[N<<1],in[N<<1],tclock,dep[N];
ll _dep[N];
int ans[N<<1][21],_log[N<<1];
inline int Min(int x,int y){
return dep[x]>dep[y]?y:x;
}
inline void dfs(int x,int fa){
seq[in[x]=++tclock]=x;
for(int j=head[x];j;j=next[j])
if(end[j]!=fa){
dep[end[j]]=dep[x]+1;
_dep[end[j]]=_dep[x]+len[j];
dfs(end[j],x);
seq[++tclock]=x;
}
}
inline void rmq_init(){
for(int i=1;i<=tclock;++i)
ans[i][0]=seq[i];
for(int j=1;j<=20;++j)
for(int i=1;i+(1<<j)-1<=tclock;++i)
ans[i][j]=Min(ans[i][j-1],ans[i+(1<<(j-1))][j-1]);
for(int i=2;i<=tclock;++i)
_log[i]=_log[i>>1]+1;
}
inline int lca(int x,int y){
x=in[x],y=in[y];
if(x>y)
swap(x,y);
int d=_log[y-x+1];
return Min(ans[x][d],ans[y-(1<<d)+1][d]);
}
inline ll dist(int x,int y){
return _dep[x]+_dep[y]-2ll*_dep[lca(x,y)];
}
struct Node{
Node*pa;
ll sum,_sum,siz;
int up,g;
vector<Node*>son;
}mem[N],*P=mem,Tnull,*null=&Tnull,*ins[N];
inline Node*newnode(){
P->pa=null;
return P++;
}
bool vis[N];
inline void maxi(int&x,int y){
if(x<y)
x=y;
}
inline Node*divide(int x){
static int q[N],pa[N],siz[N],ms[N],fr,ta;
static Node*tmp;
int i,j;
Node*re=newnode();
re->up=x;
fr=ta=pa[x]=0;
q[ta++]=x;
while(fr!=ta){
i=q[fr++];
for(j=head[i];j;j=next[j])
if(end[j]!=pa[i]&&!vis[end[j]])
pa[q[ta++]=end[j]]=i;
}
int g,Min_siz=0x3f3f3f3f;
for(i=0;i<ta;++i)
siz[q[i]]=1,ms[q[i]]=0;
for(i=ta-1;i>=0;--i){
maxi(ms[q[i]],ta-siz[q[i]]);
if(ms[q[i]]<Min_siz){
Min_siz=ms[q[i]];
g=q[i];
}
maxi(ms[pa[q[i]]],siz[q[i]]);
siz[pa[q[i]]]+=siz[q[i]];
}
ins[(re->g=g)]=re;
vis[g]=1;
for(j=head[g];j;j=next[j])
if(!vis[end[j]]){
tmp=divide(end[j]);
tmp->pa=re;
re->son.push_back(tmp);
}
return re;
}
inline void up(int x,int y){
ins[x]->siz+=y;
Node*last=ins[x];
for(Node*t=ins[x]->pa;t!=null;last=t,t=t->pa){
t->siz+=y;
t->sum+=(ll)dist(t->g,x)*y;
last->_sum+=(ll)dist(t->g,x)*y;
}
}
inline ll getans(int x){
ll ans=ins[x]->sum;
Node*last=ins[x];
for(Node*t=ins[x]->pa;t!=null;last=t,t=t->pa)
ans+=t->sum-last->_sum+(ll)dist(t->g,x)*(t->siz-last->siz);
return ans;
}
inline ll solve(Node*root){
ll res=getans(root->g);
for(int j=0;j<root->son.size();++j)
if(getans(root->son[j]->up)<res)
return solve(root->son[j]);
return res;
}
int main(){
//freopen("tt.in","r",stdin);
int n,m;
scanf("%d%d",&n,&m);
int i,a,b,c;
for(i=1;i<n;++i){
scanf("%d%d%d",&a,&b,&c);
make(a,b,c);
}
dfs(1,-1);
rmq_init();
Node*root=divide(1);
while(m--){
scanf("%d%d",&a,&b);
up(a,b);
printf("%lld\n",solve(root));
}
return 0;
}
WJMZBMR模拟赛的某题
我们有一个树，大小为n。考虑树上的一条路径，如果一个边的两个点都在这路径
上，我们称这个边属于这个路径，如果一个边有且只有一个点在这路径上，我们
称这个边与这个路径相邻。现在每个边要么是黑色的要么是白色的，一开始所有
边都是白色的。
我们有3个操作，将某路径反色，将与某路径相邻的所有边反色，求一个路径
上黑边的总数。
上，我们称这个边属于这个路径，如果一个边有且只有一个点在这路径上，我们
称这个边与这个路径相邻。现在每个边要么是黑色的要么是白色的，一开始所有
边都是白色的。
我们有3个操作，将某路径反色，将与某路径相邻的所有边反色，求一个路径
上黑边的总数。
思路:给每个点和每条边(看做一个点)都维护一个颜色,那么每条边的真实颜色就是两个点和一条边的异或和.
路径反色只需要将路径上的所有点都打上取反的标记即可.
然后Access时随便维护一下?
算了,现在只管基本的思路.
BZOJ4012
每个分治结构维护所有版本的关键点到根的距离之和,以及所有版本关键点到父分治结构的距离之和,以及所有版本的关键点数.
然后按照年龄顺序添加版本,每添加一个点都只会增加$O(logn)$个版本,因此空间复杂度$O(nlogn)$.
时间$O(nlog^2n)$,自带大常数垫底辣!
#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define pb push_back
#define inf 0x3f3f3f3f
#define N 150010
int head[N],next[N<<1],end[N<<1],len[N<<1];
inline void addedge(int a,int b,int c){
static int q=1;
end[q]=b;
next[q]=head[a];
head[a]=q;
len[q++]=c;
}
inline void make(int a,int b,int c){
addedge(a,b,c);
addedge(b,a,c);
}
int seq[N<<1],in[N],tclock,dep[N],_dep[N];
int ans[N<<1][21],_log[N<<1];
inline int Min(int x,int y){
return dep[x]<dep[y]?x:y;
}
inline void dfs(int x,int fa){
seq[in[x]=++tclock]=x;
for(int j=head[x];j;j=next[j]){
if(end[j]!=fa){
dep[end[j]]=dep[x]+1;
_dep[end[j]]=_dep[x]+len[j];
dfs(end[j],x);
seq[++tclock]=x;
}
}
}
inline void rmq_init(){
for(int i=2;i<=tclock;++i)
_log[i]=_log[i>>1]+1;
for(int i=1;i<=tclock;++i)
ans[i][0]=seq[i];
for(int j=1;j<=20;++j)
for(int i=1;i+(1<<j)-1<=tclock;++i)
ans[i][j]=Min(ans[i][j-1],ans[i+(1<<(j-1))][j-1]);
}
inline int lca(int x,int y){
x=in[x],y=in[y];
if(x>y)
swap(x,y);
int d=_log[y-x+1];
return Min(ans[x][d],ans[y-(1<<d)+1][d]);
}
inline int getdist(int x,int y){
return _dep[x]+_dep[y]-(_dep[lca(x,y)]<<1);
}
struct Node{
Node*pa;
vector<ll>sum;
vector<ll>_sum;
vector<int>tim;
vector<int>_tim;
vector<int>siz;
vector<int>__tim;
int up,g;
inline ll qsum(int _time){
int d=upper_bound(tim.begin(),tim.end(),_time)-tim.begin()-1;
return sum[d];
}
inline ll q_sum(int _time){
int d=upper_bound(_tim.begin(),_tim.end(),_time)-_tim.begin()-1;
return _sum[d];
}
inline ll qsiz(int _time){
int d=upper_bound(__tim.begin(),__tim.end(),_time)-__tim.begin()-1;
return siz[d];
}
}mem[N],*P=mem,Tnull,*null=&Tnull,*ins[N];
inline Node*newnode(){
P->pa=null;
return P++;
}
bool vis[N];
inline void maxi(int&x,int y){
if(x<y)
x=y;
}
inline Node*divide(int x){
static int q[N],siz[N],ms[N],pa[N],fr,ta;
int i,j;
Node*re=newnode();
re->up=x;
fr=ta=pa[x]=0;
q[ta++]=x;
while(fr!=ta){
i=q[fr++];
for(j=head[i];j;j=next[j])
if(end[j]!=pa[i]&&!vis[end[j]])
pa[q[ta++]=end[j]]=i;
}
int g,Min_siz=0x3f3f3f3f;
for(i=0;i<ta;++i)
siz[q[i]]=1,ms[q[i]]=0;
for(i=ta-1;i>=0;--i){
maxi(ms[q[i]],ta-siz[q[i]]);
if(ms[q[i]]<Min_siz){
Min_siz=ms[q[i]];
g=q[i];
}
maxi(ms[pa[q[i]]],siz[q[i]]);
siz[pa[q[i]]]+=siz[q[i]];
}
ins[re->g=g]=re;
vis[g]=1;
for(j=head[g];j;j=next[j])
if(!vis[end[j]])
(divide(end[j]))->pa=re;
re->tim.pb(0);
re->sum.pb(0ll);
re->_tim.pb(0);
re->_sum.pb(0ll);
re->__tim.pb(0);
re->siz.pb(0);
return re;
}
int a[N],w[N],sav[N];
int qu[N];
inline bool cmp(const int&x,const int&y){
return a[x]<a[y];
}
inline void up(int x,int _time){
ins[x]->tim.pb(_time);
ins[x]->sum.pb(ins[x]->sum.back());
ins[x]->__tim.pb(_time);
ins[x]->siz.pb(ins[x]->siz.back()+1);
Node*last=ins[x];
for(Node*t=ins[x]->pa;t!=null;last=t,t=t->pa){
int _dis=getdist(t->g,x);
last->_tim.pb(_time);
last->_sum.pb(last->_sum.back()+_dis);
t->tim.pb(_time);
t->sum.pb(t->sum.back()+_dis);
t->__tim.pb(_time);
t->siz.pb(t->siz.back()+1);
}
}
inline ll query(int x,int _tim){
ll ans=ins[x]->qsum(_tim);
Node*last=ins[x];
for(Node*t=ins[x]->pa;t!=null;last=t,t=t->pa)
ans+=t->qsum(_tim)-last->q_sum(_tim)+(ll)(t->qsiz(_tim)-last->qsiz(_tim))*getdist(x,t->g);
return ans;
}
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,Q,A;
cin>>n>>Q>>A;
int i,j;
for(i=1;i<=n;++i)
a[i]=getint(),w[i]=a[i];
sort(w+1,w+n+1);
int id=0;
for(i=1;i<=n;){
for(j=i;j!=n&&w[j]==w[j+1];++j);
sav[++id]=w[i];
i=j+1;
}
sav[id+1]=inf;
for(i=1;i<=n;++i){
qu[i]=i;
a[i]=lower_bound(sav+1,sav+id+1,a[i])-sav;
}
sort(qu+1,qu+n+1,cmp);
int x,y,z;
for(i=1;i<n;++i){
x=getint();
y=getint();
z=getint();
make(x,y,z);
}
dfs(1,-1);
rmq_init();
divide(1);
for(i=1;i<=n;++i)
up(qu[i],a[qu[i]]);
for(i=1;i<=n;++i){
ins[i]->tim.pb(inf);
ins[i]->_tim.pb(inf);
ins[i]->__tim.pb(inf);
}
ll ans=0;
int u,l,r;
while(Q--){
u=getint();
l=getint();
r=getint();
l=(ans+l)%A,r=(ans+r)%A;
if(l>r)
swap(l,r);
--l;
ans=0;
if(l>=sav[1])
ans-=query(u,upper_bound(sav+1,sav+id+2,l)-sav-1);
if(r>=sav[1])
ans+=query(u,upper_bound(sav+1,sav+id+2,r)-sav-1);
//printf("%I64d\n",ans);
printf("%lld\n",ans);
}
return 0;
}
BZOJ1511
首先KMP,然后令$ans_i$表示前缀$i$的答案,然后依照我的代码分类讨论...就没了.
#include<cstdio>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
char s[1000010];
int next[1000010],ans[1000010];
int main(){
int n;
scanf("%d",&n);
int i,j=0;
scanf("%s",s+1);
long long res=0;
for(i=2;i<=n;++i){
for(;j&&s[j+1]!=s[i];j=next[j]);
if(s[j+1]==s[i])
++j;
next[i]=j;
if(next[i]){
if(i%(i-next[i])==0)
ans[i]=next[i]+ans[i-next[i]];
else
ans[i]=i-i%(i-next[i])+ans[i%(i-next[i])];
}
}
for(i=1;i<=n;++i)
res+=ans[i];
cout<<res<<endl;
return 0;
}
BZOJ2850
基本全是KDTree,我们考虑一种复杂度稳定的算法吧...
我们将点分块,分成$\sqrt{n}$块,每块$\sqrt{n}$个点,那么每个块都有$O(n)$个斜率,对于每个块,我们把所有的询问离线进去跟斜率一起排序,维护一个点的序列使得点到当前向量的有向距离是有序的,然后斜率每一次改变相当于只是交换了对应两个点在序列中的位置.
我们用一个树状数组维护一下就行了,询问的时候直接二分.
于是这样的复杂度是$O(\sqrt{n}\times((n+m)logn))$.
可是细节太多...
我决定写KDTree辣!
BZOJ2028
set随便玩...
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
typedef pair<int,int> pii;
set<pii>be,en;
#define mp make_pair
#define N 200010
char s[10];
int _be[N],_en[N];
int main(){
int n;
scanf("%d",&n);
int cnt=0,now=0,num,lab;
set<pii>::iterator it,next;
while(n--){
scanf("%s",s);
if(s[0]=='A'){
++cnt;
num=0;
++now;
scanf("%d%d",&_be[cnt],&_en[cnt]);
it=en.lower_bound(mp(_be[cnt],0));
while(1){
if(it==en.end()||_be[(*it).second]>_en[cnt])
break;
--now;
++num;
lab=(*it).second;
next=it,++next;
be.erase(be.find(mp(_be[lab],lab)));
en.erase(en.find(mp(_en[lab],lab)));
it=next;
}
be.insert(mp(_be[cnt],cnt));
en.insert(mp(_en[cnt],cnt));
printf("%d\n",num);
}
else
printf("%d\n",now);
}
return 0;
}
BZOJ4134
我忽略了一点,那就是Trie树是可以在$O(logn)$时间内求出mex的!
这样随便yy就是带标记Trie树合并啦?
如何求mex呢?首先考虑左子树,如果没有满就进入左子树,否则进入右子树.
又如何合并呢?我们类比线段树合并,首先下传这个点的标记,然后下去合并就行了.由于都是自顶向下,是不矛盾的.
我要写一写!
时间复杂度$O(nlogn)$,并不用启发式合并.
代码慢到死.
其实线段树合并为什么是$O(nlogn)$的呢...
感觉我现在还不十分理解.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define N 100010
#define Log 29
struct Node{
Node*l,*r;
bool full;
int c;
Node():full(0),c(0){}
}mem[N*100],*P=mem,Tnull,*null=&Tnull;
inline Node*newnode(){
P->l=P->r=null;
P->full=0,P->c=0;
return P++;
}
inline void addit(Node*p,int _c,int d){
p->c^=_c;
if((_c>>d)&1)
swap(p->l,p->r);
}
inline void down(Node*p,int d){
if(p==null)
return;
if(p->c){
if(p->l!=null)
addit(p->l,p->c,d-1);
if(p->r!=null)
addit(p->r,p->c,d-1);
p->c=0;
}
}
inline void copy(Node*&x,Node*y){
if(y==null)
x=null;
else
*x=*y;
}
Node*Merge(Node*x,Node*y,int d){
down(x,d);
down(y,d);
Node*ret=newnode();
if(x==null||y==null){
copy(ret,x==null?y:x);
return ret;
}
else if(d==-1){
ret->full=x->full|y->full;
return ret;
}
else{
ret->l=Merge(x->l,y->l,d-1);
ret->r=Merge(x->r,y->r,d-1);
ret->full=ret->l->full&ret->r->full;
}
return ret;
}
inline void insert(Node*&p,int x,int d){
if(p==null)
p=newnode();
if(d==-1){
p->full=1;
return;
}
insert((x>>d)&1?p->r:p->l,x,d-1);
p->full=p->l->full&p->r->full;
}
inline int mex(Node*p,int d){
if(p==null)
return 0;
down(p,d);
if(d==-1)
return p->full?0:1;
if(p->l->full)
return (1<<d)+mex(p->r,d-1);
else
return mex(p->l,d-1);
}
int col[N];
int head[N],next[N<<1],end[N<<1];
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);
}
int pa[N];
inline void dfs(int x,int fa){
for(int j=head[x];j;j=next[j]){
if(end[j]!=fa){
pa[end[j]]=x;
dfs(end[j],x);
}
}
}
inline int getpa(int x){
int t;
for(t=pa[x];t&&col[t];t=pa[t]);
return t;
}
vector<int>son[N];
int sg[N],sum[N];
Node*root[N];
inline void solve(int x){
if(son[x].size()==0){
sg[x]=1;
insert(root[x]=null,0,Log);
return;
}
int i,j;
for(i=0;i<son[x].size();++i){
solve(son[x][i]);
sum[x]^=sg[son[x][i]];
}
root[x]=null;
insert(root[x],sum[x],Log);
for(i=0;i<son[x].size();++i){
addit(root[son[x][i]],sum[x]^sg[son[x][i]],Log);
root[x]=Merge(root[x],root[son[x][i]],Log);
}
sg[x]=mex(root[x],Log);
}
int ans[N];
inline void getans(int x,int lastxor){
ans[x]=lastxor^sum[x];
for(int i=0;i<son[x].size();++i)
getans(son[x][i],ans[x]^sg[son[x][i]]);
}
vector<int>tot;
int main(){
//freopen("tt.in","r",stdin);
int n;
scanf("%d",&n);
int i,j;
for(i=1;i<=n;++i)
scanf("%d",&col[i]);
int a,b;
for(i=1;i<n;++i){
scanf("%d%d",&a,&b);
make(a,b);
}
dfs(1,-1);
int _pa;
for(i=1;i<=n;++i)
if(!col[i]){
_pa=getpa(i);
son[_pa].push_back(i);
}
solve(0);
getans(0,0);
for(i=1;i<=n;++i)
if(!col[i]&&!ans[i])
tot.push_back(i);
if(tot.size()==0)
puts("-1");
else
for(i=0;i<tot.size();++i)
printf("%d\n",tot[i]);
return 0;
}
BZOJ3294
令$f[i][j][k]$表示前$i$种颜色占据$j$行$k$列的方案数,令$g[i][j][k]$表示$i$个棋子占满$j$行$k$列的方案数.
则有:$f[i][j][k]=\sum_{_j}\sum_{_k}f[i-1][j-_j][k-_k]\times{C_{j}^{_j}\times{C_{k}^{_k}}\times{g[x_i][_j][_k]}}$
关键是$g$怎么求.
我们考虑,如果用更少的行数和列数就能够占满,那么剩下的行和列一定都是空的.
故而我们利用补集转化,具体看代码.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
static const int mod=(1e9)+9;
inline void inc(int&x,int y){
if((x+=y)>=mod)
x-=mod;
}
inline void dec(int&x,int y){
if(x>=y)
x-=y;
else
x=x+mod-y;
}
int C[1510][1510];
int f[15][35][35],g[1010][35][35];
inline void getG(int x,int n,int m){
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
g[x][i][j]=C[i*j][x];
for(int _i=1;_i<=i;++_i)
for(int _j=1;_j<=j;++_j)
if(_i*_j<i*j)
dec(g[x][i][j],(long long)g[x][_i][_j]*C[i][_i]%mod*C[j][_j]%mod);
}
}
int main(){
//freopen("tt.in","r",stdin);
int n,m,c;
cin>>n>>m>>c;
int i,j,k;
for(C[0][0]=C[1][0]=C[1][1]=1,i=2;i<=n*m;++i){
C[i][0]=C[i][i]=1;
for(j=1;j<i;++j)
inc(C[i][j]=C[i-1][j],C[i-1][j-1]);
}
g[1][1][1]=1;
f[0][0][0]=1;
int x;
for(i=1;i<=c;++i){
scanf("%d",&x);
getG(x,n,m);
for(j=0;j<=n;++j)
for(k=0;k<=m;++k)
for(int _j=0;j+_j<=n;++_j)
for(int _k=0;k+_k<=m;++_k)
if(_j*_k>=x)
inc(f[i][j+_j][k+_k],(long long)f[i-1][j][k]*g[x][_j][_k]%mod*C[j+_j][_j]%mod*C[k+_k][_k]%mod);
}
int ans=0;
for(j=0;j<=n;++j)
for(k=0;k<=m;++k)
inc(ans,(long long)f[c][j][k]*C[n][j]%mod*C[m][k]%mod);
cout<<ans<<endl;
return 0;
}
弱省胡策Round7 A
我这个大傻叉只会$O(n^3)$,并且知道prufer序列之后也不会$O(n^2)$.
于是果断请教ZYF大爷.
首先肯定是要枚举环的长度$k$,关键的是剩下的怎么搞.
这个我现在还不是非常理解,等我稍微好一点了在进行解释...
弱省胡策Round7 B
对每个高度维护一颗线段树维护最长连续存在区间,注意到存在性是随着高度递减有包含关系的,所以直接用持久化线段树,空间复杂度$O(nlogn)$.
维护一个全局堆表示每个高度的答案,同时每次修改相当于对两个高度进行单点修改,直接改一下,然后在全局堆里面修改就行了.
于是时间复杂度$O((n+m)logn)$.
BZOJ4143
对于每一天分别维护最早结束的和最晚开始的.
BZOJ4144
首先spfa搞出对于每个点$x$到最近的加油站的距离$d[x]$.
然后对于原有的边$(x,y,w)$建立新边$(x,y,d[x]+d[y]+w)$.
然后将询问离线,每次插入所有权值不超过询问的边,并回答两个询问的点是否连通.
利用并查集维护即可.
正确性:我们考虑$(x,y)$如果在新边的意义下连通,那么脑补一下可以发现必定存在一个加油站序列使得两两之间的最短路不超限制.这样的话自然就是可达的了.
BZOJ4145
令$f[s]$表示在一家店购买集合$s$的最小值,令$g[s]$表示购买集合$s$的最小值.
枚举一遍更新出$f$,注意把到商店的费用也算上.
然后$O(3^n)$枚举子集状压dp.
BZOJ4146
令$f[i]$表示有多少数是$i$的倍数.
这个直接$O(nlogn)$求就行了.
然后枚举每个数作为约数的对即可.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 2000010
int a[N];
int c[N],d[N];
int main(){
int n;
scanf("%d",&n);
int i,j;
for(i=1;i<=n;++i)
scanf("%d",&a[i]),++c[a[i]];
for(i=1;i<=2000000;++i)
for(j=i;j<=2000000;j+=i)
d[i]+=c[j];
long long ans=0;
for(i=1;i<=n;++i)
ans+=d[a[i]]-1;
cout<<ans<<endl;
return 0;
}
BZOJ4152
考虑每个点,以这个点为中心,在每个象限内,假设是代价为$delta_y$的那个象限,必定只有与这个点$y$的差的绝对值最小的点才有用.
于是这样只会有$O(n)$条边.
就可以做了.
BZOJ3608
个人以为和COT3并没有不同?
BZOJ2563
我们要从考虑答案的贡献入手.
假设现在有一个人要先手,我们考虑所有事情对先手-后手分数的贡献.
选择一个点:贡献$w_i$.
不选一个点:贡献$-w_i$.
一条边的两个端点都被选中:贡献$c_j$.
一条边只有一个端点被选中:贡献$0$.
一条边没有端点被选中:贡献$-c_j$.
我们发现这是一个等差数列,于是预先将答案加上$\sum{w_i}+\sum{c_j}$,于是现在的贡献分别变成:
$2w_i,0,2c_j,c_j,0$.
令每个点的贡献为$2w_i+c_j$,每个点的贡献都是独立的.
于是贪心从大到小选就行了.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define N 10010
#define M 100010
int a[N];
int main(){
int n,m;
scanf("%d%d",&n,&m);
ll ans=0;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
ans-=a[i];
a[i]*=2;
}
int x,y,z;
for(int i=1;i<=m;++i){
scanf("%d%d%d",&x,&y,&z);
ans-=z;
a[x]+=z,a[y]+=z;
}
sort(a+1,a+n+1);
for(int i=2;i<=n;i+=2)
ans+=a[i];
cout<<ans<<endl;
return 0;
}
2333
随便搞点什么东西罢...
Jun 05, 2015 08:17:13 PM
BZOJ2709
二分+最短路,主要是精度问题,可以根据我的程序调整精度.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef double f2;
int head[10010],next[100010],end[100010],ind;
f2 len[100010];
inline void reset(){
ind=0;
memset(head,0,sizeof head);
}
inline void addedge(int a,int b,f2 l){
int q=++ind;
end[q]=b;
next[q]=head[a];
head[a]=q;
len[q]=l;
}
bool map[110][110];
char s[110];
int lab[110][110],id;
static const int dx[]={-1,1,0,0};
static const int dy[]={0,0,-1,1};
f2 d[10010];
queue<int>q;
bool inq[10010];
inline void spfa(int s){
int i,j;
for(i=1;i<=id;++i)
d[i]=1e10;
d[s]=0;
inq[s]=1;
q.push(s);
while(!q.empty()){
i=q.front();
q.pop();
inq[i]=0;
for(j=head[i];j;j=next[j]){
if(d[end[j]]>d[i]+len[j]){
d[end[j]]=d[i]+len[j];
if(!inq[end[j]]){
inq[end[j]]=1;
q.push(end[j]);
}
}
}
}
}
bool inrange(int x,int l,int r){
return x>=l&&x<=r;
}
int main(){
int T;
cin>>T;
f2 L;
int n,m,i,j,k;
for(int Tcase=1;Tcase<=T;++Tcase){
scanf("%lf%d%d",&L,&n,&m);
int bx,by,ex,ey;
memset(map,0,sizeof map);
gets(s+1);
for(i=1;i<=n;++i){
gets(s+1);
for(j=1;j<=m;++j){
if(s[j]!='#')
map[i][j]=1;
if(s[j]=='S')
bx=i,by=j;
if(s[j]=='E')
ex=i,ey=j;
}
}
id=0;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
lab[i][j]=++id;
f2 l=0,r=1000,mid;
while(r-l>1e-10){
mid=(l+r)/2;
reset();
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
if(map[i][j])
for(k=0;k<4;++k)
if(inrange(i+dx[k],1,n)&&inrange(j+dy[k],1,m)&&map[i+dx[k]][j+dy[k]])
addedge(lab[i][j],lab[i+dx[k]][j+dy[k]],(k==0||k==1)?mid:1);
spfa(lab[bx][by]);
if(d[lab[ex][ey]]<L)
l=mid;
else
r=mid;
}
printf("%.5lf\n",l+1e-8);
}
return 0;
}
BZOJ2891
请参见弱省胡策Round2题解.
BZOJ2719
将所有坐标按照模3的余数分为九种类型,只考虑每种类型棋子的数目.
不难发现不跳过棋子的操作对于局面并不存在影响,然后跳过棋子的操作可以看做将两个棋子合并成一个.
于是搜索就行了.
需要注意一点:当当前棋盘上要合并到的位置已经满了,则不能进行这种合并.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
typedef unsigned long long llu;
struct State{
int d[3][3];
State(){
memset(d,0,sizeof d);
}
bool operator==(const State&B)const{
for(int i=0;i<3;++i)
for(int j=0;j<3;++j)
if(d[i][j]!=B.d[i][j])
return 0;
return 1;
}
inline llu hash(){
llu re=0,s=1;
for(int i=0;i<3;++i)
for(int j=0;j<3;++j)
re+=s*d[i][j],s*=131;
return re;
}
};
set<llu>s;
bool ok[3][3][3][3][3][3];
struct Ope{
int x1,y1,x2,y2,x3,y3;
Ope(){}
Ope(int _x1,int _y1,int _x2,int _y2,int _x3,int _y3):x1(_x1),y1(_y1),x2(_x2),y2(_y2),x3(_x3),y3(_y3){}
}O[1010];
int num;
int n,m,x0,y0,K;
int lim[3][3];
static const int dx[]={-1,-1,-1,0,0,1,1,1};
static const int dy[]={-1,0,1,-1,1,-1,0,1};
inline bool check(int x,int y){
return x>=1&&x<=n&&y>=1&&y<=m;
}
inline void pre(){
num=0;
memset(ok,0,sizeof ok);
int x2,y2,x3,y3;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
for(int k=0;k<8;++k){
x2=i+dx[k],y2=j+dy[k];
x3=x2+dx[k],y3=y2+dy[k];
if(check(x2,y2)&&check(x3,y3)&&!ok[i%3][j%3][x2%3][y2%2][x3%3][y3%3]){
ok[i%3][j%3][x2%3][y2%2][x3%3][y3%3]=1;
O[++num]=Ope(i%3,j%3,x2%3,y2%3,x3%3,y3%3);
}
}
}
State end;
inline bool dfs(State&st){
State tmp;
if(st==end)
return 1;
int x1,y1,x2,y2,x3,y3;
for(int i=1;i<=num;++i){
x1=O[i].x1,y1=O[i].y1;
x2=O[i].x2,y2=O[i].y2;
x3=O[i].x3,y3=O[i].y3;
if(st.d[x1][y1]&&st.d[x2][y2]&&st.d[x3][y3]<lim[x3][y3]){
tmp=st;
--tmp.d[x1][y1];
--tmp.d[x2][y2];
++tmp.d[x3][y3];
if(s.find(tmp.hash())==s.end()){
s.insert(tmp.hash());
if(dfs(tmp))
return 1;
}
}
}
return 0;
}
int main(){
int i,j,x,y;
while(scanf("%d%d%d%d%d",&K,&n,&m,&x0,&y0)!=EOF){
memset(lim,0,sizeof lim);
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
++lim[i%3][j%3];
State begin;
while(K--){
scanf("%d%d",&x,&y);
++begin.d[x%3][y%3];
}
for(i=0;i<3;++i)
for(j=0;j<3;++j)
end.d[i][j]=0;
end.d[x0%3][y0%3]=1;
pre();
s.clear();
s.insert(begin.hash());
if(dfs(begin))
puts("Yes");
else
puts("No");
}
return 0;
}
BZOJ4103
虽然是傻逼题,但是多带一个log也是会TLE的.然而带不带log代码都一样长.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
struct Node{
int d[2],s;
}S[300010*32];
int cnt;
int a[1010],b[300010],root[300010];
inline void insert(int&q,int last,int dep,int x){
q=++cnt;
S[q]=S[last];
++S[q].s;
if(dep<0)
return;
insert(S[q].d[(x>>dep)&1],S[last].d[(x>>dep)&1],dep-1,x);
}
int rootl[1010],rootr[1010];
int main(){
int n,m;
scanf("%d%d",&n,&m);
int i,j;
for(i=1;i<=n;++i)
scanf("%d",&a[i]);
for(i=1;i<=m;++i)
scanf("%d",&b[i]);
for(i=1;i<=m;++i)
insert(root[i],root[i-1],30,b[i]);
int q,u,d,l,r,k;
scanf("%d",&q);
while(q--){
scanf("%d%d%d%d%d",&u,&d,&l,&r,&k);
k=(d-u+1)*(r-l+1)+1-k;
for(i=u;i<=d;++i)
rootl[i]=root[l-1],rootr[i]=root[r];
int ans=0;
for(i=30;i>=0;--i){
int ls=0;
for(j=u;j<=d;++j)
ls+=S[S[rootr[j]].d[(a[j]>>i)&1]].s-S[S[rootl[j]].d[(a[j]>>i)&1]].s;
if(ls>=k){
for(j=u;j<=d;++j){
rootl[j]=S[rootl[j]].d[(a[j]>>i)&1];
rootr[j]=S[rootr[j]].d[(a[j]>>i)&1];
}
}
else{
k-=ls;
ans+=1<<i;
for(j=u;j<=d;++j){
rootl[j]=S[rootl[j]].d[1-((a[j]>>i)&1)];
rootr[j]=S[rootr[j]].d[1-((a[j]>>i)&1)];
}
}
}
printf("%d\n",ans);
}
return 0;
}
BZOJ3064
其实写这道题一开始我是拒绝的,但后来心血来潮了,于是就写了.
觉得这些操作都非常有道理.
同时必须要注意先下传历史标记,再下传当前标记.
具体的题解看18357的博客吧...
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100010
#define inf 0x3f3f3f3f
inline void maxi(int&x,int y){
if(x<y)
x=y;
}
struct Node{
int l,r;
int v,ad,c;
int hv,had,hc;
}S[200010];
inline void h_add(int x,int _had){
maxi(S[x].hv,S[x].v+_had);
if(S[x].c!=-inf)
maxi(S[x].hc,S[x].c+_had);
else
maxi(S[x].had,S[x].ad+_had);
}
inline void h_cover(int x,int _hc){
maxi(S[x].hv,_hc);
maxi(S[x].hc,_hc);
}
inline void add(int x,int _ad){
maxi(S[x].hv,S[x].v+=_ad);
if(S[x].c!=-inf)
maxi(S[x].hc,S[x].c+=_ad);
else
maxi(S[x].had,S[x].ad+=_ad);
}
inline void cover(int x,int _c){
maxi(S[x].hv,S[x].v=_c);
maxi(S[x].hc,S[x].c=_c);
S[x].ad=0;
}
inline void down(int x){
if(S[x].had!=0){
h_add(S[x].l,S[x].had);
h_add(S[x].r,S[x].had);
S[x].had=0;
}
if(S[x].hc!=-inf){
h_cover(S[x].l,S[x].hc);
h_cover(S[x].r,S[x].hc);
S[x].hc=-inf;
}
if(S[x].ad!=0){
add(S[x].l,S[x].ad);
add(S[x].r,S[x].ad);
S[x].ad=0;
}
if(S[x].c!=-inf){
cover(S[x].l,S[x].c);
cover(S[x].r,S[x].c);
S[x].c=-inf;
}
}
inline void up(int x){
S[x].v=max(S[S[x].l].v,S[S[x].r].v);
maxi(S[x].hv,max(S[S[x].l].hv,S[S[x].r].hv));
}
int cnt=0,a[N];
inline int build(int tl,int tr){
int q=++cnt;
S[q].ad=S[q].had=0;
S[q].c=S[q].hc=-inf;
if(tl==tr){
S[q].v=S[q].hv=a[tl];
return q;
}
int mid=(tl+tr)>>1;
S[q].l=build(tl,mid);
S[q].r=build(mid+1,tr);
up(q);
return q;
}
inline void Qadd(int q,int tl,int tr,int dl,int dr,int _ad){
down(q);
if(dl<=tl&&tr<=dr){
add(q,_ad);
return;
}
int mid=(tl+tr)>>1;
if(dr<=mid)
Qadd(S[q].l,tl,mid,dl,dr,_ad);
else if(dl>mid)
Qadd(S[q].r,mid+1,tr,dl,dr,_ad);
else{
Qadd(S[q].l,tl,mid,dl,mid,_ad);
Qadd(S[q].r,mid+1,tr,mid+1,dr,_ad);
}
up(q);
}
inline void Qcover(int q,int tl,int tr,int dl,int dr,int _c){
down(q);
if(dl<=tl&&tr<=dr){
cover(q,_c);
return;
}
int mid=(tl+tr)>>1;
if(dr<=mid)
Qcover(S[q].l,tl,mid,dl,dr,_c);
else if(dl>mid)
Qcover(S[q].r,mid+1,tr,dl,dr,_c);
else{
Qcover(S[q].l,tl,mid,dl,mid,_c);
Qcover(S[q].r,mid+1,tr,mid+1,dr,_c);
}
up(q);
}
inline int Qv(int q,int tl,int tr,int dl,int dr){
down(q);
if(dl<=tl&&tr<=dr)
return S[q].v;
int mid=(tl+tr)>>1;
if(dr<=mid)
return Qv(S[q].l,tl,mid,dl,dr);
else if(dl>mid)
return Qv(S[q].r,mid+1,tr,dl,dr);
else
return max(Qv(S[q].l,tl,mid,dl,mid),Qv(S[q].r,mid+1,tr,mid+1,dr));
}
inline int Qhv(int q,int tl,int tr,int dl,int dr){
down(q);
if(dl<=tl&&tr<=dr)
return S[q].hv;
int mid=(tl+tr)>>1;
if(dr<=mid)
return Qhv(S[q].l,tl,mid,dl,dr);
else if(dl>mid)
return Qhv(S[q].r,mid+1,tr,dl,dr);
else
return max(Qhv(S[q].l,tl,mid,dl,mid),Qhv(S[q].r,mid+1,tr,mid+1,dr));
}
int main(){
int n;
scanf("%d",&n);
int i,j;
for(i=1;i<=n;++i)
scanf("%d",&a[i]);
build(1,n);
int m,l,r,x;
char q[10];
scanf("%d",&m);
while(m--){
scanf("%s%d%d",q,&l,&r);
if(q[0]=='Q')
printf("%d\n",Qv(1,1,n,l,r));
else if(q[0]=='A')
printf("%d\n",Qhv(1,1,n,l,r));
else if(q[0]=='P'){
scanf("%d",&x);
Qadd(1,1,n,l,r,x);
}
else{
scanf("%d",&x);
Qcover(1,1,n,l,r,x);
}
}
return 0;
}
BZOJ2482
考虑如果我们已经有了所有以$i$为开头的区间的满足题意的子段和(而不是最大子段和),那我们如何求出所有开头为$i-1$的区间的子段和呢?
令$nxt[i]$表示$i$后面第一个与$i$的权值相同的位置,那我们只需把$(i-1,nxt[i-1]-1)$这段区间的答案加上$i-1$的权值即可.
我们可以考虑离线处理,将所有询问区间按照起点从大到小排序,然后依次从大到小添加左端点,添加完左端点后则回答所有左端点为当前左端点的询问区间的答案,答案显然就是这段区间答案的历史最大值.
至于为什么是这样,大家理性yy一下吧.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100010
int a[N],seq[N],sav[N],id;
inline int getid(int x){
return lower_bound(sav+1,sav+id+1,x)-sav;
}
int nxt[N],last[N];
struct Node{
int l,r,hv,v,ad,had;
}S[200010];
int cnt;
inline void maxi(int&x,int y){
if(x<y)
x=y;
}
inline int build(int tl,int tr){
int q=++cnt;
S[q].v=0;
S[q].hv=-inf;
if(tl==tr)
return q;
int mid=(tl+tr)>>1;
S[q].l=build(tl,mid);
S[q].r=build(mid+1,tr);
return q;
}
inline void add(int x,int _ad){
maxi(S[x].hv,S[x].v+=_ad);
maxi(S[x].had,S[x].ad+=_ad);
}
inline void h_add(int x,int _had){
maxi(S[x].hv,S[x].v+_had);
maxi(S[x].had,S[x].ad+_had);
}
inline void down(int x){
if(S[x].l){
if(S[x].had!=0){
h_add(S[x].l,S[x].had);
h_add(S[x].r,S[x].had);
S[x].had=0;
}
if(S[x].ad!=0){
add(S[x].l,S[x].ad);
add(S[x].r,S[x].ad);
S[x].ad=0;
}
}
}
inline void up(int x){
if(S[x].l){
S[x].v=max(S[S[x].l].v,S[S[x].r].v);
maxi(S[x].hv,max(S[S[x].l].hv,S[S[x].r].hv));
}
}
inline void Qadd(int q,int tl,int tr,int dl,int dr,int _ad){
down(q);
if(dl<=tl&&tr<=dr){
add(q,_ad);
return;
}
int mid=(tl+tr)>>1;
if(dr<=mid)
Qadd(S[q].l,tl,mid,dl,dr,_ad);
else if(dl>mid)
Qadd(S[q].r,mid+1,tr,dl,dr,_ad);
else{
Qadd(S[q].l,tl,mid,dl,mid,_ad);
Qadd(S[q].r,mid+1,tr,mid+1,dr,_ad);
}
up(q);
}
inline int Qhv(int q,int tl,int tr,int dl,int dr){
down(q);
if(dl<=tl&&tr<=dr)
return S[q].hv;
int mid=(tl+tr)>>1;
if(dr<=mid)
return Qhv(S[q].l,tl,mid,dl,dr);
else if(dl>mid)
return Qhv(S[q].r,mid+1,tr,dl,dr);
else
return max(Qhv(S[q].l,tl,mid,dl,mid),Qhv(S[q].r,mid+1,tr,mid+1,dr));
}
struct Interval{
int l,r,lab;
Interval(){}
Interval(int _l,int _r):l(_l),r(_r){}
bool operator<(const Interval&B)const{
return l>B.l;
}
}I[N];
int ans[N];
int main(){
//freopen("tt.in","r",stdin);
int n;
scanf("%d",&n);
int i,j;
for(i=1;i<=n;++i)
scanf("%d",&a[i]),seq[i]=a[i];
sort(seq+1,seq+n+1);
for(i=1;i<=n;){
for(j=i;j!=n&&seq[j]==seq[j+1];++j);
sav[++id]=seq[i];
i=j+1;
}
for(i=n;i>=1;--i){
int _id=getid(a[i]);
nxt[i]=last[_id]==0?n+1:last[_id];
last[_id]=i;
}
int Q;
scanf("%d",&Q);
for(i=1;i<=Q;++i){
scanf("%d%d",&I[i].l,&I[i].r);
I[i].lab=i;
}
sort(I+1,I+Q+1);
build(1,n);
j=1;
for(i=n;i>=1;--i){
Qadd(1,1,n,i,nxt[i]-1,a[i]);
for(;j<=Q&&I[j].l==i;++j)
ans[I[j].lab]=Qhv(1,1,n,i,I[j].r);
}
for(i=1;i<=Q;++i)
printf("%d\n",max(0,ans[i]));
return 0;
}
弱省胡策Round1 IHHH
令字符集大小为$|S|$,所有串的总长度为$\sum{L}$.
如果内存大一点的话,就可以直接fail树+主席树了,这样空间和时间是$O(\sum_{L}|S|+\sum{L}logn)$.
由于空间的常数有点大,这样就MLE了.
考虑把所有的询问拆分到$O(logn)$个线段树节点上,然后对于每个线段树节点,我们建立这个节点的所有串的ac自动机,然后对于这个节点上所有的询问暴力在上面走一遍.
这样每个串都会被建到$O(logn)$的ac自动机上,然后每个询问串都会被走$O(logn)$遍.
这样时间复杂度是$O(\sum{L}logn)$,但内存是线性的,于是很轻松就过了.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
#define N 100010
#define L 500010
int s_begin[N],s_end[N],ends,t_begin[N],t_end[N],endt;
char s[L],t[L],tmp[L];
struct Node{
int l,r;
std::vector<int>v;
}S[N<<1];
int cnt;
inline int build(int tl,int tr){
int q=++cnt;
if(tl==tr)
return q;
int mid=(tl+tr)>>1;
S[q].l=build(tl,mid);
S[q].r=build(mid+1,tr);
return q;
}
inline void cover(int q,int tl,int tr,int dl,int dr,int lab){
if(dl<=tl&&tr<=dr){
S[q].v.push_back(lab);
return;
}
int mid=(tl+tr)>>1;
if(dr<=mid)
cover(S[q].l,tl,mid,dl,dr,lab);
else if(dl>mid)
cover(S[q].r,mid+1,tr,dl,dr,lab);
else{
cover(S[q].l,tl,mid,dl,mid,lab);
cover(S[q].r,mid+1,tr,mid+1,dr,lab);
}
}
int id,tranc[L][26],dep[L],fail[L];
inline void reset(){
id=0;
memset(tranc[0],0,sizeof tranc[0]);
}
inline int newnode(){
int q=++id;
for(int i=0;i<26;++i)
tranc[q][i]=0;
dep[q]=fail[q]=0;
return q;
}
std::queue<int>q;
int ans[N];
inline void solve(int q,int tl,int tr){
if(S[q].v.size()){
reset();
for(int i=tl;i<=tr;++i){
int p=0;
for(int j=s_begin[i];j<=s_end[i];++j){
if(!tranc[p][s[j]-'a'])
tranc[p][s[j]-'a']=newnode();
p=tranc[p][s[j]-'a'];
}
dep[p]=s_end[i]-s_begin[i]+1;
}
int u,v,r;
for(int i=0;i<26;++i)
if(tranc[0][i])
::q.push(tranc[0][i]);
while(!::q.empty()){
u=::q.front();
::q.pop();
for(int i=0;i<26;++i){
if(tranc[u][i]){
::q.push(v=tranc[u][i]);
for(r=fail[u];r&&!tranc[r][i];r=fail[r]);
dep[v]=std::max(dep[v],dep[fail[v]=tranc[r][i]]);
}
else
tranc[u][i]=tranc[fail[u]][i];
}
}
for(int i=0;i<S[q].v.size();++i){
int p=0;
for(int j=t_begin[S[q].v[i]];j<=t_end[S[q].v[i]];++j)
ans[S[q].v[i]]=std::max(ans[S[q].v[i]],dep[p=tranc[p][t[j]-'a']]);
}
}
int mid=(tl+tr)>>1;
if(tl!=tr){
solve(S[q].l,tl,mid);
solve(S[q].r,mid+1,tr);
}
}
int main(){
//freopen("tt.in","r",stdin);
int n,q;
scanf("%d%d",&n,&q);
int i,j,len;
for(i=1;i<=n;++i){
scanf("%s",tmp+1);
len=strlen(tmp+1);
s_begin[i]=ends+1;
s_end[i]=ends+len;
for(j=1;j<=len;++j)
s[++ends]=tmp[j];
}
build(1,n);
int l,r;
for(i=1;i<=q;++i){
scanf("%d%d%s",&l,&r,tmp+1);
len=strlen(tmp+1);
t_begin[i]=endt+1;
t_end[i]=endt+len;
for(j=1;j<=len;++j)
t[++endt]=tmp[j];
cover(1,1,n,l,r,i);
}
solve(1,1,n);
for(i=1;i<=q;++i)
printf("%d\n",ans[i]);
return 0;
}
[20150607]A
题目大意:对于一个排列,权值为相邻两个元素的差的绝对值之和.给定$n$,并给出某些限制,限制形式为$A_{x}=y$,即排列的第$x$个元素是$y$.求所有$1-n$的且满足限制条件的排列的权值之和对$998244353$取模的余数.
思路:由于太懒就不写题解啦蛤蛤.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define N 1000010
int d[N],ins[N],seq[N],id;
ll pre[N];
int ds[N];
static const int mod=998244353;
inline void inc(int&x,int y){
if((x+=y)>=mod)
x-=mod;
}
int fac[N];
int dist(int a,int b){
return a<b?b-a:a-b;
}
struct Interval{
int l,r;
Interval(){}
Interval(int _l,int _r):l(_l),r(_r){}
}I[N];
int num;
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(){
int n;
scanf("%d",&n);
int i,j;
for(i=1;i<=n;++i){
d[i]=getint();
if(d[i])
ins[d[i]]=i;
}
for(i=1;i<=n;++i)
if(!ins[i]){
seq[++id]=i;
pre[id]=pre[id-1]+seq[id];
}
seq[id+1]=n+1;
for(fac[0]=i=1;i<=n;++i)
fac[i]=(ll)fac[i-1]*i%mod;
if(id==n){
int ans=0;
for(i=1;i<n;++i)
ans=((ll)ans*i%mod+2ll*fac[i]%mod*((ll)i*(i+1)/2%mod)%mod)%mod;
cout<<ans<<endl;
}
else if(id==0){
int ans=0;
for(i=1;i<n;++i)
inc(ans,dist(d[i],d[i+1]));
cout<<ans<<endl;
}
else if(id==1){
for(i=1;i<=n;++i)
if(!d[i])
d[i]=seq[1];
int ans=0;
for(i=1;i<n;++i)
inc(ans,dist(d[i],d[i+1]));
cout<<ans<<endl;
}
else{
int preans=0;
for(i=1;i<id;++i)
preans=((ll)preans*i%mod+2ll*fac[i]%mod*(((ll)seq[i+1]*i-pre[i])%mod)%mod)%mod;
int dsum=0;
for(i=1;i<=id;++i)
inc(dsum,(((ll)(i-1)*seq[i]-pre[i-1])+(pre[id]-pre[i]-(ll)(id-i)*seq[i]))%mod);
int ans=0;
j=0;
for(i=1;i<=n;++i){
if(ins[i]){
while(i>=seq[j+1])
++j;
ds[i]=(((ll)j*i-pre[j])+(pre[id]-pre[j]-(ll)(id-j)*i))%mod;
}
}
for(i=1;i<=n;){
if(d[i]==0){
for(j=i+1;j<=n&&d[j]==0;++j);
i=j;
}
else{
for(j=i+1;j<=n&&d[j]>0;++j);
I[++num]=Interval(i,j-1);
i=j;
}
}
for(i=1;i<=num;++i){
for(j=I[i].l;j<I[i].r;++j)
inc(ans,(ll)dist(d[j],d[j+1])*fac[id]%mod);
if(I[i].l!=1&&I[i].r!=n){
inc(ans,(ll)(ds[d[I[i].l]]+ds[d[I[i].r]])%mod*(id-1)%mod*fac[id-2]%mod);
inc(ans,(-(ll)dsum*fac[id-2]%mod+mod)%mod);
}
else if(I[i].l==1)
inc(ans,(ll)ds[d[I[i].r]]*fac[id-1]%mod);
else if(I[i].r==n)
inc(ans,(ll)ds[d[I[i].l]]*fac[id-1]%mod);
}
ans=((preans+ans)%mod+mod)%mod;
cout<<ans<<endl;
}
return 0;
}
[20150607]B
题目大意:定义一个数的权值为这个数的十进制表示的最长的等差子串的长度.现在问$[l,r]$区间内的权值和.
思路:典型的数位dp.我是这样做的:令$f[i][j][k][lp][ls]$表示长度为$i$,首位的数字为$j$,最长前缀等差子串的公差为$k$,最长前缀等差子串的长度为$lp$,最长等差子串的长度为$ls$的个数.
然后转移就随便了.
最后还是转化为前缀和相减,按位确定一下,也不是很难.
拍一下就行了.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<ctime>
using namespace std;
typedef long long ll;
ll f[14][10][22][14][14];
#define c(x) ((x)+10)
inline int getans(ll x){
if(x==0)
return 0;
int stack[20];
int top=0;
for(;x;x/=10)
stack[++top]=x%10;
int ans=1;
for(int i=1;i<top;++i){
int q=stack[i]-stack[i+1];
int j=i+1;
for(;j!=top&&stack[j]-stack[j+1]==q;++j);
ans=max(ans,j-i+1);
}
return ans;
}
inline ll solve(ll x){
if(x==0)
return 0;
int stack[20];
int top=0;
ll tmp=x;
for(;tmp;tmp/=10)
stack[++top]=tmp%10;
ll ans=0;
int i,j,k,lp,ls;
for(i=1;i<top;++i)
for(j=1;j<10;++j)
for(k=-9;k<=10;++k)
for(lp=1;lp<=i;++lp)
for(ls=1;ls<=i;++ls)
ans+=f[i][j][c(k)][lp][ls]*ls;
for(i=top;i>=1;--i){
int ch=stack[i];
for(int _j=i==top?1:0;_j<ch;++_j){
stack[i]=_j;
for(j=0;j<10;++j)
for(k=-9;k<=10;++k)
for(lp=1;lp<=i-1;++lp)
for(ls=1;ls<=i-1;++ls){
if(f[i-1][j][c(k)][lp][ls]){
int _lp=lp,_ls=ls,last=j,_k=k;
for(int ins=i;ins<=top;++ins){
if(stack[ins]-last==_k){
++_lp;
}
else{
_lp=2;
_k=stack[ins]-last;
}
_ls=max(_ls,_lp);
last=stack[ins];
}
ans+=f[i-1][j][c(k)][lp][ls]*_ls;
}
}
}
stack[i]=ch;
}
for(long long c=max(1ll,x/10*10);c<=x;++c)
ans+=getans(c);
return ans;
}
int main(){
int i,j,k,lp,ls,g,np,ns;
for(i=0;i<10;++i)
f[1][i][c(10)][1][1]=1;
for(i=1;i<13;++i)
for(j=0;j<10;++j)
for(k=-9;k<=10;++k)
for(lp=1;lp<=i;++lp)
for(ls=1;ls<=i;++ls)
for(g=0;g<10;++g){
np=(j+k==g)?lp+1:2;
ns=max(ls,np);
f[i+1][g][c(g-j)][np][ns]+=f[i][j][c(k)][lp][ls];
}
int T;
cin>>T;
ll L,R;
while(T--){
cin>>L>>R;
cout<<solve(R)-solve(L-1)<<endl;
}
return 0;
}
[20150607]C
题目大意:(以下是原题面)
hzc有一个只包含大写字母的字符串 s. 他可以对这个字符串进行任意次的修改，允许的修改有：
1. 他可以添加下划线：('_') 到字符串的任意位置。
2. 他可以删除字符串里边的任意字符。
3. 他可以交换字符串的任意两个字符。
修改后的字符串，每一个字符的值为它的ASCII码值。
修改后的字符串必须满足如下条件：
1. 字符串的长度等于 n
2. 每个相同字母之间必须有至少 k 个字符的值比它们的值大。（下划线不当作字母）
计算hzc一共能得到多少不同的字符串？ 答案对1000003取模。
思路:注意到答案只与字母的数量有关.我们从小到大向最终的字符串中插入字母,令$f[i][j]$表示只考虑前$i$种字母,共插入了$j$个的方案数.那么我们显然应该枚举插入多少个当前的字母,假设我们要从$f[i-1][j]$转移到$f[i][j+g]$,那么方案数是多少呢?现在空着的位置还有$n-j$个,同时相邻的两个当前字母至少至少应该相隔$k$个空格,那么有$(g-1)\times{k}$个空格是不能用的,于是从剩下的空格中选择$g$个就行了,利用组合数算一算就行了.
那么从大到小为什么不能这样简单呢?
总之是不能像从小到大这样直接做的啦!
弱省胡策Round1 OVOO
一个状态就是一个合法的点集,权值即为所有点集里面的点的父亲边的权值和.
那么我们依然利用优先队列来维护,弹出一个状态的时候在队列中加入比这个状态大且最小的状态,这样做$k$次就行了.
要想比这个状态大一点点,我们首先可以考虑添加一个儿子,同时这个儿子父亲边的权值最小.
对于每个状态,我们维护一个堆,里面存的是所有接下来可以拓展的儿子,那么拓展下一个状态直接取堆顶就行喽.
然而比这个状态大一点点不一定就是拓展出一个新的儿子.
考虑这个状态的父亲状态,在这个父亲状态中我们取堆顶的左右儿子进行拓展不也是比这个状态大一点点嘛.
所以我们得到一个状态,首先拓展出一个添加最小儿子的状态,然后再添加一个将堆顶删除掉的状态.
(说不太明白,不过容易发现这样是对的
然后这些东西都用可持久化可并堆来维护.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define N 100010
struct Node{
Node*l,*r;
int v,lab,dist;
Node():dist(0){}
}mem[N*60],*P=mem,Tnull,*null=&Tnull;
inline void copy(Node*&x,Node*y){
if(y==null)
x=null;
else
*x=*y;
}
inline Node*Newnode(){
P->l=P->r=null;
P->dist=1;
return P++;
}
inline Node*Merge(Node*x,Node*y){
Node*re=Newnode();
if(x==null||y==null)
copy(re,x==null?y:x);
else{
if(x->v>y->v)
swap(x,y);
copy(re,x);
re->r=Merge(x->r,y);
if(re->r->dist>re->l->dist)
swap(re->l,re->r);
re->dist=re->r->dist+1;
}
return re;
}
Node*Root[N];
int pa[N],v[N];
int head[N],next[N],end[N];
inline void addedge(int a,int b){
static int q=1;
end[q]=b;
next[q]=head[a];
head[a]=q++;
}
inline void dfs(int x){
Root[x]=null;
for(int j=head[x];j;j=next[j]){
Node*tmp=Newnode();
tmp->v=v[end[j]];
tmp->lab=end[j];
tmp->dist=1;
Root[x]=Merge(Root[x],tmp);
}
for(int j=head[x];j;j=next[j])
dfs(end[j]);
}
typedef long long ll;
struct State{
Node*p;
ll v;
bool operator<(const State&B)const{
return v+p->v>B.v+B.p->v;
}
};
priority_queue<State>Q;
int main(){
int n,K;
scanf("%d%d",&n,&K);
int i,j;
for(i=2;i<=n;++i){
scanf("%d%d",&pa[i],&v[i]);
addedge(pa[i],i);
}
dfs(1);
State begin;
begin.p=Root[1];
begin.v=0;
Q.push(begin);
ll ans=0;
State tmp,nxt;
for(int i=2;i<=K;++i){
if(Q.empty())
break;
tmp=Q.top();
Q.pop();
ans=tmp.v+tmp.p->v;
Node*next=Merge(tmp.p->l,tmp.p->r);
if(next!=null){
nxt=tmp;
nxt.p=next;
Q.push(nxt);
}
next=Merge(next,Root[tmp.p->lab]);
if(next!=null){
nxt=tmp;
nxt.p=next;
nxt.v+=tmp.p->v;
Q.push(nxt);
}
}
cout<<ans%998244353<<endl;
return 0;
}
弱省胡策Round4 Message
无脑分数规划+最大权闭合图,有点卡精度,比赛时inf设成了1e12是70分,后来改成了1e10就过了.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
typedef double f2;
#define eps 1e-10
#define inf 1e10
struct Solver{
static const int V=2010;
static const int E=100010;
int head[V],end[E],next[E],ind;
f2 flow[E];
int d[V];
inline void reset(){
ind=0;
memset(head,-1,sizeof head);
}
inline void addedge(int a,int b,f2 c){
int q=ind++;
end[q]=b;
next[q]=head[a];
head[a]=q;
flow[q]=c;
}
inline void make(int a,int b,f2 c){
addedge(a,b,c);
addedge(b,a,0);
}
inline bool bfs(int s,int t){
static int q[V];
memset(d,-1,sizeof d);
d[s]=0;
int fr=0,ta=0;
q[ta++]=s;
while(fr!=ta){
int i=q[fr++];
for(int j=head[i];j!=-1;j=next[j])
if(flow[j]>eps&&d[end[j]]==-1){
d[end[j]]=d[i]+1;
q[ta++]=end[j];
}
}
return d[t]!=-1;
}
inline f2 dinic(int p,int t,f2 Maxflow){
if(p==t)
return Maxflow;
f2 last=Maxflow;
for(int j=head[p];j!=-1;j=next[j]){
if(flow[j]>eps&&d[end[j]]==d[p]+1){
f2 to=dinic(end[j],t,flow[j]>last?last:flow[j]);
if(to>eps){
flow[j]-=to;
flow[j^1]+=to;
if((last-=to)<eps)
return Maxflow;
}
}
}
d[p]=-1;
return Maxflow-last;
}
inline f2 Maxflow(int s,int t){
f2 re=0;
while(bfs(s,t))
re+=dinic(s,t,inf);
return re;
}
}g;
#define N 110
#define M 1010
int c[N];
int a[M],b[M],p[M];
int main(){
int n,m;
scanf("%d%d",&n,&m);
int i,j;
for(i=1;i<=n;++i)
scanf("%d",&c[i]);
int sigp=0;
for(i=1;i<=m;++i){
scanf("%d%d%d",&a[i],&b[i],&p[i]);
sigp+=p[i];
}
f2 L=0,R=1e6,mid;
while(R-L>eps){
mid=(L+R)*.5;
g.reset();
int s=0,t=n+m+1;
for(i=1;i<=m;++i)
g.make(s,n+i,p[i]);
for(i=1;i<=n;++i)
g.make(i,t,mid*c[i]);
for(i=1;i<=m;++i){
g.make(n+i,a[i],inf);
g.make(n+i,b[i],inf);
}
f2 res=g.Maxflow(s,t);
if(sigp-res>0)
L=mid;
else
R=mid;
}
printf("%.2lf",L+eps);
return 0;
}
弱省胡策Round4 Road
一个非常有用的事实:一个边双连通图必定是一个边双连通子图再加上条链组合成的.
一个点自己可以是一个边双连通子图,也可以看成一条链.
这样可以令$f_i$表示$i$这个集合内部的点组成一个双连通图的最小代价.
再令$g_{i,j,k}$表示$i$这个集合内部的点组成一条链,且两个端点分别是$j,k$的最小代价.
再预处理出$h1_{i,j},h2_{i,j}$分别表示点$j$到集合$i$的所有边的最小长度和次小长度.
然后再按照刚才说的状态随便转移一下就好了.
复杂度呢:我懒不想算了哈哈哈.
弱省胡策Round4 Express
原题大赛:BZOJ3302
暴力很好写,就是枚举把哪条边割断,然后两个部分分别求一下重心就行了.
然后现在我们知道树的高度很小,于是我们可以先做一些预处理,然后我们找出每个点子树权值和最大以及次大的儿子,这样找重心的时候$O(1)$就能知道走向哪个儿子了.
然后依然枚举割断那条边,但是不同的是这次我们直接$O(h)$就能找到重心,然后根据我们之前处理出的信息$O(1)$就能知道现在的代价.
所以这样做的复杂度$O(nh)$.
我的代码会被菊花卡超时,就不放了.
欧拉回路(通路)
最近随便搞了一下这个东西,稍微总结一下吧.
有向图:
存在欧拉回路当且仅当图连通并且所有点入度与出度相等.
存在欧拉通路当且仅当图连通并且所有点入度与出度相等或存在两个点入度-出度分别为-1和1,且剩下的点入度=出度.
无向图:
存在欧拉回路当且仅当图连通并且所有点度数为偶数.
存在欧拉通路当且仅当图连通并且所有点度数为偶数,或者存在两个点度数为奇数,剩下的点度数为偶数.
在判定了以上条件的情况下,就可以用一个简单的dfs找出一条欧拉回路(通路).
从一个合法的起点出发,然后每走一条边就将这条边删除,然后走完之后就把这条边入栈.
最后从栈顶到栈底就是一个合法的序列.
(但是现在依然没有非常理解...)
BZOJ2013
一开始看题目是觉得所有两块砖都满足上述的关系.
然后没过样例...
然后发现是只有相邻两块砖满足题目中说的关系!
于是就变成了逗逼题.
按照砖块长度从小到大排序,考虑前面所有的砖块都放好了,现在我们要插入最大的砖块,那么他作为下面的砖块肯定不会有影响(因为他最大),那么只需考虑他作为上面的砖块,也就是说他只能放在一些砖块的上面,而这个数目我们可以利用单调性扫出来,对于前面放的所有方案,我们都有这些放法,所以答案显然就是前面的答案乘上这个数目.
于是简单扫一遍.
时间$O(nlogn)$.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
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 A[1000010];
static const int mod=(1e9)+9;
int main(){
int n=getint(),d=getint();
int i,j;
for(i=1;i<=n;++i)
A[i]=getint();
sort(A+1,A+n+1);
j=n;
A[0]=-1e9;
int ans=1;
for(i=n;i>=1;--i){
while(A[i]-A[j-1]<=d)
--j;
ans=(long long)ans*(i-j+1)%mod;
}
cout<<ans<<endl;
return 0;
}
BZOJ2386
显然将要求从小到大排序,则同一个分组的人是连续一段.
令$f_i$表示把前$i$个人进行分组,最多分成多少组.
然后利用前缀和优化一下就行了.
时间$O(nlogn)$.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
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;
}
#define N 1000010
int a[N],f[N],g[N];
int main(){
int n=getint();
int i,j;
for(i=1;i<=n;++i)
a[i]=getint();
sort(a+1,a+n+1);
for(i=1;i<=n;++i){
if(a[i]>i)
f[i]=-inf;
else
f[i]=g[i-a[i]]+1;
g[i]=max(g[i-1],f[i]);
}
cout<<f[n]<<endl;
return 0;
}
BZOJ3242
首先显然暴力算法是枚举删掉环上每条边,并求此时树的直径,并取最小值.这样是$O(n^2)$的.
我们只考虑环上的点,记录第$i$个点下面子树的最长延伸为$d_i$,从这个点到第$i$个点需要走的链的长度为$s_i$(由于删除了一条边,所以变环为链).那我们就需要找出一对$(i,j)$,使得$d_i+s_i-s_j+d_j=(d_i+s_i)+(d_j-s_j)$最大,所以我们分别维护这两个量的最大值即可,由于要求$i,j$不同,我们就维护这两个量的最大值以及次大值就行了.
于是这样就能做到$O(nlogn)$.
我一开始的方法非常麻烦,是因为我没有将式子拆开,因而考虑了很多点之间的位置关系,这样固定一个点,将信息都利用值来表示看起来就非常简单了.
由于我太懒就不写代码了.
BZOJ3648
考虑对于树的情况直接树分治就行了.
玛德我就暴力用树状数组$O(nlog^2n)$!
对于基环树,我们不妨拆掉一条环上的边变成一颗树,首先对于这棵树统计一下所有合法路径的数目;然后剩下的路径都固定的经过一条环上的边,直接拿主席树随便玩就行了.
BZOJ1768
考虑先枚举行,然后很容易处理出这一行最多往下延伸多少.然后我们需要排个序,然后枚举一遍.关键这样是$O(nmlogm)$,会超时.
窝们考虑相邻的两行,对于所有的元素,要么+1,要么变成0.这样就不用排序也能维护啦!
总时间复杂度$O(nm)$.
[UR8]A
我的思路比较傻逼,就是把整个图划分成一些黑白相间的块,然后就可以$O(1)$统计两个块之间的距离了.
于是在找这个块在哪里的时候带了一个log...
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100010
int s[N];
int x[N],y[N],cntx,cnty;
inline int getxid(int _x){
int d=upper_bound(x+1,x+cntx+1,_x)-x;
return d-1;
}
inline int getyid(int _y){
int d=upper_bound(y+1,y+cnty+1,_y)-y;
return d-1;
}
inline int getansx(int x1,int x2){
if(x1>x2)
swap(x1,x2);
return min(x2-x1,cntx-(x2-x1)-(cntx&1));
}
inline int getansy(int y1,int y2){
if(y1>y2)
swap(y1,y2);
return min(y2-y1,cnty-(y2-y1)-(cnty&1));
}
int main(){
//freopen("tt.in","r",stdin);
int n,m;
scanf("%d%d",&n,&m);
int i,j;
for(i=1;i<=n;++i)
scanf("%d",&s[i]);
for(i=1;i<=n;){
for(j=i;j!=n&&s[j]==s[j+1];++j);
x[++cntx]=i;
i=j+1;
}
x[cntx+1]=n+1;
for(i=1;i<=m;++i)
scanf("%d",&s[i]);
for(i=1;i<=m;){
for(j=i;j!=m&&s[j]==s[j+1];++j);
y[++cnty]=i;
i=j+1;
}
y[cnty+1]=m+1;
int q;
scanf("%d",&q);
int x1,y1,x2,y2;
while(q--){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x1=getxid(x1),y1=getyid(y1);
x2=getxid(x2),y2=getyid(y2);
printf("%d\n",getansx(x1,x2)+getansy(y1,y2));
}
return 0;
}
[UR8]B
感觉好神一点不会,其实是简单题.
由于有$a,b,c\geq{0}$,所以对于$x_1\leq{x_2},y_1\leq{y_2}$,$(x1,y1)$什么时候都没有$(x2,y2)$优,就可以直接扔掉了.
所以对于每个线段树节点维护一个阶梯状序列就行了.
由于数据随机,这样的序列长度为$O(logn)$级别.
由于要打翻转标记,所以还要维护一个反的序列.
这样修改和询问都是$O(log^2n)$,直接暴力维护序列.
我们换一种方法,每个线段树节点都维护一个矩形框,这样修改只需$O(logn)$.
对于询问,窝现在有点难受,泥萌去看吉利的题解吧...
BZOJ3198
hash+容斥原理,我写的容斥是关于集合的,有点暴力...
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100010
int a[N][6];
typedef unsigned long long llu;
static const int seed=200019;
struct Hashset{
static const int mod=13131;
int head[mod],v[N],next[N],ind;
llu f[N];
inline void reset(){
ind=0;
memset(head,-1,sizeof head);
}
inline void insert(llu x){
int ins=x%mod;
for(int j=head[ins];j!=-1;j=next[j])
if(f[j]==x){
++v[j];
return;
}
f[ind]=x;
v[ind]=1;
next[ind]=head[ins];
head[ins]=ind++;
}
}M;
long long f[1<<6],g[1<<6];
int main(){
int n,k;
cin>>n>>k;
int i,j;
for(i=1;i<=n;++i)
for(j=0;j<6;++j)
scanf("%d",&a[i][j]);
for(int s=0;s<(1<<6);++s){
M.reset();
for(i=1;i<=n;++i){
llu p=0;
for(j=0;j<6;++j)
if((s>>j)&1)
p=p*seed+a[i][j];
M.insert(p);
}
for(i=0;i<M.ind;++i)
f[s]+=(long long)M.v[i]*(M.v[i]-1)/2;
}
long long ans=0;
for(int s=(1<<6)-1;s>=0;--s){
g[s]=f[s];
for(int _s=s+1;_s<(1<<6);++_s)
if((_s|s)==_s)
g[s]-=g[_s];
int cnt=0;
for(i=0;i<6;++i)
if((s>>i)&1)
++cnt;
if(cnt==k)
ans+=g[s];
}
cout<<ans<<endl;
return 0;
}
BZOJ2102
看起来和上面的那道题目没什么区别.
BZOJ2384
以前拿主席树暴力,现在由于主席树要被卡内存,于是学习了一下树状数组的方法.
话说我一直以为这个方法是数据弱才能卡过去的,其实不然,KMP算法是最坏$O(n)$的!
我们考虑一次匹配,会有一个指针$j$,如果匹配了$j++$,否则不断执行$j=next[j]$这个过程.
不妨设模式串长度为$n$,文本串长度为$m$,那么匹配的时候$j++$这个过程最多只会进行$m$次,而每执行一次$j=next[j]$这个过程$j$都会减少,并且$j$不能为负数,所以减少总量$\leq$增加总量$\leq{m}$.所以这两个过程都是$O(m)$级别的.
这个题目是求排名的匹配,那我们就把一个元素的"值"规定为这个元素比前面的区间中大的元素的个数,然后匹配的时候就比较一下这个值相不相等就行了.
我们用两个树状数组暴力维护当前合法区间的值,由于上述的复杂度证明,总时间为$O(mlogm)$.
具体的细节需要自己脑补一下...
(不知道怎么线性...)
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define N 1000010
int a[N],b[N],sav[N];
int A[N],B[N];
inline int ask(int A[],int x){
int re=0;
for(;x;x-=x&-x)
re+=A[x];
return re;
}
inline void modify(int A[],int x,int d){
for(;x<=1000000;x+=x&-x)
A[x]+=d;
}
int pre[N];
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=getint(),m=getint();
int i,j;
for(i=1;i<=n;++i){
a[getint()]=i;
}
for(i=1;i<=m;++i)
sav[i]=b[i]=getint();
sort(sav+1,sav+m+1);
for(i=1;i<=m;++i)
b[i]=lower_bound(sav+1,sav+m+1,b[i])-sav;
//modify(a[1],1);
j=0;
for(i=2;i<=n;++i){
int ins=i-j;
while(1){
if(j==0)
break;
if(ask(A,a[j+1]-1)==ask(B,a[i]-1))
break;
int _(pre[j]);
while(j>_){
modify(B,a[ins++],-1);
modify(A,a[j--],-1);
}
}
if(ask(A,a[j+1]-1)==ask(B,a[i]-1)){
modify(A,a[++j],1);
modify(B,a[i],1);
}
pre[i]=j;
}
memset(A,0,sizeof A);
memset(B,0,sizeof B);
j=0;
vector<int>ans;
for(i=1;i<=m;++i){
int ins=i-j;
while(1){
if(j==0)
break;
if(ask(A,a[j+1]-1)==ask(B,b[i]-1))
break;
int _=pre[j];
while(j>_){
modify(B,b[ins++],-1);
modify(A,a[j--],-1);
}
}
if(ask(A,a[j+1]-1)==ask(B,b[i]-1)){
modify(A,a[++j],1);
modify(B,b[i],1);
}
if(j==n){
int ins=i-j+1;
while(j>pre[n]){
modify(B,b[ins++],-1);
modify(A,a[j--],-1);
}
ans.push_back(i-n+1);
}
}
printf("%d\n",ans.size());
for(i=0;i<ans.size();++i){
if(i)
putchar(' ');
printf("%d",ans[i]);
}
return 0;
}
BZOJ1461
基本同上一题,但是还需要考虑到相等元素的影响,需要分别比较小于的个数以及等于的个数,需要均相等才能匹配.
BZOJ1390
注意到111>3*20,所以一棵树能够围起来的话,肯定是要围起来.
将所有的固定点拿出来做凸包,然后在凸包外面的树就可以放弃治疗了.
在凸包里面的树肯定都是能被保护到的,然后把这些树都拿出来做一个凸包,那么我们要找出最少的固定点把这个凸包围起来.
窝是大逗比...只会$O(n^4)$枚举起点暴力dp...
然而我忘了一个非常简单的东西--直接Floyd求最小环就行了啊!
这样只有$O(n^3)$.
BZOJ1767
NOI2014的d2t3就是从这里来的吧...
这道题太弱了就说原题吧.
树分治做法:
首先找出树的重心,首先分治含有根的那一部分子树(包括重心),然后把剩下的所有点按照购买的范围从小到大排序,这样就可以离线把重心到根路径上的点插入凸包,并直接二分就行了.然后再分治剩下的子树就行了.
线段树+凸包做法:
每到一个点,线段树上都存的是从根到这个点父亲路径上的序列的那些点,然后就像一个区间那样维护,询问的时候二分找到限制的范围,然后进行区间查询,对于每个线段树节点都二分寻找最优值.
怎么维护这个线段树呢?计算完答案,向下dfs时,将这个点插入凸包,由于$x$坐标是递增的,只需要插在末尾就行了.然后向上回溯时在吧这个点删除就行了,也是只删除末尾的点就行了.
关键是我们如果真的模拟一个栈,复杂度就不对了.
所以我们插入的时候直接二分得到应该插入在哪里,然后直接更改尾指针就行了,稍微记录一点东西就能够$O(1)$还原了.
这样只需要严格$O(logn)$就能插入了.
树链剖分+线段树+凸包做法:
玛德我就暴力3个log你管我?
策爷现场好像就是这么过的?
BZOJ3874
猜结论可以发现最终的答案关于叫外卖的次数是一个单峰函数.(玛德!)
于是三分.
那么怎么知道此时的值呢.
我们把所有的外卖进行排序,得到一个关于保质期价格单调递增的序列,然后按照保质期从小到大把外卖塞进这些次的叫外卖中就行了.
于是时间为$O(nlog(10^{18}))$.
BZOJ1789
yy了好长时间的dp没有yy出来QwQ.
结果题解是说最终相同的串必定是某个串的前缀!
这个证明还是很显然吧.
然后模拟就行啦QwQ.
BZOJ3454
暴力并查集.
BZOJ3233
首先我们考虑一个很显然的事情,假如知道硬币序列,那么最少应该用多少枚硬币呢?
我们从大到小贪心就行了,可以证明这样一定是最优的.
不妨令$f[i][j]$表示序列中第$i$大的为$j$时的最小硬币数.
我们预处理$g[j]=\sum_{i=1}^{n}a_i\%j$备用.
注意到序列最多只有$O(logn)$项,且第$i$项不超过$\frac{10^5}{2^{i-1}}$.
那么我们就可以这样转移:$f[i][j]=\sum_{j|k}min\{{f[i-1][k]+(g[k]-g[j])/j}\}$
然后转移的时候充分利用取值范围的限制.
具体的复杂度我就不分析了,但总之转移的总量完全可以接受.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define N 51
int a[N];
int f[21][100010],g[100010];
int main(){
int n;
scanf("%d",&n);
int i,j,k,p,Max=0;
for(i=1;i<=n;++i){
scanf("%d",&a[i]);
Max=max(Max,a[i]);
}
for(i=1;i<=n;++i)
for(j=1;j<=Max;++j)
g[j]+=a[i]%j;
memset(f,0x3f,sizeof f);
for(i=1;i<=Max;++i){
f[1][i]=0;
for(j=1;j<=50;++j)
f[1][i]+=a[j]/i;
}
for(i=2;i<=17;++i)
for(j=1;j<<(i-1)<=Max;++j){
for(k=2*j;k<<(i-2)<=Max;k+=j){
if(f[i-1][k]!=inf)
f[i][j]=min(f[i][j],(g[k]-g[j])/j+f[i-1][k]);
}
}
int ans=inf;
for(i=1;i<=17;++i)
ans=min(ans,f[i][1]);
cout<<ans<<endl;
return 0;
}
BZOJ3460
树上莫队大法嚎!
BZOJ4129
带修改树上莫队大法嚎!
/*强烈鄙视某些人把我送回家种田了*/
弱省胡策Round5A
考试时:
通过找规律发现了$A_i=\sum_{j=i}^{n}C_{j}^{i}(-1)^{j-i}B_{j}$.
然后?不会啦...
明明展开之后用一点技巧就变成卷积了...
结果我根本没展开,而是构造了一个大多项式,但是并没有卵用.
我真TM是大逗比.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define N 262144
int b[N];
#define P 998244353
#define g 3
inline int ksm(int x,int y){
int re=1,t=x;
for(;y;y>>=1,t=(ll)t*t%P)
if(y&1)
re=(ll)re*t%P;
return re;
}
inline int inv(int x){
return ksm(x,P-2);
}
int fac[N],ifac[N];
int X[N],Y[N],pow[N];
inline int revbit(int x,int bit){
int re=0;
for(int i=0;i<bit;++i)
if((x>>i)&1)
re|=1<<(bit-1-i);
return re;
}
inline void fft(int A[],int n,int rev){
static int B[N];
int bit=0,i,j,k;
for(int tmp=n;tmp^1;tmp>>=1,++bit);
for(i=0;i<n;++i)
B[i]=A[revbit(i,bit)];
for(i=0;i<n;++i)
A[i]=B[i];
int w,wn,t;
for(k=2;k<=n;k<<=1)
for(wn=ksm(g,rev==1?(P-1)/k:(P-1)-(P-1)/k),i=0;i<n;i+=k)
for(w=1,j=0;j<(k>>1);++j,w=(ll)w*wn%P){
t=(ll)A[i+j+(k>>1)]*w%P;
A[i+j+(k>>1)]=(A[i+j]-t+P)%P;
(A[i+j]+=t)%=P;
}
if(rev==-1){
int _inv=inv(n);
for(i=0;i<n;++i)
A[i]=(ll)A[i]*_inv%P;
}
}
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=getint();
int i,j;
for(i=0;i<=n;++i)
b[i]=getint();
for(fac[0]=1,i=1;i<=n;++i)
fac[i]=(ll)fac[i-1]*i%P;
for(i=0;i<=n;++i)
ifac[i]=inv(fac[i]);
for(pow[0]=1,i=1;i<=n;++i)
pow[i]=P-pow[i-1];
for(i=0;i<=n;++i){
X[i]=((ll)fac[i]*b[i]%P*pow[i]%P+P)%P;
Y[i]=ifac[n-i];
}
int M;
for(M=1;M<(2*n+2);M<<=1);
fft(X,M,1);
fft(Y,M,1);
for(i=0;i<M;++i)
X[i]=(ll)X[i]*Y[i]%P;
fft(X,M,-1);
for(i=0;i<=n;++i){
if(i)
putchar(' ');
printf("%d",((ll)X[n+i]*ifac[i]%P*pow[i]%P+P)%P);
}
return 0;
}
弱省胡策Round5B
考试是没看出来是构造一个无向图...反而硬找规律...
其实就是构造一个连通无向图使得最长的最短路为$k$.
我们可以构造一个长度为$k-2$的链,然后往两个端点加叶子就行了.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
int G[310][310];
inline void addedge(int a,int b){
G[a][b]=G[b][a]=1;
}
int main(){
int n,k;
scanf("%d%d",&n,&k);
if(k==1){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)
putchar('1');
puts("");
}
}
else{
for(int i=1;i<=n;++i)
addedge(i,i);
for(int i=1;i<k-1;++i)
addedge(i,i+1);
addedge(k,1);
for(int i=k+1;i<=n;++i)
addedge(i,k-1);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)
printf("%d",G[i][j]);
puts("");
}
}
return 0;
}
弱省胡策Round5C
好神的dp...
考虑一个$n\times{m}$的矩阵,假设现在我们要往里面填充第$k$种颜色.
那么现在是有一个长度为$n$的序列,每个元素都表示一行这种元素的个数.
假设我们把这个序列排好了序.
我们肯定需要枚举最小值,以及这个最小值出现了多少次.
不妨令$f_{n,m,d,k}$表示一个$n\times{m}$的矩阵,现在要填充第$k$种颜色,且序列的最小值为${d}$且合法的方案数.
记录一个前缀和$g_{n,m,d,k}=\sum_{i=0}^{d}f_{n,m,i,k}$.
我们枚举这个最小值出现了多少次,假设出现$i$次.
那么这种方案就是$\binom{n}{i}\times\binom{m}{d}^i\times{g_{i,m-d,m-d,k-1}\times{(g_{n-i,m,m,k}-g_{n-i,m,d,k})}}$.
(以上仅仅是基本思路,还有一些坑以及特判,详情看代码吧QAQ)
#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 21
#define M 51
#define P 101
typedef long long ll;
static const int mod=(1e9)+7;
inline void inc(int&x,int y){
if((x+=y)>=mod)
x-=mod;
}
int C[M][M],pC[M][M][N];
int g[N][M][M][P];
int main(){
int n,m,p;
cin>>n>>m>>p;
int i,j,_i,k;
C[0][0]=C[1][0]=C[1][1]=1;
for(i=2;i<=50;++i){
C[i][0]=C[i][i]=1;
for(j=1;j<i;++j)
inc(C[i][j]=C[i-1][j-1],C[i-1][j]);
}
for(i=0;i<=50;++i){
for(j=0;j<=i;++j){
pC[i][j][0]=1;
for(k=1;k<=20;++k)
pC[i][j][k]=(ll)pC[i][j][k-1]*C[i][j]%mod;
}
}
for(j=1;j<=m;++j)
g[1][j][j][1]=1;
for(k=2;k<=p;++k)
for(i=1;i<=n;++i)
for(j=1;j<=m;++j){
for(int d=0;d<j;++d){
g[i][j][d][k]=d?g[i][j][d-1][k]:0;
for(_i=1;_i<i;++_i)
inc(g[i][j][d][k],(ll)C[i][_i]*pC[j][d][_i]%mod
*g[_i][j-d][j-d][k-1]%mod
*(g[i-_i][j][j][k]+mod-g[i-_i][j][d][k])%mod);
inc(g[i][j][d][k],(ll)pC[j][d][i]*g[i][j-d][j-d][k-1]%mod);
}
inc(g[i][j][j][k]=g[i][j][j-1][k],i==1);
}
cout<<g[n][m][m][p]<<endl;
return 0;
}
BZOJ3052
经典的带修改树上莫队.
VFK的博客已经写得非常详细了.
这里我再稍微说一点心得.
首先是树分块的姿势.
设每一块大小的基准值为$B$.
对树进行dfs,给每个点维护一个一开始为空的等待序列,然后向上回溯的时候返回这个等待序列.
那么这个点要依次遍历他的儿子,每搞完一个儿子,就把这个儿子的等待序列加入自己的等待序列.如果加入之后发现等待序列的长度$\geq{B}$,就把当前等待序列里面的所有点都分成一个块,并从等待序列中删除.
这样做完之后,把这个点自己加入自己的等待序列(此时就算满足$B$分块的条件也不分成一块),然后向上回溯.
那么最后根还会返回一个等待序列,这怎么分块呢?
直接加入最后一个块就行啦.
我们分析一下:一个点向上返回的等待序列的长度肯定$\leq{B}$,刚才分成的每个块的大小$siz$肯定满足$B\leq{siz}\leq{2B-1}$,所以这两个加在一起最大不超过$3B$.并且由于dfs序的性质,这个块肯定是连通的.
这样就满足所有块的大小都满足$[B,3B]$.
我们定义状态$(u,v,t)$表示有效路径为$u,v$之间的路径再抛去$lca(u,v)$,且时间为$t$的答案.
这个答案需要记录的是真实的答案,以及每个点当前的颜色,以及有效路径上每种颜色出现多少次,以及所有点的有效性.
这样才能实现$O(1)$的修改.
路径之间的转移就是简单把两对端点之间的去lca路径有效性取反.(详细见VFK博客)
时间的转移就是改变某个点的颜色,也非常简单.
注意的是时间倒流的时候,需要还原在这个时间的修改,则需要知道上一个时刻这个点是什么颜色,我用了vector+二分.
类似莫队算法,我们把所有询问按照第一个端点的块序号为第一关键字,第二个端点的块序号为第二关键字,时间为第三关键字排序.
然后如上面所述转移就行了.
令$B=n^{\frac{2}{3}}$,则块的数目有$n^{\frac{1}{3}}$,则总转移数目为:$O(n^{\frac{5}{3}})$.(证明见VFK博客)
另外再跪一下VFK.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
#define N 100010
#define M 100010
#define Q 100010
int n,m,q,head[N],next[N<<1],end[N<<1];
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);
}
int val[M],w[N],c[N];
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 dep[N],pa[N][21],belong[N],cnt,stack[N],top,B;
inline int lca(int x,int y){
if(dep[x]<dep[y])
swap(x,y);
for(int i=20;i>=0;--i)
if(dep[pa[x][i]]>=dep[y])
x=pa[x][i];
if(x==y)
return x;
for(int i=20;i>=0;--i)
if(pa[x][i]!=pa[y][i])
x=pa[x][i],y=pa[y][i];
return pa[x][0];
}
inline int dfs(int x,int fa){
int size=0;
for(int j=head[x];j;j=next[j]){
if(end[j]!=fa){
dep[end[j]]=dep[x]+1;
pa[end[j]][0]=x;
int t=dfs(end[j],x);
if((size+=t)>=B){
++cnt;
while(size--)
belong[stack[top--]]=cnt;
}
}
}
stack[++top]=x;
return ++size;
}
int type[Q],x[Q],y[Q];
struct Query{
int u,v,t;
Query(){}
Query(int _u,int _v,int _t):u(_u),v(_v),t(_t){
if(belong[u]>belong[v])
swap(u,v);
}
bool operator<(const Query&B)const{
if(belong[u]!=belong[B.u])
return belong[u]<belong[B.u];
if(belong[v]!=belong[B.v])
return belong[v]<belong[B.v];
return t<B.t;
}
}S[Q];
int numQ;
int num[M];
int u,v,_lca,t;
ll G;
bool vis[N];
vector<int>ti[N],col[N];
inline ll getans(){
return G+(ll)w[num[c[_lca]]+1]*val[c[_lca]];
}
ll ans[Q];
inline void c_s(int x){
if(vis[x]){
vis[x]=0;
G-=(ll)w[num[c[x]]--]*val[c[x]];
}
else{
vis[x]=1;
G+=(ll)w[++num[c[x]]]*val[c[x]];
}
}
inline void c_c(int x,int _c){
if(vis[x]){
G-=(ll)w[num[c[x]]--]*val[c[x]];
G+=(ll)w[++num[c[x]=_c]]*val[_c];
}
else
c[x]=_c;
}
inline void go(int t){
if(type[t]==0)
c_c(x[t],y[t]);
}
int rx[Q],ry[Q];
inline void ret_pre(){
for(int i=1;i<=q;++i){
if(type[i]==0){
int _x=x[i];
int d=lower_bound(ti[_x].begin(),ti[_x].end(),i)-ti[_x].begin();
rx[i]=_x;
ry[i]=col[_x][d-1];
}
}
}
inline void ret(int t){
if(type[t]==0)
c_c(rx[t],ry[t]);
}
inline void uppath(int u,int v){
int _lca=lca(u,v);
for(;u!=_lca;u=pa[u][0])
c_s(u);
for(;v!=_lca;v=pa[v][0])
c_s(v);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("tt.in","r",stdin);
#endif
n=getint();
m=getint();
q=getint();
int i,j;
for(i=1;i<=m;++i)
val[i]=getint();
for(i=1;i<=n;++i)
w[i]=getint();
for(i=1;i<n;++i)
make(getint(),getint());
B=(int)pow(n,2.0/3);
dep[1]=1;
int last=dfs(1,-1);
while(last--)
belong[stack[top--]]=cnt;
for(j=1;j<=20;++j)
for(i=1;i<=n;++i)
pa[i][j]=pa[pa[i][j-1]][j-1];
for(i=1;i<=n;++i){
ti[i].push_back(0);
col[i].push_back(c[i]=getint());
}
for(i=1;i<=q;++i){
type[i]=getint();
if(type[i]==0){
x[i]=getint();
y[i]=getint();
ti[x[i]].push_back(i);
col[x[i]].push_back(y[i]);
}
else{
S[++numQ]=Query(getint(),getint(),i);
}
}
ret_pre();
sort(S+1,S+numQ+1);
u=v=_lca=1;
t=G=0;
for(i=1;i<=numQ;++i){
uppath(u,S[i].u);
uppath(v,S[i].v);
_lca=lca(u=S[i].u,v=S[i].v);
while(t<S[i].t)
go(++t);
while(t>S[i].t)
ret(t--);
ans[S[i].t]=getans();
}
for(i=1;i<=q;++i)
if(type[i]==1)
printf("%lld\n",ans[i]);
return 0;
}
现在开始,再战"紫荆花之恋"!
233
【弱省胡策】Round2题解
Jun 03, 2015 08:44:08 AM
A.沼跃鱼的FFF
By wyfcyx
来自BZOJ2891,但是上一次AC已经是近两年前,而且多位神犇都是利用随机很多次这种方法过的.
其实这个题很简单.
注意到$n\leq{6}$,显然要在这个上面做文章啦.
令$f[i][j]$表示在前$i$个Po姐参与匹配的情况下,大爷匹配状态的集合为$j$这种情况发生的概率.
何谓匹配状态:就是指一个二进制数,第$i-1$位以0/1表示第$i$个大爷是否在匹配中.
考虑第$i+1$个Po姐,我们可以$O(2^n)$枚举她可以和哪些大爷进行匹配,那么现在的集合会变成什么样子呢?
对于原集合的所有状态,以及现在新增的若干匹配边,若这个状态加上这条匹配边得到的新状态不在原集合中,我们就将这个新状态加入集合.
于是这样的集合数明面看来是$O(2^{2^n})$的,看起来直接要爆炸了.
其实很容易注意到每个大爷只会在第一次出现在匹配边时造成影响,那么有用的信息只有最终所有匹配边中大爷的并集,以及加入大爷的顺序.
于是可用的集合数最多只有$O(n!2^n)$这么多.这样算一下感觉很爆炸,但其实还有很多重复,最坏只有$4000$个状态.
这样简单的dp就可以了.
状态数为$O(n!2^nm)$,转移数为$O(2^n)$,总时间复杂度为$O(n!4^nm)$.
当然需要一些简单的预处理,不过这里就不说了.
http://ch.ezoj.tk/record/45061
B.沼跃鱼的Mushroom
By 18357
1.呵呵。强行分类讨论？
2.呵呵。强行分类讨论？
3.枚举然后判断树同构？
4.枚举然后判断树同构？
5.贪心+贪心。
6.贪心+贪心。
7.贪心+树DP（呃或许说是dfs？）。
8.贪心+贪心。
9-25.膜能写出特判的神犇。
[正解]
我们从深往浅对每一层进行处理，求f(I,j)表示左子树选个节点i，右子树选个节点j，所能得到的最多匹配节点数，这个过程可以用最大费用最大流来求解。
[分值设置]
我觉得出100个点会卡爆CH。就是这样。
[题面思路]
我不认为小丑的盒子、女警豹女的夹子、巴德的坛子等等可以搞成这道题。
其实扎克变成若干块，然后判断扎克同构神马的嘛。呃扎克变500块太可怕了Qwq。
http://ch.ezoj.tk/record/45054
C.沼跃鱼的Password
By jkxing
算法1 KMP+暴力check
KMP出哪些串的前7位和B串是匹配的，然后暴力check有多少不一样的，期望复杂度$O(nm)$,期望得分30分.
算法2 KMP+FFT
前半部分还是KMP,但是后半部分不同。
把A,B串的末位提出来，B串反向，求一遍卷积，这样我们就得到了从某个位置开始匹配两串同为1的个数.
然后把A，B串分别按位异或，再求一遍卷积，就求出了同为0的个数。
然后就可以$O(1)$时间内判断从某个点开始匹配需要更改的字符个数了，时间复杂度$O(nlogn)$，期望得分100.
算法3 乱搞
或许可以只check最后一位，有可能会得到很多分，因为并没有特意做数据……期望复杂度O(?),期望得分?
http://ch.ezoj.tk/record/45020
