E - Rotation Matching(思维） 题目传送门 思路：由于最多只有轮，根据题意可知，每进行一轮就相当整个序列向左移动一格，如果是第一格就移动到最后一格。 要使轮每个人都不会打重复的对手，显然每一个场地两个人的数字差肯定要不一样。 因此我们构造m对数字差分别为的数字对即可。这样轮过后才会重复。 所以我们可以将分为两部分，第一部分：+1, 然后配对 差值分别为 第二部分同理：,然后配对 差值分别为 综上此题就得到解决。 AC代码：（写法1） #include<cstdio> using namespace std; int main(){ int...

D. Phoenix and Science(贪心&排序） 题目传送门 算法：贪心时间复杂度：思路：题目可以转化为构造一个数组： 使最小。根据贪心思想：将依次放入数组直到不能再放，若此时刚好满足，否则将此时的放入数组再排序即可。最后答案序列即为： AC代码： #include<cstdio> #include<iostream> #include<string> #include<algorithm> #include<vector> using namespace std; int main(){ int t; ...

C. Phoenix and Distribution(贪心&字符串) 题目传送门 算法：贪心 题意：将长度为的字符串分成个子序列(每个字母只使用一次)，将字典序最大的子序列最小化。 思路：显然可以对字符串进行排序后再分配，根据贪心思想，每个子序列尽可能占用少的字典序小的字母。 于是有 ： ​ ​ 对于情况，若,显然是平均分配最好，否则将其全部分配给是最优的。 此种情况显然是最好的。 此种情况显然是最优的。 AC代码： #include<cstdio> #include<iostream> #include<string> #incl...

简单搜索题解+个人思考+记录 A - 棋盘问题 在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。 Input 输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不...

L - Floating-Point Numbers 题目大意:题目向我们解释了浮点数在计算机中的储存方式,分为三部分，第一部分表示符号正负(0为正，1为负),第二部分为尾数M，第三部分为阶码E，在计算机中用二进制表示M和E的时候如果位数不同，那么它们所能表示的最大值也不同。题目要求我们将输入的十进制的指数形式的数转化为二进制表示，求出尾数M和阶码E。 借鉴了别人的思想，写了下。 代码如下。 #include<bits/stdc++.h> using namespace std; int i, j; double a[10][31],m[10],e[31]; voi...

01背包题目+代码详解+一些易错点 01背包最原始题目 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。 输入格式 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。 输出格式 输出一个整数，表示最大价值。 数据范围 0<N,V≤1000 0<vi,wi≤1000 时间复杂度o(nm...

约瑟夫环的三种解法 约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。 N个人从1开始编号，问最后活下来的人的编号是多少。 方法1：数组模拟。 #include<bits/stdc++.h> using namespace std; int main(){ printf("--------约瑟夫环问题----------\n"); printf("请输入总共人数和报数死亡的编号数:"); int n,m; cin>>n>>m; ...

素数判断的两个方法 法1：最为普通的方法从1遍历到sqrt(n)，上核心代码 bool ss(int n){ for(int i=2;i<=sqrt(n);i++) if(n%i==0) return 0; return 1; } 法2：优化方法： 一个数是素数(n>3)的必要条件是 N一定可以写成6k+1或6k-1 N=2或3时特判一下,由必要条件可知: 如果N不在6的倍数旁边, 一定不是素数. 然后从5=6-1开始遍历, 6k-1 6k 6k+1 6k+2 6k+3 6k+4 6k-1 6(k+1) 6(k+1)+1 从上面数组可...

介绍两种筛法 第一种：埃拉托斯特尼(Eratosthenes)筛法 简称：普通筛或埃氏筛 时间复杂度：O(nloglogn) 下面上普通筛法的两种写法及优化 写法1： #include<bits/stdc++.h> using namespace std; const int N=1e5; int a[N]; void ss(int n){ memset(a,-1,sizeof(a));//a[i]=-1 先假定所有数都为素数,i是素数a[i]=-1,不是素数a[i]=0 a[0]=a[1]=0; for(int i=2;i<=n;i++) ...

常见的几个博弈 第一种：巴什博弈 游戏玩法: 有一堆物品共n个,两人轮流取物，一次最少取一个最多取m个。取走最后一个的胜。 思路：当n<=m时 显然先手胜。 n=m+1时 无论先手怎么取 后手都能取完,所以此时的状态为平衡态。谁面临这个状态必输。 已知n%(m+1)!=0时 先手显然可以取走n%(m+1)的余数让对手变为平衡态。 至此，规律已经出来了： N%(m+1)==0 后手胜,否则先手胜。 试题传送门： HDU-Brave_Game 第二种：威佐夫博弈 两堆物品,两人轮流取,一次可从一堆取至少 1个至多全部，或从两堆取相同数，取最后一...

常见的背包问题总结与优化代码(DP) 1.01背包 优化时需要注意：第二层循环是倒序,原因这里不作说明,读者自行查找. 下面上核心代码。 for(int i=1;i<=n;i++)///n物品数,m背包容量 for(int j=m;j>=w[i];j--)//w[i]物品i的重量,v[i]物品i的价值 f[j]=max(f[j],f[j-w[i]]+v[i]); 2.完全背包(每种物品次数无限的01背包） 优化时与01背包唯一不同的一点的是：第二层循环是顺序,原因这里不作说明,读者自行查找. 下面上核心代码。 for(int i=1;i...

费马小定理与逆元 由费马小定理可知,（a/b)%c可以变换 1.如果c为质数,且b不是c的倍数 (注意这里不是b,c互质,因为c必须为质数，若b=5,c=6,b与c互质，但是结论不成立， 比如：a=100,b=5,c=6 (100/5)%6=2,但（100*5^4)%6=4,显然不对) 由逆元知识可知(a/b)%c=(ak)%c k为b模c的逆元 即 bk≡1mod(c ) 又 b^(c-1)=1mod(c ),所以k=b^(c-2) 综上 (a/b)%c=(a*b^(c-2))%c。 2.一个恒成立的式子： (a/b)%c=a%(b*c)/b;

图论之最短路的几个算法 1.Floyd 时间复杂度：O(v^3) v:vertex(顶点数( 空间复杂度：O(v^2) 思想：DP 用g[ i ] [ j ] 表示从 顶点 i 到 顶点 j 的最小权值和。 状态转移方程：g[ i ] [ j ] = m i n( g[ i ] [ j ] , g[ i ] [ k] + g[ k] [ j ] ) 直白意思就是：顶点 i 到 顶点 j 经过顶点 k 和 不经过 顶点 k 取最小值。 初始化：所有点之间距离 为 I N F 具体细节见下面模板代码： for(int k=1;k<=n;k++)//k循环必须放在最...

二叉树系列题目 1.利用二叉树性质解题. UVA 679 - Dropping Balls 有一棵二叉树，最大深度为D，且所有叶子的深度都相同。所有结点从上到下从左到右 编号为1, 2, 3,…, 2D-1。在结点1处放一个小球，它会往下落。每个内结点上都有一个开关， 初始全部关闭，当每次有小球落到一个开关上时，状态都会改变。当小球到达一个内结点 时，如果该结点上的开关关闭，则往左走，否则往右走，直到走到叶子结点，如图6-2所示。 一些小球从结点1处依次开始下落，最后一个小球将会落到哪里呢？输入叶子深度D和 小球个数I，输出第I个小球最后所在的叶子编号。假设I不超过整棵树的叶子个...