在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。 思路：石子距离超过S×T之后的任...

题目：帕秋莉掌握了一种火属性魔法由于钟爱扫雷游戏，帕秋莉把自己图书馆前的走廊看作一个一维的扫雷地图，她制造了很多烈焰，排在这条走廊内现在帕秋莉告诉你一部分烈焰的分布情况，请你告诉她可能的情况有多少种对于一个格子，里面会有以下几种字符：0：这个格子没有烈焰，且其左右两个格子均没有烈焰1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰2：这个格子没有烈焰，且其左右两个格子中均有烈焰*：这个格子有烈焰？：未告诉你本格情况 思路：动态规划，状态受前一个、当前、后一个影响，故用三维数组f[i][0/1][0/1]，i表示前i个，第二维表示当前位置是否有烈焰，第三维表示后一位是否有烈焰。 代码： #in...

题意：贝西喜欢下载游戏在手机上玩，尽管她觉得用她的大蹄子来操作小触摸屏有点麻烦。她对目前正在玩的游戏特别感兴趣。游戏从N个正整数(2≤N≤248)开始，每个正整数的范围为1…40。贝西一次移动可以把两个相邻的相同的数字合成大一的数字(例如,她可能会取代两个相邻7变成8)。求出最大的数字。 知识点：DP 代码： #include<bits/stdc++.h> using namespace std; int n,f[60][1000],ans; int main() { cin>>n; for(int i=1; i<=n; i++) { ...

题意：给Alice一个数组A[1..N]和N个数字。现在Alice想用参数K构建一个数组B，规则如下：最初，数组B是空的。考虑数组A中的每个间隔。如果此间隔的长度小于K，则忽略此间隔。否则，在此间隔中找到第K个最大的数字，并将该数字添加到数组B中。事实上，Alice并不关心数组B中的每个元素。她只想知道数组B中的第M个最大元素。请帮助她查找这个数字。 知识点：二分，尺取。 代码： #include <bits/stdc++.h> using namespace std; #define ll long long ll num[100005]; ll n,k,p; bool pd(l...

题意：从前，有n只萌萌的糖糖，他们分成了两组一起玩游戏。他们会排成一排，第i只糖糖会随机得到一个能力值bi。从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。为了使游戏更加有趣，糖糖的爸爸，娇姐，会发功m次，第i次发功的时间为ci，则在第ci秒结束后，b1,b2,.....,bci都会增加1.现在，娇姐想知道在第n秒后，会有多少只糖糖存活下来。思路：差分，模拟。代码： #include<bits/stdc++.h> using namespace std; #define ll long long int zu[5000005]; int...

题意：将n个木条切割，至少得到k个相同木条的最大长度是多少思路：二分求解代码： #include<bits/stdc++.h> using namespace std; #define ll long long ll num[200005]; int n,k; bool pd(ll x) { int cnt=0; for(int i=0;i<n;i++) cnt+=num[i]/x; return cnt>=k; } int main() { cin >> n >> k; ll l=1,r...

考虑选取两个位置，前一个位置放1，后一个位置放0，则得到一个逆序对。则逆序对有 个。 代码： #include<bits/stdc++.h> using namespace std; #define ll long long const ll mod=1e9+7; ll ksm(ll k,ll c) { ll ans=1; while(k) { if(k&1) ans=(ans*c)%mod; c=(c*c)%mod; k>>=1; } return...

题目描述给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。 思路：从一点开始dfs求出每个点的深度，分出奇点个数a、偶点个数b，根据奇数深度+奇数深度=偶数深度、偶数深度+偶数深度=偶数深度可以得出答案ans=a(a-1)/2+b(b-1)代码： #include<bits/stdc++.h> using namespace std; #define ll long long struct pp{ int to,next; }r[200005]; int head[100005]; i...