# CCPC2022 Guilin G Group Homework # 题意 给出一个有点权的树，你需要选择两条链，收益为两条链并的权值和减去两条链交的权值和，使得收益最大。 # 题解 如果选择的两条链，交点多于111 个，那么我可以重新选择划分成两条不相交的链，使得收益比原来更大。所以情况只有两种：两条链有一个交点，两条链没有焦点。 对于两条链有一个交点的情况，做 dp 计算从每个点延伸出的前四大最长链。这里用 换根dp 实现。首先自下而上计算f0[x][0,1,2,3]f_0[x][0,1,2,3]f0​[x][0,1,2,3] 表示以111 为根时xxx...

# [题解] ICPC2023 HongKong Sum of Numbers [线段树][扫描线] 也是好久没写博客了。最近学校各种事情太多了，基本每周都有事。 下周更是：CCSP 要来了，在此之前还有网综实验考试。。 好在网综实验貌似并不是太难，用了半个上午时间大概会了一半的分数了；老师也还算和善。 希望不出什么岔子。 # 题目大意 给定一个长度为nnn 的颜色数组aaa, 对于一个区间[l,r][l,r][l,r], 称其是不好的当且仅当区间内存在一个颜色ccc 且这个颜色恰好出现了kkk 次。问数组中一共有多少个好的区间。 # 题解 对于每一个颜色 c，将其出现位置抽离出来。记 pos...

# [题解] 2023 杭电多校 King’s Ruins [偏序][bitset][dp] # 题目大意传送门\footnotesize^{传送门}传送门 六维偏序dpdpdp。 # 高维偏序 bitset 做法 一维、二维、三维偏序分别有排序、排序 + 一维数据结构、CDQCDQCDQ 分治的做法，比较经典。维数再高点，多层嵌套的CDQCDQCDQ、多层嵌套数据结构，复杂度都不会太理想。 专门处理高维查询的数据结构K−DTreeK-D TreeK−DTree...

# [题解] CF1864E Exotic Queries [区间问题][二维偏序] # 题目大意传送门\footnotesize^{传送门}传送门 给一个长度为nnn 的数组，有qqq 个询问，每次询问对于值域[L,R][L,R][L,R] 的所有元素，通过以下操作使得这些元素全部变为000 的最小操作次数。 指定操作(l,r,x)(l,r,x)(l,r,x)：选取一段区间[l,r][l,r][l,r] 和一个正整数xxx, 将这段区间上的元素减去xxx。 你可以操作任意多次，但是对于所有操作区间，只存在包含、相离关系，不存在相交关系。 #...

# [题解] CF1864E Guess Game [期望][Trie] # 题目大意传送门\footnotesize^{传送门}传送门 给一个长度为nnn 的数组，每次从中随机选取两个数a,ba,ba,b，进行游戏： Alice 得到aaa 和a∣ba|ba∣b 的值，Bob 得到bbb 和a∣ba|ba∣b 的值，从 Alice 开始，他们轮流猜aaa 和bbb 的大小关系。 如果不能确定就说 idk ，否则直接会说出a<ba\lt ba<b,a>ba\gt ba>b...

# 矩阵类 struct Mat{ int **a; int r,c; Mat(const int &r,const int &c):r(r),c(c){ a=new int * [r]; for(int i=0;i<r;++i) a[i]=new int [c](); } Mat(const int &r,const int &c,const int &x):Mat(r,c){ for(int...

# [题解] 2023 杭电多校 Do You Like Interactive Problems? [期望][分类讨论] # 题目大意传送门\footnotesize^{传送门}传送门 你需要猜一个在[1,n][1,n][1,n] 范围内的整数xxx，每次你随机选择一个y∈[1,n]y \in [1,n]y∈[1,n] 进行询问，并得到答案 y>x,y<x,y=xy>x,y<x,y=xy>x,y<x,y=x 其中之一，直到能确定xxx 的值停止询问。 问期望询问次数。 #...

# [题解] 2023 杭电多校 Many Topological Problems [树计数] # 题目大意 # Topological Problem 给定一个nnn 个节点的有标号有根树和整数kkk，称一个长度为 n 的排列aaa 为好的，当且仅当∀i,1≤i≤n\forall i,1\le i\le n∀i,1≤i≤n, 满足afa[i]<ai≤afa[i]+ka_{fa[i]} \lt a_i \le a_{fa[i]}+kafa[i]​<ai​≤afa[i]​+k,fa[i]fa[i]fa[i] 表示iii...

# [题解] 2023 CCPC 华为云计算挑战赛 博弈，启动！ [BFS] # 题目大意 给定一个有向二分图，分为GGG 部分和YYY 部分，有一个棋子位于图上任意一节点。当棋子在GGG 部分时，玩家GGGGGG 沿节点出边操作棋子；当棋子在YYY 部分时，玩家YYYYYY 沿出边操作棋子。循环往复该过程，直至棋子到达的节点没有出边。GGGGGG 的目标是让棋子在图上每个节点经过无穷次，YYYYYY 的目标与之相反。两人均采取最优策略，问GGGGGG 是否有必胜策略。 # 题解 先来剖析一下题目的意思，GGGGGG...

# [题解] 2023 杭电多校 Rikka with Square Numbers [数论] 哎，数学！ # 题目大意 每次操作可以加或者减一个完全平方数，问至少多少次可以把aaa 变成bbb。 1≤a,b≤1091 \le a,b\le 10^91≤a,b≤109。 # 题解 看到这个题面首先想了dpdpdp 或者搜索的做法。 发现这里的加减两个方向的转移其实没办法很好地dpdpdp。而且并没有找到合理的操作策略，不像是直接能递推出来的。 所以大概率是个结论题。然而我对数学不那么敏感，也推不出来什么式子。 如果当初先暴力打个表说不定就有思路了，那就能看到答案其实只有111...