考虑到第四场题目难度过大，加了两道水题
结果就只做出这两道水题
Hdu 5327 Olympiad
链接
Olympiad
题意
统计区间[a,b]内满足各位数字不同的数的个数
分析
多区间查询，若每次都计算个数效率非常低，可以预处理，先标记[1,100000]内每个数是否满足条件，再用s[i]累计区间[1,i]的满足条件的总个数
计算[a,b]的个数，只需用s[b]-s[a-1]即可
代码
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
| #include<stdio.h>
const int N=100000;
int s[N+10];
void init()
{
for(int i=1;i<=N;i++){
bool flag[10]={false};
int t=i;
while(t){
if(flag[t%10])
break;
flag[t%10]=true;
t/=10;
}
s[i]=s[i-1];
if(!t)
s[i]++;
}
}
int main()
{
init();
int T;
scanf("%d",&T);
while(T--){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",s[r]-s[l-1]);
}
return 0;
}
|
Hdu 5328 Problem Killer
链接
Problem Killer
题意
给定长度为n的数列，求最长的区间[l,r]满足
区间[l,r]形成的数列必须为等差数列或者等比数列
分析
等差数列公差相等，等比数列公比相等
可以求出原数列所有相邻两项的差和比，
然后求最长的连续相等序列的长度
代码
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
| #include<stdio.h>
#define max(a,b) a>b?a:b
const int N=1000000;
int n;
double a[N+10],b[N+10],c[N+10];
int solve(double x[])
{
int l=1,cnt=0;
while(l<n){
int r=l;
while(r<n&&x[r]==x[l])
r++;
cnt=max(cnt,r-l);
l=r;
}
return cnt;
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf",&a[i]);
for(int i=1;i<n;i++){
b[i]=a[i+1]-a[i];
c[i]=a[i+1]/a[i];
}
int ans=0;
ans=max(ans,solve(b));
ans=max(ans,solve(c));
printf("%d\n",ans+1);
}
return 0;
}
|