20231019NOIP训练赛
时间安排
7:50-8:50 写T1
8:50-9:30写T2
9:30-10:30写T3T4
10:30-11:50写T1
总结
T2没花时间想，没想到建图
题解
T1
枚举最大公约数，然后统计最大公约数的倍数
T2
并查集，设u=\(X_{b_i}\)，v=\(X_{a_i}\)，在u和v间建一条长度为\(c_i\)的边，可以用并查集维护，如果u和v已经属于同一个集合了，就把他们储存下来，到最后时用一遍dfs验证这些存下来的边是否合法
T3
状压DP，设\(f_i\)表示边分配的状态为i时的方案数，我们可以从大到小进行加边，并计算其贡献，计算贡献可以用并查集进行维护
T4
我们把询问和修改拆成如下4部分
然后分三种情况讨论，发现是一个二维数点问题，可以用树状数组维护
标签：30,查集,T2,50,T1,训练赛,20231019NOIP From： https://www.cnblogs.com/RYANGSJ/p/17788853.html