前言

最自闭的一集

T1 这一切

题意：给你一个图，定义操作为 若一个点只有一条白边 那么剩余的白边就会自动变黑 求至少要提前染几条边 通过若干次操作后使所有边都变黑

思考：画一下图就知道 满足所有点只有一条出边 其实就是一棵树 所以将每个联通快多余的边删掉即可

Code

#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,m,ans;
int head[N],tot=1;
struct edge{
	int to,next;
}e[N*4];
void add(int u,int v)
{
	e[tot]=(edge){v,head[u]};
	head[u]=tot++;
}
int vis[N],cnt,p;
void dfs(int now)
{
	p++;
	vis[now]=1;
	for(int i=head[now];i;i=e[i].next)
	{
		int to=e[i].to;
		cnt++;
		if(!vis[to]) dfs(to);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++)
		if(!vis[i]) cnt=0,p=0,dfs(i),ans+=cnt/2-p+1;
	cout<<ans;
	return 0;
}

T2 都是 原题

题意：你可以随意交换数列两个数 使得最后的数列成为单峰数列 即存在一个 \(a_x\) 满足：

• \(i<k\) \(a_i>a_{i-1}\)
• \(i<k\) \(a_i<a_{i-1}\)

e.g 1 1 4 5 4 1
考场上是问了同学的 一开始一直在想逆序对
其实不妨这样思考：
从 \(1\) 开始考虑 \(1\) 必须扔到最前面或者最后面 扔完就变成了一个子问题
这样一想这问题就变成一个弟弟题了
所以往前找到有几个数和往后找到有几个数 哪里少就往哪里扔就行
树状数组维护即可

Code

#include<bits/stdc++.h>
#define ll long long
#define N 300005
using namespace std;
int n,a[N];
ll ans;
vector <int> pos[N];
struct tree{
	ll tr[N];
	void add(int x,int v)
	{
		while(x<=n)
		{
			tr[x]+=v;
			x+=x&-x; 
		}
	}
	ll ask(int x)
	{
		ll sum=0;
		while(x)
		{
			sum+=tr[x];
			x-=x&-x;
		}
		return sum;
	}
}tr;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		pos[x].push_back(i);
		tr.add(i,1);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<pos[i].size();j++) tr.add(pos[i][j],-1);
		for(int j=0;j<pos[i].size();j++)
		{
			int x=pos[i][j];
			ans+=min(tr.ask(x-1),tr.ask(n)-tr.ask(x));
		}
	}
	cout<<ans;
	return 0;
}

T3

呜呜呜我好菜写了一天
题意：有 \(n\) 个笼子 每个笼子可能会有动物 \(A,B,C\) \(A\) 能吃 \(B\),\(B\) 能吃 \(C\),\(C\) 能吃 \(A\).明显最初有 \(3^n\) 种状态

我好菜 不会在线算法 被吊打了
想想在线怎么做
考虑两个并查集 \(u,v\) 要合并到 \(u\)
那么 \(u\) 子树所有胜利状态应该乘上 \(\frac{2}{3}\) \(v\) 子树所有节点胜利状态应该乘上 \(\frac{1}{3}\) 这是题目给定的胜利概率 然后两棵树再并起来

然后因为并查集动态搞我太菜了不会 所以只能离线把原树拍到树上 dfs 序解决
时间复杂度还带个 \(log\) 我太菜了

#include<bits/stdc++.h>
#define ll long long
#define N 400005
using namespace std;
ll mod=998244353,inv[5],pw=1;
int n,m;
int trs[N][2],fa[N],cnt,pre[N];
struct prob{
	int opr,u,v;
}op[N];
int in[N],out[N],dfn;
void dfs(int now)
{
	if(!now) return;
	in[now]=++dfn;
	dfs(trs[now][0]);
	dfs(trs[now][1]);
	out[now]=dfn;
}
int tr[N];
void add(int x,ll v)
{
	while(x<=dfn)
	{
		tr[x]=tr[x]*v%mod;
		x+=x&-x;
	}
}
ll ask(int x)
{
	ll sum=1;
	while(x)
	{
		sum=tr[x]*sum%mod;
		x-=x&-x;
	}
	return sum;
}
int main()
{
	inv[2]=(mod-mod/2);
	inv[3]=(mod-mod/3)*inv[2]%mod;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		pre[i]=i,pw=pw*3%mod;
	cnt=n;
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&op[i].opr);
		if(op[i].opr==1)
		{
			scanf("%d%d",&op[i].u,&op[i].v);
			int node=++cnt;
			fa[pre[op[i].u]]=node,fa[pre[op[i].v]]=node;
			trs[node][0]=pre[op[i].u],trs[node][1]=pre[op[i].v];
			pre[op[i].u]=node;
		}
		else
			scanf("%d",&op[i].u);
	}
	for(int i=1;i<=cnt;i++)
	{
		if(fa[i]==0) dfs(i);
	}
	for(int i=1;i<=n;i++)
		pre[i]=i;
	for(int i=1;i<=dfn;i++)
		tr[i]=1;
	add(1,pw);
	for(int i=1;i<=m;i++)
	{
		if(op[i].opr==1)
		{	
			int u=pre[op[i].u],v=pre[op[i].v];
			add(in[u],inv[3]*2ll%mod),add(out[u]+1,3ll*inv[2]%mod);
			add(in[v],inv[3]),add(out[v]+1,3);
			pre[op[i].u]=fa[u];
		}
		else
			printf("%lld\n",ask(in[op[i].u]));
	}
	return 0;
}