A.Clam and Fish 题意：一个游戏有n个阶段。每个阶段是四种状态中的一种.  0： 没有鱼、没有蛤蜊 1： 没有鱼、有一个蛤蜊 2： 有一条鱼、没有蛤蜊 3: 有一条鱼、有一个蛤蜊游戏规则：一个蛤蜊可以做成鱼饵存储起来，在0状态下如果有鱼饵，那么可以钓到一条鱼。有蛤蜊并且也有鱼，可以直接用蛤蜊钓到鱼。  问在n个阶段后，能钓到最大的鱼条数是多少。 分析：有一个贪心策略，在没有鱼只有蛤蜊（1状态）的时候进行制作鱼饵，在有一条鱼和一个蛤蜊的时候（3状态）直接钓鱼，在没有鱼没有蛤蜊的时候（0状态）如果当前有鱼饵那么直接钓鱼。这个策略下有可能会剩下a个鱼饵，那么我们只需要将减少a/2个制作...

B. Boundary 题意：给定n个点的点坐标，求所有过(0,0)的圆中，圆上能覆盖最多给定点的圆。输出覆盖点的最大个数。  分析： n=1,那么答案就是1. n>1,因为三个点能确定一个圆，n^2枚举两个点与原点连成三角形，求三角形的外心，然后存储坐标。这样我们可以枚举c出所有覆盖点>=2的圆。(求三角形外心直接百度板子 由于这道题卡常数，不能用map计数，我们可以sort一遍，然后遍历计算圆心的出现次数。求得最大值 . 假如一个圆覆盖了 个点，那么对于 个点两两组合，重复计数圆心次数有 次。所以最后计算答案还要再转换一下。 #include<bits/stdc++.h&...

类似题目：https://ac.nowcoder.com/acm/problem/50493 石子位置成一个环(就是多存一遍石子，跑2*n大致题意： 个石子，每个石子有一定的价值，每次可以合并相邻个石子，合并的代价是两个石子的价值和，合并完后两个石子的价值累加一成石子的价值，问将 个石子合并成一个石子的最小代价是多少。分析:   考虑子问题,对于区间 的石子合并成一个石子，更小的子问题就是区间已经分成了两个石子然后合并成一个石子，那么代价其实就是区间所有石子价值和(用前缀和 维护)。假如我们已经得到了 , 的最优合并解，那么对于 的最优解应该是: . 表示当前子问题合并的代价。 那么如何抉择循...

题目大意：给定 种花 个花瓶，每种花插在花瓶上都有一个美观值 ,对于第 种花，满足第 种花插在的花瓶位置一定是在第 种花插在花瓶位置之前.每个花瓶只能插一种花。问将 朵花插入花瓶最大的美观值之和是多少.并且输出插入花瓶的位置方案。(如果有方案美观值相同，按字典序最小输出) 分析：动态规划.   表示第 种花插入第 个花瓶、前 种花插入前 个花瓶的最大美观值。 转移方程： . 可以用前缀和维护。 最优解方案可以用 表示当前 前 种花插入前 个花瓶中可以获得最大的美观值，第 种花插入的花瓶位置。因为是字典序最小所以转移时 就是最大美观值，获得方案，需要倒序遍历找到最优位置，然后倒置输出。  #in...

类似题目：https://ac.nowcoder.com/acm/problem/14701 取数游戏题意： 的矩阵，每次从每行中取一个数，每行取数的得分 = 被取走的元素值 * ，其中 表示第 次取数（从1开始编号）。并且每次取走的各个元素只能是该元素所在行的行首或行尾。一共取 次，问每行取数的最大得分和是多少。  分析：每行取数互不影响，所以我们依次计算每行的最大取数方案累加起来即可。   和 的范围不大，我们可以定义 表示该行左边取数取到 位置，右边取数取到 位置的最大得分。进行dfs记忆化搜索答案。 注意数据范围爆long long,用__int128才能过.  #include&lt...

题意：给定花费上限 ,你有 件物品，有m 件装饰品，每件物品和每件装饰品都有两个值攻击力 和花费 。一个物品最多被一个装饰品所装饰，每个装饰品不能独立存在，问在不超过花费上限的前提下，攻击力最大能到达多少.购买限制：物品最多只能买五个.并且同一种商品不能重复购买. 分析：每种商品只能选购一次，那么就是01背包问题，状态的值就是当前ATK的最大值.  根据数据范围开状态，我们可以让花费作为状态的第一维，题目限制买的物品数量不超过5个，购买物品的数量作为状态的第二维，并且装饰品与物品数量相关，购买装饰品的数量作为第三维。 因为购买装饰品与购买物品唯一相关联的是数量，那么我们可以分两次背包，第一次背...

1.POJ1379  HDU 1109题面相同题意：给定0——X,0——Y的矩形，给定n个点的坐标，在矩形中求得一个点是的该点到所有点的最短距离最大。(保留小数 )分析：模拟退火(随机化)算法，可求解精度要求较小的几何寻点问题.随机选取多个(20个)初始点，进行多次随机坐标变换，并且根据降温概率进行选择是否转移次优解。随机坐标变换：随机半径，随机角度进行改变坐标. #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<ctime>...

%参考fyj大佬题解：https://blog.nowcoder.net/n/9eb663297d054e8898236cf06bed7f17分析：骚区间定义：区间左端点为区间的第二小值,区间右端点为区间的第二大值.给定序列是一个1-n的排列,所以无重复元素.求所有骚区间个数.容易想到枚举一个端点，求另外一个端点的有效个数，然后依次累加.原序列定义为 .  对于当前下标为 的元素作为区间左端点 , 是下标大于 并且值小于 的下标最小的元素， 是下标大于 并且值小于 的下标最小元素。那么有效右端点一定是在 中.表示为：   对于当前下标为 的元素作为区间右端点 , 是下标小于 并且值大于 的下标...

#Robot Sends Red Packets > https://ac.nowcoder.com/acm/contest/8829/E n个硬币分成若干堆，每堆硬币的价值相同，求最堆最小价值的分配方案。 思路：三层dfs剪枝. #include<bits stdc++.h> using namespace std; typedef long long ll; ll dp[100][2]; int sum=0; int b[100],a[100]; int m; int n; vector<int> gg; bool f; int cnt=0; bool vis...

1.求01矩阵中最大子正方形的面积.(n<=1e3)  https://leetcode-cn.com/problems/maximal-square/  分析：考虑动态规划。 表示以 为当前最大正方形的右下角时的正方形的最大边长。那么转移方程：  #include<bits/stdc++.h> using namespace std; const int maxn=3e3+10; int dp[maxn][maxn],a[maxn][maxn]; int main() { int n,m,ans=0; cin>>n>>m; for( int i=1;...

1.条件类型最短路  https://ac.nowcoder.com/acm/contest/370/B  题意：n个点，m无向边，n个点有一部分是特殊的点，求从1走到n最短路是多少。并且该最短路满足走过的特殊点不超过K.分析: 将所有点的状态分离成K个点(K分层图)，表示到当前该点的走过的特殊点有 个。然后跑一遍dij即可。(dis多建一维条件跑dij也可以) #include<bits/stdc++.h> #define ll long long #define inf 0x7f7f7f7f #define pr pair<ll,ll> using namespac...

大致题意：给定一个序列，求 . 表示 和 十进制下的位数差.分析：方法一:离散+树状数组我们可以逆序遍历序列，计算当前 作为 的左参数的贡献，那么我们与 相加能产生数位差 .举个例子：能至少产生一位数位差，设比 大的最小十进制数位 ，那么 的大小一定要大于等于 .依次枚举至少产生两位数位差.....其实就是遍历所有的十进制数字进行查找.那么当我们求解 的数位差贡献时，必须要有一个数据结构存储 ,并且使其有序才能进行二分查找符合条件的 的个数。-------离散所有可能出现的值(大概9e5)，然后树状数组维护即可. #include<bits/stdc++.h> #define lo...

[CQOI2011]动态逆序对

1.费马小定理运算推公式https://ac.nowcoder.com/acm/contest/5945/D