最近真是太废柴了，题没做几道，也没学什么新知识，多校做了三场也没总结~诶！好好学吧！
多校第一场感觉被完虐...orz...
Hdu 5288 OO’s Sequence
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5288
题意：
f(l,r)表示满足ai%aj≠0的i的个数(i∈[l,r],j∈[l,r],j≠i)
已知n个数 a1,a2,…an,求
思路：这个题实质是对于一个包含ai的区间，如果ai符合上述条件，即对于aj,ai%aj≠0，则aj不是ai的因子
对于每一个数ai,分别向左向右去找离它最近的因子的下标L[i],R[i],ans+=(i-L[i])*(R[i]-i);
参考代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
const int N=;
#define Mod 1000000007
using namespace std;
int a[N+],id[N+],L[N+],R[N+];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=; i<=n; i++)
scanf("%d",&a[i]);
memset(id,,sizeof(id));
for(int i=; i<=n; i++) //向左找最近的因子下标
{
L[i]=;
for(int j=; j*j<=a[i]; j++)
if(a[i]%j==) //j和a[i]/j都为a[i]的因子
{
if(id[j])
L[i]=max(L[i],id[j]); //取最大的下标即为最近的
if(id[a[i]/j])
L[i]=max(L[i],id[a[i]/j]);
}
id[a[i]]=i; //记录a[i]的下标
}
memset(id,,sizeof(id));
for(int i=n; i>=; i--) //向右找最近的因子下标
{
R[i]=n+;
for(int j=; j*j<=a[i]; j++)
if(a[i]%j==)
{
if(id[j])
R[i]=min(R[i],id[j]);
if(id[a[i]/j])
R[i]=min(R[i],id[a[i]/j]);
}
id[a[i]]=i;
}
long long ans=;
for(int i=; i<=n; i++)
ans=(ans+(long long)(i-L[i])*(R[i]-i)%Mod)%Mod;
printf("%I64d\n",ans);
}
return ;
}
Assignment
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5289
题意： 求有多少个区间满足区间内任意两个数的差值小于k
思路： 区间内最大差值为区间内最大值与最小值的差，只要其差满足条件，
则该区间符合条件左区间l先固定,去找最大区间符合条件，即[l,r-1]符合，
那么ans+=(（r−l）/2)+r−l，然后r不变，l不断加1，直到找到符合条件的 [l,r]为止，
那么[l,j-1]会被重复算，需要减掉.
为了更快的查询每个区间的最大最小值，用线段树实现
参考代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; #define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define MID(a,b) (a+((b-a)>>1))
const int N=;
#define INF (1<<30)
struct node
{
int lft,rht;
int maxm;
int minm;
int mid()
{
return MID(lft,rht);
}
};
struct Segtree
{
node tree[N*];
void build(int lft,int rht,int rt)
{
tree[rt].lft=lft;
tree[rt].rht=rht;
tree[rt].maxm=-INF;
tree[rt].minm=INF;
if(lft==rht)
{
scanf("%d",&tree[rt].minm);
tree[rt].maxm=tree[rt].minm;
}
else
{
int mid=tree[rt].mid();
build(lft,mid,LL(rt));
build(mid+,rht,RR(rt));
tree[rt].maxm=max(tree[LL(rt)].maxm,tree[RR(rt)].maxm);
tree[rt].minm=min(tree[LL(rt)].minm,tree[RR(rt)].minm);
}
}
int querymaxm(int st,int ed,int rt)
{
int lft=tree[rt].lft,rht=tree[rt].rht;
if(st<=lft&&rht<=ed)
return tree[rt].maxm;
else
{
int mid=tree[rt].mid();
int sum1=-INF,sum2=-INF;
if(st<=mid)
sum1=querymaxm(st,ed,LL(rt));
if(ed>mid)
sum2=querymaxm(st,ed,RR(rt));
return max(sum1,sum2);
}
}
int queryminm(int st,int ed,int rt)
{
int lft=tree[rt].lft,rht=tree[rt].rht;
if(st<=lft&&rht<=ed)
return tree[rt].minm;
else
{
int mid=tree[rt].mid();
int sum1=INF,sum2=INF;
if(st<=mid)
sum1=queryminm(st,ed,LL(rt));
if(ed>mid)
sum2=queryminm(st,ed,RR(rt));
return min(sum1,sum2);
}
}
} seg;
__int64 f(__int64 n)
{
if(n%)
{
return (n-)/*n;
}
return n/*(n-);
}
int main()
{
int T;
int i,j;
int n,k;
scanf("%d",&T);
while(T--)
{
__int64 sum=;
scanf("%d%d",&n,&k);
seg.build(,n,);
i=;
j=;
while(i<=n&&j<=n)
{
int ma=seg.querymaxm(i,j,);
int mi=seg.queryminm(i,j,);
if((ma-mi)>=k)
{
sum+=(j-i)+f(j-i);
i++;
for(; i<j; i++)
{
if((seg.querymaxm(i,j,)-seg.queryminm(i,j,))<k)
{
sum-=(j-i)+f(j-i);
j++;
break;
}
}
}
else
{
if(j==n)
sum+=(j-i+)+f(j-i+);
j++;
}
}
printf("%I64d\n",sum);
}
return ;
}