吴国庆

题解

acm(50) Codeforces(6) Xcpc(4) 未归档(2) 算法学习(6)

/ 注册

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

简单瞎搞题

简单瞎搞题题目描述一共有 n个数，第 i 个数是 xixi 可以取 [li , ri] 中任意的一个值。，求 S 种类数。0<=li<=ri<=100 思路由于li,ri，n范围只有100 显然可以暴力扫描所有区间中的每个值然后dpdp[i][S] 表示 1~i个数能否...

2020-05-19

0 812

【每日一题】「火」皇家烈焰

题目描述帕秋莉掌握了一种火属性魔法由于钟爱扫雷游戏，帕秋莉把自己图书馆前的走廊看作一个一维的扫雷地图，她制造了很多烈焰，排在这条走廊内现在帕秋莉告诉你一部分烈焰的分布情况，请你告诉她可能的情况有多少种对于一个格子，里面会有以下几种字符：0：这个格子没有烈焰，且其左右两个格子均没有烈焰1：这个格子没...

2020-05-12

0 660

【每日一题】4月30日换个角度思考

题面：给定一个序列，有多次询问，每次查询区间里小于等于某个数的元素的个数即对于询问 (l,r,x)，你需要输出 \sum_{i=l}^{r}[a_i \le x]∑ i=lr [a i ≤x] 的值其中 [exp] 是一个函数，它返回 1 当且仅当 exp 成立，其中 exp 表示某个表达式...

2020-04-29

0 683

K-th Number

K-th Number 突破口：直接考虑最后的B序列是一个由原序列中的数字多次或0次出现构成的序列，那么将B序列排序之后我们发现，对于每个数字出现的位置都有一个L，R，并且数字越小的其实排名越靠后，由这里我们就可以发现，最后的答案是满足二分性质的，所以我们可以直接二分Mst求出mid在B序列中的R...

2020-04-21

0 620

【每日一题】4月21日糖糖别胡说，我真的不是签到题目

题面：从前，有n只萌萌的糖糖，他们分成了两组一起玩游戏。他们会排成一排，第i只糖糖会随机得到一个能力值bi。从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。为了使游戏更加有趣，糖糖的爸爸，娇姐，会发功m次，第i次发功的时间为ci，则在第ci秒结束后，b...

2020-04-20

0 621

Treepath

题意给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。题解：方案1：假设根节点为1，那么树上两点i,j间的距离为由于后面的差一定是偶数，那么对于任意两点只要满足为偶数即可。(dep为深度)所以所有相同...

2020-04-16

0 795

华华给月月准备礼物

题意：二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为N的木棍，华华可以精准的将...

2020-04-16

0 822

Xorto

题意：给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。N<1e3 题解：如果直接暴力枚举两个区间的话复杂度为O(n^4)，显然不行。观察一下数据范围，可以得到本题能够支持O(n^2)的做法，所以我们想怎么枚举一个区间能得到答案。那么假设当前枚举...

2020-04-15

0 569

逆序对

题意: 求所有长度为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后其他位置的方案...

2020-04-15

0 596

牛客算法周周练2 ABCDE

A https://blog.nowcoder.net/n/cee5ca6956154bb6b167e35105eca4d9 B https://blog.nowcoder.net/n/0273fd1d02a4409ba5bc95e36474fc9d C https://blog.nowcoder....

2020-04-15

0 590