2018.10.21 练习赛 树专练

T1 树

题解：

记录树上前缀和,每次加入新前缀和就二分一下前缀和数组看有无满足\(sum[now]-s\)的数在里面,因为\(sum\)必定是单调的,就乱搞完毕;

\(code\):

#include
#include
#include 
#include
#include
#include
#include
#include
#include
#define lowbit(x) (x&-x)
#define ll long long
#define ld double
#define mod 998244353 
using namespace std;

char buf[1<<20],*p1,*p2;
inline char gc()
{
    return getchar();
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}

template
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(flag=1,x=0):(x=tt-'0');
    while(isdigit(tt=gc())) x=x*10+tt-'0';
    if(flag) x=-x;
}

const int maxn=1e5+2;
int n,s;
vectorG[maxn];
bool root[maxn];
int w[maxn],sum[maxn],ans;

void dfs(int x,int dep)
{
	sum[dep]=sum[dep-1]+w[x];
	if(sum[lower_bound(
	sum,sum+dep+1,sum[dep]-s)-sum]==sum[dep]-s) ans++;
	for(int i=G[x].size()-1;i>=0;i--)
	{
		int p=G[x][i];
		dfs(p,dep+1);
	}
	sum[dep]=0;
}

int main()
{
	read(n),read(s);
	for(int i=1;i<=n;i++) read(w[i]);
	for(int i=1;i

T2 联通块计数

题解：

树DP=_=

\(code:\)

#include
#include
#include 
#include
#include
#include
#include
#include
#include
#define lowbit(x) (x&-x)
#define ll long long
#define ld double
#define mod 998244353 
using namespace std;

char buf[1<<20],*p1,*p2;
inline char gc()
{
//    return getchar();
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}

template
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(flag=1,x=0):(x=tt-'0');
    while(isdigit(tt=gc())) x=x*10+tt-'0';
    if(flag) x=-x;
}
inline ll add(ll a,ll b){return a+bG[maxn];
bool book[maxn];

ll dfs(ll x,ll pre,ll lim)
{
	int ret=1;
	for(int i=G[x].size()-1;i>=0;i--)
	{
		int p=G[x][i];
		if(p==pre||book[p]||w[p]>lim) continue;
		ret=mul(ret,dfs(p,x,lim));
	}
//	printf("%d\n",lim);
	return ret+=(pre!=0);
}

int main()
{
	read(n),read(k);
	for(int i=1;i<=n;i++)
	{
		ll x;
		read(x);w[i]=x;
		a[i]=node(x,i);
	}sort(a+1,a+1+n);
	for(int i=1;i

T3 电压

题解：

题意为去掉一条边,看此图是否仍为一个二分图;

我们考虑去掉的这条边必定是所有奇环的交,且不能在任何的偶环上,\(tarjan\)找出所有环(这里的所有环是指写出的算法所能找出的环,并非真正意义上的所有环)

每当我们遇到一条返祖边,差分记录环覆盖的边,统计答案时满足前面我们所给的条件即可;

我们发现当我们的搜索顺序不同时,我们所找出的环也不同,但是,这并不影响我们的结果,因为如果一结果对一种图成立,那么他必定对所有图成立;

\(code:\)

#include
#include
#include 
#include
#include
#include
#include
#include
#include
#define lowbit(x) (x&-x)
#define ll long long
#define ld double
#define mod 998244353 
using namespace std;

char buf[1<<20],*p1,*p2;
inline char gc()
{
//    return getchar();
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}

template
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(flag=1,x=0):(x=tt-'0');
    while(isdigit(tt=gc())) x=x*10+tt-'0';
    if(flag) x=-x;
}

struct node{
	int x,id;
	inline node(int a=0,int b=0)
	{x=a,id=b;}
};

const int maxn=1e5+2;
int n,m,dep[maxn],tot;
int cnt[maxn][2];
//0 1 odd
//0 0 eve
vectorG[maxn];
void dfs(int x,int pre)
{
	for(int i=G[x].size()-1;i>=0;i--)
	{
		int p=G[x][i].x,id=G[x][i].id;
		if(id==pre) continue;
		if(!dep[p])
		{
			dep[p]=dep[x]+1;dfs(p,id);
			cnt[x][0]+=cnt[p][0];
			cnt[x][1]+=cnt[p][1];
		}
		else if(dep[p]<=dep[x])
		{
			if((dep[x]-dep[p])&1) cnt[x][0]++,cnt[p][0]--;
			else cnt[x][1]++,cnt[p][1]--,tot++;
		}
	}
}

int main()
{
//	freopen("voltage.in","r",stdin);
	read(n),read(m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		read(x),read(y);
		G[x].push_back(node(y,i));
		G[y].push_back(node(x,i));
	}
	int ans=0;
	for(int i=1;i<=n;i++) if(!dep[i]) dep[i]=1,dfs(i,0);
	for(int i=1;i<=n;i++) if(dep[i]!=1&&!cnt[i][0]&&cnt[i][1]==tot) ans++;
	printf("%d",ans+(tot==1));
}
比赛数据结构树上问题练习赛题解树形dp

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

数据结构--栈（C语言实现）

Ubuntu 断网问题解决

牛客练习赛91（并查集+二维偏序+二分）

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

题解 Count on a tree II/【模板】树分块

HttpURLConnection发送中文乱码问题解决

数据结构----单链表升级版

数据结构/PTA-畅通工程之最低成本建设问题-畅通工程之局部最小花费问题/图/最小生成树

数据结构+java中常用的集合类

1675: [Usaco2005 Feb]Rigging the Bovine Election 竞选划区（题解第一弹）

数据结构 之二叉树

标签

一品网 冀ICP备14022925号-6