2020-hdu多校-3
1004 前缀和dp
预处理出前缀和，前缀和相同的两个点之间就可以合并成一个满足条件的数。
从后往前利用前缀和即可dp处理出最多的个数。
1009 模拟括号匹配
出现未配对的右括号就用最左边的*去匹配，出现未配对的左括号就用最右边的*去匹配。
差不多是这样
1005 并查集&计数
先统计一下所有点集在无边时的ans值，然后每连两个联通块，就将这两个联通块之间之前会产生的贡献全部减去即可。
两个联通块可能产生的情况有：
-
1号贡献一个1，2号贡献一个2，在剩余其他所有点中找一个2
-
1号贡献一个2，2号贡献一个1，在剩余其他所有点中找一个2
-
1号贡献一个2，2号贡献一个2，在剩余点中随意找一个
那么随便搞一下就行了。
注意不要爆int 我是sb我是sb我是sb…
1const itn maxn = 1e5 + 10;
2const int M = 1e9 + 7;
3
4int par[maxn];
5ll cnt2[maxn], cnt1[maxn], s1, s2;
6
7int find(int x){return x == par[x]? x: par[x] = find(par[x]);}
8void merge(int x, int y){
9 int r1 = find(x), r2 = find(y);
10 assert(r1 != r2);
11 par[r2] = r1;
12 cnt2[r1] += cnt2[r2]; cnt1[r1] += cnt1[r2];
13}
14
15int main(){
16// Fastin;
17// Fastout;
18 int t; scanf("%d", &t); while(t--){
19 int n; scanf("%d", &n); s1 = s2 = 0;
20 for(int i = 1; i <= n; i++){
21 int x; scanf("%d", &x);
22 par[i] = i;
23
24 if(x == 1){cnt1[i] = 1;cnt2[i] = 0; s1++;}
25 else{cnt2[i] = 1; cnt1[i] = 0; s2++;}
26 }
27
28 ll ans = s1 * s2 * (s2 - 1) / 2 % M + s2 * (s2 - 1) * (s2 - 2) / 6 % M; ans %= M;
29 printf("%lld\n", ans);
30 for(int i = 0; i < n - 1; i++){
31 int u, v; scanf("%d %d", &u, &v);
32 int r1 = find(u), r2 = find(v);
33 ll res = (cnt1[r1] * cnt2[r2] + cnt2[r1] * cnt1[r2]) * (s2 - cnt2[r1] - cnt2[r2])
34 + (cnt2[r1] * cnt2[r2]) * (s1 + s2 - cnt1[r1] - cnt2[r1] - cnt1[r2] - cnt2[r2]);
35 res %= M;
36 ans -= res; ans = (ans % M + M) % M;
37 printf("%lld\n", ans);
38 merge(u, v);
39 }
40 }
41 return 0;
42}1007 边权随机均匀分布的完全图上问题
当V与E同阶时，可以使用堆优化的dij算法$O(ElogE)$
用斐波那契堆可以降低到$O(VlogV+E)$ 不会
当完全图时，则应该使用朴素的dij算法$O(n^2)$
在这道题中，因为边权随机均分分布，所以最短路径不会很长(个数意义上)。同时我们发现，如果不堵塞当前最短路径中的某一条边，那么修改其他边是不会影响结果的。因而我们跑最短路算法，枚举路径上每一条边来堵塞，递归地在新图中再次跑最短路，堵塞最短路上的每一条边…枚举&回溯即可得到所有的结果，取出最长的最短路作为答案即可。
时间复杂度$O(Tn^2L^k)$ 其中$L$是最短路径可能的长度。
虽然没有测试，但是L大概最多大概也就6、7的级别
然而wmx真算法了结果没有初始化GG
IGVA orz
1008 计算几何与平面旋转
转化思路，不考虑小球在这个三角形中如何弹射，而是用三角形密铺整个平面，那么小球在三角形的弹射路径就可以通过对称操作变成一条直线，那么现在的问题就是在三角形平面中求一条线碰到第k个交点时的时间。
二分时间，检查当前时间时只需要检查当前长度的线段与三族平行线(0, pi / 3, pi * 2 / 3)之间各自交了多少个点。
检查0时只需要看y轴方向的速度，该方向上的长度h能跨越多少个平行线，注意判断一下最开始的半截的影响。
接下来要判断pi / 3, pi * 2 / 3的平行线族的相交情况时不需要从小球初始位置斜着找投影后的长度，可以相对地将初始位置和速度旋转一番，这样就可以化归到对0的情况，而对0的情况很容易考虑，$v_y*t$就是平行线方向的投影。
1const double pi = acos(-1);
2double l, x, y, vx, vy; int k;
3const double eps = 1e-8;
4
5//将(x, y)逆时针旋转a度
6void rotate(double &x, double &y, double cx, double cy, double a){
7 x -= cx; y -= cy;
8 double cosa = cos(a), sina = sin(a);
9 double xx = x * cosa + y * -sina;
10 double yy = x * sina + y * cosa;
11 x = xx + cx; y = yy + cy;
12}
13
14void fun(double &x, double &y, double &vx, double &vy){
15 double cx = 0, cy = l / sqrt(3) / 2;
16 rotate(x, y, cx, cy, -pi * 2 / 3);
17 rotate(vx, vy, 0, 0, -pi * 2 / 3);
18}
19
20bool check(double t, double h = 0){
21 ll cnt = 0;
22 double L = l / 2 * sqrt(3);
23 for(int i = 0; i < 3; i++){
24 h = abs(vy) * t;
25 if(vy < 0) cnt += h < y? 0: 1 + (ll)((h - y) / L);
26 else cnt += h < L - y? 0: 1 + (ll)((h - (L - y)) / L);
27 fun(x, y, vx, vy);
28 }
29 return cnt < k;
30}
31
32int main(){
33// Fastin;
34 int t; scanf("%d", &t); while(t--){
35 scanf("%lf %lf %lf %lf %lf %d", &l, &x, &y, &vx, &vy, &k);
36 double left = 0, right = 1e10, middle;
37 while(left + eps < right){
38 middle = (left + right) / 2;
39 if(check(middle)) left = middle;
40 else right = middle;
41 }
42 printf("%.10f\n", left);
43 }
44
45 return 0;
46}