链接： @[toc] 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 输入描述: 第一行两个整数n,m 第二行n个整数表示序列a的元素，序列下标从1开始标号，保证1 ≤ ai ≤ 10^5^之后有m行，每行三个整数(l,r,k)，保证1 ≤ l ≤ r ≤ n，且1 ≤ k ≤ 10^5^ 输出描述: 对于每一个询问，输出一个整数表示答案后回车 示例1输入 5 1 1 2 3 4 5 1 5 3 输出 3 备注:数据范围1 ≤ n ≤ 10^5^1 ≤ m ≤ 10^5^ 题...

链接： 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 524288K，其他语言1048576K 64bit IO Format: %lld 题目描述 输入描述: The input consists of several test cases and is terminated by end-of-file. Each test case contains two integers n and m. 输出描述: For each test case, print an integer which denotes the result. 示例1输入 3 1000000000 1...

比赛链接@[toc] 求导 链接： 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 输入描述:给出一个数 n输出描述:输出求 x^n^求 n - 1 次导后 x 前的系数。(答案对 10^9^+7 取余)示例1输入复制 5 输出复制 120 备注:对于50% 的数据满足n≤15 对于%100% 的数据满足 n≤10 ^5^ 题解： 第一次求导，系数为n第二次求导，系数为n（n-1）。。。第n-1次求导，系数为n（n-1）......*2不就是阶乘吗？直接暴力走起 #include&l...

二分用到的挺多，三分用的少，但也不能忘。。。二分我们常常用于一个具有单调性的情况中求解某值而三分就像是求一个凸性或凹形函数时，来求那个凹凸点一开始L=0，R=inf，然后也是不断缩小L与R的范围，逼近最值点 这里面有两个中间点mid1与mid2mid1=(L+R)>>1mid2=(mid1+R)>>1然后判断mid1与mid2的大小关系，从而缩小不同范围当while（L<R）不再满足条件时，答案也就呼之欲出 详细过程： check()为三分的判断函数1.check(mid1)>check(mid2),我们可以得知最值点位于mid2的左侧，我们通过R=mid2...

@[TOC]昨天做蓝桥杯的题，最后一题最小生成树，但好久没用一下子生疏了。。。又过了几天离散学到了最小生成树。。。趁此复习一波 最小生成树两种方法：Prim和Kruskal 关于时间复杂度： prim:该算法的时间复杂度为O(n2)。与图中边数无关，该算法适合于稠密图。 kruskal:需要对图的边进行访问，所以克鲁斯卡尔算法的时间复杂度只和边又关系，可以证明其时间复杂度为O（eloge）。适合稀疏图。 Kruskal讲解 利用并查集来求连通块：无向图中相互连通 的一些点 具体步骤：将一个连通块当做一个集合，然后按照边的大小（从小到大）进行排序，一开始认为每个点都是孤立的，自身是一个集合。然后...

ST表主要用于解决RMQ问题（区间最值问题）当然你可以用线段树等，但今天用一种ST表（倍增算法） ST表是倍增算法的一个典型应用暴力做RMQ问题，往往会超时，ST表利用对其进行优化 给定一段序列A，ST算法能在O(NlogN)的时间预处理后，以O(1) 的复杂度查询，在线回答在一段区间l,r 中最大（小）值是多少。 f[i][j]用于表示在序列a中， 从第i位数字往后数2^j^个数，这个区间内的最大值，即区间[ i , i + 2 ^j^ ]内取得的最大值。 而这段区域的最大值等于左右子区间的最大值,2^j^ = 2 * 2 ^j-1^ = 2^j-1^ + 2^j-1^,把区间[i,i+2...

@[TOC]欧拉序与DFS序相似又不同 欧拉序的定义树在dfs过程中的节点访问顺序称为欧拉序.那有人会问：dfs序和欧拉序啥区别？ dfs序：是指将一棵树被dfs时所经过的节点顺序（不绕回原点）。欧拉序：就是从根结点出发，按dfs的顺序在绕回原点所经过所有点的顺序。 欧拉序与dfs序不同地方在于，欧拉序中每个节点可以出现多次，比如进入一次退出一次，又比如每次回溯时记录一次。 代码： s[maxn]存放“入时间戳”，e[maxn]存放“出时间戳”； DFS序 核心代码 const int maxn = 1e5+5; vector<int> g[maxn]; //存放节点 int s[...

转载 @[TOC] 算法一：乘法逆元，在m,n和mod比较小的情况下适用 乘法逆元：（a/b）% mod = a * b^(mod-2)，mod为素数 #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<queue> #include<stack> #include<vector> #define LL long long using namespace std; const int MOD = 998...

链接：https://ac.nowcoder.com/acm/contest/5505/B来源：牛客网 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 输入描述:第一行一个整数 N，表示数组 A 和 B 的长度。第二行 N 个整数表示数组 A。第三行 N 个整数表示数组 B。输出描述:输出一行 N 个整数，表示加密后的数组 C。示例1输入复制 10 65605 70259 77306 43823 61443 98602 9261 7662 46394 83019 81393 5966 ...

比赛链接@[TOC] A [SDOI2016]齿轮 B Rinne Loves Xor 再看遍其他题解后，逐渐明白一点点。。两个方法（其实本质都差不多） 题解 C 阶乘 两个方法题解 D 小石的签到题 题解 E 装备合成 两个方法题解

链接： 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 输入描述: 共一行，输入一个数 n 。输出描述:共一行，输出 "Shi" 或 "Yang"（不输出引号）。示例1输入 1 输出 Yang 说明小石只能取走 11，小阳赢。示例2输入 2 输出 Shi 说明若小石取走 1，则小阳只能取走 2，小石赢。 题解： 我一开感觉是博弈论，模拟了几轮发现只要n不等于1，其他小石必赢。。。我也不知道该怎么证 代码： #include<bits/stdc++.h> typedef l...

链接： 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 输入描述: 输入包含t组数据第一行一个整数t接下来t行每行两个整数x,y输出描述:每组数据输出一行一个整数表示答案。示例1输入复制 5 4 8 7 6 8 10 100 4555 45465 24124 输出复制 2 2 3 50 13917 备注:1<=t<=100001<=x,y<=1e9 题解： 两个做法一个三分，一个贪心 三分的做法 ：我们都知道 二分查找 适用于单调函数中逼近求解某点的值。如果遇...

链接： 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 给定一个正整数 p 求一个最小的正整数 n，使得 n! 是 p 的倍数 输入描述: 第一行输入一个正整数T表示测试数据组数 接下来T行，每行一个正整数p 输出描述: 输出T行，对于每组测试数据输出满足条件的最小的n 示例1输入 4 1 2 4 8 输出 1 2 4 4 备注:T≤10^3^,p≤10^9^题解：两个方法：二分与贪心 在什么条件下n!会是p的倍数呢？n!的素因子集合包含p的素因子集合，也就是对于每个质因...