传送门 给你一个数，求约数和等于的数。 好像也没什么好说的，主要就两个式子： 1、整数的唯一分解定理 2、一个数的所有约数和 然后发现枚举选了哪些质数，以及这些质数的指数，等于得到了，判断是否符合条件即可。暴力枚举肯定会，那就搜索，因为搜索可以在条件满足时再进入下一层，效率肯定大于枚举。 搜索需要三个参数，，，，分别表示：还剩多少能够分解，当前枚举第个质数，当前是哪个数。 我们知道，搜索满足条件时，就可以得到答案。那么，什么叫满足条件？有两种： 1、若当前数可表示成一个并未搜索过的质数与的和设这个质数为，其实就是 ，则与的乘积可以成为答案。 2、，即当前的数不能再分解。则当前的数可以成为答案。...

传送门      N   O   I   P    NOIP   NOIP题做的好心累。。 最后一列维护一个平衡树，每行维护一个动态开点的权值线段树。 我们给所有操作过的点一个权值，再用     m   a    ma   ma数组，表示值映射的编号，这样是为了在平衡树内有序。 考虑一行内经过一系列操作会变成什么样，首先本来是有序的，之后我们删除了一些点，再从行末尾插入了一些点，那么这一行的前半段还是有序的，后半段是无序的。 所以我们用权值线段树维护每一行删除了哪些节点，然后对于一个     (   x   ,   y   )    (x,y)   (x,y)的查询，如果这一行剩下的数的个数 ...

传送门 先算出所需亵渎个数     k    k   k，观察就可以发现     k   =   m   +   1    k=m+1   k=m+1，有一个小细节，如果从     n    n   n开始有一段连续的空位，应该把它去掉，因为不会需要多余的亵渎。 我们计算每一次亵渎的贡献，第一次亵渎我们认为是在     0    0   0位置。显然第一次的贡献是      ∑    i   =   1    n     i   k     \sum\limits_{i=1}^{n}i^k   i=1∑n​ik      −    -   − 空位的贡献。 之后我们考虑在一个空位上使用亵渎，设...

传送门 考虑     B    B   B的范围比较小，那就      B   2     B^2   B2暴力枚举所有的座次区间。枚举到一个座次从     l    l   l到     r    r   r的区间，意义是奶牛只能选它心目中座次从     l    l   l到     r    r   r区间的牛棚。 然后就是判断区间是否可行，考虑网络流，源点向奶牛连边，奶牛向可选牛棚连边，牛棚向汇点连它容量的边。     D   i   n   i   c    Dinic   Dinic判断最大流是否是     n    n   n。 不用当前弧优化好像会     T    T   T...

传送门 或许你们更愿意看短一点的代码。 每个密码单词长度小于等于     20    20   20，那么我们在     d   p    dp   dp时直接暴力判断能不能匹配。      a   n   s   [   i   ]    ans[i]   ans[i]表示长度为     i    i   i时候的答案，为     "   "    ""   ""时表示不存在。对于原密码的每一位，枚举所有单词，钦定这个单词的结尾为这一位，然后找到开头，看一下中间一段能不能匹配。如果能匹配，看一下答案是...

传送门 对于这种中位数的题目，按照套路，把大于等于     x    x   x的置为     1    1   1，小于     x    x   x的置为     −   1    -1   −1，然后先计算一波前缀和。 然后，问题就转化成要找满足     s   u   m   [   r   ]   −   s   u   m   [   l   −   1   ]   >   =   0    sum[r]-sum[l-1]>=0   sum[r]−sum[l−1]>=0的     (   l   ,   r   )    (l,r)   (l,r)...

传送门 先成绩从大到小排序，然后考虑枚举哪一同学的成绩为中位数。      f   [   i   ]    f[i]   f[i]表示第     i    i   i个同学的成绩作为中位数时，左边     n   /   2    n/2   n/2个最小值的和      g   [   i   ]    g[i]   g[i]表示…同理，为右边     n   /   2    n/2   n/2个最小值的和      f   [   i   ]   ,   g   [   i   ]    f[i],g[i]   f[i],g[i]满足     n   /   2   +   1   &...

传送门 这里补充一下三分的做法。 首先      n   2     n^2   n2枚举对角线，然后我们要算的是在对角线左边最大的三角形和对角线右边最大的三角形。 显然如果我们任选一侧，从对角线的一个顶点到另一个顶点依次计算，三角形的面积肯定是先增大后减小的，所以考虑三分。 显然我们三分凸包上点的下标，然而我们会遇到一个问题：比如我们的顶点标号是     0   −   6    0-6   0−6，当前我们枚举到对角线     1   −   4    1-4   1−4，然后我们在对角线左边三分的话，我们发现这些点的下标变成了     5   ,   6   ,   0    5,6,0...

传送门 调了一下午才调出来。主要是这道题的数据太能构造了，导致每次改完都只能多过几个点。 对于这种问平面被图形分割成几个部分的题，如果你对欧拉公式熟悉的话，发现直接套用就好：      V   −   E   +   R   =   2    V-E+R=2   V−E+R=2 其中，     V    V   V是交点个数，     E    E   E是边数，     R    R   R是被分割的平面数 。 由于这道题几个分割的圆可以不连通，改一下公式即可：      V   −   E   +   R   =   C   +   1    V-E+R=C+1   V−E+R=C+1 其...

传送门 题面的定义显然就是求一个点集     A   ,   B    A,B   A,B的闵可夫斯基和的凸包的面积的两倍。 那么这道题就是闵可夫斯基和的模板了。 所谓闵可夫斯基和，即给你两个点集     A   ,   B    A,B   A,B，求一个点集     C   =   {   x   +   y  <mtext>   </mtext>  ∣  <mtext>   </mtext>  x   ∈   A   ,   y   ∈   B   }    C=\{x+y \ | \ x \in A, y \in B\}   C={x+y...

传送门 题目大意： 给你一堆城市，每个城市由一堆点构成，城市的围墙是包含这个城市所有点的最小多边形，城市之间两两不相交。然后有给出一堆导弹的坐标，若一个导弹打在某个城市内部即可摧毁这个城市，问导弹摧毁的城市的总面积。 整道题显然就是考了对计算几何模板的掌握，显然先求出每个城市的凸包，然后判断导弹是否在凸包内。 对于判断一个点是否在凸包内，可以     O   (   l   o   g  <mtext>   </mtext>  n   )    O(log \ n)   O(log n)求     (   n    (n   (n是凸包上点的个数     )    ) ...

传送门 没有题解，来补一篇。 观察到题目中     B   e   s   s   i   e    Bessie   Bessie和杀手都在动，所以考虑相对运动，以     B   e   s   s   i   e    Bessie   Bessie的位置作为原点，     B   e   s   s   i   e    Bessie   Bessie不动，只考虑杀手运动。让     B   e   s   s   i   e    Bessie   Bessie不动，直接杀手的位置和速度减去     B   e   s   s   i   e    Bessie   Bessie的即...

传送门 好像这道题并没有其他两篇题解说的那么简单吧？？？或者是我太菜了 考虑以请求为点进行建图，对每个请求进行拆点，拆点后两个点之间连价值为     c    c   c，流量为     1    1   1的边，代表着一个请求只能执行一次。 然后我们考虑时间限制： 对于一个请求，如果     0    0   0时刻可以从     0    0   0机场飞到该请求的起点机场，那么源点向该请求连价值为(     −    -   −飞行费用)，流量为     I   N   F    INF   INF的边，同理，若一个请求的结束时间，加上它的结束机场飞回     0    0   0的时间...

传送门 每辆出租车只能接1人，显然是二分图匹配。 二分图左部为车，右部为人，车根据距离向能接到的人连边。 跑匈牙利即可。 #include<bits/stdc++.h> #define ts cout<<"ok"<<endl #define ll long long #define hh puts("") #define time TTTT using namespace std; int n,m,s,lim,head[1005],vis[305],match[505]; int cnt,time,ans; struc...