弓长九日

分类

CDQ(1) codeforces(1) DP(9) SSM框架(3) 《算法竞赛进阶指南》杂谈(14) 二分(1) 分块(1) 动态规划(1) 图论(11) 基本算法(5) 字符串(6) 差分(2) 并查集(2) 思维(18) 搜索(7) 数学(16) 数据结构(17) 未归档(128) 树型结构(4) 树套数(1) 模拟(2) 爬虫(6) 系统配置记录(1) 线段树(8) 计算机网络(2) 贪心(2) 面试(3) 题解(4) 题集(45)

/ 注册

全部文章（共320篇）

题解 | 算法竞赛进阶指南城市游戏

城市游戏这题NOI出过叫什么玉蟾宫单调栈。。。。。其实还能用悬线法处理找到每层每个相对这个数据的最远的左端右端 * 自己的高度即可之后补充一个悬线法解的题 #include <bits/stdc++.h> using namespace std; const int ...

单调栈 DP

2019-08-20

0 668

[线段树] CodeForces - 920F SUM and REPLACE (数学优化)

[线段树] CodeForces - 920F SUM and REPLACE (数学优化) https://vjudge.net/problem/1349242/origin 题意：给出一个数组，有两个操作，一个操作把区间所有数都变成其因子个数，另一个操作询问区间和。一个树的约束个数最多 ...

2019-08-20

0 521

[线段树] Codeforces 482B Interesting Array (思维小优化)

Codeforces 482B Interesting Array(线段树) 题目大意：给定一个长度为N的数组，现在有M个限制，每个限制有l，r，q，表示从a[l]~a[r]取且后的数一定为q，问是否有满足的数列。考虑维护 30颗线段树每个代表这位二进制 0 1 区间修改区间查这线段树代...

2019-08-20

0 515

2019杭电多校第五场 permutation 1 (全排列)

给你n个数 1到n 你全排列相邻差序列有字典序第k大差序列的输出数据到1e4 大于 8 的直接暴力 n 后面 1 ~ n-1 的第k-1排列就是解然后 1 到 8 打表处理 #include <bits/stdc++.h> using namespace std; con...

2019-08-19

0 431

2019 牛客多校第十场 E Hilbert Sort (分形 | 平面坐标旋转)

算法竞赛进阶指南差不多就是分形之城看作向量旋转平移细节还不算多 #include <bits/stdc++.h> using namespace std; long long f(int n, int x, int y) { if (n == 0) retur...

2019-08-19

0 576

2019 牛客多校第十场 B Coffee Chicken (数学思维)

类似斐波那契数列这个字符在coffe 还是 chicken 我们只需要每次减去 dp[n - 2] 判断它在那个串中能减去就意味是每个串重新换了减去 ad– 不然-=2 #include<bits/stdc++.h> using namespace std; typedef l...

2019-08-19

0 457

2019牛客多校 H Stammering Chemists (模拟)

这题找到他们的不同特征判断就好了题意还说不是下面的随便输出就可以少盘一种了虽然也没有少写啥第一个连边只有2个是出现1次的 4 和 5 用 2个 3边和一个4边判断 2 和 3 我dfs2边 3 的话 4深度出现2次剩下的直接出 2图就好 #include <bits...

2019-08-19

0 443

题解 | 算法进阶指南导弹防御塔

我们考虑跑网络流首先是二分图最大匹配 == 入侵者数量时时间可以缩小点才最多50个 50 * 50 最多发 3000 不到的导弹3000 和原点连 3000个边3000 和入侵者连最多15000边开前向星按 40000 * 8 边差不多了就因为连的太多了暴力点建图将塔分成很...

二分图网络流

2019-08-19

0 705

2019年牛客多校第八场 Explorer (线段树+可撤销并查集)

线段树上套每个区间可以有哪些并查集一直向下如果已经有大区间的管道到n 这个点覆盖区间线段树往下就不必要走了然后学会了安秩合并(启发式搜索) 不能压缩路径我们把大的合并到小的上面就使得长的被查询的的路径尽可能慢的长这样不压缩路径不超时的完成我们合并和实现撤销的操作 ...

2019-08-19

0 422

2019n牛客多校第八场 B Beauty Values (DP or 找规律)

f(i)=f(i-1)+i-(vis[a[i]]?vis[a[i]]:0) 公式怎么出来的呢?考虑由1-i 如果第i个数字出现过,那么他对前一个出现过的i维护的区间是没有贡献的,只有vis[i]-i有贡献. 如果没出现过肯定是前面维护的都+1: 有人可以看出是总ans不断减现在数据之前...

2019-08-19

0 516