题目链接：http://codeforces.com/problemset/problem/1072/B   题意：        给出长度为n-1的两个数组a和b，要求找出一个长度为n的数组t，使得t[i]|t[i+1]=a[i] && t[i]&t[i+1]=b[i]，问是否存在这样的数组t   第一行输入一个n ( 2 < = n < = 1e5) 表示t数组的长度   第二行输入n-1个数 a1,a2……an-1 （0 < = ai < =3)   第三行输入n-1个数b1,b2……bn-1 (0 < = bi <...

题目链接：http://codeforces.com/problemset/problem/614/A   题意： 给你一个范围[l,r]，求k的i次方在那个范围的数   思路： 这题的坑点就在于long long 可能会发生溢出，如果溢出的话我们就停止   1 #include <iostream> 2 #include <algorithm> 3 #include <stdlib.h> 4 #include <cstring> 5 #include <string> 6 #include <...

题目链接：http://codeforces.com/problemset/problem/1097/C   题意： 有n个只含有'('和')'的字符串，现在要字符串两两拼接，如果一个拼接后的字符串中的括号都配对了就称为完美匹配，问最多有几个完美匹配。(())就算一个完美匹配，))((或者())就不算。   思路： 我们能想到的是先让每一个字符串自己先匹配，比如(())((就相当于((，然后我们将所有的只含有一种括号的字符串存起来，因为如果是))((这种字符串的话不可能拼成完美匹配的字符串的，所以我们把所有的只含有一种括号的字符串存起来，对于((就只能和))拼接，就算一个完美匹配，...

题目链接：http://codeforces.com/contest/670/problem/D2   题意： 你的蛋糕需要n个原材料，你现在有k个魔法材料，魔法材料可以转化为任何材料 现在告诉你蛋糕每个材料需要多少，以及你现在有多少个 问你最多能够做出多少个蛋糕来   思路： 直接二分就好了，注意加起来会爆int 以及r给到2e9才行   1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1e5+7; 4 long long a[maxn],b[maxn],k...

题目链接：http://codeforces.com/problemset/problem/602/B   题意： 给你一个相邻数差不超过 1 的序列，求最长子串的长度，满足子串中的最大值减最小值也不超过 1。   思路： 区间最大值，区间最小值分别用ST表去维护就可以了，然后之后去二分答案就好了   1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <math.h&...

题目链接：http://codeforces.com/problemset/problem/347/B   题意： 给你一个 0 ~ n-1 的全排列，可以交换两个数的位置一次，问最多能有多少个数与自己所在的位置对应   思路： 注意它给的是0->n-1的全排列，这个非常特别，因为0 的话就应该在0号位置，1就应该在1号位置 所以如果他在正确的位置那么我们就不用管它，如果它不在我们就采取贪心的策略：这个数应该在的那个位置的数应该在的位置是不是就是这个数现在在的位置呢？ 如果发现不存在这种完美的策略，那么最后随便换一个就好了   1 #include <i...

题目链接：http://codeforces.com/problemset/problem/158/C   题意： 模拟对文件路径的操作。   1 #include <iostream> 2 #include <algorithm> 3 #include <stdlib.h> 4 #include <string> 5 #include <string.h> 6 #include <set> 7 #include <queue> 8 #include <stdbool.h&...

题意： 给你一个字符串s，接着有m次循环移位。 循环移位的一个操作就是将s的最后一个字符移动到第一个字符的位置，并且将所有其他的字符向右移动一个位置。 例如，s='abacaba'，查询是L1=3，R1=6，K1=1，那么答案是’abbacaa’（解释：从s第三个位置到第六个位置’acab’，循环1次，把b移到第一位，其他往后移一位，就是’baca’，替换之前的’acab’），之后如果我们再做处理L2=1，R2=4，K2=2，那么答案就变’baabcaa’（解释：首先从第一个位置到第四个位置’abba’，第一次通过移位得到’aabb’，第二次就得到’baab’，替换之前的’ab...

题目链接：http://codeforces.com/problemset/problem/9/C   题意： 输入n，输出1-n的自然数中各数位只包含0和1的数的个数。   思路： 不难知道1，10，11，100 这种是满足要求的。那么如何去求呢？ 直接根据1，去找10，11 再根据10，去找100，101 再根据11，去找110，111   啊！好水的 dfs 为什么我当时就没有想到。。 1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> ...

题目链接：http://codeforces.com/problemset/problem/509/B   题意：有n堆石头，每堆有ai个,有k种颜色要求给所有石头涂上色。要求任意两堆石头中相同颜色的石头的数量之差小于等于1。 1<=n,k,ai<=100   思路： 这题本质上其实就是[贪心] 考虑到求出最小的一堆石子数量，设为mina 然后将每堆的前mina+1个石子（能染多少是多少）染成1（方便起见）颜色。 后面的石子按顺序染颜色2~k即可。 例如[样例3]： 先求出mina=min{3,2,4,3,5}=2 然后...

本博客转自：https://www.cnblogs.com/linyujun/p/5194170.html 欧拉函数，用φ(n)表示 欧拉函数是求小于等于n的数中与n互质的数的数目     可以先在1到n-1中找到与n不互质的数，然后把他们减掉   比如φ(12) 把12质因数分解，12=2*2*3，其实就是得到了2和3两个质因数 然后把2的倍数和3的倍数都删掉 2的倍数：2,4,6,8,10,12 3的倍数：3,6,9,12   本来想直接用12 - 12/2 - 12/3 但是6和12重复减了 所以还要把即是2的倍数又是3的倍数的数加回来  所以这样写12 ...

题目链接：http://codeforces.com/problemset/problem/1106/D   题意：给定一张n个点，m条双向边的图，从1号点出发，沿双向边行走（可以重复经过一个点）。当经过一个之前未经过的点时，记录下其编号。这些编号组成一个长度为n的序列。求字典序最小的序列。   思路： 用字典序最小的方法走过图上的所有点，其实就是遍历整张图。因为要满足字典序最小，我们很容易想到Dj算法里面我们用优先队列去维护，使每次都走字典序列最小的。注意本题可以重复走，所以这个算法肯定是正确的   1 #include <iostream> 2 #inc...

Nauuo is a girl who loves playing chess. One day she invented a game by herself which needs 𝑛n chess pieces to play on a 𝑚×𝑚m×m chessboard. The rows and columns are numbered from 11 to 𝑚m. We denote a cell on the intersection of the 𝑟r-th row and 𝑐c-th column as (𝑟,𝑐)(r,c). The game's go...

如果要对比较大的整数分解，显然之前所学的筛选法和是试除法都将不再适用。所以我们需要学习速度更快的Pollard_Rho算法 pollard_rho 算法流程 Pollard_rho算法的大致流程是 先判断当前数是否是素数（Miller_rabin）了，如果是则直接返回。如果不是素数的话，试图找到当前数的一个因子（可以不是质因子）。然后递归对该因子和约去这个因子的另一个因子进行分解。   那么自然的疑问就是，怎么找到当前数n的一个因子？当然不是一个一个慢慢试验，而是一种神奇的想法。其实这个找因子的过程我理解的不是非常透彻，感觉还是有一点儿试的意味，但不是盲目的枚举，而是一种随机化算法。我...