和今年寒假训练营有一题差不多。 那么对于第i道题，如果要想做对，只需要满足 a[i],b[i],c[i]之中其中一个就可以，直接计算做对的概率比较麻烦，我们可以进行求反，即做不对这道题的概率 很容易得到为 ,即三次都没解决。那么正确的概率自然就是1-上面的式子。 容易得到转移方程如下dp[i][j]=dp[i-1][j-1] * yes + dp[i-1][j] * no其中yes为答案第i道题的概率，no为答错的概率。也就是前i道题答对j道，要么第i题答错了，那么前i-1道题就需要对j道。要么第i题答对了，那么需要前i-1道对j-1道。注意初始化dp[0][0]=1 #include<...

思路：    然后dp即可 #include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define inf 0x3f3f3f3f #define ll long long #define pb push_back #define PII pair<int,int> #define X first #define Y second #define MP make_pair #define PI acos(-1.0) #define eps 1e-8 const int maxn=1e6+10; con...

思路：k个数，奇数放1，偶数放2，那么最小的和就是3 * k如果n < k 肯定是输出No否则 把k个奇数 都放1即可，那么剩余数字就是 n - k，因为偶数+偶数=偶数 ，所以只要判断n - k的奇偶性即可 #include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ int t;cin>>t; while(t--){ ll n,k;cin>>n>>k; if(n<k*3 || (n-k)&1) cout<<"No"&...

思路：如果在区间[l,r]之间有一个位置p，a[p]是唯一的，那么容易知道，左端点取[l,p-1],右端点取[p+1,r]都满足要求 即都是好序列，那么只需要考虑两个区间是不是分别满足子区间都是好序列都可以。所以处理出来离每个数字左右两端最近的位置，dfs即可。 #include<bits/stdc++.h> using namespace std; typedef long long ll; map<int,int> mp; int a[1<<18],l[1<<18],r[1<<18]; bool dfs(int ll,int rr...

日常无聊摸鱼就写一下题解吧 题意：给一个长度为n的正整数序列和一个正整数s，现在要求一个子区间，使得子区间的和不小于s，求该区间长度最短是多少。 思路一：暴力O(n^2)枚举起点和终点，然后O(n)计算区间和。三个for是相互关联的，满足乘法原理，所以总复杂度O(n^3) 思路二：前缀和优化提前预处理出来前缀和，这样我们可以O(1)计算任何一个子区间的和。复杂度由思路一的O(n^3)降低为O(n^2) 思路三：尺取(我更喜欢叫双指针 当然不是c语言的那个指针)双指针说是一种算法，倒不如可以理解为是一种处理技巧。因为所有数都是正整数，越加肯定是越大的。那么我们固定左指针l不动，移动右指针r，直到...

题目描述帕秋莉掌握了一种土属性魔法  这种魔法可以在一片k×k大小的一个正方形区域内产生地震 但是如果某片即将产生地震的区域内有建筑物，帕秋莉会停止施法 整个地图大小为n×m，其中一些地方有建筑 请问有多少种可能的情况，使得帕秋莉会停止施法 输入描述:第一行三个数n, m, k，意义见描述接下来一个n×m的01矩阵表示这篇区域的情况，1表示这个地方有建筑输出描述:输出一个数表示答案 思路：很简单的题，二维前缀和+枚举即可。 暴力方法就是，枚举每一点为k * k正方形的左上角的顶点，那么只需要计算以该点为边长为k正方形内是不是存在1，存在1那么答案ans++。这样暴力的复杂度是O((n-k+1)...

思路：判断一下这个鱼缸在斜坡上的长度是不是≤斜坡的长度。超过的话，就是鱼缸体积的一半。否则的话，就是整个鱼缸体积减去空的那一部分。 #include<bits/stdc++.h> using namespace std; int main(){ int h,l,H,L;cin>>h>>l>>H>>L; double qq=1.0*L/(1.0*H)*h; if(qq<=l) printf("%.8f\n",0.5*h*qq); else printf("%.8f\n",h*l-0.5*H*l/(1.0*L)*l); return...

题目描述牛牛有一个数组长度大小为n，数组中有n个正整数。现在牛牛请你从其中选出三个元素（注意选择元素的下标不能相同，但是其值可以相同）组成一个三角形。 无法做到，请输出一行一个字符串"No solution"，反之请输出这三个元素的值。 如果有多种组成三角形的元素组合，你可以输出任意一种 思路：n范围很小，排序下，n^3判断即可。 #include<bits/stdc++.h> using namespace std; int main(){ int n;cin>>n; vector<int> a(n); int flag=0; for(auto &...

题目描述牛牛有一块长度大小为n的菜园，他首先对这块菜园从1到n进行了编号，每一块地分别为1号、2号...n号菜地，然后他往每块菜地中都种下了一些水稻，一开始，第i块菜地中的水稻高度均为a[i]个单位。然后我们知道水稻的生长周期都是n天，也就是说每逢n天水稻就会长高一个单位。但是不巧的是整个菜园中每一块菜地的生长周期都错开了，具体来说，第1天的时候第1块菜地中的水稻长高一个单位，第2天的时候第2块菜地中的水稻长高一个单位....第n天的时候第n块菜地中的水稻长高一个单位，接下来第n+1天，又轮到第1块菜地中的水稻长高一个单位以此类推。 每天在水稻进行自然生长之后，牛牛可以施展他神奇的魔法，这个魔...

题目描述   一个数轴，每一个储物点会有一些东西，同时它们之间存在距离。每次给个区间[l,r],查询把这个区间内所有储物点的东西运到另外一个储物点的代价是多少？比如储物点i有x个东西，要运到储物点j，代价为x * dist( i , j )dist就是储物点间的距离。  输入描述:第一行两个数表示n,m 第二行n-1个数，第i个数表示第i个储物点与第i+1个储物点的距离ai 第三行n个数，表示每个储物点的东西个数bi 之后m行每行三个数x l r 表示查询要把区间[l,r]储物点的物品全部运到储物点x的花费每次查询独立输出描述:对于每个询问输出一个数表示答案答案对1000000007取模 思路...

题意：给了一个n * m的矩阵，让从起点走到终点的最小花费是多少。有一些地点可以进行传送，不过需要花费的时间为3，其他的正常上下左右走花费的时间是1。 思路：挺简单的题。就是找到起点的位置，对于当前队列头的点，去走四个方向是不是满足要求。然后再看当前点是不是有传送门，看传送的地点是不是满足即可。因为要求花费时间最优，边权不都是1，所以用优先队列去bfs即可第一次到达终点的花费就是最小花费。对于标记有一个细节就是如果新的点是通过上下左右直接走到的，肯定可以标记掉，因为是附近的。但如果是传送门过去的就不要标记，因为传送门过去的不一定最优。比如从(x,y) 传送到(x,y+2) 传送门要花费3，如果...

思路：n的范围很小。所以考虑记忆化搜索dp[l][r]表示这棵树中序遍历中，第l个节点到第r个节点为一棵子树的得分最大值。那么只需要枚举l到r中每一个点作为根节点即可。容易得到方程如下dp[l][r]=max(dp[l][r],dp[l][i-1]*dp[i+1][r]+a[i])其中l≤i≤r因为最后输出不仅仅是要最大得分，还需要输出这棵树的前序遍历。我们现在已经知道中序遍历为1，2，3，4，5.....n要想知道前序遍历只需要知道每个区间的根节点是什么。然后根据根节点去左右dfs即可。所以再开一个根节点数组root[l][r]表示区间l到r选择的根节点是什么。在记忆化搜索的时候，注意dfs...

A根据更相减损术可得，gcd(x,y)=gcd(x,x-y)=gcd(x+y,x)而题意中从集合选取的数字正好满足这个意思。所以刚开始两个人取得数字就是x，y算出来的gcd(x,y)，就是等差数列的公差，那么算出来等差数列的项数，判断奇偶即可。 #include<bits/stdc++.h> using namespace std; int main(){ int t;cin>>t; while(t--){ int n,a,b;cin>>n>>a>>b; int gcd=__gcd(a,b); int num=n/gcd; if(nu...

题意：给了n个数，让球gcd{ lcm{a[i],a[j]} } (i<j) 就是n个数，两两配对求出他们的lcm，对于所有lcm在求出gcd 思路：考虑一下gcd和lcm在算术基本定理下的含义。        那么容易知道        那么对于两两组合求lcm，我们容易知道取的质因数是最大的那个，然后整体求gcd质因数取的是最小的。   那么考虑一下。如果对于n个数而言，有n-1个数都含有质因数x，那么最后的所求答案的gcd一定有质因数x，为什么？   因为只存在一个数字没有质因子x，那么因为lcm是取最大的，所以别的数都有，配对时候可以把他拉上来，也就是求出来的lcm是有的。   ...