吴国庆

分类

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

/ 注册

全部文章（共106篇）

【每日一题】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

水题(water)

题意：其中，f(1)=1;f(2)=1;Z皇后的方案数：即在Z×Z的棋盘上放置Z个皇后，使其互不攻击的方案数。题解：打表后可以发现F函数为斐波那契数列，所以问题就变成如何去求x！在m进制下末尾0的个数和Z皇后的个数由于Z<=14 所以说这一部分直接打表即可考虑如何求x！在m进制下末...

2020-04-15

2 837

小H和游戏

题意：小H正在玩一个战略类游戏，她可以操纵己方的飞机对敌国的N座城市(编号为1~N)进行轰炸敌国的城市形成了一棵树，小H会依次进行Q次轰炸，每次会选择一个城市A进行轰炸，和这座城市距离不超过2的城市都会受损(这里距离的定义是两点最短路径上的边数)，轰炸结束后，小H还想知道当前城市A受损的次数作为游...

2020-04-15

3 744