[JZOJ NOIP2018模拟10.19]
T1写炸了今天,期望70却落了个20...连链上的都没有写对
T3什么什么线段树分治套AC自动机,表示我完全自闭了,幸好考场上没有杠T3
总体比赛还是比较舒服,暴力分给的蛮足的,不像昨天那样
T1:林下风气
题目链接:
http://172.16.0.132/senior/#main/show/5913
题目:
里口福因有林下风气,带领全国各地高校掀起了一股AK风,大家都十分痴迷于AK。里口福为了打击大家的自信心,出了一道自以为十分困难的题目。
里口福有一棵树,第i个节点上有点权ai,他的问题就是这棵树中有多少个不同的连通块满足连通块的最大值与最小值之差=k,两个连通块不同当且仅当至少存在一个节点在一个连通块中出现而另一个连通块中没有出现。
痴迷于AK的你马上接下这道题目,在里口福狂妄的笑声中,你切掉这道题的决心更加坚定了,现在就差你的代码了。
题解:
我们枚举一下最小值,这样最大值就是唯一确定的了
以最小值为根跑$dp$,$dp(x,r,k)$表示最小值是$a[r]$,当前在$x$节点,最大值和最小值之差不超过$k$的连通块的个数
当$a[r]<=a[y]<=a[r]+k$时可以转移
发现这样以两个a值相等的点为根可能方案会算重,所以当$a[r]==a[y]$时我们强制让y<r的时候才可以转移
显然若当前枚举的最小值为a[i],对答案的贡献就是$dp(i,i,k)-dp(i,i,k-1)$
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std; const int N=+;
const int mo=;
int n,k,tot;
int a[N],head[N];
struct E{
int to,nxt;
}edge[N<<];
inline int read()
{
char ch=getchar();
int s=,f=;
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
return s*f;
}
void link(int u,int v){edge[++tot]=(E){v,head[u]};head[u]=tot;}
int dp(int x,int pre,int r,int k)
{
if (k<) return ;
int re=;
for (int i=head[x];i;i=edge[i].nxt)
{
int y=edge[i].to;
if (y==pre) continue;
if (a[y]>=a[r]&&a[y]<=a[r]+k&&(a[y]!=a[r]||(a[y]==a[r]&&y<r)))
{
re=1ll*re*(dp(y,x,r,k)+)%mo;
}
}
return re;
}
int main()
{
freopen("lkf.in","r",stdin);
freopen("lkf.out","w",stdout);
n=read();k=read();
for (int i=;i<=n;i++) a[i]=read();
for (int i=,u,v;i<n;i++){
u=read();v=read();
link(u,v);link(v,u);
}
int ans=;
for (int i=;i<=n;i++)
{
ans=(ans+((dp(i,,i,k)-dp(i,,i,k-))%mo+mo)%mo)%mo;
}
printf("%d\n",ans);
return ;
}
T2:盟主的忧虑
题目链接:
http://172.16.0.132/senior/#contest/show/2531/0
题目:
里口福因有林下风气,带领全国各地高校掀起了一股AK风,大家都十分痴迷于AK。里口福为了打击大家的自信心,出了一道自以为十分困难的题目。
里口福有一棵树,第i个节点上有点权ai,他的问题就是这棵树中有多少个不同的连通块满足连通块的最大值与最小值之差=k,两个连通块不同当且仅当至少存在一个节点在一个连通块中出现而另一个连通块中没有出现。
痴迷于AK的你马上接下这道题目,在里口福狂妄的笑声中,你切掉这道题的决心更加坚定了,现在就差你的代码了。
题解:
我们把密道按权值从小到大排序
对于一条密道(u,v,w),如果u到v的路径上的边中存在边之前还没有被覆盖过,那么说明这条边的答案就是w
把每条边对应到它深度较深的端点上,并查集维护一下每个点向上第一个没有被覆盖的点。从u开始不断向上跳,沿路不断染色,直到跳到超过lca就不再染色。对v也是如此
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll; const int N=1e5+;
int n,m,tot=;
int fa[N][],head[N],dep[N],f[N],ans[N];
ll color[N];
struct E{
int to,nxt;
}edge[N<<];
struct EDGE{
int u,v;
ll w;
}e[N];
bool operator <(EDGE a,EDGE b){return a.w<b.w;}
inline ll read(){
char ch=getchar();ll s=,f=;
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
return s*f;
}
void link(int u,int v){edge[++tot]=(E){v,head[u]};head[u]=tot;}
void dfs(int x,int pre){
fa[x][]=pre;
for (int i=;i<;i++) fa[x][i]=fa[fa[x][i-]][i-];
for (int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if (y==pre) continue;
dep[y]=dep[x]+;
dfs(y,x);
}
}
int lca(int x,int y){
if (dep[x]<dep[y]) swap(x,y);
for (int i=;i>=;i--) if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if (x==y) return x;
for (int i=;i>=;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][];
}
int find(int x){
if (f[x]!=x) f[x]=find(f[x]);
return f[x];
}
void col(int x,int goal,ll w)
{
if (dep[x]<dep[goal]+) return;
if (f[x]==x) color[x]=w,f[x]=f[fa[x][]];
int y=find(x);
if (dep[y]>=dep[goal]+) col(y,goal,w);
}
void dfs1(int x,int pre){
for (int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if (y==pre) continue;
ans[i>>]=color[y];
dfs1(y,x);
}
}
int main()
{
freopen("worry.in","r",stdin);
freopen("worry.out","w",stdout);
n=read();m=read();
for (int i=,u,v;i<n;i++){
u=read();v=read();
link(u,v);link(v,u);
}
dep[]=;dfs(,);
for (int i=;i<=m;i++){
e[i].u=read();e[i].v=read();
e[i].w=read();
}
for (int i=;i<=n;i++) f[i]=i;
sort(e+,e++m);
for (int i=;i<=m;i++){
int u=e[i].u,v=e[i].v;
ll w=e[i].w;
int L=lca(u,v);
col(u,L,w);col(v,L,w);
}
dfs1(,);
for (int i=;i<n;i++) if (!ans[i]) puts("-1");else printf("%d\n",ans[i]);
return ;
}
最新文章
- sql 查询表中所有字段的名称
- window 系统设置无线wifi
- 在 C++ 代码中使用 UE4 插件---Using a plugin in C++ code
- java 字节数组转int
- Android常见崩溃或闪退的问题描述及原因总结、及与性能相关的模块——持续更新
- C#:实现快捷键自定义设置
- SQL Server数据库与max degree of parallelism参数
- gitignre
- mysql数据库常用语句
- Linux下GPIO驱动(一) ----一个简单的LED驱动
- COJ 2024 仙境传奇(五)——一个天才的觉醒 素数筛
- Android Studio安装教程
- css背景图片、隐藏、指针、垂直居中、去除下划线、缩进、列表类型
- java 以a为开头单词的词典查询示例
- 深入理解JAVA虚拟机之JVM性能篇---垃圾回收
- [ 学习笔记 ] Hibernate框架学习之一
- 匿名函数,结合闭包的写法,js对象的案例
- 为什么redis是单线程的?速度还这么快
- mac上将代码上传到github
- Luogu 2051[AHOI2009]中国象棋 - DP
热门文章
- nyoj--120--校园网络(scc+缩点)
- 在单机上安装多个oracle实例
- 使用dbms_metadata.get_ddl遇到ORA-31603
- 树状数组(Binary Indexed Tree(BIT))
- 18. 4Sum[M]四数之和
- vue入门--简单嵌套路由的一个路径小问题
- 关于getElementsByTagName的遍历顺序
- ajax返回值
- 原生js简易日历效果实现
- CF894E Ralph and Mushrooms_强连通分量_记忆化搜索_缩点