链接 显然一颗树的独立集可以很容易的转移过来 dp[u][0]=∏(dp[v][0]+dp[v][1]) dp[u][1]=∏(dp[v][0]) 最后答案为dp[1][0]+dp[1][1] 加上子集其实就相当于在转移的时候把当前边断开的贡献加上去就可以了，可以得到 dp[u][0]=∏(dp[v][0]+dp[v][1]+dp[v][0]+dp[v][1]) dp[u][1]=∏(dp[v][0] +dp[v][0]+dp[v][1]) 但发现有一种情况是不合法的：改点为状态1，并且其所有子节点都未选。 所以我还需要容斥一下，把这种状态的答案减下去即可。 #pragma GCC...

链接 最短路:x->gcd(x,y)->y 然后就是一个有重复数字的错排问题， 设每种数字分别出现k1,k2,k3…kp次，并假设该错排的答案为f 那么f*k1!*k2!k3!…*kp!= ( sigma(ki) )! #pragma GCC optimize(2) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define pb push_back #define fi first #define se second #define yes puts(&quot...

链接 考虑S串中第i个字母的贡献，那么我们就可以记录一下前i-1个字母组成的各个区间的个数dp[i] [j] 表示T串的i~j区间匹配 出现的次数， 那么当加入第i个字母时，所有长度为i-1的dp区间答案已经得到，所以我们在T串中直接枚举所有长度为i的区间，即为当前字母的贡献。 转移方程：dp[l][r]+=dp[l+1][r] s[i]==t[l] || l>m dp[l][r]+=dp[l][r-1] s[i]==t[r] || r>m 难点:两个串长度不相等，初始化，dp[][]数组的意义 #pragma GCC optimize(2) #include<...

链接 m<2000 建虚树后暴力 维护虚树中两点间的实际点的个数 模拟即可 巨丑的代码 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define pb push_back #define fi first #define se second #define mkp make_pair #define yes puts("YES") #define no puts("NO") #defin...

链接 想使所有格子全被覆盖，要么所有行都有棋子，要么所有列都有棋子。 假设现在是所有行都有棋子，那么其中k对棋子互相攻击就可以看成n-k列放n个棋子。那么答案就为2*C(n,n-k)*把n个物品放n-k个集合的方案数。 最后一项为第二类斯特林数，记S｛n,k｝为n个物品放k个集合的方案数 公式：S{n,k}=sigma{C(k,i)*(k-i)^n (-1)^i} 0<=i<=k 递推公式：S{n,k}=S{n-1,k-1}+kS{n-1,k} #include<bits/stdc++.h> #define ls rt<<1 #define rs ...

链接 很有意思的规律： 将：b->a+c-b 之后的查分数组：a,c-b,b-a 本来的差分数组:a,b-a,c-b 可以发现，题目的操作就是交换 差分序列的操作，所以问题就转化为怎么交换原数组的差分序列，使其和目标序列的差分序列使相等的。 那么我们只需要需处理出两个序列的差分序列，排下序后判断就可以了 第一个数和最后一个数是不可以改变需要特判一下 #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define fi first #define se second #d...

题面： 给定一个序列，有多次询问，每次查询区间里小于等于某个数的元素的个数即对于询问 (l,r,x)，你需要输出 \sum_{i=l}^{r}[a_i \le x]∑ i=lr [a i ≤x] 的值其中 [exp] 是一个函数，它返回 1 当且仅当 exp 成立，其中 exp 表示某个表达式 题解： 离线后树状数组OR主席树我这里使用的是主席树的方法：：相当于预处理出，每个点的权值线段树。那么每次查询的时候直接查询r时刻前缀小于x的数量减去l-1时刻前缀小于x的数量就可以啦！ 代码: #include<bits/stdc++.h> #define ls rt<&l...

K-th Number 突破口：直接考虑最后的B序列是一个由原序列中的数字多次或0次出现构成的序列，那么将B序列排序之后我们发现，对于每个数字出现的位置都有一个L，R，并且数字越小的其实排名越靠后，由这里我们就可以发现，最后的答案是满足二分性质的，所以我们可以直接二分Mst求出mid在B序列中的R即可.这一部分可以用尺取法，即如果一个数要想对当前mid做出贡献，那么他所在的区间必须有>=k个比mid大的元素，所以将所有>=mid的元素看做一个，然后枚举右端点即可 #pragma GCC optimize(2) #include<bits/stdc++.h> #def...

题面： 从前，有n只萌萌的糖糖，他们分成了两组一起玩游戏。他们会排成一排，第i只糖糖会随机得到一个能力值bi。从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。 为了使游戏更加有趣，糖糖的爸爸，娇姐，会发功m次，第i次发功的时间为ci，则在第ci秒结束后，b1,b2,.....,bci都会增加1. 现在，娇姐想知道在第n秒后，会有多少只糖糖存活下来。 题解： 仔细观察'发功'这一操作可以发现，每次都是加当前位置之前的人的B[i],而我们的操作顺序也是如此，并且每个人只能攻击他前面的人，所以这些'发功'操作是不分先后顺序的，那么我们就可以预处理出来所有...

题意 给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。 题解： 方案1：假设根节点为1，那么树上两点i,j间的距离为 由于后面的差一定是偶数，那么对于任意两点只要满足为偶数即可。(dep为深度)所以所有相同奇偶性深度的点都之间的距离都为偶数,那么我们dfs分别统计一下 计算就可以啦~ 代码： #pragma GCC optimize(2) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #de...

题意： 二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为N的木棍，华华可以精准的将它们裁剪为若干段木棍，使它们的长度之和为N。华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢？ 题解： 首先假设x为最后答案，那么显然我们能够判断x是否成立（贪心将每个圆木棍 分成长...

题意： 给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。N<1e3 题解： 如果直接暴力枚举两个区间的话 复杂度为O(n^4)，显然不行。观察一下数据范围，可以得到本题能够支持O(n^2)的做法，所以我们想怎么枚举一个区间能得到答案。那么假设当前枚举的区间[i,j]两个区间中 右边的那一个，所以我们只需要知道 i 的左边有多少个区间的异或值和当前区间相等即可，我们用cnt数组表示出现次数。这一部分我们可以动态维护：每次新加入一个数i时，他的贡献就为以他为右端点的异或值，那么我们每将i+1的时候就把以他为右端点的所有区间的异或值+1即可复杂度O(...

题意: 求所有长度为n的01串中满足如下条件的二元组个数：设第i位和第j位分别位ai和aj（i<j），则ai=1,aj=0。答案对1e9+7取模。 题解： 只有当两个位置i，j a[i]=1,a[j]=0时会对答案构成1的贡献，所以其中第二项为i,j的方案数，第一项为固定i,j后其他位置的方案数 代码： #pragma GCC optimize(2) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define pb push_back #define fi first #def...

A https://blog.nowcoder.net/n/cee5ca6956154bb6b167e35105eca4d9 B https://blog.nowcoder.net/n/0273fd1d02a4409ba5bc95e36474fc9d C https://blog.nowcoder.net/n/820a03159fd840ffb21139b8ab31bc13 D https://blog.nowcoder.net/n/350fcac151eb40e39da9fe644f5717c5 E https://blog.nowcoder.net/n/ab273e35b0df4974b5...