树上背包
title: 树上背包 categories: ICPC tags: null abbrlink: 43d5793c date: 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]+∑v∈son[u]max(0,dp[v])dp[u]=a[u]+ \sum_{v \in son[u]}...
交互题专题
title: 交互题专题 categories: ICPC tags: null abbrlink: 2f5b7502 date: 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)O(n)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 list categories: ICPC tags: null abbrlink: 3b2ae474 date: 2024-05-30 00:00:00 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...
Codeforces Round 964 (Div. 4)
title: Codeforces Round 964 (Div. 4) categories: ICPC tags: null abbrlink: f0969b96 date: 2024-05-30 00:00:00 Codeforces 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: ICPC tags: null abbrlink: 4f0d28e2 date: 2024-05-30 00:00:00 1.就算不知道用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 ...
图论一般题合集
title: 图论一般题合集 categories: ICPC tags: null abbrlink: ed979e34 date: 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: ICPC tags: null abbrlink: 3ba2d0ef date: 2024-05-23 00:00:00 二进制的妙用
匹配计数
title: 匹配计数 categories: ICPC tags: null abbrlink: 6a9b25b9 date: 2024-05-22 00:00:00 匹配计数 https://yijan.co/domino/#题目描述 https://www.cnblogs.com/tzcwk/p/tutte.html https://qoj.ac/contest/1794/problem/9310
带权并查集板子
title: 带权并查集板子 categories: ICPC tags: null abbrlink: c6cf29bf date: 2024-05-18 00:00:00 以一道区间和查询来说明板子如何使用 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∑rAi=Al+Al+1+⋯+Ar 是多少? 然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 MMM 个部分和的值。其中第 iii 个部分和是下标 lil_{i}li 到 rir_{i}ri 的部分和...
牛客练习赛114
title: 牛客练习赛114 categories: ICPC tags: null abbrlink: 133825f3 date: 2024-05-17 00:00:00 B题是纯数学期望推导，用到错位相减，注意数学式子推导过程中一些常数不要丢掉，由于式子其中一部分非常复杂导致计算出来后忘掉最初式子。 c题待补 D题是贪心，需要找到最优策略。策略是倒着推并且遇到当前数出现次数比他的出现次数多时就停下。不停下会导致多出现的呢个数没有数列带它走。