搜索结果
查询Tags标签： stk，共有 90条记录-
CodeCraft-22 and Codeforces Round #795 D
D. Max GEQ Sum 我们考虑暴力枚举a[i]为最大值 通过单调栈可以求出a[i]左边右边第一个大于a[i]的 然后通过ST表查询前缀和数组（i，R[i]-1）的最大值 （L[i]+1,i)的最小值得到我们需要的区间和最大值 check即可 注意我们这里因为是前缀和 query_max(i, R[i] - 1) - query_…
2022/9/10 6:24:33 人评论 次浏览 -
CF1702G2 Passable Paths (hard version)
Passable Paths (hard version) 给出一棵大小为 \(n\) 的树，\(q\) 次询问，每次给出一大小为 \(m\) 的点集，判断是否存在一条链覆盖这些点，注意这条链可以经过其他点。\(n,\sum m \leq 2\times 10^5\) ，\(q \leq 10^5\)。SOLUTION1: 虚树 由于 \(q\) 次询问的 \(\sum …
2022/9/4 23:25:29 人评论 次浏览 -
虚树
一种大树变小树的方法。大概就是只保留题目要求的关键点和其他一些统计答案必须的点，把剩余的所有点从树上砍掉。原理是维护一条最右链（就是我们扫到的最右边的一条链，它左边的虚树已经建好）。 具体的操作： 首先把所有的关键点按照dfs序排序。然后开始分讨：如果栈空…
2022/9/3 23:22:58 人评论 次浏览 -
求一个图的最打的半联通子集=求一个图的最长链方案和个数
拓扑图最长路 等于 背包问题求方案数 因为要求点不同 存在多条边同一情况 需要边判重(set) 拓扑求方案数 #include <iostream> #include <cstring> #include <algorithm> #include <unordered_set>using namespace std; typedef long long LL; c…
2022/8/30 23:53:03 人评论 次浏览 -
CF1506G 题解
前言 题目传送门！ 更好的阅读体验？ 校内考试题目。写一篇题解。 思路 首先记录每个字符出现了多少次，然后创建单调栈。 看当前字符是否入栈，如果没有入栈，就不停 pop()，直到：栈空了。 栈顶字典序大于当前字符。 栈顶元素已经被删掉了（因为栈外面用 cnt[i] 记录了每…
2022/8/27 23:22:46 人评论 次浏览 -
1175. 最大半连通子图
题目链接 1175. 最大半连通子图 一个有向图 \(G = (V,E)\) 称为半连通的 (Semi-Connected)，如果满足：\(\forall u,v \in V\)，满足 \(u \to v\) 或 \(v \to u\)，即对于图中任意两点 \(u,v\)，存在一条 \(u\) 到 \(v\) 的有向路径或者从 \(v\) 到 \(u\) 的有向路径。 若…
2022/8/11 23:24:41 人评论 次浏览 -
非递归遍历二叉树Java
import java.util.*;public class Test {static class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val = val;}}public static void main(String[] args) {TreeNode treeNode1 = new TreeNode(1);TreeNode treeNode2 = new TreeNode…
2022/6/28 14:20:26 人评论 次浏览 -
`
#include <stdio.h> enum {the_size = 100010 }; class FIBO_TREE {private : struct TREE {int lid, rid, pid;int key;int cnt;} tree[the_size];int ROOT, tot;int stk[the_size], top;#define lid(id) tree[id].lid#define rid(id) tree[id].rid#define pid(id)…
2022/6/16 23:20:08 人评论 次浏览 -
BalticOI2017 Political Development
对于度数\(<k\)的点可以快速的求出包含它的团，问题就是解决度数比较大的团 注意到题目特殊限制，没有一个导出子图所有点度数都较大，所以一定可以通过不停地遍历、删除度数\(<k\)的点来遍历整张图（类似于拓扑排序） 并且我们可以发现对于一个已经check的点删除后…
2022/6/4 23:22:54 人评论 次浏览 -
B. Mike and Feet_单调栈+RMQ
Problem - B - Codeforces 题目大意 求出所有长度x的子段中最小值的最大值 思路和代码 考虑O(n3)暴力的做法，枚举所有长度的子区间找最小值的最大。 这种做法即便是将最小值的查询通过线段树或散列表（ST）降低到log级别也还是有O(n2logn)的复杂度。 考虑另外的做法： 我…
2022/6/2 23:23:05 人评论 次浏览 -
cf1482 E. Skyline Photo
题意： 给定一排 n 个点，每个点有 \(h_i\) 和 \(v_i\)。把它们划分成任意数量的连续段，每个点仅属于一段，每段的价值等于段中 \(h\) 最小的点的 \(v\) 值。求最大价值和 \(h_i\) 为 1~n 的一个排列，\(-1e9\le v_i\le 1e9\) 思路： 用到单调（递增）栈的两个性质：1. 栈…
2022/5/30 23:20:15 人评论 次浏览 -
进制转换
二进制转十进制 #include <iostream> using namespace std; int main() { int a[10], n, i; cout<<"Enter the number to convert: "; cin>>n; for(i=0; n>0; i++) { a[i]=n%2; n= n/2; } cout<<"…
2022/5/26 23:20:22 人评论 次浏览 -
【力扣】 503. 下一个更大元素 II
503. 下一个更大元素 II 给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。 数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个…
2022/5/22 23:05:34 人评论 次浏览 -
D
#include<bits/stdc++.h> using namespace std;typedef pair<int,int> pii;const int N = 2e5+10;int fa[N]; bool isleaf[N];int get_dis(int x){int res=0;while(fa[x]!=x){res++;x=fa[x];}return res; }int print_path(int x){stack<int> stk;stk.pu…
2022/5/6 6:14:22 人评论 次浏览 -
1019. Next Greater Node In Linked List
This problem is as same as https://www.cnblogs.com/feiflytech/p/16169025.htmlclass Solution {public int[] nextLargerNodes(ListNode head) {List<Integer> list = new ArrayList<>();ListNode point = head;while(point!=null){list.add(point.val);p…
2022/4/20 14:42:37 人评论 次浏览
