- UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359) 题
点我看题A-CountTakahashi没啥好说的点击查看代码#include<bits/stdc++.h>#definerep(i,n)for(inti=0;i<n;++i)#definerepn(i,n)for(inti=1;i<=n;++i)#defineLLlonglong#definefifirst#definesesecond#definepbpush_back#definemprmake_pair......
- abc359_G Sum of Tree Distance 题解
题目链接：Atcoder或者洛谷先考虑暴力，显然是枚举整棵树的路径，这个枚举复杂度显示是\(O(n^2)\)，还不考虑计算\(f(i,j)\)，考虑使用点分治优化枚举复杂度：\(O(n\log{n})\)。接下来考虑如何计算每条路径的\(f(i,j)\)，注意到\(f(i,j)\)：当且仅当\(a[i]=a[j]\)时，答案加上\(dis(i,j......
- P1971 [NOI2011] 兔兔与蛋蛋游戏 题解
Description这些天，兔兔和蛋蛋喜欢上了一种新的棋类游戏。这个游戏是在一个\(n\)行\(m\)列的棋盘上进行的。游戏开始之前，棋盘上有一个格子是空的，其它的格子中都放置了一枚棋子，棋子或者是黑色，或者是白色。每一局游戏总是兔兔先操作，之后双方轮流操作，具体操作为：兔兔每次操作......
- P10538 [APIO2024] 星际列车 题解
题意：有\(n\)个行星，编号为\(0\simn-1\)。有\(m\)辆星际列车，第\(i\)辆列车在时刻\(a_i\)从行星\(x_i\)出发，在时刻\(b_i\)到达行星\(y_i\)，代价为\(c_i\)。换乘条件为上一辆车的终点和下一辆车的起点相同，且上一辆车到达时刻\(\le\)下一辆车出发时刻。你需要吃......
- qoj8542 Add One 2 题解
题目链接点击打开链接题目解法我们先考虑什么样的序列\(x_1,...,x_n\)是可以被得到的对于\(x_i>x_{i+1}\)的位置，我们需要至少对前缀\([1,i]\)做\(x_i-x_{i+1}\)次操作；对于\(x_{i-1}<x_{i}\)的位置，我们需要至少对后缀\([i,n]\)做\(x_i-x_{i-1}\)次操作我们需要......
- [集训队互测 2023] 树哈希 题解报告
[集训队互测2023]树哈希题解报告/bx/bx/bxzky！！！题意给定常数\(q\)，定义一棵以\(1\)为根的有根树\(T\)的\(s(T)\)为\(T\)中本质不同的子树数量，定义其权值为\(q^{s(T)}\)。给定\(n\)，对于\(i=1,\dots,n\)求所有大小为\(i\)的有标号有根树的权值之和对\(P\)......
- CF1978E Computing Machine 题解
好写程度：\(E>D>C\)。好想程度：\(C>D=E\)。总结：C是全场最难。我们考虑把两个操作对全体的\(a_i,b_i\)都做一遍，会发现我们只会做这两遍，不会再有嵌套的了，因为都做过一遍后\(\{a\}\)中0的数量只会减少，而且即使再做一遍也无法给\(\{b\}\)改成不一样的了，比较显然。下文中令......
- [题解]AT_abc267_f [ABC267F] Exactly K Steps
大家好，我是毒瘤，喜欢用玄学算法过题。发现题解区没有这个做法，于是来发一篇。思路不难发现如果一个点对\((u,v)\)的距离为\(d\)，那么在这棵树以\(u\)为根时，\(v\)的深度为\(d\)。于是考虑换根DP。首先思考如何计算答案。显然我们可以将查询离线下来，然后当换根到以\(u\)......
- BD202301·公园题解
BD202301·公园题解考虑将整个移动过程分为两个部分：小度和度度熊汇合之前小度和度度熊汇合之后第一部分可以直接用Dijkstra算法直接搞定，第二部分可以考虑反向思考，从N点出发做一次Dijkstra，最后枚举每个汇合点即可得到答案。时间复杂度\(\Theta(nlogn)\)代码如下：#include......
- [题解]AT_abc264_e [ABC264E] Blackout 2
思路一道很经典的题，运用了一种叫「时光倒流」的技巧。「时光倒流」本质上就是将所有删边（或删点）的操作，通过倒序循环求值的方式转化为加边（或加点）。「时光倒流」具体实现通常伴随着并查集出现，维护一个连通块的某种性质。首先，我们需要将所有从始至终没有删过的边加入并查集。在这......