前言
最自闭的一集
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;
}