树上背包
title: 树上背包categories: - ICPCtags: - nullabbrlink: 43d5793cdate: 2024-06-08 00:00:00从树形dp到树上背包1.https://www.luogu.com.cn/problem/P1122给定一棵树，每个点有点权，可能为负，求最大权值联通块。 Sol：我们考虑以1为根。树定向后对于任意一个连通块来说，他的形态也一定是一棵树，我们考虑在它的根上会计算到他对答案的贡献。所以问题转化为：求以i为根的最大子树权值和。 对于这个问题我们直接进行dp即可。dp[i]表示在i的子树里面，包含i的联通块的最大权值和。转移就是$dp[u]=a[u]+ \sum_{v \in son[u]} \max(0,dp[v])$ 一个实现细节是：我们必须不能选择空集，所以我们需要保证我们的答案初始值足够小，是负无穷。 几乎一模一样的阅读理解题https://www.luogu.com.cn/problem/P5766 void solve() { int n; cin...
交互题专题
title: 交互题专题categories: - ICPCtags: - nullabbrlink: 2f5b7502date: 2024-06-06 00:00:00交互题专题每次输出后，必须刷新标准输出：fflush(stdout);https://atcoder.jp/contests/practice/tasks/practice_2 题意：询问q次之内完成对元素的排序。一个是对26个元素在100次之内。一个是对5个元素排序在7次之内。分析：对于26-100的情况，我们想到用类似于插入排序的二分，每次插入的时候二分插入的位置，这样子询问比较次数是logn，但是元素移动次数单词是$O(n)$的，但我们只关心交互的次数，所以算法没问题。再考虑对于5—7的这个数学小问题的具体做法： 7次比较完成5个元素的排序： 有五个数字，[a, b, c, d, e]，进行排序。以下排序均按从小到大进行排序： 将a与b进行排序，排序结果为[a’, b’]，共用1次比较，累计1次比较； 将c与d进行排序，排序结果为[c’,...
AAATo do list
title: AAATo do listcategories: - ICPCtags: - nullabbrlink: 3b2ae474date: 2024-05-30 00:00:00To do list1.子序列自动机 算法学习笔记(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...
Codeforces Round 964 (Div. 4)
title: Codeforces Round 964 (Div. 4)categories: - ICPCtags: - nullabbrlink: f0969b96date: 2024-05-30 00:00:00Codeforces Round 964 (Div. 4)](https://codeforces.com/contest/1999)B.如何优雅的暴力？ 题意：总共四张牌，每个人分两张牌，进行两轮游戏。每轮游戏双方各出一张牌，谁大谁win。在所有可能的抽卡结果和出牌顺序中，alice能win的数量。win定义为两场全胜 int 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...
二叉树给出先序和中序遍历序列，求和树 要求输出中序遍历序列；
title: 二叉树给出先序和中序遍历序列，求和树 要求输出中序遍历序列；categories: - ICPCtags: - nullabbrlink: 4f0d28e2date: 2024-05-30 00:00:001.就算不知道用vector的初始化，也可以手动赋值创建子数组。2.不断找到当前序列对应的根节点，计算他的子节点的总和，在这样递归处理过程中，注意要中序输出，所以对于是先遍历完左子树，然后输出答案，然后遍历右子树#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...
图论一般题合集
title: 图论一般题合集categories: - ICPCtags: - nullabbrlink: ed979e34date: 2024-05-26 00:00:00病毒溯源题意：给定一棵树，求出最大深度，要求输出字典序最小的路径Solution:由于看错题，以为是dag，然后发现只需要拓扑排序一下然后dp最长路就可以了。但值得注意的是需要提前对邻接表排序保证字典序，每次更新都需要维护终点，必须在过程中维护。我们找的是后缀最大值，但希望前缀结构最小。vector<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...
二进制的妙用
title: 二进制的妙用categories: - ICPCtags: - nullabbrlink: 3ba2d0efdate: 2024-05-23 00:00:00二进制的妙用
匹配计数
title: 匹配计数categories: - ICPCtags: - nullabbrlink: 6a9b25b9date: 2024-05-22 00:00:00匹配计数 https://yijan.co/domino/#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0 https://www.cnblogs.com/tzcwk/p/tutte.html https://qoj.ac/contest/1794/problem/9310
带权并查集板子
title: 带权并查集板子categories: - ICPCtags: - nullabbrlink: c6cf29bfdate: 2024-05-18 00:00:00以一道区间和查询来说明板子如何使用1.merge的时候只需要维护两个根节点的距离，利用的是合并时题目给的信息2.find的时候更新维护是子节点到根的距离3.需要加一个查询函数，因为距离数组是开在结构体内部的。 题目描述对于一个长度为 $N$ 的整数数列 $A_{1}, A_{2}, \cdots A_{N}$，小蓝想知道下标 $l$ 到 $r$ 的部分和 $\sum\limits_{i=l}^{r}A_i=A_{l}+A_{l+1}+\cdots+A_{r}$ 是多少? 然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 $M$ 个部分和的值。其中第 $i$ 个部分和是下标 $l_{i}$ 到 $r_{i}$ 的部分和 $\sum_{j=l_{i}}^{r_{i}}=A_{l_{i}}+A_{l_{i}+1}+\cdots+A_{r_{i}}$, 值是...
牛客练习赛114
title: 牛客练习赛114categories: - ICPCtags: - nullabbrlink: 133825f3date: 2024-05-17 00:00:00B题是纯数学期望推导，用到错位相减，注意数学式子推导过程中一些常数不要丢掉，由于式子其中一部分非常复杂导致计算出来后忘掉最初式子。c题待补D题是贪心，需要找到最优策略。策略是倒着推并且遇到当前数出现次数比他的出现次数多时就停下。不停下会导致多出现的呢个数没有数列带它走。