题目链接：http://codeforces.com/problemset/problem/579/A   这题目其实是个思维题！！！   首先我们想每个细菌扔到培养基里面数目就会增长一倍，所以如果是2的倍数的话我们就不用管 但是，如果是奇数的话，就说明需要扔一只细菌下去。   神他妈的知道为啥我会想到贪心和dp？？   AC代码：  #include <cstdio> #include <cstring> #include <iostream> #include <cstdbool> using namespace std; int main(...

题目链接：http://codeforces.com/problemset/problem/584/A 题目的大致题意就是： 求一个n位数，这个n位数可以被t整除   这题其实是个非常水的题目，但是我的思想出错了： 我的想法是： 因为是n位数，那么我从10^(n-1) -> 10^(n) 开始遍历，如果出现了一个能被t整除的就break   但是用算法实现的话这个思想很容易爆数据，所以遇到大的数据我的代码就WA了   后来就重新想了一个思路： 首先，看看数据范围： ( 1<=n<=100,2<=t<=10 )(1<=n<=100,2<=t<...

题目链接：http://codeforces.com/problemset/problem/82/A   这道题一开始我拿到的时候，第一反应就是这道题是一道找规律的模拟题 但是我进入了一个误区：那就是我在想：如果是使某一人拿到可乐的n之间存在某种特殊的联系 然后我就进入这个坑里面再也出不来了   后来在网上看了很多题解，但是他们大概的思想我可以理解，但是就是他们的实现过程我可以说我完全看不懂大佬们的思想吗？！   这道题目的思想其实很简单：  队伍的变换： abcde -> aabbccddee -> aaaabbbcccdddeee -> aaaaaaaabbbbbbbbc...

首先先看一道很简单的并查集的题目：https://vjudge.net/contest/297398#problem/A 这道题就是让你判断两两城镇之间是否联通  如果不联通就要修建一条道路   就我的理解来说，如果单独使用并查集就是为了合并有相同根结点(或者理解成有相同的性质)的这样的数据   这里我们引入一个我在网上看到的一个关于并查集的一个很有意思的故事： 并查集由一个整数型的数组和两个函数构成。数组pre[]记录了每个点的前导点是什么  函数find是查找  函数join是合并。 话说江湖上散落着各式各样的大侠，有上千个之多。他们没有什么正当职业，整天背着剑在外面走来走去，碰到和自己不...

数论倒数，又称逆元   先讲求余的概念： (a + b) % p = (a % p + b % p) % p  (对) (a - b) % p = (a % p - b % p) % p  (对) (a * b) % p = (a % p * b % p) % p   (对) (a / b) % p = (a % p / b % p) % p     (错)   为什么除法是错的呢？ 举个例子： (100/50) % 20 = 2   !=   (100%20)/(50%20) % 20 = 0   对一些题目，我们需要在中间进行求余运算，否则数据太大可能会爆！那么是不是这个算式中出现了除法，...

扩展欧几里得extgcd算法    首先， ax+by = gcd(a, b) 这个公式肯定有解 所以 ax+by = gcd(a, b) * k 也肯定有解  所以，这个公式我们写作ax+by = d，(gcd(a, b) | d) gcd(a, b) | d，表示d能整除gcd，这个符号在数学上经常见       设 ax1+ by1= gcd(a,b);        bx2+ (a mod b)y2= gcd(b,a mod b);        根据朴素的欧几里德原理有 gcd(a,b) = gcd(b,a mod b);        则:ax1+ by1= bx2+ (a mod...

gcd(a,b)  就是求a,b的最大公约数   lcm(a,b)  就是求a,b的最小公倍数   这里讲一个公式：        a*b=gcd(a,b)*lcm(a,b) 通过这个公式，我们就可以根据gcd从而求出lcm   至于求gcd的算法  初中就已经介绍过了辗转相除法  LL gcd(LL a,LL b) { LL t; while (b) { t = b; b = a % b; a = t; } return a; }    也可以用递归的写法  LL gcd(LL a,LL b) { if (b==0) return a; else return gcd(b, a%b); } ...

在ACM的比赛中，我们经常会遇到指数型的数据的取模问题。 如果我们直接对数据进行取模，由于题目所给的数据的范围很大，会导致爆int 或者 long long 所以我们要采取快速幂取模   先看一组例子： 2*2*2*2*2*2*2*2*2*2*2 我们可以这样去算 原式=4*4*4*4*4*2 =8*8*4*2 =16*4*2 就是先合并后计算，这样就可以减少计算的步骤   快速幂的基本理论： 积的取余等于取余的积取余 快速幂就是我们先不断的降低a，b的规模，然后再进行计算   a^b 降低a的规模：  只要让 a变成a*a 降低b的规模：  如果b是偶数，那么每次a=a*a之后，b=b/2 ...

素数又叫做质数，即除了1和其本身之外，不存在其他的因数。   最简单的一个判断是不是素数的方法，就是从2开始一直到该数-1  如果中途出现了一个数i 可以被该数整除，那么就说明这个数不是素数   程序也很简单只需要一个for循环就可以实现   bool prime(int x) { if (x <= 1) return false; for (int i=2;i<x;i++) { if (x % i == 0) return false; } return true; }  View Code     这个算法的时间复杂度是O(n)  时间太长了！ 我们可以进一步的优化。 首先，我...

    最小生成树的算法分为 prim和kruscal算法   初始状态：   设置2个数据结构： lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MST mst[i]:表示对应lowcost[i]的起点，即说明边<mst[i],i>是MST的一条边，当mst[i]=0表示起点i加入MST   我们假设V1是起始点，进行初始化（*代表无限大，即无通路）：        lowcost[2]=6，lowcost[3]=1，lowcost[4]=5，lowcost[5]=*，lowcost[6]=* m...