传送门 题意： 给定n,k,求 ∑nr=1Crnrk  ∑ r = 1 n C n r r k   n<=1e9,k<=5e3  n <= 1 e 9 , k <= 5 e 3  Solution: 冥思苦想数论方式……..最后GG 题解让人眼前一亮： 定义函数 f(x)=(1+x)n=∑nr=0Crnxr  f ( x ) = ( 1 + x ) n = ∑ r = 0 n C n r x r  那么我们对他求一次导: f′(x)=n(1+x)n−1=∑nr=1Crnrxr−1  f ′ ( x ) = n ( 1 + x ) n − 1 = ∑ r = 1 n C ...

传送门 题意： 给出一颗树，初始每条边是蓝色，可以选择一条全是蓝色的路径，删去其中一条边，在这条路径的两个端点连上一条红色边，现给你两棵树，判断第一棵树能不能变成第二棵树 （n<=1e5） Solution： 我们只考虑蓝色边，注意到这是一棵树，所以每次删除一条边后会把图分成两部分，分成两部分后就不会出现不同部分的点之间有全是蓝色的路径这种情况，那么我们就可以把这两部分递归来处理了。 考虑处理到最后，同部分内会剩下两个点，那么这两个点在原来的树和最终的树中都有边 那么方法就明了了：我们倒着来进行这种操作，每次选择有两条边的点对，把它们缩起来，判断能不能缩n-1次即可 具体实现可以用map...

传送门  题意： 给出一些限制形如 xi≠xj  x i ≠ x j 或 xi=xj  x i = x j  判断最早出现矛盾的位置（n<=1e5） Solution： 等于关系满足传递性，可以用并查集来维护 而不等关系呢？ 可以这样做：把相等元素放在一个集合里，每个集合看做一个点，出现不等关系时，我们把这两个不等元素所在的集合直接互相连边，合并两个集合时顺带处理一下与他们相连的边即可。 当给出相等条件时，判断这两个元素所在集合之间是否有边，合并两个点； 给出不等条件时，判断这两个元素是否在一个集合里，对两个元素所在集合互相连边 代码： #include<cstdio> #i...

传送门 题意： 在n*n的坐标内给出一些箭头，给出一些出发点、出发方向以及出发时间，遇到箭头就需要改变方向为箭头的方向，对每个出发点求最后能走到哪 数据范围1e5 Solution： 口胡起来特别简单：对于不同方向的箭头和出发点分别用线段树+扫描线建出相应的图，最后在建出的图上跑倍增就可以了  我们可以把出发点看做没有长度的箭头，就可以和箭头一起搞了，在建图时我们可以添加一个中间点作为一个箭头延长后与另一个箭头的交点，注意虽然题目上说箭头不能重合，交叉，但是如果我们把出发点看成箭头的话会出现箭头包含箭头的情况，这里和走到边界时都需要特殊处理一下  另外，由于倍增时可能会爆longlong，注意...

传送门 题意： 有2∗n的时间去煎一块两面的肉,给你k个可以翻转的区间 [li,ri]  [ l i , r i ] ,可以在区间内翻转任意次, 保证区间不相交  问是否存在合法的方案使得两面恰好都只煎了 n 分钟,并求最小翻转次数  n<=100000,k<=100 Solution： 考虑朴素的dp  f[i][j]  f [ i ] [ j ] 表示前i秒，当前不在烤的面被烤过j秒，所需的最短翻转次数 转移 f[i][j]=f[i−1][j],f[i][j]=f[i−1][i−j]+1  f [ i ] [ j ] = f [ i − 1 ] [ j ] , f [ i ] ...

传送门 题意： 给出一个算式，由括号和小于10的正整数和问号组成，问号是算式中的符号，现给出原式中加号的个数p和减号的个数m，对于所有填放方式对应的结果，求最大值。 算式长度<=1e4 min(p,m)<=100 Solution： 考试时这种题居然没想到转换模型…好菜啊我 我们可以把这个算式化成一个二叉树，叶子节点是一个数，非叶子节点表示一个符号，当一个非叶子结点填加号时，我们就需要最大化左右子树的值，当一个非叶子结点填减号时，我们就需要最大化左子树值，最小化右子树值 那么就可以用树形dp啦 我们可以用 f[i][j][k][0/1]  f [ i ] [ j ] [ k ] [...

传送门 题意： 给出一个序列A，定义函数 f(A)=∑n−1i=1|ai−ai+1|  f ( A ) = ∑ i = 1 n − 1 | a i − a i + 1 |  先给出两种操作： 1.在区间[l,r]内找一个位置，使得把这个位置的值加上x后，f(A)最大，求这个最大值 2.把区间[l,r]加上x 序列长度和询问长度<=1e5 Solution： 对于操作1，我们可以大力分类讨论一下一个位置i与他的左右两边的位置i-1和i+1的关系，我们先考虑简单点：假设 ai+x≥ai+1 ai+x≥ai−1  a i + x ≥ a i + 1   a i + x ≥ a i − 1 ，那...

传送门 题意： 给出一个有n个字符串的匹配串，和m个有k个字符串的文本串，将匹配串进行全排列和文本串进行匹配，找到能全匹配成功的最小的逆序对数 n<=15,m<=10,k<=500000 Solution： 通过哈希+map把字符串变成数字 那么问题就转化成了把一个1到n的序列的全排列和一些序列进行匹配，找到能全匹配成功的最小的逆序对数 一个显然的状压dp状态是能想到的： f[i][j]  f [ i ] [ j ] 表示前i位已经匹配了状态为j的数，最小的逆序对数，转移可以通过预处理达到O(n)，但是这样一次的复杂度是 O(k∗2n∗n)  O ( k ∗ 2 n ∗ n ...

传送门 题意： 有一个长度为n的排列A，你想通过一些询问知道它是什么样的. 每次你构造一个长度为k(0<k≤m)的序列B,满足 1 ≤ B i ≤ n 1≤B_i≤n 1≤Bi​≤n且B中没有相同的元素，系统会根据序列B生成一个长度为k的序列C，Ci的值为 A B i A_{B_i} ABi​​,然后打乱C序列后返回给你,问至少要多少次询问才能知道A究竟是什么  n , m ≤ 1 0 9 n,m≤10^9 n,m≤109数据组数 ≤ 1 0 3 ≤10^3 ≤103 Solution： 神题。 考虑二分，二分一个答案x，求询问x次所能得到的最大的序列长度maxn，然后比较maxn和n的...

简介 普通的莫队算法相信大家都熟悉，那么如果有些问题加上修改操作是否可以用莫队维护呢？下面就介绍一种 O(n53)  O ( n 5 3 ) 的带修莫队算法。 算法详解 只需要再维护一维表示操作的时间即可 然后我们按照左边界所在块为第一关键字、右边界所在块为第二关键字，操作时间为第三关键字排序 在算答案时再维护一个记录修改操作的指针即可 这样排序所产生的复杂度为： 左指针移动次数: O(块的大小∗n)  O ( 块 的 大 小 ∗ n )  右指针移动次数: O(块的大小∗n)  O ( 块 的 大 小 ∗ n )  修改指针移动次数: O(块的个数2∗n)  O ( 块 的 个 数 2 ∗ ...

传送门 题意： 高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。 n,m<=100 Solution： 看到这道题首先想到dp，但是在转移的时候发现需要记录的东西太多，然后便陷入江局。。。 最后发现是网络流，果然网络流是我永远主动想不出来的。。。 说下建图方法： 对于每个人，我们从S向这个人连容量为 ai,j  a i , j 的边...

传送门 题意： 数轴上有 n 个广播站。第 i 个广播站坐标为 xi  x i ，信号半径为 ri  r i ，频率为 fi  f i 。 1.如果称两个广播站i和j（i< j）是可互相到达的，那么 min(ri,rj)>=|xi−xj|  m i n ( r i , r j ) >= | x i − x j |   2.如果称两个广播站i和j（i< j）是”坏的”，那么i和j可互相到达，且 |fi−fj|<=k  | f i − f j | <= k  求”坏的”的数对数量  n<=1e5,k<=10,xi,ri<=1e9,fi<=...

传送门 题意： 如果一个包含i个可重复元素的数组合法，那么这个数组中每个元素的取值范围是[1,n]，这i个元素的和为n，异或和为0。 给出一个数n，对于 i=[1,n]  i = [ 1 , n ] ，求包含i个可重复元素的数组的方案数，对p取模 n<=500,p<=2^30 Solution： 一个简单的想法就是 f[i][j][k]  f [ i ] [ j ] [ k ] 表示前i位，和为j，异或和为k的方案数，然后进行 O(n)  O ( n ) 转移 但是复杂度是 O(n4)  O ( n 4 ) 的，无法满足要求 发现优化不了，那么我们考虑转换状态：原先状态中的k这一维...

题意： 戳这里 Solution： 我们可以把大小写分别看成0和1，这样我们就可以转化一下问题：构造一个最短的布尔函数，使得将m个01串作为变量代入这个布尔函数后，布尔函数的值都为1。这样就变成了一个加权覆盖子集的最小覆盖问题。 因为布尔函数是由一堆“或”连起来的“和”，所以我们的一个浅显的想法就是枚举子集，然后再枚举选那些子集，子集数量是 35=243  3 5 = 243 ，总复杂度 2243  2 243 ，显然我们已经爆炸了，所以说我们需要优化： 假设a，b，c都是布尔函数中的”和”，那么： 1.如果满足a条件的01串是满足b条件的01串的子集，那么除去a 2.如果a=xc,b=Xc，...