今天照常7:45开始打模拟赛,11:45时结束。打了T1的40分暴力、T3的20分暴力,没有注意到T4的特殊样例可以骗分(悲),最后以60分收尾。总结一下,没有挂分,但也没和正解挨上边,算是不好也不坏吧。
订题时我看着T1 26行的AC代码陷入了沉思。三个人,想了至少三个小时,结果全没想出来,于是来整理一下今天的神奇模拟赛。
题目小链接:?
T1【集合】
题目大意:给定一棵n个节点的树,共m次操作,每次操作形如对于第x条边(u,v),将Su,Sv替换成两者的并集。求m次操作后,每个i属于多少个集合
解题思路:经过一定的思考之后,我们发现正序操作可以理解为“我会有多少个朋友”,明显不好处理;但倒序操作可以理解为“我会是谁的朋友”,可以转移。
举个栗子:对于操作加盟u->v边,此时u与v中都包含彼此,所以当下次对u进行操作时,v一定也会被那个节点包含。
可以转移为s[u]=s[v]=s[u]+s[v]。但这样当出现重边时,因为u与v已有相同元素,这个操作就会应取了相同元素而不满足集合性质(题目中取并集)。但是,众所周知,|S∪T|=|S|+|T|−|S∩T|,而经过一系列推论我们容易发现|S∩T|为上一次对该边操作后的答案,即上一次操作取的并集会是此次操作中u与v的交集。那么会不会出现|S∩T|中不仅仅是上次并集中的元素情况呢?手模后发现是不会的。因为……反正……这样这样,那样那样,树上是没有环的,若S、T中的其他元素想要影响|S∩T|,只能通过再次操作该边影响,所以上次的操作的集合并就是这次操作中的集合角。
于是乎,我们维护pre数组与ans数组,pre[i]表示对于边i,上一次操作的答案,ans[i]表示对于节点i之中元素的个数。于是我们稍加整理,可以得到神奇的式子:ans[u]=ans[v]=pre[op[i]]=ans[u]+ans[v]-pre[op[i]]。于是26行代码就解决了
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=4e5+10;
int n,m;
int u[N],v[N];//记录每条边
int op[N];//操作
int ans[N],pre[N];//答案与上次答案
void read()
{
scanf("%d%d",&n,&m);
for (int i=1;i<n;i++) scanf("%d%d",&u[i],&v[i]);
for (int i=1;i<=m;i++) scanf("%d",&op[i]);
}
int main()
{
read();
for (int i=1;i<=n;i++) ans[i]=1;
for (int i=m;i>=1;i--)
{
int uu=u[op[i]],vv=v[op[i]];
ans[uu]=ans[vv]=pre[op[i]]=ans[uu]+ans[vv]-pre[op[i]];
}
for (int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}