题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6442 定义序列{a}=(a0,a1,a2,… )\{a\}=(a_0,a_1,a_2,\dots){a}=(a0​,a1​,a2​,…) 它的指数型生成函数为g{a}(x)=∑i=0∞aii!xig_{\{a\}}(x)=\sum_{i=0}^{\infty}\frac{a_i}{i!}x^ig{a}

有一类经典的问题，之前见过很多次了，好像某一场区域赛的热身赛里就出过：一维数轴上有nnn个炸弹，xi,rix_i,r_ixi​,ri​分别表示第iii个炸弹的位置和引爆半径，即如果引爆炸弹iii，那么位置在[xi−ri,xi+ri][x_i-r_i,x_i+r_i][xi​−ri​,xi​+ri​]范围内的炸弹都会爆炸，并且引发连锁反应。然后比如询问最少引爆几个炸弹才能全部炸完。 首先一个建图思路

题目链接：https://vijos.org/p/category/2014 D1T1 生活大爆炸版 石头剪刀布 没想到noip还会出纯模拟 1234567891011121314151617181920212223#include<bits/stdc++.h>using namespace std;#define N 205#define rep(i,l,r) for(int i=l

最近突然想回顾一下历年noip题目，就开个新坑吧，题解就从略了 题目链接 https://vijos.org/p/category/2013 D1T1 转圈游戏 公式就(x+m10k)%n(x+m10^k)\%n(x+m10k)%n，现在一眼的事情当时想了很久orz 12345678910111213141516171819202122#include<bits/stdc++.h>us

问题引入 题目要求解决的模型： 给定有向图G（可能有环）和图中的一个点r，对于G中的任意一个点x，求从r到x的路径上（可能有很多条）必须经过的点集。 Flow Graph：若有向图G中存在一点r，从r出发可到达G中所有的点，则称G是Flow Graph，记为(G,r)。 必经点（dom）：若在(G,r)中从r到y的路径一定经过点x，则称x是从r到达y的必经点，记为x dom y。 从r出发到达y

来自Petrozavodsk Winter-2018. AtCoder Contest里的D题 题意是说，有QQQ次操作，分为两种，一是添加一个重量为www，价值为vvv的物品，保证插入的www单增，二是删除当前重量最小的物品。每次操作完之后，都有一个询问，询问能否从已有物品中选出一个子集，使得重量之和在模MMM之后在区间[l,r][l,r][l,r]内，并且价值和最大。 数据范围，Q≤10000

关于Stern-Brocot tree网上的资料较少（后记：实际上并不少，只是竞赛中讨论的不多），能够找到的资源有Wikipedia以及《具体数学》上的介绍，这里大概总结一下这个树形结构的性质。 Stern-Brocot tree: Stern-Brocot tree构成了一个无限的二叉排序树，可以将所有的正有理数从小到大列举出来。 构造方法可以理解为：先在左边写上01\frac{0}{1}10

适用条件：动态开点的(权值)线段树。 关于时间复杂度的结论： 每次合并的代价是两棵树的公共节点数。 若有n棵含有单个元素的树，经过n-1次merge操作，将他们合并成一棵树的代价是O(nlogn)O(nlogn)O(nlogn)或O(nlogC)O(nlogC)O(nlogC)的 单次merge操作开销可大可小，均摊下一次就是一个log的。 关于空间复杂度，普通版本是O(nlogn)O(nlo

最近想起来这么一道题，当时q神没rush出来，赛后几分钟AC掉的 题目链接：https://nanti.jisuanke.com/t/17114 题意是树上有NNN个点，每个点的点权是一个01矩阵，有QQQ次询问，每次问树上从x到y这条路径上的矩阵依次乘起来的结果是多少(模2意义下)。数据范围N≤3000,Q≤30000N\le 3000,Q\le 30000N≤3000,Q≤30000，矩阵大小

最近做了几道高维偏序的简单题。 对于这类题目一般有三种通用方法，一是cdq分治，维数越多嵌套次数就越多，总体来说思路就是对时间分治，每次统计出左半区间的贡献点对右半区间的询问点的贡献，这样对于每个询问点来说，它前面的所有对它造成影响的点就都会被算到。二是用bitset优化暴力，应该只能处理计数问题，但优点是好写，适合做高维偏序。三是KDtree，emmmm，这个没怎么写过，多校训练十分艰难的写过一