Sure之ACM题解
I
给出1~n的一个排列，统计该排列有多少个长度为奇数的连续
子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于
中间的数。
输入:
第一行为两个正整数n和b，第二行为1~n的排列。
输出:
输出一个整数，即中位数为b的连续子序列个数。
样例输入：
54
12345
样例输出：
2
样例输入：
74
5724316
样例输出：
4
提示：
第三个样例解释：{4},{7,2,4},{5,7,2,4,3}和{5,7,2,4,3,1,6}。
对于40%的数据，n<=300;
对于80%的数据，n<=25000;
对于全部的数据，n<=100000。
解题分析：
1.思路应该来说还是比较清晰的，数据预处理(比b小的数赋值为-1，
b赋值为0，比b大的数赋值为1)。则包含b并且序列和为0的连
续子序列即为所求。
2.求数组区间和问题，似乎是树状数组的优势O(logn)。
3.假设原数组为a[n]，我们是否可以求出c[n]=a[1]+a[2]+…+a[n],
从k1到k2区间和就转化为c[k2]-c[k1]=0,也就是说满足
c[k1]=c[k2](其中1<=k1
hash数组来保存b两端的c[n]的值。
Sure之ACM题解
II
4.细节很重要。
①hash是以数组的值为下标的，下标的值有负数怎么处理，现在
采用的方法c[n]+length,不会发生冲突；
②b为1或者n的时候；b在序列的第一位时；(边界情况要注意)
③后端(b以后包含b)中，c[i]出现0时，即1~i序列已经满足
条件，需要单独计算。
④如果数据量很大的时候，数组是采用栈分配还是堆分配。
补充：单循环求两数组中相同的数
如果都为整数可以采取与本题相同的方法。
如果不含重复的数字可以这样做：
先分别排序再遍历。O(nlogn)
intIsMiddleNum(inttest_value[],intlength_sequence,intmiddle
_location){
intis_middle=0;
sort(test_value,test_value+middle_location);
sort(test_value+middle_location,test_value+length_sequence
+1);
inti=0,j=middle_location;
while(i
{
if(test_value[i]==test_value[j])
{
is_middle++;
i++;
j++;
}
if(test_value[i]>test_value[j])
j++;
if(test_value[i]
i++;
}
returnis_middle;
}
Sure之ACM题解
III
附C源码：
#include
usingnamespacestd;
voidIsMiddleNum(inttest_value[],intlength_sequence,intmiddl
e_location){
inthash1[100006]={0};
inthash2[100006]={0};
intis_middle=0;
inti;
if(middle_location==1)
{
for(i=1;i<=length_sequence;i++)
if(test_value[i]==0)
is_middle++;
}
else{
for(i=1;i
{
if(test_value[i]<0)
hash1[test_value[i]+length_sequence]++;
else
hash1[test_value[i]]++;
}
for(i=middle_location;i<=length_sequence;i++)
{
if(test_value[i]<0)
hash2[test_value[i]+length_sequence]++;
else
hash2[test_value[i]]++;
}
for(i=0;i<=length_sequence;i++)
is_middle+=(hash1[i]hash2[i]);
is_middle+=hash2[0];
}
cout<
}
intmain()
{
intmiddle,length_sequence,middle_location;
inttest_num=newint[100006];
inttest_value=newint[100006];
cin>>length_sequence>>middle;
intsum=0;
Sure之ACM题解
IV
for(inti=1;i<=length_sequence;i++)
{
cin>>test_num[i];
if(test_num[i]
test_num[i]=-1;
if(test_num[i]==middle)
{
test_num[i]=0;
middle_location=i;
}
if(test_num[i]>middle)
test_num[i]=1;
sum+=test_num[i];
test_value[i]=sum;
}
if((middle==1)||(middle==length_sequence))
cout<<"1"<
else
IsMiddleNum(test_value,length_sequence,middle_location);
delete[]test_num;
delete[]test_value;
return0;
}
|
|
