爱飞鱼的blog

从树形dp到树上背包 1.https://www.luogu.com.cn/problem/P1122给定一棵树，每个点有点权，可能为负，求最大权值联通块。 Sol：我们考虑以1为根。树定向后对于任意一个连通块来说，他的形态也一定是一棵树，我们考虑在它的根上会计算到他对答案的贡献。所以问题转化为：求以i为根的最大子树权值和。 对于这个问题我们直接进行dp即可。dp[i]表示在i的子树里面，包含i的联通块的最大权值和。转移就是dp[u]=a[u]+∑v∈son[u]max⁡(0,dp[v])dp[u]=a[u]+ \sum_{v \in son[u]} \max(0,dp[v])dp[u]=a[u]+∑v∈son[u]​max(0,dp[v]) 一个实现细节是：我们必须不能选择空集，所以我们需要保证我们的答案初始值足够小，是负无穷。 几乎一模一样的阅读理解题https://www.luogu.com.cn/problem/P5766 12345678910111213141516171819202122232425262728void solve() { ...

交互题专题 每次输出后，必须刷新标准输出：fflush(stdout); https://atcoder.jp/contests/practice/tasks/practice_2 题意：询问q次之内完成对元素的排序。一个是对26个元素在100次之内。一个是对5个元素排序在7次之内。 分析：对于26-100的情况，我们想到用类似于插入排序的二分，每次插入的时候二分插入的位置，这样子询问比较次数是logn，但是元素移动次数单词是O(n)O(n)O(n)的，但我们只关心交互的次数，所以算法没问题。再考虑对于5—7的这个数学小问题的具体做法： 7次比较完成5个元素的排序： ​ 有五个数字，[a, b, c, d, e]，进行排序。以下排序均按从小到大进行排序： 将a与b进行排序，排序结果为[a’, b’]，共用1次比较，累计1次比较； 将c与d进行排序，排序结果为[c’, d’]，共用1次比较，累计2次比较； 将a’与c’进行比较，若a’ < c’，则a’ < c’ < d’，同时a’ < b’；否则 c’ < a’ <...

To do list 1.子序列自动机 算法学习笔记(90): 序列自动机 - 知乎 (zhihu.com) 序列自动机 - OI Wiki (oi-wiki.org) P5826 【模板】子序列自动机 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) [算法模版]子序列DP - GavinZheng - 博客园 (cnblogs.com) https://leetcode.cn/problems/is-subsequence/solutions/346539/pan-duan-zi-xu-lie-by-leetcode-solution/ 题目-子序列个数 (51nod.com) 2.子序列计数https://www.luogu.com.cn/problem/P3193 https://codeforces.com/gym/105336/attachments D题 P7888 「MCOI-06」Distinct Subsequences - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 115. 不同的子序列 -...

Codeforces Round 964 (Div. 4)](https://codeforces.com/contest/1999) B.如何优雅的暴力？ 题意：总共四张牌，每个人分两张牌，进行两轮游戏。每轮游戏双方各出一张牌，谁大谁win。在所有可能的抽卡结果和出牌顺序中，alice能win的数量。win定义为两场全胜 12345678910111213141516171819202122int f(int x, int y) { if (x > y) return 1; else if (x == y) return 0; else return -1;}void solve() { int a, b, c, d; cin >> a >> b >> c >> d; int ans = 0; if (f(a, c) + f(b, d) > 0) ans++; if (f(a, d)...

1.就算不知道用vector的初始化，也可以手动赋值创建子数组。 2.不断找到当前序列对应的根节点，计算他的子节点的总和，在这样递归处理过程中，注意要中序输出，所以对于是先遍历完左子树，然后输出答案，然后遍历右子树 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include <bits/stdc++.h>using namespace std;#define ll long long//# define int long long#define ull unsigned long long#define pii pair<int,int>#define baoliu(x, y) cout << fixed << setprecision(y) << x#define endl "\n"#define...

病毒溯源 题意：给定一棵树，求出最大深度，要求输出字典序最小的路径 Solution:由于看错题，以为是dag，然后发现只需要拓扑排序一下然后dp最长路就可以了。但值得注意的是需要提前对邻接表排序保证字典序，每次更新都需要维护终点，必须在过程中维护。我们找的是后缀最大值，但希望前缀结构最小。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263vector<int>e[N];int din[N];vector<int>tp;vector<int>dp(N+1,0);void topsort(){ queue<int>q; for(int i=0;i<=n-1;i++)if(din[i]==0){q.push(i);dp[i]=1;} while(q.size()){ auto...

二进制的妙用

匹配计数 https://yijan.co/domino/#题目描述 https://www.cnblogs.com/tzcwk/p/tutte.html https://qoj.ac/contest/1794/problem/9310

以一道区间和查询来说明板子如何使用 1.merge的时候只需要维护两个根节点的距离，利用的是合并时题目给的信息 2.find的时候更新维护是子节点到根的距离 3.需要加一个查询函数，因为距离数组是开在结构体内部的。 题目描述 对于一个长度为 NNN 的整数数列 A1,A2,⋯ANA_{1}, A_{2}, \cdots A_{N}A1​,A2​,⋯AN​，小蓝想知道下标 lll 到 rrr 的部分和 ∑i=lrAi=Al+Al+1+⋯+Ar\sum\limits_{i=l}^{r}A_i=A_{l}+A_{l+1}+\cdots+A_{r}i=l∑r​Ai​=Al​+Al+1​+⋯+Ar​ 是多少? 然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 MMM 个部分和的值。其中第 iii 个部分和是下标 lil_{i}li​ 到 rir_{i}ri​ 的部分和...

B题是纯数学期望推导，用到错位相减，注意数学式子推导过程中一些常数不要丢掉，由于式子其中一部分非常复杂导致计算出来后忘掉最初式子。 c题待补 D题是贪心，需要找到最优策略。策略是倒着推并且遇到当前数出现次数比他的出现次数多时就停下。不停下会导致多出现的呢个数没有数列带它走。