首页 > 代码库 > poj 4090:超级备忘录

poj 4090:超级备忘录

2024-07-29 09:42:26   221人阅读

poj 4090:超级备忘录


题目：
描述

你的朋友Jackson被邀请参加一个叫做“超级备忘录”的电视节目。在这个节目中，参与者需要玩一个记忆游戏。在一开始，主持人会告诉所有参与者一个数列，{A1, A2, ..., An}。接下来，主持人会在数列上做一些操作，操作包括以下几种：

  1. ADD x y D：给子序列{Ax, ..., Ay}统一加上一个数D。例如，在{1, 2, 3, 4, 5}上进行操作"ADD 2 4 1"会得到{1, 3, 4, 5, 5}。

  2. REVERSE x y：将子序列{Ax, ..., Ay}逆序排布。例如，在{1, 2, 3, 4, 5}上进行操作"REVERSE 2 4"会得到{1, 4, 3, 2, 5}。

  3. REVOLVE x y T：将子序列{Ax, ..., Ay}轮换T次。例如，在{1, 2, 3, 4, 5}上进行操作"REVOLVE 2 4 2"会得到{1, 3, 4, 2, 5}。

  4. INSERT x P：在Ax后面插入P。例如，在{1, 2, 3, 4, 5}上进行操作"INSERT 2 4"会得到{1, 2, 4, 3, 4, 5}。

  5. DELETE x：删除Ax。在Ax后面插入P。例如，在{1, 2, 3, 4, 5}上进行操作"DELETE 2"会得到{1, 3, 4, 5}。

  6. MIN x y：查询子序列{Ax, ..., Ay}中的最小值。例如，{1, 2, 3, 4, 5}上执行"MIN 2 4"的正确答案为2。

为了使得节目更加好看，每个参赛人都有机会在觉得困难时打电话请求场外观众的帮助。你的任务是看这个电视节目，然后写一个程序对于每一个询问计算出结果，这样可以使得Jackson在任何时候打电话求助你的时候，你都可以给出正确答案。

输入
第一行包含一个数n (n ≤ 100000)。
接下来n行给出了序列中的数。
接下来一行包含一个数M (M ≤ 100000)，描述操作和询问的数量。
接下来M行给出了所有的操作和询问。
解题方案
这里面最有深度的题目就是旋转了，所以分析只有针对旋转的
对一个数组旋转怎么做呢？暴力法可以么，可以，但是很慢
那么我们怎么办？如果实验较多我们会发现有一个规律，我们设 length 为数组长度，需要旋转的次数为 n （0 < n < length ）

我们将根据 length 是否能整除 m （= n<(length-n) ? n : length - n ）分为两种情况设计算法
但是每一种情况时间复杂度都是 O（length），所以这是比较快的
我们先看能整除的那种情况

length = 6; m = 1; length % m = 0;共有m个大循环

length = 6 ; m = 2; length % m = 0; 共有m个大循环




第二种情况，不能整除
length = 7 ；n = 4 ； m = 3 ；length % m == 1; 这时只用一个大循环就可以。


代码

#include <iostream>
using namespace std;


class intList
{
	int * data;
	int length;
public:
	intList()
	{
		data = http://www.mamicode.com/NULL;>

poj 4090:超级备忘录


联系
我们