hihocoder编程练习赛51

自用笔记算法

B

描述

恺撒密码是一种古老的加密方法。它将26个英文字母’A’-‘Z’向左循环移动K位，得到新的密码表。
例如K=2，有:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
CDEFGHIJKLMNOPQRSTUVWXYZAB
则用’C’替代’A’，’D’替代’B’……
对于两个只包含大写字母的字符串A和B，如果A和B长度相同，并且A可以通过某种(某个K)恺撒加密得到B，我们就认为A和B是相似的。
例如”ABC”与”DEF”相似，”HI”与”ZA”相似。显然”相似”关系具有传递性和对称性。
给定N个字符串，请你将相似的字符串聚成一类，并输出最终有几个不同的类别。

输入
第一行包含一个整数N。
以下N行每行包含一个字符串S。S只包含大写字母。
对于50%的数据，1 ≤ N ≤ 100，N个字符串总长度不超过10000。
对于100%的数据，1 ≤ N ≤ 100000，N个字符串总长度不超过1000000。

输出
一个整数表示答案。

样例输入
6
ABC
DEF
ZAB
HIHO
JKJQ
NONU

样例输出
2

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
int n;
set<string>ss;
int main(){
//	freopen("input.txt","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		for(int j=1;j<s.length();j++) s[j]=(s[j]-s[0]+26)%26+'A';
		s[0]='A';
		ss.insert(s);
	}
	cout<<ss.size()<<endl;
	return 0;
}

思路

把每个字符串的开头都移动到A 判断有多少个相等的字符串
放到set里 求size即可
注意s[0]要最后赋值 因为比较时每个字符要与原来的第一个字符算出差值 因为存在环 所以+26 mod 26

C

描述
给定N个整数A1, A2, … AN，小Hi会询问你M个问题。
对于每个问题小Hi给出两个整数L和R(L ≤ R)，请你找出[AL, AL+1, AL+2, … AR]中最长的等差连续子数列，并输出其长度。
例如[2, 3, 5, 7, 9]中最长的等差连续子数列是[3, 5, 7, 9]长度为4。

输入
第一行包含两个整数N和M。
第二行包含N个整数A1, A2, … AN。
以下M行每行包含两个整数L和R，代表一次询问。
对于30%的数据，1 ≤ N, M ≤ 1000
对于100%的数据，1 ≤ N, M ≤ 100000 0 ≤ Ai ≤ 10000000

输出
依次对于每个询问输出一个整数，代表答案。

样例输入
6 2
1 2 3 5 7 9
2 6
1 4

样例输出
4
3

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
#define maxn 100050
using namespace std;
int n,m;
int a[maxn],tmp[maxn];
int dp1[maxn][18],dp2[maxn][18];   
void makermq(int b[]){
    for(int i=0;i<n;i++) dp1[i][0]=b[i];
    for(int j=1;(1<<j)<=n;j++){
    	for(int i=0;i+(1<<j)-1<n;i++) dp1[i][j]=max(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);  
	}
}
int rmq(int s,int v){ 
    int k=(int)(log((v-s+1)*1.0)/log(2.0));  
    return max(dp1[s][k],dp1[v-(1<<k)+1][k]);  
}
void makeRmqIndex(int b[]){
    for(int i=0;i<n;i++) dp2[i][0]=i;  
    for(int j=1;(1<<j)<=n;j++){
    	for(int i=0;i+(1<<j)-1<n;i++)  
            dp2[i][j]=b[dp2[i][j-1]] > b[dp2[i+(1<<(j-1))][j-1]]? dp2[i][j-1]:dp2[i+(1<<(j-1))][j-1];  
	}
}  
int rmqIndex(int s,int v,int b[]){ 
    int k=(int)(log((v-s+1)*1.0)/log(2.0));  
    return b[dp2[s][k]] > b[dp2[v-(1<<k)+1][k]]? dp2[s][k]:dp2[v-(1<<k)+1][k];  
}  
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	memset(tmp,0,sizeof tmp);
	tmp[n-1]=1,tmp[n-2]=2;
	for(int i=n-3;i>=0;i--){
		if(a[i]-a[i+1]==a[i+1]-a[i+2]) tmp[i]=tmp[i+1]+1;
		else tmp[i]=2;
	}
	makermq(tmp);
	makeRmqIndex(tmp);
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		x--,y--;
		int num1=rmq(x,y),pos=rmqIndex(x,y,tmp);
		if(pos+num1<=y) printf("%d\n",num1);
		else{
			if(pos-1>=x){
				int num2=rmq(x,pos-1);
				printf("%d\n",max(num2,y-pos+1)); 
			}
			else printf("%d\n",y-pos+1);
		}
	}
	return 0;
}

思路

on预处理出每个数字向右延伸最远的连续等差数列长度
每次在l到r的区间内找出长度的最大值len 用rmq 以及该最大值的位置pos
判断pos+len是否≤r 若满足说明符合条件 直接输出
否则说明len的长度超出了r的限制 这一部分的长度实际为r-pos+1 要与左侧剩下的x到pos-1的位置中的最大值(依然用rmq) 两者求max
所求就是答案

本文标题:hihocoder编程练习赛51

文章作者:Hippopmonkey

发布时间:2018-03-20, 22:49:39

最后更新:2018-03-26, 20:37:49

原始链接:http://xuboming8.github.io/2018/03/20/hihocoder编程练习赛51/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. B
    1. 1.1. 参考AC代码
    2. 1.2. 思路
  2. 2. C
    1. 2.1. 参考AC代码
    2. 2.2. 思路
|