闲扯
今天又是暴力满满(并不)的一天呢
昨天老师说了分数要正态分布,今天看起来...不过暴力分很多,虽然我人太傻逼又没打满
T1 woc?不是说送分的吗,看起来又是个树形DP神题,暴力告辞,链上的搞一搞
T2 woc?又是树 纪中这么喜欢出图/树题的吗?第一眼暴力dij告辞
T3 woc?又又又是树?!看起来十分码农?!部分分还好很多,想到昨天老师提到了天天爱跑步的例子,感觉可以搞一搞...于是就开始爆肝了...结果期望30分开了个fread爆0了
\(30+30+0\)凉凉,T2堆改成\(paring\)_\(heap\)就50了,辣鸡STL.虽然有一个更优的暴力...
T1 lkf
又是道神奇树形DP,分析先咕会
懒得写了,看代码注释吧...
这道题好题啊
学会两个技巧
对于差值恰为\(k\)的毒瘤限制,转化为小于等于\(k\)的限制,答案就是小于等于k的减去小于等于k-1的
对于可能重复计算的状态强制安排一个顺序,如dfs序之类的防止算重
/* code by RyeCatcher*/inline char gc(){ static char buf[SIZE],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;}#define gc getchartemplate inline void read(T &x){ x=0;int ne=0;char c; while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48; while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;}const int maxn=3335;const int inf=0x7fffffff;const int P=19260817;struct Edge{ int ne,to;}edge[maxn<<1];int h[maxn],num_edge=1;inline void add_edge(int f,int to){ edge[++num_edge].ne=h[f]; edge[num_edge].to=to; h[f]=num_edge;}int n,k,w[maxn],mx=-inf;int id,o,lim;ll f[maxn][maxn];ll ans=0;void dfs(int now,int fa){ int v;ll p=1; //printf("%d %d\n",now,fa); for(ri i=h[now];i;i=edge[i].ne){ v=edge[i].to; if(v==fa)continue; if(w[v]>=o&&w[v]<=o+lim&&(w[v]!=o||(w[v]==o&&v>id))){//前两个限制是因为状态的设计本身,第三个限制是防止联通块算重,如果还有一个点值为枚举的最小值,我们可能已经计算了那个联通块的个数 //于是我们强制安排一个顺序使得不重不漏 dfs(v,now); p=p*(f[v][lim]+1)%P;//乘法原理,连上v贡献为f[v][lim] 否则为1 } } f[now][lim]=p; return ;}int main(){ int x,y; read(n),read(k); for(ri i=1;i<=n;i++){ read(w[i]); } for(ri i=1;i T2 worry
有个性质就是因为你树上边随便走,你断掉一条树边后你最多走一条非树边。\(naiive\)的做法就是枚举了,有没有更高明的呢?
我们边从小到大排序,发现对于边\((x,y)\),它影响\((x,y)\)路径上的边(也就是断掉路径上的任何一条边还可以通过\((x,y)\)联通),也就是\(x,y\)分别到\(lca(x,y)\)路径上的
树链剖分
那么链剖就可以搞喽,线段树维护一个永久标记,如果有标记了也不管(因为边权从小到大排序)
跑得还挺快
/* code by RyeCatcher*/inline char gc(){ static char buf[SIZE],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;}template inline void read(T &x){ x=0;int ne=0;char c; while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48; while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;}const int maxn=200005;const int inf=0x7fffffff;int n,m;struct Edge{ int ne,to; ll dis;}edge[maxn<<1];int h[maxn],num_edge=1;inline void add_edge(int f,int to,ll c){ edge[++num_edge].ne=h[f]; edge[num_edge].to=to; edge[num_edge].dis=c; h[f]=num_edge;}pair qwq[maxn];struct Niconiconi{ int x,y; ll dis; Niconiconi(){x=y=dis=0;} Niconiconi(int _x,int _y,ll _c){x=_x,y=_y,dis=_c;} bool operator <(const Niconiconi &rhs)const{ return dis >1; pushdown(now); if(L<=mid&&!tag[now<<1])update(now<<1,l,mid); if(mid <<1|1])update(now<<1|1,mid+1,r); return ;}void ahaha(int now,int l,int r){ if(l==r){ if(tag[now])w[rnk[l]]=tag[now]; else w[rnk[l]]=-1; return ; } int mid=(l+r)>>1; pushdown(now); ahaha(now<<1,l,mid); ahaha(now<<1|1,mid+1,r); return ;}inline void update_path(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]] dep[y])std::swap(x,y); L=dfn[x]+1,R=dfn[y]; //printf("--%d %d--\n",rnk[L],rnk[R]); if(L>R)return ; update(1,1,n);}int main(){ int x,y;ll z; FO(worry); read(n),read(m); for(ri i=1;i (x,y); } for(ri i=1;i<=m;i++){ read(x),read(y),read(z); con[i]=Niconiconi(x,y,z); } std::sort(con+1,con+1+m); dep[1]=0,fa[1]=0; dfs1(1); dfs2(1,1); memset(tag,0,sizeof(tag)); for(ri i=1;i<=m;i++){ x=con[i].x,y=con[i].y,dta=con[i].dis; update_path(x,y); } ahaha(1,1,n); for(ri i=1;i 并查集
题解是更高明的并查集做法,我还是Too Young Too Simple,只会SB暴力树剖
每个点指向下一个没被打标记的点\(nxt[x]\)(以点代边),显然这是可传递的
这样的话每次查询直接往上跳就好了,连LCA都不用求
居然跑到rank1哈哈
/* code by RyeCatcher*/inline char gc(){ static char buf[SIZE],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;}#define gc getchartemplate inline void read(T &x){ x=0;int ne=0;char c; while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48; while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;}const int maxn=100005;const int inf=0x7fffffff;int n,m;struct Edge{ int ne,to;}edge[maxn<<1];int h[maxn],num_edge=1;inline void add_edge(int f,int to){ edge[++num_edge].ne=h[f]; edge[num_edge].to=to; h[f]=num_edge;}struct Niconiconi{ int x,y,z; bool operator <(const Niconiconi &qwq)const{ return z