树状数组

例1:给出一个长度为n的序到,有m个询问,每次形如l,r,求[l,r]的区间和。

法1: 暴力

  • 每次询问都扫一遍。

法2: 前缀和

  • 预处理O(n),每询问次O(1)时间复杂度。

法3: 线段树 & 树状数组

  • 弱智。。。

Read More

题解 P2920 【[USACO08NOV]时间管理Time Management】

题面

作为一名忙碌的商人,约翰知道必须高效地安排他的时间.他有N工作要 做,比如给奶牛挤奶,清洗牛棚,修理栅栏之类的.

为了高效,列出了所有工作的清单.第i分工作需要T_i单位的时间来完成,而 且必须在S_i或之前完成.现在是0时刻.约翰做一份工作必须直到做完才能停 止.

所有的商人都喜欢睡懒觉.请帮约翰计算他最迟什么时候开始工作,可以让所有工作按时完成.(如果无法完成全部任务,输出-1)

Read More

题解 P2701 【[USACO5.3]巨大的牛棚Big Barn】

题解 P2701 【[USACO5.3]巨大的牛棚Big Barn】

题面

农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。

他讨厌在他的农场中砍树,想找一个能够让他在空旷无树的地方修建牛棚的地方。

我们假定,他的农场划分成 N x N 的方格。输入数据中包括有树的方格的列表。你的任务是计算并输出,在他的农场中,不需要砍树却能够修建的最大正方形牛棚。

牛棚的边必须和水平轴或者垂直轴平行。

Read More

题解 P1312 【Mayan游戏】

题解 P1312 【Mayan游戏】

题面

过长已遮挡

题意

体面已经陈述题意(这题没有考语文阅读理解)

题解

* 我还记得我曾经给自己找的锅,给某些人讲课的时候说过一句话:体面越长的题,越简单。** *这句话没有错,我会用接下来解决这道题的思路过程,来证明这句话。

  1. 首先我们知道存在这么几种操作:

    a. 交换操作

    b. 下沉操作

    c. 消除操作

    d. 搜索操作

    e. 玩完判断

    f. 拷贝操作(回溯)

  2. 这时候可以看得出来这里面除了搜索操作,剩余的操作都是模拟,我们只需要分出多个函数进行模拟就好了。

  3. 但是思路就是如此简单的一道题我却调了一个下午。(代码量是真的大,不压横150+行代码),还是我太菜了。

  4. 因为数据量非常小,不用怎么优化也能过,但是写代码的时候一定要小心。


Read More

题解 P1550 【[USACO08OCT]打井Watering Hole】

题解 P1550 【[USACO08OCT]打井Watering Hole】

题面(翻译有点问题,最后一句话)

农民John 决定将水引入到他的n(1<=n<=300)个牧场。他准备通过挖若干井,并在各块田中修筑水道来连通各块田地以供水。在第i 号田中挖一口井需要花费W_i(1<=W_i<=100,000)元。连接i 号田与j 号田需要P_ij (1 <= P_ij <= 100,000 , P_ji=P_ij)元。

Read More

题解 P1120 【小木棍 [数据加强版]】

题解 P1120 【小木棍 [数据加强版]】

题面

乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过50。

现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。

题意

有n段同样长的木棍,现在将这n段木棍随意分段(保证每段长度不超过50)。乔治比较闲,又想把它拼回原始木棍,但是又比较智障,忘了原来有多少根,长度是多少。

给出每段的长度,求出木棍最小可能长度。(使n尽量大,又要保证每段都拼上)

题解

题目看上去很简单,也很好想到这是一个搜索题,但是拿到后非常难以无法下手,数据的加强非常容易使这题超时。这是一道剪枝的经典题目

Read More