本场总结: 题目类型:A.概率问题D.bfs第K小团E.线性dp，线段树维护矩阵加速F.dfs剪搜H.单调栈维护第二大子矩阵J.区间合并问题其他题目暂时鸽了  小结:--概率问题脑子不够用--k小团问题bit<int.> & 极好用--线段树还能维护矩阵加速 震惊--单调栈找第二大子矩阵小细节--注意--区间合并问题一直是zero 下次还是不会 A. Eddy Walker 大致题意：一个由0--n-1组成的环，你的起点为0,你在环上行走,你会独立地随机选择前进或后退。现给你T个场景，场景先后关联产生。场景给定n,m，n表示行走的是0--n-1的环,m表示你从起点0开始行走...

本场总结： 题目类型:A.dfs找直径B.线段树上 维护 线性基交C.单调栈找min边界和线段树z维护区间最值D.分类讨论构造E.F.G.H 留坑没想法I.后缀数组找不同子串个数和回文树找回文串个数J.最短路k次免费K.签到  小结:---学习 线段树上 维护 线性基交---找固定区间最小值求区间左右边界可以用单调栈维护O(n)---按位或的知识小讨论---复习了一下后缀数组和回文树  A.meeting 题意：有n个城市，编号从1到n,然后只有n-1条连线，不会成环。从第一个地方到另一个地方只需要1秒，现在有k个人，分别分布在不同的城市，现在问他们相聚最短所需的时间，。分析:就是k个人相聚，...

本场总结: 题目类型:A.分块B.签到C.巨巨才能A的题D.数论---找最小循环节E.kruskal重构树--巨巨才能A的题F.单调队列G.ST表分治、贪心H.构造I:dpJ. unordered_map<string,list<node>::iterator>mp; 模拟</node>  小结:---点集可以用点异或和，点权可以用随机hash产生.---数论还得多练---ST表可以维护最值下标，分治一般取较小侧暴力---map 存关键字 和 链表索引地址 优雅   A.Graph Games 题意:一个图有n个点m条边关系，有q次操作(1 l r ):m边...

A. Equivalent Prefixes --两个单调栈维护 #include<bits/stdc++.h> using namespace std; const int maxn=5e5+10; int a[maxn],b[maxn]; int dp1[maxn],dp2[maxn]; int main() { int n; while( ~scanf("%d",&n) ) { for( int i=1;i<=n;i++ ) scanf("%d",&a[i]); for( int i=1;i<=n;i++ ) scanf("%d",&b[i...

摘录 https://blog.nowcoder.net/n/c3ed459a06074283be1cf9ea1e2c9261 #include<bits/stdc++.h> using namespace std; int t,n,m,a,b,c,ans,k,s; int v[105],mp[105][105]; int ok( int x ) { v[x]=++c; for( int i=2;i<=n;i++ ) { if( !v[i] && ( mp[x][i] & m ) && ok(i) ) break; // 搜索剪枝 } ...

https://www.luogu.com.cn/blog/kkxhh/solution-p1654

题目链接:https://ac.nowcoder.com/acm/contest/2908/G 以 x 或者 y 结点作为根结点建树求解用 x 结点建树作为例子：先dfs标记每个结点的子节点个数，然后找到 y 的离 x 最近的父节点 z ，那么从 对应结点与 对应结点 的任意两点的最短路 必经过 x,y 结点 ，那么 即为不符合方案数。那么答案即为： . #include<bits/stdc++.h> #define sscc ios::sync_with_stdio(false) #pragma comment(linker, "/STACK:102400000,10240000...

B题 题目大意:求一个由二元组组成最长序列，二元组的相对位置不变，并且满足对于数列a中任意一个数字都是极大值或者极小值  首先离散将所有数字离散化.分两种情况，奇数位较大和偶数为较大.1.奇数位较大的情况， 我们需要将所有满足 x>y 的二元组选出来。用 表示前 i 个二元组选出的最后一个二元组的 y 小于等于 j 最多可以选出二元组的数量。由此可以写出状态转移方程：  这显然可以用个树状数组维护，树状数组维护以该数字结尾最优方案数，每次查询前缀最大值更新答案 ：   2.奇数位较小的情况，状态转移方程:   我们同样用树状数组维护，采用倒序插入的方式将后缀最小值转变为前缀最大值进行维护...