题目描述 有一只老鼠很喜欢奶酪，但是奶酪被分别放在N个房间里，而且这些房间都有一只猫咪看守，现在它准备和猫咪们做个交易。它有M磅的猫食，想用这M磅猫食换取奶酪。在猫咪看守的每一个房间里有奶酪J[i] 磅，同时猫咪需要F[i]磅的食物，如果老鼠给猫咪F[i] * (a)%的猫食，那么它就可以得到J[i] * (a)%的奶酪。现在已知每只猫咪对猫食的需求量和每个房间的奶酪数，那老鼠怎样才能换得最多的奶酪呢？ 输入格式 第一行输入两个正整数M和N（M和N不大于10000），后面跟N行（每个房间的奶酪数和猫食的需求量）。 输出格式 输出老鼠得到的最多的奶酪数，保留三位小数。 样例 样例1输入 5 3 ...

防线 2020/3/31 题目描述 达达学习数学竞赛的时候受尽了同仁们的鄙视，终于有一天…受尽屈辱的达达黑化成为了黑暗英雄怪兽达达。 就如同中二漫画的情节一样，怪兽达达打算毁掉这个世界。 数学竞赛界的精英 lqr 打算阻止怪兽达达的阴谋，于是她集合了一支由数学竞赛选手组成的超级行动队。 由于队员们个个都智商超群，很快，行动队便来到了怪兽达达的黑暗城堡的下方。 但是，同样强大的怪兽达达在城堡周围布置了一条“不可越过”的坚固防线。 防线由很多防具组成，这些防具分成了 N 组。 我们可以认为防线是一维的，那么每一组防具都分布在防线的某一段上，并且同一组防具是等距离排列的。 也就是说，我们可以用三个整...

摘自几个月前的帖子。。。 DFS模板：向深处搜索，直到找到解或者走不下去。这一般解决全排列问题 //No.1 Void DFS（deep，...）{ if(找到解 || 走不下去了){ ......//根据题意添加 return; } for(扩展方式){ if(扩展方式所能达到的状态合法){ 修改操作；//根据题意添加 标记； DFS(deep+1,...); //根据题意是否要还原 } } } //No.2 int check(参数) { if(满足条件) return 1; return 0; } void dfs(int step) { 判断边界 { 相应操作 } 尝试每一种可能 { ...

定义  并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。 并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。 —...

小球 #include <cstdio> #include <cstring> const int MAXN = 25; int d, i; int s[1 << MAXN]; int main() { memset(s, 0, sizeof(s)); scanf("%d %d", &d, &i); int k, n = (1 << d) - 1; for(int j = 1;j <= i;j ++) { k = 1; while(1) { s[k] = !s[k]; k = s[k] ? k * 2 :...

区间DP定义 顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。 实现思路  既然是在区间里进行DP： 以‘区间长度’作为阶段 状态为某区间内的最有解，即将长度为1的元区间作为DP的最小状态。使用      d   p   [   l   ,   r   ]    dp[l, r]   dp[l,r] 描述每一个维度。  典型例题 删除字符串 题目描述  给出一个长度为n的字符串，每次可以删除一个字母相同的子串，问最少需要删多少次。 数据规模：n <= 500  输入格式  第1行：1个整数，表示字符串...

1.递归 int name(int n) { if(满足边界条件) return ...; if(满足边界条件) return ...; ... else { sbproblems... ... return name(...) + ... } }  2.二分 2.1 左边界 int left_bound(int[] nums, int target) { if (nums.length == 0) return -1; int left = 0; int right = nums.length; // 注意 while (left < right) { // 注意 int mid = ...

防线 2020/3/31 题目描述 达达学习数学竞赛的时候受尽了同仁们的鄙视，终于有一天…受尽屈辱的达达黑化成为了黑暗英雄怪兽达达。 就如同中二漫画的情节一样，怪兽达达打算毁掉这个世界。 数学竞赛界的精英 lqr 打算阻止怪兽达达的阴谋，于是她集合了一支由数学竞赛选手组成的超级行动队。 由于队员们个个都智商超群，很快，行动队便来到了怪兽达达的黑暗城堡的下方。 但是，同样强大的怪兽达达在城堡周围布置了一条“不可越过”的坚固防线。 防线由很多防具组成，这些防具分成了 N 组。 我们可以认为防线是一维的，那么每一组防具都分布在防线的某一段上，并且同一组防具是等距离排列的。 也就是说，我们可以用三个整...

关于昨天搜索考试的题目考察内容大体如下: 1.有重复元素的排列问题  dfs + STL大法(去重)  2.烈火金刚  bfs板子题  3.剪纸  记忆化搜索  4.玛丽有只小羔羊  二分 + bfs   难度排序  1 < 2 < 3 < 4   1.有重复元素的排列问题 此题可以用STL模板自带的去重完成,其思想和全排列类似 上代码 #include<cstdio> #include<algorithm> #include<cstring> using namespace std; char a[505], b[505];//一个输入,...

施工完毕 二分算法是分治中的一种，所谓二分，其实就是将一个较大的问题缩小x区间去求解废话不多说详情请见百度 我个人认为二分有点儿难，主要要将l,r与mid处理好 Knuth(好像 是他发明的KMP 来着）曾经说过  Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky  思路很简单，细节是魔鬼。   First二分查找 额，k才开始学习二分时，没弄懂二分查找的 用途 好处，觉得它还是停留在暴力上面。我总结了一下二分查找的关...

递推总结 首先： 什么是递推 递推    中文名 外文名     递推 The Recursive    定义 “递推是按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。” “所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。 从已知条件出发逐步推到问题结果，此种方法叫顺推。 从问题出发逐步推到已知条件，此种方法叫逆推。 无论顺推还是逆推，其关...

区间DP定义 顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。 实现思路  既然是在区间里进行DP： 以‘区间长度’作为阶段 状态为某区间内的最有解，即将长度为1的元区间作为DP的最小状态。使用 $dp[l, r]$ 描述每一个维度。  典型例题 删除字符串 题目描述  给出一个长度为n的字符串，每次可以删除一个字母相同的子串，问最少需要删多少次。 数据规模：n <= 500 输入格式 第1行：1个整数，表示字符串的长度 第2行：n个字符的字符串  输出格式  第1行：1个整数，表示答案  样例 样例...

关于昨天搜索考试的题目考察内容大体如下:  1.有重复元素的排列问题  dfs + STL大法(去重)   2.烈火金刚  bfs板子题   3.剪纸  记忆化搜索   4.玛丽有只小羔羊  二分 + bfs  难度排序   1 < 2 < 3 < 4   1.有重复元素的排列问题 此题可以用STL模板自带的去重完成,其思想和全排列类似 上代码  #include<cstdio> #include<algorithm> #include<cstring> using namespace std; char a[505], b[505];//...

1.递归 int name(int n) { if(满足边界条件) return ...; if(满足边界条件) return ...; ... else { sbproblems... ... return name(...) + ... } } 2.二分 2.1 左边界 int left_bound(int[] nums, int target) { if (nums.length == 0) return -1; int left = 0; int right = nums.length; // 注意 while (left < right) { // 注意 int mid = (...