Canan

题解

/ 注册

全部文章 / 题解（共31篇）

货币系统

https://ac.nowcoder.com/acm/problem/21228题意：有n种货币，每种货币数量无限，问能否删掉几种货币，使得原来能组成的数现在仍能组成。分析：想要去掉某种硬币，说明它可以被一种或多种面值比它小的货币所组成，一个或多个的和能组成某一个数，明显的背包问题，而且每个类...

2020-05-26

0 580

建筑抢修

https://ac.nowcoder.com/acm/problem/20154题意：已知每个建筑的报废时间和维修时间，只有一个人去维修，问最多能维修多少建筑？分析：典型贪心题，我们要在规定时间内维修尽可能多的建筑，大体上先贪心一下，先维修截止时间迫在眉睫的建筑，那么怎么判断当前是否可以进行维修...

2020-05-25

1 1091

中位数图

https://ac.nowcoder.com/acm/problem/19913 题意：给你一个排列和一个数字b，问数组中有多少连续奇数子序列的中位数为b。分析：我们首先想到的方法是找到数字b的位置，然后从该位置向两边左右枚举取数判断是否合法，但1e5的数据显然这么做会超时，所以我们适着转换一下...

2020-05-21

1 733

图的遍历

https://ac.nowcoder.com/acm/problem/52275 题意：需要加多少条边才能使从1开始遍历整张图？分析：先从简单的问题进行考虑，假设每次都只能走1步，那么需要加多少条边才能遍历完呢，显然要把全部点都连通起来，因此需要加的边数就是（连通块的数量-1）条边。如果每次只能...

2020-05-20

1 820

牛客算法周周练7A和E

https://ac.nowcoder.com/acm/contest/5713/A题意：给定物品坐标与初始坐标，求收集完所有物品再回来的最短路径分析：看一下题目数据，最多只有10张卡片，数据很小直接枚举就行了，用dfs全排列搜索，记录每个方式的路径，取最小值即可。复杂度O(10!) #inclu...

2020-05-20

1 632

大吉大利，今晚吃鸡

https://ac.nowcoder.com/acm/problem/14585 题意：只能通过移动到相邻位置的汉诺塔问题。汉诺塔讲解：有三根A,B,C相邻的柱子，A柱子从上到下按递增方式摆放了n个不同大小的圆盘，现在要把A中所有的盘子移动到柱子C上，并且每次移动同一根柱子上都不能出现大盘子在小...

2020-05-19

2 796

Laptop

https://ac.nowcoder.com/acm/problem/14266 题意：找出某种电脑内存和速度比另一台电脑都低的数量分析：枚举模拟一下题意就行了，锤爆牛客评测机，n^2都能过1e5。代码： #include<stdio.h> #include<algorith...

2020-05-19

5 753

比赛

https://ac.nowcoder.com/acm/problem/14734 题目理解：题意很简单，就是给你12道题3种途径的概率，求解决0~12题的概率。题目分析：正着求每道题解决的概率，显然有点困难，那么我们不妨逆向考虑一下每道题无法解决的概率，答案显然 fail[i]=(1-a[i])...

2020-05-18

0 534

【土】秘法地震

https://ac.nowcoder.com/acm/problem/53676题意：给定一个由01字符串矩阵，求包含1的k*k矩阵个数。分析：地图大小为10001000，枚举kk矩阵即可，若矩阵数字和不为0，则ans++ 求区间和我们首先想到前缀和，可以O（1）查询区间和，感觉和昨天的...

2020-05-15

0 562

maze

题意：走迷宫，有传送阵，移动花费1秒，传送花费3秒，求到达终点的最短时间。思路：最短路问题，首先想到的是Dijkstra算法，但是题目数据不大，建图起来麻烦（其实不会），所以我们直接用bfs跑一便就行了，一个多了几个传送阵的迷宫问题，丢进优先队列里搜索时特判一下就行了，一些细节的说明在代码上有注释...

2020-05-15

1 688