#1197 : Give My Text Back

题目:

1.主要涉及字符串处理,把一些凌乱的句子转换为正常的句子。

2.字母之间只能够是空格或者逗号+空格或者句号+空格隔开。

3.一行里面可能有多个句子,这些句子不用换行,但是需要用句号+空格隔开,并且第一个字母需要大写。

4.注意最后结尾只能是句号,如果还包含有空格,则会出现Presentation Error。

4.主要是上面的情况,下面是一个测试用例及其正确的答案,这个测试用例正确,就能AC。

/*

测试用例:
 my Name  is Little   Hi. ami           .i hate      hiho                     ,codr. EEENNN.
   His   name IS Little ho  ,  We are   friends.
 my Name  is Little   Hi.His   name IS Little ho  ,  We are   friends.
my Name  is Little   Hi. His   name IS Little ho  ,  We are   friends.
 His   name IS Little ho  ,We are   friends.   weoifj   ,jo.
Jo, f, j l, o,o, l.

正确答案:
My name is little hi. Ami. I hate hiho, codr. Eeennn.
His name is little ho, we are friends.
My name is little hi. His name is little ho, we are friends.
My name is little hi. His name is little ho, we are friends.
His name is little ho, we are friends. Weoifj, jo.
Jo, f, j l, o, o, l.


*/

 

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

To prepare for the English exam Little Ho collected many digital reading materials. Unfortunately the materials are messed up by a malware.

It is known that the original text contains only English letters (a-zA-Z), spaces, commas, periods and newlines, conforming to the following format:

1. Each sentence contains at least one word, begins with a letter and ends with a period.

2. In a sentence the only capitalized letter is the first letter.

3. In a sentence the words are separated by a single space or a comma and a space.

4. The sentences are separated by a single space or a single newline.

It is also known the malware changes the text in the following ways:

1. Changing the cases of letters.

2. Adding spaces between words and punctuations.

Given the messed text, can you help Little Ho restore the original text?

输入

A string containing no more than 8192 English letters (a-zA-Z), spaces, commas, periods and newlines which is the messed text.

输出

The original text.

样例输入
my Name  is Little   Hi.
His   name IS Little ho  ,  We are   friends.
样例输出
My name is little hi.
His name is little ho, we are friends.

 
AC代码:

/*
题目:
1.主要涉及字符串处理。
2.字母之间只能够是空格或者逗号+空格或者句号+空格隔开。
3.一行里面可能有多个句子,这些句子不用换行,但是需要用句号+空格隔开,并且第一个字母需要大写。

*/
/*

测试用例:
 my Name  is Little   Hi. ami           .i hate      hiho                     ,codr. EEENNN.
   His   name IS Little ho  ,  We are   friends.
 my Name  is Little   Hi.His   name IS Little ho  ,  We are   friends.
my Name  is Little   Hi. His   name IS Little ho  ,  We are   friends.
 His   name IS Little ho  ,We are   friends.   weoifj   ,jo.
Jo, f, j l, o,o, l.

正确答案:
My name is little hi. Ami. I hate hiho, codr. Eeennn.
His name is little ho, we are friends.
My name is little hi. His name is little ho, we are friends.
My name is little hi. His name is little ho, we are friends.
His name is little ho, we are friends. Weoifj, jo.
Jo, f, j l, o, o, l.


*/

#include<string>
#include <iomanip>
#include<fstream>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;
char lower(char&c)
{
	if (c <= 'Z'&&c >= 'A') return c - 'A' + 'a';
	else return c;
}

char upper(char&c)
{
	if (c <= 'z'&&c >= 'a') return c - 'a' + 'A';
	else return c;
}
/*
函数名  :main
函数功能:主函数
*/
int main(void)
{

	string str;
	while (getline(cin, str))
	{
		string newStr="";
		bool blank = false;
		bool comma = false;
		bool period = false;
		for (int i = 0; i < str.size(); i++)
		{
			//如果是句子的开头,且str[i]元素不为空
			if (newStr == ""&&str[i]!=' ')
			{
				newStr += upper(str[i]);
			}
			//如果不是句子的开头
			else if (newStr != "")
			{
				//如果是句号
				if (str[i] == '.')
				{//标记之前记录的是句号
					period = true;
					newStr += str[i];
				}
				else if (str[i] == ',')
				{
					comma = true;
					newStr += str[i];
				}
				//标记空白
				else if (str[i]==' ')
					blank = true;
				else
				{
					//如果之前是句号,则这个是新的句子,要加上空白,并且字母要大写
					if (period)
					{
						newStr += ' ';
						newStr += upper(str[i]);
						period = false;
						comma = false;
						blank = false;
					}
					//如果之前是逗号或者是空白,则要加上空白,字母要小写
					else if (comma || blank)
					{
						newStr += ' ';
						newStr += lower(str[i]);
						period = false;
						comma = false;
						blank = false;
					}
					//其他情况,即只是字母,全部小写
					else
						newStr += lower(str[i]);
				}

			}
		}
		cout << newStr << endl;
	}
	return  0;
}

#1037 : 数字三角形

1.题目求一三角形(树)中,从根到叶子节点总和的最大值。

2.如果进行深度搜索的话,时间复杂度会很大,所以采用动态规划。

3.动态规划状态转移方程为:

reward[i][j]=reward[i][j]+max(reward[i+1][j],reward[i+1][j+1])

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

问题描述

小Hi和小Ho在经历了螃蟹先生的任务之后被奖励了一次出国旅游的机会,于是他们来到了大洋彼岸的美国。美国人民的生活非常有意思,经常会有形形色色、奇奇怪怪的活动举办,这不,小Hi和小Ho刚刚下飞机,就赶上了当地的迷宫节活动。迷宫节里展览出来的迷宫都特别的有意思,但是小Ho却相中了一个其实并不怎么像迷宫的迷宫——因为这个迷宫的奖励非常丰富~

于是小Ho找到了小Hi,让小Hi帮助他获取尽可能多的奖品,小Hi把手一伸道:“迷宫的介绍拿来!”

小Ho选择的迷宫是一个被称为“数字三角形”的n(n不超过200)层迷宫,这个迷宫的第i层有i个房间,分别编号为1..i。除去最后一层的房间,每一个房间都会有一些通往下一层的房间的楼梯,用符号来表示的话,就是从第i层的编号为j的房间出发会有两条路,一条通向第i+1层的编号为j的房间,另一条会通向第i+1层的编号为j+1的房间,而最后一层的所有房间都只有一条离开迷宫的道路。这样的道路都是单向的,也就是说当沿着这些道路前往下一层的房间或者离开迷宫之后,小Ho没有办法再次回到这个房间。迷宫里同时只会有一个参与者,而在每个参与者进入这个迷宫的时候,每个房间里都会生成一定数量的奖券,这些奖券可以在通过迷宫之后兑换各种奖品。小Ho的起点在第1层的编号为1的房间,现在小Ho悄悄向其他参与者弄清楚了每个房间里的奖券数量,希望小Hi帮他计算出他最多能获得多少奖券。

提示一:盲目贪心不可取,搜索计算太耗时

提示二:记忆深搜逞神威,宽度优先解难题

提示三:总结归纳提公式,减少冗余是真理

输入

每个测试点(输入文件)有且仅有一组测试数据。

每组测试数据的第一行为一个正整数n,表示这个迷宫的层数。

接下来的n行描述这个迷宫中每个房间的奖券数,其中第i行的第j个数代表着迷宫第i层的编号为j的房间中的奖券数量。

测试数据保证,有100%的数据满足n不超过100

对于100%的数据,迷宫的层数n不超过100

对于100%的数据,每个房间中的奖券数不超过1000

对于50%的数据,迷宫的层数不超过15(小Ho表示2^15才3万多呢,也就是说……)

对于10%的数据,迷宫的层数不超过1(小Hi很好奇你的边界情况处理的如何?~)

对于10%的数据,迷宫的构造满足:对于90%以上的结点,左边道路通向的房间中的奖券数比右边道路通向的房间中的奖券数要多。

对于10%的数据,迷宫的构造满足:对于90%以上的结点,左边道路通向的房间中的奖券数比右边道路通向的房间中的奖券数要少。

输出

对于每组测试数据,输出一个整数Ans,表示小Ho可以获得的最多奖券数。

样例输入
5
2
6 4
1 2 8
4 0 9 6
6 5 5 3 6
样例输出
28

AC代码:

/*
题目:

意思主要是从根到叶子节点,求出一个总和最大的路径的值。

主要使用动态规划,自底向上进行动态规划,每次挑选最大的值。
*/


#include<string>
#include <iomanip>
#include<fstream>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;
/*
函数名  :main
函数功能:主函数
*/
int main(void)
{
	
	int n;
	scanf("%d", &n);
	int **reward = new int *[n];
	//输入数据
	for (int i = 0; i<n; i++)
	{
		reward[i] = new int[i + 1];
		for (int j = 0; j <= i; j++)
		{
			scanf("%d", &reward[i][j]);
		}
	}

	//自底向上,进行动态规划。
	for (int i = n - 2; i >= 0; i--)
	{
		for (int j = 0; j <= i; j++)
		{
			reward[i][j] = reward[i][j] + max(reward[i + 1][j], reward[i + 1][j + 1]);
		}
	}
	printf("%d\n", reward[0][0]);
	return  0;
}

#1143 : 骨牌覆盖问题·一

首先,这道题目是一道斐波那契数列的题目。
我们来分析一下,第三个图形是如何由前两个图形组成。

blog

 

 

扩展到第n个图形,我们有:

blog2

 

 

所以,f(n)=f(n-1)+f(n-2)

由于n可能会很大,所以我们需要一些计算的技巧。
斐波那契数列是可以由矩阵计算得到,如下:

[a,b]* [0,1] = [b,a+b]
[1,1]

令mat =
[0,1]
[1,1]

那么,理论上,我们乘以n个矩阵mat,就可以求得f(n),
但是n个矩阵相乘,时间复杂度为O(n),
这时候,我们采用快速幂运算来求解,可以把时间复杂度降为O(logn)。

其中,为了方便计算,编写了class matrix22,重载了乘法运算符。

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

骨牌,一种古老的玩具。今天我们要研究的是骨牌的覆盖问题:
我们有一个2xN的长条形棋盘,然后用1×2的骨牌去覆盖整个棋盘。对于这个棋盘,一共有多少种不同的覆盖方法呢?
举个例子,对于长度为1到3的棋盘,我们有下面几种覆盖方式:

提示:骨牌覆盖

提示:如何快速计算结果

输入

第1行:1个整数N。表示棋盘长度。1≤N≤100,000,000

输出

第1行:1个整数,表示覆盖方案数 MOD 19999997

样例输入
62247088
样例输出
17748018

AC代码:

/*
题目:
首先,这道题目是一道斐波那契数列的题目。
我们来分析一下,第三个图形是如何由前两个图形组成。
 ______           _______
|    | |   或    |  |____|
|____|_|         |__|____|

扩展到第n个图形,我们有:
 _____________           ______________
|           | |  或     |         |____|
|___________|_|         |_________|____|
所以,f(n)=f(n-1)+f(n-2)

由于n可能会很大,所以我们需要一些计算的技巧。
斐波那契数列是可以由矩阵计算得到,如下:

[a,b]* [0,1] = [b,a+b]
       [1,1]

令mat =[0,1]
       [1,1]

那么,理论上,我们乘以n个矩阵mat,就可以求得f(n),
但是n个矩阵相乘,时间复杂度为O(n),
这时候,我们采用快速幂运算来求解,可以把时间复杂度降为O(logn)。

*/

#include<string>
#include <iomanip>
#include<fstream>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;
#define MOD 19999997
class matrix22{
public:
	long long a1, a2;
	long long  b1, b2;
	matrix22() :a1(0), a2(1), b1(1), b2(1){};
	matrix22 operator*(const matrix22 tmp)
	{
		matrix22 mat;
		mat.a1 = (a1%MOD)*(tmp.a1%MOD) + (a2%MOD)*(tmp.b1%MOD);
		mat.a2 = (a1%MOD)*(tmp.a2%MOD) + (a2%MOD)*(tmp.b2%MOD);
		mat.b1 = (b1%MOD)*(tmp.a1%MOD) + (b2%MOD)*(tmp.b1%MOD);
		mat.b2 = (b1%MOD)*(tmp.a2%MOD) + (b2%MOD)*(tmp.b2%MOD);
		return mat;
	}
};
/*
函数名  :main
函数功能:主函数
*/
int main(void)
{
	int n;
	scanf("%d", &n);
	int dp1 = 1;
	int dp2 = 2;
	if (n <= 0) printf("0\n");
	else if (n == 1) printf("1\n");
	else if (n == 2) printf("2\n");
	else
	{
		n -= 3;
		matrix22 mat;
		matrix22 ans;
		while (n != 0)
		{
			//如果二进制该位为1,则ans*mat
			if (n & 1)
				ans = ans*mat;
			//mat每次与自身相乘,求得矩阵的1,2,4,8,16次方
			mat = mat*mat;
			n = (n >> 1);
		}
		//输出f(n)
		long long answer =( ans.a2 + 2 * ans.b2)%MOD;
		cout << answer << endl;

	}
	return  0;
}

#1032 : 最长回文子串

1.使用manacher算法进行检测,时间复杂度为O(n)

2.其中需要对字符串进行预处理,头部加上$,然后间隔加上#,如123变为$#1#2#3#

3.需要额外添加变量id,即最长回文的中心,mx,即最长回文的右边界

4.其中当mx>i,我们有定理p[i]>=min(p[j],mx-i),其中j为i关于id的对称点,即j=2*id-i;即直接从p[i]进行检测

5.当mx<i时,无法进行更多的预测,需要从p[i]=1开始检测

6.检测完以当前字符串为中心的回文后,如果p[i]+i大于最长回文的右边界,则进行更新mx=p[i]=i,id=i;

时间限制:1000ms
单点时限:1000ms
内存限制:64MB

描述

小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程产生了莫大的兴趣,他们约定好互相帮助,在编程的学习道路上一同前进。

这一天,他们遇到了一连串的字符串,于是小Hi就向小Ho提出了那个经典的问题:“小Ho,你能不能分别在这些字符串中找到它们每一个的最长回文子串呢?”

小Ho奇怪的问道:“什么叫做最长回文子串呢?”

小Hi回答道:“一个字符串中连续的一段就是这个字符串的子串,而回文串指的是12421这种从前往后读和从后往前读一模一样的字符串,所以最长回文子串的意思就是这个字符串中最长的身为回文串的子串啦~”

小Ho道:“原来如此!那么我该怎么得到这些字符串呢?我又应该怎么告诉你我所计算出的最长回文子串呢?

小Hi笑着说道:“这个很容易啦,你只需要写一个程序,先从标准输入读取一个整数N(N<=30),代表我给你的字符串的个数,然后接下来的就是我要给你的那N个字符串(字符串长度<=10^6)啦。而你要告诉我你的答案的话,只要将你计算出的最长回文子串的长度按照我给你的顺序依次输出到标准输出就可以了!你看这就是一个例子。”

提示一 提示二 提示三 提示四

样例输入
3
abababa
aaaabaa
acacdas
样例输出
7
5
3

AC代码:

/*
题目:
1.使用manacher算法进行检测,时间复杂度为O(n)
2.其中需要对字符串进行预处理,头部加上$,然后间隔加上#,如123变为$#1#2#3#
3.需要额外添加变量id,即最长回文的中心,mx,即最长回文的右边界
4.其中当mx>i,我们有定理p[i]>=min(p[j],mx-i),其中j为i关于id的对称点,即j=2*id-i;即直接从p[i]进行检测
5.当mx<i时,无法进行更多的预测,需要从p[i]=1开始检测
6.检测完以当前字符串为中心的回文后,如果p[i]+i大于最长回文的右边界,则进行更新mx=p[i]=i,id=i;
*/


#include<string>
#include <iomanip>
#include<fstream>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;

int manacher(string str)
{
	vector<int > p(str.size(), 0);
	int id = 1;//初始化开始检测回文的中心为1
	int mx = 0;//初始化最大的边界值为0
	for (int i = 1; i < str.size(); i++)
	{
		//如果边界值mx大于i,那么p[i] = min(p[2 * id - i], mx - i);
		if (mx > i)
			p[i] = min(p[2 * id - i], mx - i);
		//否则,无法对p[i]进行预测,令p[i]=1
		else
			p[i] = 1;
		//检测回文
		while (str[i + p[i]] == str[i - p[i]])
			p[i]++;
		//如果大于最大边界,则进行更新
		if (p[i] + i > mx)
		{
			mx = p[i] + i;
			id = i;
		}
	}
	int maxP=INT_MIN;
	for (int i = 0; i < p.size(); i++)
		maxP = max(p[i], maxP);
	return maxP - 1;
}
/*
函数名  :main
函数功能:主函数
*/
int main(void)
{
	int n;
	scanf("%d", &n);
	while (n--)
	{
		string str;
		cin >> str;
		string newStr = "$#";
		for (int i = 0; i < str.size(); i++)
		{
			newStr += str[i] ;
			newStr += '#';
		}
		cout << manacher(newStr) << endl;
	}
	return  0;
}

315. Count of Smaller Numbers After Self(Hard)

题目要求出所有元素的其右边比它小的元素个数。

我的解法:

1.先对数组进行排序,然后采用树状数组记录比当前元素出现次数少的元素的个数。如5,4,7,2,排序后为2,4,5,7,那么树状数组记录了0(比2小的元素个数),1(比4小的元素个数),2(比5小的元素个数),3(比7小的元素个数)。

2.查询的时候查询比元素nums[i]小的元素出现次数总和,查询当前元素时,对当前元素的出现次数进行-1操作(同时会更新树状数组),表示当前元素出现在后面元素的前面,后面的元素统计时不应该把这个元素的数量计算进去。

3.按照nums的次序进行查询,这样可以确保已经查询过的元素(即在当前元素左边的元素)在树状数组里面的出现次数也相应减少了,所以可以放心查询比nums[i]元素小的元素个数。

4.排序使用了set,时间复杂度为O(nlogn),后面树状数组查询操作时间复杂度为O(nlogn)。

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

AC代码:

class Solution {
public:
	vector<int> tree;
	//树状数组函数:
	int lowbit(int x)
	{
		return (x&-x);
	}

	void add(int x, int val)
	{
		for (int i = x; i<tree.size(); i += lowbit(i))
			tree[i] += val;
	}

	int get(int x)
	{
		int sum = 0;
		for (int i = x; i; i -= lowbit(i))
			sum += tree[i];
		return sum;
	}

	vector<int> countSmaller(vector<int>& nums) {

		set<int> sortNumsSet;
		map<int, int> times;

		//对nums进行排序和统计
		for (int i = 0; i<nums.size(); i++)
		{
			times[nums[i]]++;
			sortNumsSet.insert(nums[i]);
		}
		//建立树状数组
		tree = vector<int>(sortNumsSet.size() + 1, 0);

		map<int, int> pos;
		vector<int> sortNums(sortNumsSet.size(), 0);
		set<int>::iterator ite = sortNumsSet.begin();
		//复制到新的数组中,并且记录元素的位置。
		for (int i = 0; i<sortNums.size(); i++)
		{
			sortNums[i] = *ite;
			pos[sortNums[i]] = i + 1;
			ite++;
			add(i + 1, times[sortNums[i]]);
		}

		vector<int> ans(nums.size(), 0);
		for (int i = 0; i<nums.size(); i++)
		{
			//当前元素的出现次数-1
			add(pos[nums[i]], -1);
			//获取nums[i]前面的元素总数
			ans[i] = get(pos[nums[i]] - 1);
			//cout<<ans[i]<<' ';
		}

		return ans;

	}
};

307. Range Sum Query – Mutable(Medium)

该题目是一个区间求和及更新问题,使用树状数组(Binary Indexed Tree)求解。

相关文章:1057. Stack (30)

需要注意的是:

1.采用两个数组,一个是原始数据数组,一个是树状数组;

2.树状数组的下标需要从1开始,不然在使用(x&-x)时恒为0

3.更新完树状数组后,原数组也要进行更新(卡在这里);

 

Given an integer array nums, find the sum of the elements between indices i and j (ij), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.

AC代码:

class NumArray {
public:
	vector<int> num;
	vector<int> tree;

	NumArray(vector<int> &nums) {
	    //初始化两个数组,一个是num,用来存储原来的数组
		num = nums;
		//一个是树状数组,存储和信息
		tree = vector<int>(nums.size() + 1, 0);
		for (int i = 0; i < nums.size(); i++)
		{//采用add操作进行更新
			add(i + 1, nums[i]);
		}
	}

	void update(int i, int val) {
	    //求出差值,进行add
		int diff = val - num[i];
		add(i + 1, diff);
		//由于update操作设计到val-num[i],所以除了更新树状数组,原数组也需要更新
		num[i] = val;
	}

	int sumRange(int i, int j) {
	    //求出1到j+1的和,求出1到i的和,然后进行相减
		return get(j+1) - get(i);
	}
	//x=0时返回0,所以x必须>=1
	int lowbit(int x)
	{
		return (x&-x);
	}
	void add(int x, int value)
	{
		for (int i = x; i < tree.size(); i += lowbit(i))
			tree[i] += value;
	}
	
	//get操作是得到1到x的和
	int get(int x)
	{
		int sum = 0;
		for (int i = x; i; i -= lowbit(i))
			sum += tree[i];
		return sum;
	}
};

// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);

#1077 : RMQ问题再临-线段树

1.这道题目使用线段树求解。

2.其中,线段树有三个操作,初始化、更新和查询。

3.初始化操作是把数组初始化为最大值,这时尚未进行填充。数组扩展到了2的n次方大小。

4.更新操作是把值更新到叶子节点及叶子节点的祖先上,这个时候才是真正意义的初始化数组值。

5.查询使用递归实现。

6.该题比较奇怪,有时候能够ac,有时候会tle,同样的代码,但是没有想到更好的优化办法。

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

上回说到:小Hi给小Ho出了这样一道问题:假设整个货架上从左到右摆放了N种商品,并且依次标号为1到N,每次小Hi都给出一段区间[L, R],小Ho要做的是选出标号在这个区间内的所有商品重量最轻的一种,并且告诉小Hi这个商品的重量。但是在这个过程中,可能会因为其他人的各种行为,对某些位置上的商品的重量产生改变(如更换了其他种类的商品)。

小Ho提出了两种非常简单的方法,但是都不能完美的解决。那么这一次,面对更大的数据规模,小Ho将如何是好呢?

提示:其实只是比ST少计算了一些区间而已

输入

每个测试点(输入文件)有且仅有一组测试数据。

每组测试数据的第1行为一个整数N,意义如前文所述。

每组测试数据的第2行为N个整数,分别描述每种商品的重量,其中第i个整数表示标号为i的商品的重量weight_i。

每组测试数据的第3行为一个整数Q,表示小Hi总共询问的次数与商品的重量被更改的次数之和。

每组测试数据的第N+4~N+Q+3行,每行分别描述一次操作,每行的开头均为一个属于0或1的数字,分别表示该行描述一个询问和描述一次商品的重量的更改两种情况。对于第N+i+3行,如果该行描述一个询问,则接下来为两个整数Li, Ri,表示小Hi询问的一个区间[Li, Ri];如果该行描述一次商品的重量的更改,则接下来为两个整数Pi,Wi,表示位置编号为Pi的商品的重量变更为Wi

对于100%的数据,满足N<=10^6,Q<=10^6, 1<=Li<=Ri<=N,1<=Pi<=N, 0<weight_i, Wi<=10^4。

输出

对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。

样例输入
10
3655 5246 8991 5933 7474 7603 6098 6654 2414 884 
6
0 4 9
0 2 10
1 4 7009
0 5 6
1 3 7949
1 3 1227
样例输出
2414
884
7474
/*
题目:
实则为RMQ问题。
主要使用线段树求解。
*/


//#include<string>
//#include <iomanip>
#include<fstream>
//#include<set>
//#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;

const int MAX_N = 1 << 20;
int SegTree[2 * MAX_N - 1];
int n;
void init(int size)
{
	n = 1;
	//把线段树的大小扩充到2的n次方
	while (n < size) n *= 2;
	//初始化为最大值
	for (int i = 0; i < 2 * n - 1; i++)
		SegTree[i] = INT_MAX;
}

void update(int k, int val)
{
	//前面n-1个节点用来存储非叶子节点的线段树节点
	//最后的n个节点是用来存储数组
	k += n - 1;
	SegTree[k] = val;
	while (k > 0)
	{
		//找到父节点
		k = (k - 1) / 2;
		//取左右儿子的最大值
		SegTree[k] = min(SegTree[k * 2 + 1], SegTree[k * 2 + 2]);
	}
}

int query(int a, int b, int k,int l,int r)
{

	//如果[a,b)与[l,r)不相交
	if (r <= a || b <= l) return INT_MAX;
	
	//如果[a,b)包含[l,r),则返回当前节点的值
	if (a <= l && r <= b||k>n) return SegTree[k];
	else
	{//把区间分成两部分进行查询
		int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return min(vl, vr);
	}

}

/*
函数名  :main
函数功能:主函数
*/
int main(void)
{
	int sum;
	scanf("%d", &sum);
	init(sum);
	for (int i = 0; i < sum; i++)
	{
		int tmp;
		scanf("%d", &tmp);
		//初始化的时候使用update操作
		update(i, tmp);
	}
	int queryN;
	scanf("%d", &queryN);
	while (queryN--)
	{
		int operation, a, b;
		scanf("%d %d %d", &operation, &a, &b);
		if (operation == 0)
		{
			//因为查询求解的是[a,b)区间,需要注意
			printf("%d\n", query(a-1, b, 0, 0, n));
		}
		else
		{
			update(a - 1, b);
		}
	}

	return  0;
}

#1074 : 字体设计

题目:
实则为RMQ问题。

主要求出锚点,锚点即为包含区间的两端,包含区间里面的数统一大于起点,且小于终点;或者统一小于起点,且大于重点。

使用ST表进行求解,其中我们需要求出两个ST表,一个用来存储最大值的,一个用来存储最小值的。

我们通过不断递归搜索区间[l,r],找出区间中的最大值maxPos和最小值minPos的位置,然后划分为三个区间:
如果maxPos>minPos,则三个区间为:
[l,minPos],[minPos,maxPos],[maxPos,r]

如果maxPos<minPos,则三个区间为:
[l,maxPos],[maxPos,minPos],[minPos,r]

然后挑选出锚点。

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

你正在协助某人开发某种新的 Linux 下的中文字体。

现在需要给上图里的黄点做「位置锚固」,然而有些黄点的位置可以由「插值(IUP)」确定,这样就可以减少锚固的数量。

例如,在上图中,#46 #49 #52 #53 的位置可以由 #42 和 #57 插值得到, 我就不需要去锚固它们,只需要固定 #42 和 #57 就可以了。 可以给这个字减少至少 12 字节 ……

抽象一下问题,现在给出输入数组 a

定义 ax 可以被 alar 插值得到为:

存在 l < x < r

使得 al ≤ ax ≤ ar 或者 al ≥ ax ≥ ar

求最少的「锚固」元素的数目,使得非锚固元素都可以由其左右最靠近它的锚固元素插值得到。并输出锚固元素的下标。

输入

第一行输入一个数 n,表示数组的大小(1 ≤ n ≤ 105)。 接下来的一行,输入一行 n 个整数 a1, a2, …, an,表示数组中的元素(1 ≤ ai ≤ 109)。所有 ai 互不相同。

输出

输出的第一行包含一个整数 ans,表示锚固元素的数目。 接下来一行包含 ans 个递增的整数,表示锚固元素的下标。

提示

额外的样例数据:

样例输入 样例输出
7
1 2 3 10 5 6 4
3
1 4 7
样例输入
8
3 4 2 1 8 5 7 6
样例输出
7
1 2 4 5 6 7 8

AC代码:

/*
题目:
实则为RMQ问题。

主要求出锚点,锚点即为包含区间的两端,包含区间里面的数统一大于起点,且小于终点;或者统一小于起点,且大于重点。

使用ST表进行求解,其中我们需要求出两个ST表,一个用来存储最大值的,一个用来存储最小值的。

我们通过不断递归搜索区间[l,r],找出区间中的最大值maxPos和最小值minPos的位置,然后划分为三个区间:
如果maxPos>minPos,则三个区间为:
[l,minPos],[minPos,maxPos],[maxPos,r]

如果maxPos<minPos,则三个区间为:
[l,maxPos],[maxPos,minPos],[minPos,r]

然后挑选出锚点
*/


//#include<string>
//#include <iomanip>
#include<fstream>
//#include<set>
//#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;

vector<int> preLog2;
//预先计算log2数组,方便后续处理
void calPreLog2(int n,vector<int>&log2)
{
	log2[1] = 0;
	for (int i = 2; i <= n; i++)
	{
		log2[i] = log2[i - 1];
		//恰好是2的次方
		if ((1 << (log2[i] + 1)) == i)
			log2[i]++;
	}
}
vector<int> arr;
vector<vector<pair<int, int>>> stMin;
vector<vector<pair<int, int>>> stMax;

//准备st表
void ST_Prepare()
{
	for (int i = arr.size() - 1; i >= 0; i--)
	{
		stMin[i][0] = { arr[i], i };
		stMax[i][0] = { arr[i], i };
		for (int j = 1; i + (1 << j) - 1 < arr.size(); j++)
		{
			//求min
			if (stMin[i][j - 1].first < stMin[i + (1 << (j - 1))][j - 1].first)
				stMin[i][j] = stMin[i][j - 1];
			else
				stMin[i][j] = stMin[i + (1 << (j - 1))][j - 1];

			//求max
			if (stMax[i][j - 1].first > stMax[i + (1 << (j - 1))][j - 1].first)
				stMax[i][j] = stMax[i][j - 1];
			else
				stMax[i][j] = stMax[i + (1 << (j - 1))][j - 1];
		}
	}
}
//查询最小值
int queryMin(int l, int r)
{
	int len = r - l + 1;
	int k = preLog2[len];
	if (stMin[l][k].first < stMin[r - (1 << k) + 1][k].first)
		return stMin[l][k].second;
	else
		return stMin[r - (1 << k) + 1][k].second;
}
//查询最大值
int queryMax(int l, int r)
{
	int len = r - l + 1;
	int k = preLog2[len];
	if (stMax[l][k].first > stMax[r - (1 << k) + 1][k].first)
		return stMax[l][k].second;
	else
		return stMax[r - (1 << k) + 1][k].second;
}
map<int,int> ans;

//递归找出包含区间,这些区间的特点是起点和终点分别是最大值和最小值(或最小值和最大值)
void dfs(int l,int r)
{
	//求出最大值最小值的位置
	int minPos = queryMin(l, r);
	int maxPos = queryMax(l, r);
	if (l == r)
	{//如果左右相等,则压入答案后直接返回
		ans[l]=1;
		return;
	}
	//如果最大值和最小值恰好是区间的两端,则压入答案后直接返回
	else if ((l == minPos&&r == maxPos) || (l == maxPos &&r == minPos))
	{
		ans[l] = 1;
		ans[r] = 1;
		return;
	}

	//进行递归
	dfs(l, min(minPos, maxPos));
	dfs(min(minPos, maxPos), max(minPos, maxPos));
	dfs(max(minPos, maxPos), r);
}

/*
函数名  :main
函数功能:主函数
*/
int main(void)
{
	int n;
	scanf("%d", &n);
	arr = vector<int>(n, 0);
	for (int i = 0; i < n;i++)
	{
		scanf("%d", &arr[i]);
	}

	preLog2 = vector<int>(n+1, 0);
	stMin = vector<vector<pair<int, int>>>(n, vector<pair<int, int>>(32, { 0, 0 }));
	stMax = vector<vector<pair<int, int>>>(n, vector<pair<int, int>>(32, { 0, 0 }));

	//预处理求出log2,log2向下取整
	calPreLog2(n, preLog2);
	//预处理stTable,包括最大值和最小值
	ST_Prepare();
	//进行递归搜索
	dfs(0, n - 1);

	printf("%d\n", ans.size());
	for (map<int, int>::iterator ite = ans.begin(); ite != ans.end(); ite++)
	{
		printf("%d ", ite->first + 1);
	}
	printf("\n");
	return  0;
}

#1070 : RMQ问题再临

1.根据题意,进行普通的遍历操作求解。

2.使用ST表的话,更新需要O(nlogn)的时间复杂度。

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

终于,小Hi和小Ho踏上了回国的旅程。在飞机上,望着采购来的特产——小Hi陷入了沉思:还记得在上上周他们去超市的时候,前前后后挑了那么多的东西,都幸运的没有任何其他人(售货员/其他顾客)来打搅他们的采购过程。但是如果发生了这样的事情,他们的采购又会变得如何呢?

于是小Hi便向小Ho提出了这个问题:假设整个货架上从左到右摆放了N种商品,并且依次标号为1到N,每次小Hi都给出一段区间[L, R],小Ho要做的是选出标号在这个区间内的所有商品重量最轻的一种,并且告诉小Hi这个商品的重量。但是在这个过程中,可能会因为其他人的各种行为,对某些位置上的商品的重量产生改变(如更换了其他种类的商品),面对这样一个问题,小Ho又该如何解决呢?

提示:平衡乃和谐之理

输入

每个测试点(输入文件)有且仅有一组测试数据。

每组测试数据的第1行为一个整数N,意义如前文所述。

每组测试数据的第2行为N个整数,分别描述每种商品的重量,其中第i个整数表示标号为i的商品的重量weight_i。

每组测试数据的第3行为一个整数Q,表示小Hi总共询问的次数与商品的重量被更改的次数之和。

每组测试数据的第N+4~N+Q+3行,每行分别描述一次操作,每行的开头均为一个属于0或1的数字,分别表示该行描述一个询问和描述一次商品的重量的更改两种情况。对于第N+i+3行,如果该行描述一个询问,则接下来为两个整数Li, Ri,表示小Hi询问的一个区间[Li, Ri];如果该行描述一次商品的重量的更改,则接下来为两个整数Pi,Wi,表示位置编号为Pi的商品的重量变更为Wi

对于100%的数据,满足N<=10^4,Q<=10^4, 1<=Li<=Ri<=N,1<=Pi<=N, 0<weight_i, Wi<=10^4。

输出

对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。

样例输入
10
618 5122 1923 8934 2518 6024 5406 1020 8291 2647 
6
0 3 6
1 2 2009
0 2 2
0 2 10
1 1 5284
0 2 5
样例输出
1923
2009
1020
1923

AC代码:

//#include<string>
//#include <iomanip>
#include<fstream>
//#include<set>
//#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;
/*
根据题意,使用普通的遍历操作
*/
/*
函数名  :main
函数功能:主函数
*/
int main(void)
{
	int n;
	scanf("%d", &n);
	vector<int> weight(n, 0);
	for (int i = 0; i < n;i++)
	{
		scanf("%d", &weight[i]);
	}

	int queryN;
	scanf("%d", &queryN);
	while (queryN--)
	{
		int operation;
		int a, b;
		scanf("%d %d %d",&operation, &a, &b);
		//进行修改操作
		if (operation == 1)
			weight[a - 1] = b;
		else
		{//进行查询操作
			int result = INT_MAX;
			for (int i = a - 1; i < b; i++)
				result = min(weight[i], result);
			printf("%d\n", result);
		}
	}

	return  0;
}

#1068 : RMQ-ST算法

这道题目主要是求解RMQ问题,给出某个查询的范围,求出该范围里面的最小值。

注意输入的查询是1到N,需要进行-1操作。

使用了ST算法,ST算法的详细说明为:ST表(Sparse Table)

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi和小Ho在美国旅行了相当长的一段时间之后,终于准备要回国啦!而在回国之前,他们准备去超市采购一些当地特产——比如汉堡(大雾)之类的回国。

但等到了超市之后,小Hi和小Ho发现者超市拥有的商品种类实在太多了——他们实在看不过来了!于是小Hi决定向小Ho委派一个任务:假设整个货架上从左到右拜访了N种商品,并且依次标号为1到N,每次小Hi都给出一段区间[L, R],小Ho要做的是选出标号在这个区间内的所有商品重量最轻的一种,并且告诉小Hi这个商品的重量,于是他们就可以毫不费劲的买上一大堆东西了——多么可悲的选择困难症患者。

(虽然说每次给出的区间仍然要小Hi来进行决定——但是小Hi最终机智的选择了使用随机数生成这些区间!但是为什么小Hi不直接使用随机数生成购物清单呢?——问那么多做什么!)

提示一:二分法是宇宙至强之法!(真的么?)

提示二:线段树不也是二分法么?

输入

每个测试点(输入文件)有且仅有一组测试数据。

每组测试数据的第1行为一个整数N,意义如前文所述。

每组测试数据的第2行为N个整数,分别描述每种商品的重量,其中第i个整数表示标号为i的商品的重量weight_i。

每组测试数据的第3行为一个整数Q,表示小Hi总共询问的次数。

每组测试数据的第N+4~N+Q+3行,每行分别描述一个询问,其中第N+i+3行为两个整数Li, Ri,表示小Hi询问的一个区间[Li, Ri]。

对于100%的数据,满足N<=10^6,Q<=10^6, 1<=Li<=Ri<=N,0<weight_i<=10^4。

输出

对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。

样例输入
10
7334
1556
8286
1640
2699
4807
8068
981
4120
2179
5
3 4
2 8
2 4
6 8
7 10
样例输出
1640
981
1556
981
981

AC代码:

//#include<string>
//#include <iomanip>
#include<fstream>
//#include<set>
//#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;

/*
这道题目主要是求解RMQ问题,给出某个查询的范围,求出该范围里面的最小值。

使用了ST算法,ST算法的详细说明为:http://maybi.cn/wp_siukwan/?p=830
*/

//stTable的准备函数
void ST_Prepare(vector<int> a, vector<vector<int>>&stTable)
{
	for (int i = a.size()-1; i >=0; i--)
	{
		//初始化0
		stTable[i][0] = a[i];
		//使用动态规划计算出stTable
		for (int j=1; i + (1<<j) -1 < a.size(); j++)
		{
			stTable[i][j] = min(stTable[i][j - 1], stTable[i + (1<<(j-1)) ][j - 1]);
		}
	}
}

int queryMin(int l, int r, vector<vector<int>>&stTable)
{
	int len = r - l + 1;
	int k = 0;
	int tmpLen = len;
	//求出合适的指数k
	while (tmpLen != 1)
	{
		k++;
		tmpLen = (tmpLen >> 1);
	}
	return min(stTable[l][k], stTable[r - (1 << k) + 1][k]);
}

/*
函数名  :main
函数功能:主函数
*/
int main(void)
{
	int n;
	scanf("%d", &n);
	vector<int> a(n, 0);
	for (int i = 0; i < n;i++)
	{
		scanf("%d", &a[i]);
	}

	vector<vector<int>>stTable(n, vector<int>(32, 0));
	ST_Prepare(a, stTable);

	int queryN;
	scanf("%d", &queryN);
	while (queryN--)
	{
		int l, r;
		scanf("%d %d", &l, &r);
		int answer = queryMin(l-1, r-1, stTable);
		printf("%d\n", answer);
	}

	return  0;
}