跳至正文

算法

USACO 2.1.3 Sorting A Three-Valued Sequence 解题报告

首先用两个数组分别保存排了序的数组和没排序的数组,然后再根据这两个判断,当前这个位置上应该是放什么数,而实际上放的是什么数,如果两个位置上需要的都正好是对方所有的,那么这是最好的,进行循环,把所有这种的都交换掉,然后累计交换次数。 但是最后会有这么一种情况,三个位置需要的分别是1, 2, 3,而他[……]

继续阅读

Noip 2010 提高组 第三题 关押罪犯

  • OI路程

  这题的话,就是贪心,把最大的罪恶值的两个囚犯都不关在一个牢房里,反复的贪心,但是数据太大,不允许使用邻接表和邻接矩阵,用什么结构来保存呢?我觉得(也是网上的资料里的咯)使用动态分配是个方法,因为最多10000条边,根据实际情况来分配,这样不会有浪费的空间,也就不会导致空间爆掉了。

#include[……]

继续阅读

Noip 2010 提高组 第二题 乌龟棋

  • OI路程

  在考场上我的思想是这么的,f[n +
j] = max{当在n这个位置时还有布数为j的卡片|f[n] + map[n + j]},后来发现这么是不行的,因为f[n + j]不是最大但也可能有更好的取值,因为它可以留下另外一张卡片,只有10分呢!
  后来,我又想了另外一种算法,用一个维护一个栈,[……]

继续阅读

Noip 2010 提高组 第一题 机器翻译

  • OI路程

  纯水题,维护一个列队,作为内存列队,并且写两个操作:进列队、出列队;因为数据量十分的小(n<=1000)所以可以维护一个用于标记的数组,如果单词在列队中则置为1,不在则置为0,接着就是暴力——模拟就是。

#include <stdio.h>

int queue[[……]

继续阅读

算法: 求最长的回文字符串

  • OI路程

  最近USACO写到了(第三次)1.3.3,这一题我用的是我自己原创的一个算法(可能也有别人想到了,但是对于我来说,确实是我自己独立思考出来的),在此发表一下。
  程序:输入:一行字符串,输出:最长的回文字符的长度以及把它们给输出来。
  如:
    输入:1596156432111234
 [……]

继续阅读

Noip 2010之旅(下)

  • OI路程

  昨晚上让柜台6:30把我们闹醒,结果7点钟他们才打电话来,真是懒,幸好我起来的早,6点半不到就醒了,不然考试不就错过了。
  早早地来到考场,虽然离考试还有一段时间,但是已经有非常多的人 在哪儿等候了,老师也碰到几个熟人,聊着聊着就开考了。
  哇,这种考试就是不一样,真大啊~宽敞的机房,虽然昨[……]

继续阅读

Noip 2010之旅(上)

  • OI路程

  学校第37届运动会闭幕式刚结束, 李智老师就准备带着我去长沙了. 他先带我去和别的老师一起吃了一餐饭, 然后就出发了!

  好久没来火车站了, 发现这里比以前要好很多了, 以前我爸带我到这里, 跟我说以前是怎么逃票的, 后来好像本来是要带我逃票的吧, 好像是我良心过不去, 所以就没了, 不太记得[……]

继续阅读