[Contest on 2021.8.31] 。

\(\text{Fansblog}\)

解法

用威尔逊定理。这里有个结论:

结论:\(10^{18}\) 范围内,两个相邻质数的差在 \(100\) 数量级。

\(\text{Lattice Animals}\)

解法

真的废啊,连 \(n\le 5\) 的表都打挂了。现在也发现 \(\min(w,h)=2\) 的做法也挺难写的…

set 维护一个图形,再用一个 set 维护点个数为 \(i\) 的图形。每次从点个数为 \(i\) 的图形 set 中取出图形,再拓展点,判断是否合法。

具体需要一个 normalize() 来使图形紧贴 \(x,y\) 轴。除此之外,还需要实现 rotate()flip() 函数将图形旋转 \(90\) 度,沿 \(x\) 轴翻折。\(y\) 轴翻折相当于沿 \(x\) 轴翻折后再旋转 \(180\) 度。

代码

#include <cstdio>
#define print(x,y) write(x),putchar(y)

template <class T>
inline T read(const T sample) {
	T x=0; char s; bool f=0;
	while((s=getchar())>‘9‘ or s<‘0‘)
		f|=(s==‘-‘);
	while(s>=‘0‘ and s<=‘9‘)
		x=(x<<1)+(x<<3)+(s^48),
		s=getchar();
	return f?-x:x;
}

template <class T>
inline void write(const T x) {
	if(x<0) {
		putchar(‘-‘),write(-x);
		return;
	}
	if(x>9) write(x/10);
	putchar(x%10^48);
}

#include <set>
#include <iostream>
using namespace std;

int ans[11][11][11];
struct node {
	int x,y;
	node() {}
	node(int X,int Y):x(X),y(Y){}
	
	bool operator < (const node &t) const {
		return (x^t.x)?x<t.x:y<t.y;
	}
};
typedef set<node> poly;
typedef poly :: iterator Type;
set <poly> buc[11];
set <poly> :: iterator it;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

poly normalize(const poly &t) {
	poly r;
	int xx=t.begin()->x,yy=t.begin()->y;
	for(Type it=t.begin();it!=t.end();++it)
		xx=min(xx,it->x),
		yy=min(yy,it->y);
	for(Type it=t.begin();it!=t.end();++it)
		r.insert(node(it->x-xx,it->y-yy));
	return r;
}

poly rotate(const poly &t) {
	poly r;
	for(Type it=t.begin();it!=t.end();++it)
		r.insert(node(it->y,-it->x));
	return normalize(r);
}

poly flip(const poly &t) {
	poly r;
	for(Type it=t.begin();it!=t.end();++it)
		r.insert(node(it->x,-it->y));
	return normalize(r);
}

void ins(const poly &t,const node &p) {
	poly r=t;
	r.insert(p);
	r=normalize(r);
	int n=r.size();
	for(int i=0;i<4;++i) {
		if(buc[n].count(r))
			return;
		r=rotate(r);
	}
	r=flip(r);
	for(int i=0;i<4;++i) {
		if(buc[n].count(r))
			return;
		r=rotate(r);
	}
	buc[n].insert(r);
}

void init() {
	poly cur;
	cur.insert(node(0,0));
	buc[1].insert(cur);
	for(int siz=1;siz<10;++siz) {
		for(it=buc[siz].begin();it!=buc[siz].end();++it)
			for(Type IT=(*it).begin();IT!=(*it).end();++IT) {
				for(int i=0;i<4;++i) {
					node t=node(IT->x+dir[i][0],IT->y+dir[i][1]);
					if(!(it->count(t)))
						ins(*it,t);
				}
			}
	}
	for(int siz=1;siz<=10;++siz) {
		for(int p=1;p<=10;++p)
			for(int q=1;q<=10;++q) {
				for(it=buc[siz].begin();it!=buc[siz].end();++it) {
					int xx=0,yy=0;
					for(Type i=(*it).begin();i!=(*it).end();++i)
						xx=max(xx,i->x),
						yy=max(yy,i->y);
					if(min(xx,yy)<min(p,q) and max(xx,yy)<max(p,q))
						++ans[siz][p][q];
				}
			}
	}
}

int main() {
	init();
	int s,n,m;
	while(~scanf("%d %d %d",&s,&n,&m)) {
		if(s>n*m) puts("0");
		else print(ans[s][n][m],‘\n‘);
	}
	return 0;
}

\(\text{[CEOI 2014] Match}\)

题目描述

给出两个长度分别为 \(n,m\) 的序列 \(A,B\),求出 \(B\) 的所有长度为 \(n\) 的连续子序列(子串),满足:序列中第 \(i\) 小的数在序列的 \(A_i\) 位置。其中 \(A\) 是一个排列,\(B\) 中的数字各不相同。

\(2\le n,m\le 10^6,1\le B_i\le 10^9\)

解法

首先将序列 \(A\) 转化一下,令 \(C_{A_i}=i\),那么其实就是求 \(B\) 中长度为 \(n\) 的连续子序列离散化之后与 \(C\) 相同。再转化一下,对于 \(i\in[l,l+n)\),令 \(t_i\) 为在区间 \([l,i]\) 中小于 \(B_i\) 的数字个数,相应地,对应 \(C\) 处理出 \(s_i\),那么当 \(\forall i\in[l,l+n),s_{i-l+1}=t_i\),这个子序列就是合法的。

这与 \(\mathtt{kmp}\) 很类似,区别就是 \(t_i\) 是需要动态维护的。在撤销也即令 \(p=nxt_p\) 时,相当于把 \([(i-1)-p+1,(i-1)-nxt_p]\) 从子序列中删除,需要用一个树状数组维护。可以发现,长度为 \(1\) 是一定可以匹配的,所以也不用特判无解的情况。

分析一下时间复杂度。对于 \(p\),每次只能增加 \(1\),所以最多达到 \(n\)。在撤销的时候,\(p\)\(1\) 对应一次 \(\mathcal O(\log m)\) 的树状数组修改。所以时间复杂度是 \(\mathcal O((n+m)\cdot \log m)\) 的。

另:还有一个 \(\mathcal O(n)\) 的做法,但我着实没看懂…

代码

#include <cstdio>
#define print(x,y) write(x),putchar(y)

template <class T>
inline T read(const T sample) {
	T x=0; char s; bool f=0;
	while((s=getchar())>‘9‘ or s<‘0‘)
		f|=(s==‘-‘);
	while(s>=‘0‘ and s<=‘9‘)
		x=(x<<1)+(x<<3)+(s^48),
		s=getchar();
	return f?-x:x;
}

template <class T>
inline void write(const T x) {
	if(x<0) {
		putchar(‘-‘),write(-x);
		return;
	}
	if(x>9) write(x/10);
	putchar(x%10^48);
}

#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn=1e6+5;

int n,m,c[maxn];
int a[maxn],b[maxn];
int v[maxn],s[maxn];
int nxt[maxn];
vector <int> ans;

int lowbit(int x) {
	return x&-x;
}

void add(int x,int k) {
	while(x<=m)
		c[x]+=k,
		x+=lowbit(x);
}

int ask(int x) {
	int r=0;
	while(x)
		r+=c[x],
		x-=lowbit(x);
	return r;
}

int main() {
	n=read(9),m=read(9);
	for(int i=1;i<=n;++i) {
		int x=read(9);
		s[x]=i; 
	}
	for(int i=1;i<=n;++i)
		v[i]=ask(s[i]),
		add(s[i],1);
	for(int i=1;i<=m;++i)
		a[i]=b[i]=read(9);
	memset(c,0,sizeof c);
	int p=0;
	for(int i=2;i<=n;++i) {
		while(v[p+1]^ask(s[i])) {
			for(int j=i-p;j<i-nxt[p];++j)
				add(s[j],-1);
			p=nxt[p];
		}
		nxt[i]=++p;
		add(s[i],1);
	}
	memset(c,0,sizeof c);
	p=0; 
	sort(b+1,b+m+1);
	for(int i=1;i<=m;++i) {
		a[i]=lower_bound(b+1,b+m+1,a[i])-b;
		while(p==n or (v[p+1]^ask(a[i]))) {
			for(int j=i-p;j<i-nxt[p];++j)
				add(a[j],-1);
			p=nxt[p];
		}
		++p;
		if(p==n) ans.push_back(i-n+1);
		add(a[i],1);
	}
	print(ans.size(),‘\n‘);
	for(auto i:ans)	
		print(i,‘ ‘);
	puts("");
	return 0;
}

[Contest on 2021.8.31] 。

上一篇:Photoshop将制作出漂亮的带青色花纹的立体字效果


下一篇:Photoshop为森林人物图片打造梦幻的暗蓝色特效