newbits
newbits
全部文章
分类
algorithm(2)
题解(5)
归档
标签
去牛客网
登录
/
注册
newbits的博客
keep writing and keep running~
全部文章
(共6篇)
双指针 题解 | #最长无重复子数组#
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param arr int整型vector the array * @return int...
2023-06-27
0
126
[NOIP2014]寻找道路
初探 本质是最短路,奈何加了最短路的点的出边必须直接或间接到达终点。 想法 先开始没有注意到条件,写了堆优化dij就交了。看到条件后想着反向建边加拓扑,发现很烦。并查集也寄了。 分解条件 出边直接或者间接到达终点,就是说出边的点只要和终点连通即可。 因此我先求一遍时候连通,然后再dfs求出边均连通。...
最短路
2022-12-15
0
369
组合数进阶-Counting Swaps
对于一个排列p,交换多少次变成1,2,3单调递增的排列。 啥事排列,就是n个数,这n个数由1到n的自然数组成。 将 p[i] 与 i 连接可以形成若干个圈。 。 对于每个圈交换次数为圈长度n减一。(不会证) 后面的思路要用到证明,请参考进阶指南。 将一个圈中的任意两个点交换会形成两个圈,只把一个圈的...
组合数
2022-08-23
1
141
求组合数-预处理阶乘,模数为质数
(ax+by)k(ax+by)^k(ax+by)k的每一项咱们提取出来的 xnymx^ny^mxnym 的系数应该是(kn)anbm\binom{k}{n}a^nb^m(nk)anbm 组合数用阶乘预处理可得,复杂度为 O(k)O(k)O(k)。 指数用费马小定理快速幂求逆元,复杂度为 O(log...
组合数
2022-08-23
0
176
题解 | #牛牛的xor#
将数字中含1的地方尽量大,从29开始因为1<<29是1e9的最高位。 #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector&l...
2022-06-13
1
232
[NOIP2011]统计单词数
分析 首先分别将两个字符串输入 std::getline(std::cin, p); std::getline(std::cin, s); 分别小写化,使用tolower函数将字符串的每一个字符变成小写。 遍历字符串s int len_s = s.length(); for (int i = 0;...
2022-01-14
0
456