题目链接

A.动态点分治 模拟

题目链接

---

#include<cstdio>
typedef long long ll;
int t,find;
ll l,r,k,x;
int main()
{
	//freopen("in.txt","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
    	find=0;
    	scanf("%lld%lld%lld",&l,&r,&k);
    	switch(k){
    		case 0:{
    			if(l<=0&&0<=r)printf("0 "),find=1;
			}
			case 1:{
				if(l<=1&&1<=r)printf("1 "),find=1;
				break;
			}
			default:for(x=1;;)
			{
					if(l<=x&&x<=r)printf("%lld ",x),find=1;
					if(x<=r/k)x*=k;else break;
			}
		}
		if(!find)puts("None.");else puts("");
	}
	return 0;
} 

总结

根据题目模拟

---

B.区间 乱搞

题目链接

---

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e7+10;
ll a[MAXN];
int r[MAXN],N,ans=1;
#define RG register
#define getc() (S == T && (T = (S = B) + fread(B, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
char B[1 << 15], *S = B, *T = B;
inline long long F() {
	RG char ch; RG long long x = 0; RG bool m = 0;
	while (ch = getc(), (ch < '0' || ch > '9') && ch != '-') ;
	ch == '-' ? m = 1 : x = ch - '0';
	while (ch = getc(), ch >= '0' && ch <= '9') x = x * 10 + ch - '0';
	return m ? -x : x;
}
int main()
{
	//freopen("in.txt","r",stdin);
	N=F();ll v;
	for(int i = 1; i <= N; ++i) a[i] = F();
    for(int i = 1, j = 1; i <= N; ++i) {v = a[i]; while(j <= N && a[j] % v == 0) ++j; r[i] = j;}
	for(int i = N, j = N; i >= 1; --i) {v = a[i]; while(j >= 1 && a[j] % v == 0) --j; if(r[i] - j - 1 > ans) ans = r[i] - j - 1;}
	printf("%d\n",ans);
	return 0;
}

总结

无

---

C.灭虫 线性DP+堆优化

题目链接

---

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=3e3+10;
struct node{
	int p,l,r;
	bool operator <(const node&rhs)const{
	return p<rhs.p;}
}v[N];
int n,h[N*3],H,f[N][N*3],pre[N][N];
inline int ID(int p){return lower_bound(h+1,h+H+1,p)-h;}
int main()
{
	//freopen("in.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	    scanf("%d%d%d",&v[i].p,&v[i].l,&v[i].r);
	for(int i=1;i<=n;i++)
	{
		h[++H]=v[i].p-v[i].l;
		h[++H]=v[i].p;
		h[++H]=v[i].p+v[i].r;
	}
	sort(v+1,v+n+1);sort(h+1,h+H+1);H=unique(h+1,h+H+1)-h-1;
	for(int i=1;i<=n;i++)
	{
		pre[i+1][i]=v[i].p;
		for(int j=i;j<=n;j++)
		    pre[i][j]=min(pre[i][j-1],v[j].p-v[j].l);
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int p=ID(v[i].p),l=ID(v[i].p-v[i].l);
		priority_queue<pair<int,int> >q;
		for(int k=1;k<=i;k++)
		    q.push({f[k-1][ID(pre[k+1][i])]-pre[k+1][i],v[k].p+v[k].r});
		for(int j=1;j<=H;j++)
		{
			f[i][j]=f[i][j-1];
			if(j<=p)f[i][j]=max(f[i][j],(j<l)?f[i-1][j]:(f[i-1][l]+h[j]-h[l]));
			else
			{
				while(q.size()&&q.top().second<h[j])q.pop();
				if(q.size())f[i][j]=max(f[i][j],q.top().first+h[j]);
			}
			ans=max(ans,f[i][j]);
		}
	}
	printf("%d\n",ans);
	return 0;
}

总结

线性DP好题