18duangduang

题解

未归档(23) 计算几何(1)

/ 注册

全部文章 / 题解（共7篇）

ccpc绵阳站

Defuse the Bombs 听说是公司面试题，答案满足二分性质，直接二分check（对于每个ai***桶在x的时间段，要么有ti时间一直在降低，x-ti时间在保持不变.贪心让不变的时间尽可能少。)本题坑点：二分右边界设置1e10(设置太大直接爆long long WA) #include<...

二分答案check 线段树博弈 SG函数暴力组合

2020-11-10

3 913

厦门大学“网宿杯“17届程序设计竞赛决赛（同步赛）H.时间管理

大致题意：一个序列，可以执行两种操作。对区间内的元素依次对x取，然后将结果赋值给 . 求区间元素和。分析：这道题跟区间开方思路类似。每次对一个区间进行gcd的话一般会有大部分会变成1，可以用一些小技巧来保证复杂度不会太差，用一个tag变量去标记一下这个区间是不是全都相等，再用...

线段树区间gcd

2020-06-01

0 622

厦门大学程序设计大赛月赛 D.小C的棋王之路

题目大意:给定一个有个元素序列,有四种操作和一种询问. 1 L R K 让区间的元素加上 . 2 L R K 让区间的元素乘上 . 3 L R K 让区间的元素变为 . 4 L R K 在末尾位置添加一个元素值为 . 5 L R 询问区间元素的值的和. 分析: 赛中分析，前四个...

线段树

2020-05-18

0 645

线段树维护等差数列

题面 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+10; const int mod=3*5*7*11*13*17*19*23; const int i...

线段树维护等差数列标记

2020-04-20

1 613

牛客多校赛第八场总结来自专栏

本场总结： A.单调栈B.区间贡献C.构造D.三维树状数组----维护曼哈顿距离E.线段树区间维护dfs并查集撤销G.签到I.树上差分和树状数组区间差分J.组合数学和dp 小结：---矩阵中子矩阵问题单调栈继续练---构造先蒙---学习三维树状数组如何维护，后缀最小值转前缀最大值---学习线段树...

树上差分线段树单调栈构造三维树状数组区间交贡献并查集组合数容斥 dp

2020-02-24

0 708

牛客多校赛第二场总结来自专栏

本场总结: 题目类型:A.概率问题D.bfs第K小团E.线性dp，线段树维护矩阵加速F.dfs剪搜H.单调栈维护第二大子矩阵J.区间合并问题其他题目暂时鸽了小结:--概率问题脑子不够用--k小团问题bit<int.> & 极好用--线段树还能维护矩阵加速震惊--单调栈找第二...

概率第k小团 dfs 单调栈第二大子矩阵区间合并 dp 线段树矩阵加速线性dp

2020-02-02

0 598

牛客多校赛第四场总结来自专栏

本场总结：题目类型:A.dfs找直径B.线段树上维护线性基交C.单调栈找min边界和线段树z维护区间最值D.分类讨论构造E.F.G.H 留坑没想法I.后缀数组找不同子串个数和回文树找回文串个数J.最短路k次免费K.签到小结:---学习线段树上维护线性基交---找固定区间最小值求区间左...

dfs找直径最短路k次免费线段树线性基交单调栈后缀数组不同字符个数

2020-01-31

0 615