T1 林下风气

100pts

树形DP

枚举每一个点作为根节点，并且将当前点的值设为联通块的最大值st，向下搜索子节点a[j]，a[j]满足条件

0<=st-a[j]<=k；若当前j不满足条件，就return。否则继续向下统计满足条件的子树个数。而对于搜索的每个节点的返回值为所有子树返回值＋1的乘积（由乘法原理得到最大值与最小值相差<=k的总方案数）。

再按照以上思路搜索最大值与最小值相差<=k-1的总方案数。

两者相减即为最大值与最小值相差==k的总方案数。

注意相减后要先加mod再取模，否则会有负数，只能得70分。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=4000,mod=19260817;
typedef long long ll;
int n,k,a[N],head[N],tot,x,y;
ll sum1,sum2,ans;
struct edge{int v,to;
}e[N*2];
void add(int x,int y)
{e[++tot].v=y;e[tot].to=head[x];head[x]=tot;
}
int read()
{int sum=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}return sum*f;
}
void print(int x)
{if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10+'0');
} 
ll dfs(int x,int fa,int st,int k)
{  ll sum=1;for(int i=head[x];i;i=e[i].to){int y=e[i].v;if(y==fa)continue;if(y>st||a[y]!=a[st]){if(a[st]-a[y]<=k&&a[st]-a[y]>=0)sum=((long long)sum*(dfs(y,x,st,k)+1))%mod;}} return sum%mod; 
}
int main(){
//  freopen("lkf.in","r",stdin);
//  freopen("lkf.out","w",stdout);n=read();k=read();for(int i=1;i<=n;i++)a[i]=read();for(int i=1;i<n;i++){x=read();y=read();add(x,y);add(y,x);
}ll cnt;for(int i=1;i<=n;i++){cnt=dfs(i,0,i,k);sum1=(sum1+cnt)%mod;	}if(k)for(int i=1;i<=n;i++){cnt=dfs(i,0,i,k-1);sum2=(sum2+cnt)%mod;}ans=(sum1-sum2+mod)%mod;print(ans);return 0;
}

T2 盟主的忧虑

100pts

并查集缩点

对于密道按从小到大排序。对于当前密道能覆盖的小道（即与当前密道构成环的小道)，若小道没有被别的密道覆盖，则被当前密道覆盖（距离为当前密道距离）。因为这样可以保证所有替换小道的密道均为最小值。

每次覆盖之后发现覆盖的都是一段连续的区域，那么把这个区域缩成一个点——即用并查集维护，把区域中所有元素所在的集合与最上面元素的父节点合并。

而求最上面的元素就要用lca。而这道题数据范围不是很大，直接暴力一个个往上跳，不能用倍增（因为要修改区域中每一个元素的集合）

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
typedef long long ll;
int n,m,head[N],tot,x,y;
int fa[N],p[N],dep[N],f[N],ans[N];
struct edge{int v,to,id;
}e[N*2];
struct node{int x,y,w;
}b[N];
void add(int x,int y,int i)
{e[++tot].v=y;e[tot].to=head[x];e[tot].id=i;head[x]=tot;
}
int read()
{int sum=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}return sum*f;
}
void print(int x)
{if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10+'0');
} 
bool comp(node a,node b){return a.w<b.w;
}
void dfs(int x,int pre)
{fa[x]=pre;dep[x]=dep[pre]+1;for(int i=head[x];i;i=e[i].to){int y=e[i].v;if(y==pre)continue;p[y]=e[i].id;dfs(y,x);}
}
int find(int x)
{if(x==f[x])return x;return f[x]=find(f[x]);
}
void lca(int x,int y,int val)
{while(x!=y){while(dep[x]>dep[y]&&x!=y){ans[p[x]]=val;f[x]=find(fa[x]);x=f[x];} while(dep[x]<=dep[y]&&x!=y){ans[p[y]]=val;f[y]=find(fa[y]);y=f[y];} }
}
void serch()
{for(int i=1;i<=n;i++)f[i]=i;for(int i=1;i<=m;i++){ x=find(b[i].x);y=find(b[i].y);lca(x,y,b[i].w);}
}
int main(){//  freopen("worry.in","r",stdin);//  freopen("worry.out","w",stdout);n=read();m=read();for(int i=1;i<n;i++){x=read();y=read();add(x,y,i);add(y,x,i);}for(int i=1;i<=m;i++){b[i].x=read();b[i].y=read();b[i].w=read();}sort(b+1,b+m+1,comp);dfs(1,0);serch();for(int i=1;i<n;i++){if(ans[i]==0)ans[i]=-1;print(ans[i]);if(i!=n-1)putchar('\n');}return 0;
}

T3 明日之星

100pts

括号序+AC自动机+树状数组+线段树
注意到询问满足加减性,因此可以直接转换为括号序。
设px,qx分别表示x左括号的位置和右括号的位置
左括号代表a[x]，右括号代表-a[x]

对于询问x->y,设z=lca(x,y)
查询就变成了链上的[pz…px]+(pz…py]
因为对于x->y,x是y的祖先，[px…py]间除了x->y路
径上的点，其它点出现的次数都是偶数。x->y路
径上的点恰好出现了一个左括号。

原理理解了，但是几百行代码真的orz暂时调不出来，数据结构＋字符串+思维的完美（划掉）结合T—T。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！