题意  n*m的棋盘，卒在(0,0)，可以向右或者向下走，最终要走到(n,m)，同时，棋盘上还有一匹马，它会控制他能走到的8个点，以及它自己所在的位置,卒不能走这几个位置 请问最终有多少条路径能让卒走到(n,m)  思路  实现方法一：提前把不能走的点标一个极小值，转移方程为 实现方法二：走到每一个位置都检查是不是被马覆盖，如果是就清零  代码 //思路一 #include<bits/stdc++.h> using namespace std; long long dp[30][30]; int main(){ int n,m,x,y; cin >> n >&gt...

题意  一个竖直放置的三角形模板，钉着n(n+1)/2颗钉子，最底下有(n+1)个格子 从最顶上落下一个小球，小球碰到钉子落向两边的概率相等 求去除m个钉子后，落到最底下第m+1格的概率是多少，以a/b的形式输出  思路  概率不好处理，不妨认为小球每下落一层就分裂成两个，在有钉子的地方，一个去左边，一个去右边 因此，没有钉子的时候会下落两层，由(i,j)到(i+2,j+1) 综上写出状态转移方程       代码 #include<bits/stdc++.h> #define int long long using namespace std; int a[100][100]; ...

题意  多组数据 每组数据给出一个图中点的个数n，链接任意一条边需要的代价是这个边所连的两个联通块的大小的差值，使这n个点联通所需的最小代价是多少  思路  贪心的思考，想让价值最小，每一步合并的两个块得大小接近 最终都会合成一个联通图，逆序思考   深搜即可  代码 #include<bits/stdc++.h> using namespace std; /** * 1 0 * 2 0 * 3 1 * 4 0 * 5 2 * 6 2 * 7 2 * 8 0 100 * 9 2 101 * 10 4 110 * 11 4 * 12 4 */ long long dfs(long l...

题意  花店有f朵花，v个盆，每个花放每个盆有不同的美观度，求如何摆放能使美观度最大 特别的，给花编上号，花必须按照顺序摆放，编号小的的花不能放在编号大的花的后面  思路  由于必须按照顺序摆放，所以新的一盆花可放的盆一定是上一盆花放的盆的后面   初始化:对于最开始，每朵花放在自己编号的盆里，其它位置都放极小值即可 对于输出路径，使用记录到(i,j)这个点是谁转移来的，然后dfs回溯即可  代码 #include<bits/stdc++.h> using namespace std; /** * 所有的花束在放入花瓶时必须保持其标识数的顺序，即： * 杜鹃花必须放在秋海棠左边的花...

题意  在一个W*H的长方形平面内，有若干块饼下坠，每块饼会有{下坠时间，下坠位置，下坠速度，价值}四个信息 人最初站在中间，可以移动(-2,-1,0,1,2)，请输出最多获得的价值以及开始后每一秒的操作  思路  这题有很多坑点 显然是一个动态规划，状态转移方程 坑点1:由于起点强制锁定在中间，但从中间开始发散着dp不好描述，又从第一秒开始往后接饼和从最后一秒往前接饼效果是一样的，所以不妨从最后一秒开始倒推dp过程，即规划的过程从i=maxt到i=0 坑点2:计算时间的时候，虽然高度是H但是只用下落(H-1)的高度，所以下落时间是 坑点3:题干中描述，只有在每一秒末落下的饼才会被接到，也就是...

同值路径必须先往左再往右按照：-2,-1,0,1,2的顺序，不然会卡60%

题意  每天可以从三家店中选一家，不能连续三天选同一家，t次询问，每次询问连续选n天有多少种不同的选择方案  思路  简单动态规划，显然第i天的可选择方案数取决于第i-1和第i-2天 对于任意一个店，第i天可以选它的情况是  第i-1天选另外两家，不用考虑第i-2天  第i-1天选它，第i-2天只能选另外两家    综上,  AC代码 #include<bits/stdc++.h> using namespace std; const int mod = 1e9+7; vector<long long> dp(101010); int main(){ ios::sync...

题意  走楼梯，斐波那契换了个描述  思路  水题，  代码 #include<bits/stdc++.h> using namespace std; /** * dp[i]=dp[i-1]+dp[i-2] */ vector<long long> dp(100); int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); dp[1]=1,dp[2]=2; for(int i=3;i<=80;i++) dp[i]=dp[i-1]+dp[i-2]; int t; cin >> t; ...

题意  给定若干组数组，每组数组给出长度n和询问k 输出第k大的数  思路  水题，直接硬模拟+排序即可 注意输入量很大，需要使用快读  inline int read(){ int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if (ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ x = (x<<1) + (x<<3) + (ch^48); ch = getc...

题意  n个人参加考试录取m个人，分数线划在m*150%的地方 输出有多少人录取，录取分数线，录取的人  思路  水题，直接硬模拟+排序即可 注意如果从0开始存储m乘完要减一名  代码 #include<bits/stdc++.h> using namespace std; #define pii pair<int,int> int cmp(pii a,pii b){ if(a.second==b.second) return a.first<b.first; else return a.second>b.second; } int main(){ int ...

A 时间比较 题意  两个时间比大小  思路  签到，硬做  代码 #include<bits/stdc++.h> using namespace std; int main(){ int a,b,c,d; cin >> a >> b >> c >> d; if(a<c) cout << "No\n"; else if(a>c) cout << "Yes\n"; else{ if(b>d) cout << "Yes\n"; else cout << "No\n"; } ...

题意  一颗有n个结点的树，每个结点具有权值，求解最长（权值最大）的一条子链  思路  对于某一个结点来思考，他能构成的最长子链无非下列集中情况之一  包含他的最长链+最长的包含他一个儿子的最长链 所有结点均为负值，最长子链自身的权值 他自己的一条最长链（另一条全负）   因此我们维护一个dp数组，dp[i]表示包含结点i的最长子链，u是i的儿子，最终的为了避免dp[i]和dp[u]包含同一条子链，我们选择先更新res后更新dp[i]，由因为存在全负的可能性，所以每次遍历一颗子树时，ans的初值应该取到dp[i]  代码 #include<bits/stdc++.h> #defin...

比赛链接 A 简单游戏(语法) 题意  给定三个数，和一个序号，问序号位置的数是不是最大的  思路  遍历整个数组，找不到比他大的就Y，找不到就N  代码 #include<bits/stdc++.h> using namespace std; int main(){ int a[5]={0},idx; for(int i=1;i<=3;i++){ cin >> a[i]; } cin >> idx; for(int i=1;i<3;i++){ if(a[i]>a[idx]){ cout << "No" << end...

题意  对于一个有n个结点的二叉树，根的编号一定为1，每条边有权值 求保留q条边时，最多能获得多少权值 tip:分析样例可以知道，这棵树的根是必须保留的，“剪枝行为”一定是保留根含有根的子树  思路（法一）  由于输入是无规律的输入每一条边，所以应当先建立起二叉树，从根开始深搜建树 由于边权是较难处理的，我们发现可以把所有边权变为该条边所连的儿子的权值，把边权转换为点权，同时边转化为点，会多一个点，所以最终保留q条边会变为保留q+1个点 建完这棵树后，可以进行动态规划，对每个结点考虑剩下多少个边，进行枚举   表示i包含j个点(边) 树形dp，dfs深搜即可，每次深搜记录当前结点和剩余结点数，...