题意： 有一堆卡片，卡片上有1-4其中一个数，数字决定向前走的步数，走到某处就获得该点对应的分数，如何调整使用卡片顺序使得到达终点 n 时的得分最大。 分析： 动态规划每一步促使结果最优解，很明显思路是 dp 或者记忆化搜索（感觉搜索比较好写）dfs(int k,int a1,int a2,int a3,int a4) k表示当前位置，a1表示数字1卡片使用次数，a2表示数字2卡片使用次数，a3表示数字3卡片使用次数，a4表示数字4卡片使用次数， 由此有四个搜索方向：（前提是有卡片剩余）使用1卡片：dfs(k+1,a1+1,a2,a3,a4)使用2卡片：dfs(k+2,a1,a2+1,a3,a...

题意： 分析：（不想打字所以放了张图片） 对于每个前n项和，可以用前缀和进行预处理求出，然后负数取模注意下就可以了。 代码： #include<iostream> #include<algorithm> #include<stdio.h> #include<cstring> #include<deque> #define mem(a, x) memset(a, x, sizeof(a)) void fre() { freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout)...

题意：柱状图中已知每个矩形的宽和高，问矩形最大面积是多少？ 思路：单调栈的模板题，不过也能用单调队列来解决。对于每个位置，我们可以用单调队列（deque）维护一个单调递增的序列，当遇到递减情况时，统计前面前面形成矩形方案的最大值，同时不断维护队列单调性。（矩形底边宽可以用前缀和预处理求出）最后记得开 longlong ，应该没什么坑了 代码： #include<iostream> #include<algorithm> #include<stdio.h> #include<cstring> #include<deque> #defi...

题意： 给定一个nm的矩阵，矩阵每个元素都有一个值a[i][j]，由第一行开始向下走，每次取该行的行首或者行尾的一个元素，得分贡献为 所选元素2^k ,k表示第几次取数，由1开始，问得分最大值为多少？ 分析： 由第一行开始走到最后一行，m个回合便可获得全部元素，因此对于每一行的取数对于其他行是无影响的，得分最大值即为每一行的最大值之和，而对于每一行的最大值，可以用dp简单地求出dp[l,r]=max(dp[l,r−1]∗2+a[r],dp[l+1,r]∗2+a[l])每次的状态是由上一个状态取左边和取右边的答案最大值转移过来的。当然这种状态转移也可以用记忆化搜索表示，比较直观好理解。数据过大u...

https://ac.nowcoder.com/acm/problem/18979 题意：有n个数a1, a2, ..., aN，给出m个询问，每次询问区间[l,r]，请找出一个数x使得x异或区间每个数的和最大。 分析：异或运算，异或1取反，异或0不变，为了使结果最大，因此如果某个数位为1，那么我们对其异或0，如果某个数位为0，那么我们对其异或1取反，如此贪心取得最大值。因此对于区间[l,r]的每个数，我们只需求出每个数位上0多还是1多，如果1多，该数位为0，反之，则为1.对于求[l,r]区间每个数位1的数量，我们只需要用前缀和预处理下就行了，即a[r]-a[l-1]，而对于区间数位01总数量...

https://ac.nowcoder.com/acm/problem/16564题意：已知每天可以借出去的教室数量a[i],根据先到先得原则，按顺序分配教室，共有m个订单，第i个订单需要[li,ri]区间内借xi个教室，问到第几个订单开始无法满足（教室不够了） 分析：m次区间[li,ri]进行修改xi，边修改边查询是否满足题意，这不就是练习线段树的题目吗？首先建一颗含最小值信息的线段树，模拟题意进行区间修改，修改完后判断一下整个区间最小值是否小于0，即minx[1]是否小于0，若发现一不符合的修改，直接return 0。暴力即优雅，记得开longlong（不建议define int long...

题意： 四种彩票中奖金额分别为1，2，3，4，且各种金额中奖率相等（良心）,小A买了n张彩票，问不亏本概率为多少？ 分析： 模拟几次n发现，n每个中奖金额出现的概率总是由第n-1的概率转移过来的，具体转移方式有4种1，2，3，4，统计可行方式相加即可。因此我们可以用dp进行解决。 设dp[i][j]：前i张彩票中奖为j元的方案数。转移方程：dp[i][j] += dp[i-1][j-k] 其中1≤k≤4 k≤j初始dp[0][0]等于1 买n张彩票共有4^n方案数cnt符合题意方案数为：sum（dp[n][j]）,3n<=j<=4n最后答案为sum/cnt(gcd化简) 代码： #...

https://ac.nowcoder.com/acm/problem/53079题意：给定一数n，求1~n每个数的最小质因数的和。 分析：可以用欧拉线性筛素数法，每个数仅使用其最小素因数筛去，开始先打个表，后面直接统计答案就行了。 代码： #include<stdio.h> #include<algorithm> #include<vector> using namespace std; typedef unsigned long long ll; int n,m,v,w,s,i,j; const int LIM = 3e7 + 10; int...

https://ac.nowcoder.com/acm/problem/20241题意：一个只有两列的扫雷，其中第二列没有雷，并且给出了第二列的数字，该数字表示以其为中心连通的八个格子共含雷的数量，问第一列雷有多少摆放方案？ 分析：很有趣的一道模拟题，按照题意自己手动模拟答案发现其实第一列雷的方案数基本都被第二列给限制死了，能让你二选一的其实很少了（为什么扫雷高级还是过不了QAQ） a[i]：第二列第i个数的值f[i]：第一列的i个数是否有雷，1代表有，0代表无f[i-1]+f[i]+f[i+1]=a[i]-->f[i+1]=a[i]-f[i-1]-f[i]（扫雷规则） 先整体来看，显然...

https://ac.nowcoder.com/acm/problem/18386 题意：给定一字符串s，找到其包含所有小写字母的最短子串。 分析：枚举区间，首先想到尺取法。尺取法：先初始化区间[0,-1]，尺取移动右端点至区间[l,r]为合法区间，然后在满足条件的情况下不断向右移动左端点，缩小合法区间长度，更新ans最小值。尺取结束后答案即为ans。 代码： #include <bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; char a[1000005]; int b[30]; int ok(){ ...

https://ac.nowcoder.com/acm/problem/50995 题意：超市有n件物品，已知它们的利润p和过期时间d，每天只能卖一件一件物品，过期的物品不能售卖，合理安排每天售卖的物品，问最大利润是多少？~多组数据输入输出 分析：最大价值中先要保证物品不过期，先按日期正序排序，排序后把物品的价值放入优先队列（正序队列）中，如果队列物品数量大于当前物品的截止时间，那么把队列排头丢掉，这货利润这么低，用后面的物品可以完全代替了。最后统计求和一下优先队列里面的所有值就行了。 代码： #include<stdio.h> #include<string.h> #...

https://ac.nowcoder.com/acm/problem/19158 题意：有一个天平，每次只要放上去的东西重量相差不超过m即可拿走，问最多能带走物品的重量为多少？ 分析： 在这个问题中，我们关心的只有两边的差值，如果两边差值小于等于m，那么天平就是等价的，那么对于当前差值j，你再加一件物品后的状态，只与之前的差值j有关，差值变成j+w[i],或abs(j-w[i])，因此对于当前a[i]物品，假定放进去最优解是差值为j的时候，那么这个最优解一定是从上一个状态的其中一个差值j转化过来的，我们需要从这过程中取最优情况，因此用dp进行解决。 dp[i][j]：表示前i个物品差值为j的...

链接：https://ac.nowcoder.com/acm/contest/5758/D来源：牛客网 题意： 有n枚硬币，正反概率相同，已知至少有m枚硬币是反面，问恰好有k枚硬币是正面的概率是多少。 分析： 首先很容易，当正面硬币数+反面硬币数大于总硬币，即m+k>n时，结果不存在，概率为0。接下来考虑一下其他合法情况，先设A为至少有m枚硬币是反面，B为恰好有k枚硬币是正面，A为已知条件，所以由高中的概率可得，P（B∣A）=P（AB）/P(A)，因为 P（AB）和 P(A) 分母均为n，所以可以转化为方案数。 P（AB）：使A，B同时成立的条件为 C（n,k）或者 C（n,m）。P(...

https://ac.nowcoder.com/acm/problem/23486 题意： 有一迷宫，小A每秒移动1次，方向为上下左右左上左下右上右下8个方向，小B每秒移动2次，方向为上下左右四个方向，问他们最早什么时候能够相遇？ 分析： 迷宫问题，求最短相遇时间，优先考虑用bfs。因为小B每秒运动2次，所以我们可以给他每秒进行两次bfs，注意一下，bfs里面要判断一下是A还是B，小A是8个方向的，小B是4个方向的，用vis[0][x][y]和vis[1][x][y]分别记录走过的路径。bfs：当小A走的时候，广搜周围路径，如果该点被小B所走过的时候，说明他们相遇了，答案出来了。 代码： #i...