savage

题解

/ 注册

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

题解 | 乌龟棋-NOIP2010提高组复赛

算法知识点: 线性DP 复杂度：解题思路：状态表示：表示所有第种卡片使用了张的走法的最大分值。状态计算：将表示的所有走法按最后一步选择哪张卡片分成四类：第类为最后一步选择第种卡片。比如，则这一类的最大分值是。 C++ 代码： #...

乌龟棋题解 NOIP2010提高组复赛

2019-09-07

0 759

题解 | 关押罪犯-NOIP2010提高组复赛

算法知识点：二分，染色法判断二分图复杂度：解题思路：将罪犯当做点，罪犯之间的仇恨关系当做点与点之间的无向边，边的权重是罪犯之间的仇恨值。那么原问题变成：将所有点分成两组，使得各组内边的权重的最大值尽可能小。我们在之间枚举最大边权，当固定之后，剩下的问题就是： ...

关押罪犯题解 NOIP2010提高组复赛

2019-09-06

2 791

题解 | 机器翻译-NOIP2010提高组复赛

算法知识点: 模拟，队列复杂度：解题思路：这道题是让我们实现一个先进先出的缓存机制。数据的存储：由于是先进先出，所以我们可以用循环队列来维护缓存中的所有单词，这里可以用C++STL中的queue。用bool数组存储每个单词是否已经在队列中，这样就可以用O(1)的时间判...

机器翻译题解 NOIP2010提高组复赛

2019-09-06

0 865

题解 | 引水入城-NOIP2010提高组复赛D题

题目描述在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个N 行M 列的矩形，如上...

引水入城题解 NOIP2010提高组复赛

2019-08-31

0 835

题解 | 关押罪犯-NOIP2010提高组复赛C题

题目描述 S 城现有两座监狱，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪...

关押罪犯题解 NOIP2010提高组复赛

2019-08-31

0 756

题解 | 乌龟棋-NOIP2010提高组复赛B题

题目描述小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。乌龟棋的棋盘是一行N 个格子，每个格子上一个分数（非负整数）。棋盘第1 格是唯一的起点，第N 格是终点，游戏要求玩家控制一个...

乌龟棋题解 NOIP2010提高组复赛

2019-08-31

0 760

题解 | 机器翻译-NOIP2010提高组复赛A题

题目描述小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软...

机器翻译题解 NOIP2010提高组复赛

2019-08-31

0 897