hnust_yangyanjun

题解

大数加法(1) 尺取法(1) 面经(4)

/ 注册

全部文章 / 题解（共119篇）

Removal

题意：求一个n长度的序列删除m个元素后不同序列的个数，结果对1000000007取模思路：dp[i][j]为前i个元素删除j个元素序列的个数dp[i][j]=dp[i-1][j]+dp[i-1][j-1]去重：因为重复只存在于二个相同元素之间的元素全部删除后的在二个元素中删除其中一个dp[i][j...

dp

2020-05-02

0 705

子序列

题意：小美有一个由n个元素组成的序列{a1,a2,a3,...,an}，她想知道其中有多少个子序列{ap1,ap2,...,apm}(1 ≤ m ≤ n, 1 ≤ p1 < p2 ,..., < pm ≤ n)，满足对于所有的i,j(1 ≤ i < j ≤ m), < 成...

2020-04-23

0 557

边的染色

题意：小团有一张n个点，m条边的无向图G，有些边上已经被标记了0或1，表示它的边权。现在你需要给剩下的边标记边权为0或1，求有几种标记的方式满足：对于G中任意一个环，里面所有边的边权的异或值为0。环的定义如下：对于任意k（k≥2）个点{a1,a2,...,ak}，若对于所有的i<...

dfs 并查集

2020-04-23

0 688

K-th Number

题意：有一个n长度的A数组，求大于等于k的长度的连续子区间第K大的数加入B数组，求B数组第m大的数。思路：二分+尺取法代码： #include<bits/stdc++.h> using namespace std; #define ll long long #define inf ...

二分尺取法

2020-04-21

0 517

糖糖别胡说，我真的不是签到题目

题意：n只糖糖分为二组做游戏，排成一排，第i只糖糖有能力值bi，从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。糖糖的爸爸，娇姐，会发功m次，第i次发功的时间为ci，则在第ci秒结束后，b1,b2,.....,bci都会增加1，现在，娇姐想知道在第n秒后，...

2020-04-20

0 507

华华给月月准备礼物

https://ac.nowcoder.com/acm/problem/23049 题意：被给予n根木棍，华华需要k根，华华可以将每根木棍裁剪成若干段自己想要的长度，并丢掉多余的部分，华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。思路：二分寻找长度...

2020-04-16

1 968

逆序对

题意：求所有长度为n的01串中满足如下条件的二元组个数：设第i位和第j位分别位ai和aj（i<j），则ai=1,aj=0。答案对1e9+7取模。思路：从n个位置中选二个位置，左边一个为1，右边一个为0，其余位置随便(2的(n-2)次方)，则每一种情况都有一个二元组，由于一次只计算了选中的二个...

快速幂组合数

2020-04-15

0 612

Treepath

题意:求一棵n个点的树中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。思路：奇+奇=偶，偶+偶=偶所以用跑一遍dfs求出奇数深度结点的数目x和偶数深度结点的数目y再计算偶数路径数=(x(x-1)+y(y-1))/2; #include...

2020-04-14

0 647

Xorto

题意：求一个数组中的有多少组两个互不相交的区间异或和为零。思路：直接暴力，从左到右枚举数组，将以当前元素的前一个元素为右端点，枚举该类区间的异或和，用一个数组仿map容器记录个数，再以当前元素左端点，枚举该类区间的异或和，将map容器中值相同的数的个数加起来就是结果了代码： #include<...

2020-04-13

3 753