redoCxz

ACM练习题

ACM练习赛(18) BZOJ刷题(5) C++算法模板(20) codeforce(4) hdu(8) java(16) Java算法模板(24) kotlin(1) Leetcode(12) Lintcode(26) 剑指offer(1) 拓展欧几里德(1) 最小生成树(1) 未归档(70) 杂七杂八(41) 水题(1) 牛客网(2) 牛客网错题总结(1) 算法四(2) 题解(1)

/ 注册

全部文章 / ACM练习题（共250篇）

hiho1860——最大异或和

给一个数组，求出区间最大异或和 01字典树的典型应用，不过这个不是求和某个数x异或的最大值，而是要求出区间，区间的问题我们可以转成前缀和，比如查询与pre[2]异或最大的值，然后用这个求出的异或pre[2]就是3-k这一段的异或和了，然后为了保持查询的索引一定是再右边，所以一边扫查询一边插入新的（再...

2021-04-05

0 567

hdu6395——Sequence

递推式要用矩阵快速幂加速，但是构造出来的矩阵里面有一个不确定的遍历 p/i 所以没办法从第一项直接用矩阵快速幂推到最后一项不过可以看出p/i是可以分块的，就是从1递推到n中间的这些矩阵里，可以分成几个块这样子来递推，每一个块里面的构造矩阵就是一样了，直接用矩阵快速幂注意p/(p/i)这个就可以...

2021-04-05

0 508

Codeforces987B——High School: Become Human

判断x^y 和 y^x的大小关系很简单的题，取个log就行，比较坑的地方是取完log是一个浮点数，会出现精度误差，这样判断大小还行，判断相等就出问题了，虽然在本地a-b<0.0000001能过，提交上去就不行了，所以直接在输入两个数的时候判断就行了代码： #include <bi...

2021-04-05

0 364

Codeforces987D——Fair

Some company is going to hold a fair in Byteland. There are n towns in Byteland and m two-way roads between towns. Of course, you can reach any town f...

2021-04-05

0 483

Codeforces987E——Petr and Permutations

Petr likes to come up with problems about randomly generated data. This time problem is about random permutation. He decided to generate a random perm...

2021-04-05

0 451

牛可乐发红包脱单ACM赛C——区区区间间间

求出每个子区间的最大值减最小值的和可以化成求出每个子区间的最大值的和减去每个子区间最小值的和又可以看成求每个数作为最大值能左右延伸多远，就直接用这个数乘以这个区间能组成多少个子区间（分区间是否跨过这个数来计数）然后这个问题就可以用单调栈来解决了 #include <bits/stdc+...

2021-04-05

0 448

牛客练习赛30——小K的疑惑

读题看懂样例就花了好久… 给一棵树，树上任意两个点的距离表示为距离%2，那这样任意两个点之间距离要不就是0要不就是1了，这样就能把树上的点分成两个集合，相同集合内点相距0，不同集合点相距1，然后推出公式就是 n + 6 ∗ ( C k 2 + C n − k 2 + C k 3 + C n − k ...

2021-04-05

0 433

poj3250——Bad Hair Day

给出几个牛的高度，牛只能向右看到比他挨的，求出所有牛一共可以看到的数量学了单调栈，这题就是很模板的题目了，求出每个数作为最大值能向右延伸到最远的位置代码： #include <cstdio> #include <stack> #include <algorith...

2021-04-05

0 534

牛客练习赛30D——消消乐

比赛的时候不会做… 然后今天才得知是一道原题，一道二分图最小覆盖点的模板题… 为什么大佬什么算法都会，什么题都做过… 代码： #include <bits/stdc++.h> using namespace std; const int N=100050; const int M=1...

2021-04-05

0 460

hdu1867——A + B for you again

居然要用到kmp… 瞎搞了半天…不对是四个月，今天无意中翻到这题还是不会做，抄了下题解首先这个kmp的匹配就稍微变形了一点，用kmp(a,b)然后不是输出匹配的位置，也不是输出匹配的数量，而是输入当i==sl的时候，也就是原串匹配完了，这时候pat匹配到那个位置，输入j，这样把a和b分别作为模式串...

2021-04-05

0 563