Lyz's Blog

Never Give Up

发表于 分类于 ， 阅读次数： 本文字数： 4.3k 阅读时长 ≈ 4 分钟

Description

对一个由n个点组成的图形连续作平移、缩放、旋转变换。相关操作定义如下：

Trans(dx,dy) 表示平移图形，即把图形上所有的点的横纵坐标分别加上dx和dy；

Scale(sx,sy) 表示缩放图形，即把图形上所有点的横纵坐标分别乘以sx和sy；

阅读全文 »

发表于 分类于 ， 阅读次数： 本文字数： 4.7k 阅读时长 ≈ 4 分钟

Description

数轴上有很多单位线段，一开始时所有单位线段的权值都是1。有两种操作，第一种操作将某一区间内的单位线段权值乘以w，第二种操作将某一区间内的单位线段权值取w次幂。并且你还需要回答一些询问，每个询问需要求出某一区间的单位线段权值之积。由于答案可能很大，你只需要求出答案 mod (10^9+7)的值。

Input

第一行一个整数n，表示操作数量。

阅读全文 »

发表于 分类于 ， 阅读次数： 本文字数： 2.8k 阅读时长 ≈ 3 分钟

Description

Scofield刚从监狱里面跑出来，现在他要在进行大逃亡.

你也知道, 逃亡是非常不容易的, 现在Scofield遇到了一些困难, 你可以帮助他吗?

Scofield面前的是一个美国的交通图, 图里面有一些城市, 有些城市之间有路连接. 路的长度scofield是知道的, 但是有些城市里面的警察很多, 所以scofield对这个问题很头疼. 他现在要安排一些逃亡路线, 所以他要对你做一些询问, 询问是这样的:某两个城市之间的最短路是什么? 但是这个最短路有个前提, 那就是路径上的每个城市里的警察不得超过k个. 起点和终点除外.

阅读全文 »

发表于 分类于 ， 阅读次数： 本文字数： 2.7k 阅读时长 ≈ 2 分钟

Tips

题目来源：http://www.luo.hustoj.com/problem.php?id=1287

Analysis

从这个顺(dou)旺(bi)基同学的代码中，我们发现他的算法实际上是给逆序对连边，而独立集所在的集合中，任意两个都不存在连边(即不是逆序对)，那就是顺序的。并且题目要求我们要找出一个最大的独立集，求出他的长度，那就是要我们求最长不下降子序列，而因为给出的n个数是全排列。所以就是求最长上升子序列。这个可以用(nlogn)的二分查找求出。最关键的就是怎么求第二问最长上升子序列中那些点是必选的。

阅读全文 »

发表于 分类于 ， 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 2 分钟

Description

万老师听说某大国很流行穿越，于是他就想写一个关于穿越的剧本。

闲话休提。话说老师穿越到了某一个剑与魔法的大陆。因为如此这般，所以老师从维娜艾那里得到了预言。老师一共被告知了若干件按顺序结算的事件。这些事件分为两类：战役事件（CASE）、穿越回去事件（END）。战役事件可以选择是否参加，参加了之后会获得一定的金钱。每个END事件发生需要至少参加一定数量的战役事件。特别的是，END事件如果满足要求就会强制发生。老师希望在大陆玩个够，所以他要求只有最后一个END事件会发生。老师希望获得最多的金钱，所以求助于你。

Input

阅读全文 »
0%