斐波那契数列III Description 求数列f[n]=f[n-1]+f[n-2]+1的第N项.f[1]=1,f[2]=1. Input n(1＜n＜２^31-1) Output 第Ｎ项的结果 mod 9973 Sample Input 12345 Sample Output 8932 解题思路    代码 #include<cstdio> using namespace std; long long n,k; struct node {  long long n,m; long long oo[5][5]; }a,b,c; node operator*(node x,node...

奇怪汉诺塔 题目描述 汉诺塔问题，条件如下： 这里有 A、B、C 和 D 四座塔。 这里有 个圆盘， 的数量是恒定的。 每个圆盘的尺寸都不相同。 所有的圆盘在开始时都堆叠在塔 A 上，且圆盘尺寸从塔顶到塔底逐渐增大。 我们需要将所有的圆盘都从塔 A 转移到塔 D 上。 每次可以移动一个圆盘，当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时，可将圆盘移至这座塔上。 请你求出将所有圆盘从塔 A 移动到塔 D，所需的最小移动次数是多少。 输入格式 没有输入。 输出格式 对于每一个整数1≤n≤12 ，输出一个满足条件的最小移动次数，每个结果占一行 解题思路 首先考虑3座塔的汉诺塔问题，我们设a（n）表示n个...

数的划分 题目描述 将整数 分成 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。 例如：，下面三种分法被认为是相同的： 1,1,5; 1,5,1; 1,1,5. 问有多少种不同的分法。 输入格式 两个整数， 和 。 输出格式 输出不同的分法数。 样例 输入样例 7 3 输出样例 4 样例说明 四种分法为：1,1,5; 1,2,4; 1,3,3; 2,2,3. 数据范围与提示 对于 100% 的数据6≤n≤200，2≤k≤6。 解题思路 设f(i,j)为i分成j份的方案数 初值： 当j=1以及i=j时f(i,j)=1 递推： 两种情况  1.j份中至少一个是1，方案数为f(i-1,j-1...

传球游戏  解题思路 我们可以设f(i,j)为传i秒后，球在j号的方法数 因为0秒时球在1号，所以初值为f(0,1)=1 因为球只能从左右传来，所以递推式为  f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] + f [ i − 1 ] [ j + 1 ] f[i][j]=f[i-1][j-1]+f[i-1][j+1] f[i][j]=f[i−1][j−1]+f[i−1][j+1] 但又因为他们围成一个圆，所以1和n的传球方式特殊点 AC代码 #include<cstdio> using namespace std; int n,m,f[35][35]; ...

平铺方案 题目描述  解题思路 设f(i)表示2*i矩阵的方案数  第i列上竖着放一个2 * 1的，方案数为f(i-1) 第i列与第i-1列放一个2 * 2的，方案数为f(i-2) 第i列与第i-1列横着放一个1 * 2的，方案数为f(i-2)  故递推式为  f [ i ] = f [ i − 2 ] ∗ 2 + f [ i − 1 ] f[i]=f[i-2]*2+f[i-1] f[i]=f[i−2]∗2+f[i−1] 初值：f[0]=f[1]=1 f[2]=3 因为本题n最大为250，会炸long long 所以要用高精度 AC代码 #include<cstdio> using...

划分数列   解题思路 设  f i f_i fi​ 表示从一到 i 最少可以划分的段数 则有转移方程  f i = m i n ( f b i − 1 , f c i − 1 ) + 1 f_i=min(f_{b_i}−1,f_{c_i}−1)+1 fi​=min(fbi​​−1,fci​​−1)+1  b i b_i bi​ 表示以 i 结尾单调递增的一段的起点  c i c_i ci​ 表示以 i 结尾单调递减的一段的起点 AC代码 #include<cstdio> #include<cstring> #include<algorithm> using...

奶牛晒衣服  解题思路 贪心思想 先将所有数进入到优先队列（就是队首最大的队列） 然后让队首使用烘***（烘***可以和自然晾干一起工作） 最后再让它入队 直到干了 AC代码 #include<cstdio> #include<queue> using namespace std; int n,a,b,h,time,head; priority_queue<int>f;//优先队列 int main() {  scanf("%d%d%d",&n,&a,&b); for(int i=1;i<=n;i++) { ...

雷达装置  解题思路 对于每一个建筑物（x，y） 我们都可以在x轴上计算出能够侦查到该物的雷达建造区间[l,r] 由勾股定理得： l=x- d 2 − y 2 2 \sqrt[2]{d^2-y^2} 2d2−y2 ​ r=x+ d 2 − y 2 2 \sqrt[2]{d^2-y^2} 2d2−y2 ​ 当d2-y2<0，就是d<y时 这个建筑物就不可能会被雷达侦查到 我们可以将所有建筑物都转化成雷达建造区间 这样问题就变成 给定n个区间 求最少几个点可以覆盖到所有区间  贪心策略： 1.按右端点排增序 2.如果当前区间包含最后一个选择的点，就直接跳过 否则就在该区间的右端点放一个...

畜栏预定 解题思路 先排序 再贪心 如果当前有空的栏 就将这个空的栏变成不空的栏 否则就新开一个栏 AC代码 #include<cstdio> #include<algorithm> using namespace std; int n,o,mmax,q[1000005],num[1000005]; struct node {  int l,r; }a[1000005]; bool cmp(node x,node y)//结构体排序 {  if(x.l==y.l)return x.r<y.r; return x.l<y.l; } int main() {  ...

国王游戏  解题思路 先将所有大臣按 a i ∗ b i a_i * b_i ai​∗bi​ 从小到大排序 再贪心求答案 AC代码 #include<cstdio> #include<algorithm> using namespace std; int n,tot,tot2,b[100005],answer[100005]; struct node {  int l,r; }a[1005]; bool cmp(node x,node y) {  return x.l*x.r<y.l*y.r; } void gjd(int o) {  int c[100005]=...

数列分段  解题思路 设最优解为mid，如果每段和都小于mid 则一定存在一种最优解 段数不超过m 否则就提高mid AC代码 #include<cstdio> #include<algorithm>  using namespace std; int n,m,l,r,a[100005]; bool check(int x)//判断 {  int sum=0,num=1;//sum为当前段的和，num为分了多少段 for(int i=1;i<=n;i++) if(sum+a[i]>x) {  num++; sum=a[i]; if(a[i]>x)ret...

防具布置  解题思路 设S（i）为0~i的位置上一共的防具数 对每组防具分类讨论 若S（231-1）为偶 则无破绽 否则二分答案 AC代码 #include<cstdio> #include<algorithm> using namespace std; int T,n,s[200005],e[200005],d[200005]; int S(int x)//S（i） {  int answer=0; for(int i=1;i<=n;i++) if(s[i]<=x)answer+=(min(x,e[i])-s[i])/d[i]+1; return answ...

最大均值  解题思路 二分答案 可以将序列中的每个数减去二分的值 题目就变为 是否存在一个长度不小于L,平均值不小于mid的子段 AC代码 #include<cstdio> #include<algorithm> using namespace std; int n,L; double l=-1000000,r=1000000,a[100005],b[100005],sum[100005]; bool check(double x)//判断 {  for(int i=1;i<=n;i++)b[i]=a[i]-x,sum[i]=sum[i-1]+b[i]; doub...

拔河比赛  解题思路 深搜 设x为考虑到第x个成员 设sum为已经选择了sum个人 设ans为体重和 AC代码 #include<algorithm> #include<cstdio> #include<cmath>  using namespace std; int n,s,answer,w[25]; void dfs(int x,int sum,int ans)//dfs {  if(sum==n/2) {  answer=min(answer,abs(ans*2-s)); return; } if(x>n)return; dfs(x+1,sum+...