前言

还有不到 10 天就要 CSP-S 。。。马上我就要有我的第一篇游记了。

今天考试莽了一回，整了大概 2.5h 的 T1 ，可能是因为今天题目比较难，看起来成效不错。

以后还是要注意时间的分配（可是今天后面的题目看起来是真不可做。。）

T1 洛希极限

解题思路

正解不会。。但是貌似 \(\mathcal{O}(nm+nmlogn)\) 吸氧可以过。。（达成成就：考场唯一切题，切了但没完全切）

发现如果没有矩形的限制的话对于一个格子 \((i,j)\) 转移状态可以来自以它为右下角的矩形区域。

那么考虑优化，对于一个在上述合法区域内的点，如果它与 \((i,j)\) 的横坐标和者纵坐标之差都超过了 1 ，那么这个节点一定不是最大值。

至于原因的话，它一定可以跳到某一个中转点，于是我们成功的将复杂度由 \((n^4)\) 降到了 \(n^3\) 。

然后再每一行每一列开一颗线段树维护就可以得到 \(n^2logn\) 的复杂度。

然后瓶颈在于初始化每个点列和行上可以达到的最小值，然后我考场上就开始瞎搞，复杂度就玄学。。。（code）

一开始看了看大样例吸氧 3.7s 左右，这不是稳过？？，然后一看，评测机居然没开氧气，我***。

尝试着不吸氧 12s 于是开始大力剪枝+卡常，最终在 OJ 上只多了 5pts 这么点？？？，我的四十分钟啊（卡常之后，OJ没过但是教师机过了的code）

考后问了一下 zero4338 大概就是维护一个链表（战神叫他并茶几。。）每次更新列的。

如果一行都跳完了行指针下移就好了。

然后我发现对于列的限制用链表较快，对于行的限制我的瞎搞做法较快。

如果 OJ 没有氧的话就需要继续卡常+非法预处理了（逃

code

//%:pragma GCC optimize(2)

//%:pragma GCC optimize(3)

//%:pragma GCC optimize("inline")

//%:pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define ll long long

#define ull unsigned long long

#define f() cout<<"Failed"<<endl

#define ls x<<1

#define rs x<<1|1

using namespace std;

inline int read()

{

	int x=0,f=1;char ch=getchar();

	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}

	return x*f;

}

const int N=2e3+10,M=5e5+10,INF=1e9;

const int mod=1e9+7;

int T,q,n,m,cnt,nxt[N][N],nxt2[N],h[N][N],z[N][N];

struct Node{int x,y,x2,y2;}s[M];

struct node

{

	int mx,dat;

	inline node friend operator + (node x,node y)

	{

		if(x.mx>y.mx) return x;

		if(y.mx>x.mx) return y;

		register int temp=1ll*x.dat+y.dat;

		if(temp>=mod) temp-=mod;

		return (node){x.mx,temp};

	}

}ans;

#define int register int

struct Segment_Tree

{

	node tre[N<<2];

	#define push_up(x) tre[x]=tre[ls]+tre[rs];

	inline void build(int x,int l,int r)

	{

		if(l==r) return tre[x].mx=tre[x].dat=1,void();

		int mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r);

		push_up(x);

	}

	inline void insert(int x,int l,int r,int pos,node val)

	{

		if(l==r) return tre[x]=tre[x]+val,void();

		int mid=(l+r)>>1;

		if(pos<=mid) insert(ls,l,mid,pos,val);

		else insert(rs,mid+1,r,pos,val);

		push_up(x);

	}

	inline node query(int x,int l,int r,int L,int R)

	{

		if(L<=l&&r<=R) return tre[x];

		int mid=(l+r)>>1;

		if(L<=mid&&R>mid) return query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R);

		if(L<=mid) return query(ls,l,mid,L,R); return query(rs,mid+1,r,L,R);

	}

}H[N],Z[N];

bool comp(Node a,Node b)

{

	if(a.x!=b.x) return a.x<b.x;

	if(a.y!=b.y) return a.y<b.y;

	if(a.x2!=b.x2) return a.x2<b.x2;

	return a.y2<b.y2;

}

bool check(Node a,Node b){return a.x<=b.x&&a.x2>=b.x2&&a.y<=b.y&&a.y2>=b.y2;}

void solve()

{

	n=read(); m=read(); q=read(); cnt=1; ans=(node){0,0};

	for(int i=1,x,y,x2,y2;i<=q;i++)

		x=read(),y=read(),x2=read(),y2=read(),

		s[i]=(Node){x,y,x2,y2};

	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) h[i][j]=z[i][j]=INF;

	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) nxt[i][j]=j+1;

	for(int i=1;i<=n+1;i++) nxt2[i]=i+1;

	sort(s+1,s+q+1,comp); reverse(s+1,s+q+1);

	for(int i=2;i<=q;i++) if(!check(s[i-1],s[i])) s[++cnt]=s[i];

	reverse(s+1,s+cnt+1);

	for(int i=1;i<=cnt;i++)

	{

		int x=s[i].x,y=s[i].y,x2=s[i].x2,y2=s[i].y2;

		for(int j=x+1;j<=x2;j=nxt2[j])

		{

			for(int k=y+1;k<=y2;k=nxt[j][k]) z[j][k]=min(z[j][k],x);

			for(int k=y+1,pre=nxt[j][k];k<=y2;k=pre,pre=nxt[j][k])

				nxt[j][k]=max(nxt[j][k],y2+1);

			if(nxt[j][1]>m) nxt2[j]=nxt2[j+1];

		}

	}

	for(int i=1;i<=cnt;i++)

	{

		int x=s[i].x,y=s[i].y,x2=s[i].x2,y2=s[i].y2;

		for(int j=x2;j>=x+1;j--)

			for(int k=y2;k>=y+1;k--)

			{

				if(h[j][k]<=s[i].y) break;

				h[j][k]=s[i].y;

			}

	}

	for(int i=1;i<=n;i++) H[i].build(1,1,m);

	for(int i=1;i<=m;i++) Z[i].build(1,1,n);

	for(int i=2;i<=n;i++)

		for(int j=2;j<=m;j++)

		{

			if(h[i][j]==INF||z[i][j]==INF) continue;

			node temp=H[i-1].query(1,1,m,h[i][j],j-1);

			if(i-2>=z[i][j]) temp=temp+Z[j-1].query(1,1,n,z[i][j],i-2);

			temp.mx++;

			H[i].insert(1,1,m,j,temp); Z[j].insert(1,1,n,i,temp);

		}

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++)

			ans=ans+H[i].query(1,1,m,j,j);

	printf("%d %d\n",ans.mx,ans.dat);

}

signed main()

{

	freopen("roche.in","r",stdin); freopen("roche.out","w",stdout);

	T=read(); while(T--) solve();

	return 0;

}

T2 特立独行的图

大坑未补

T3 玩游戏

期望+调和级数+求导（我哪会啊！！）抄题解都懒得抄。。

大坑未补

T4 骆驼

解题思路

对于 5 的情况直接处理即可。

然后考虑将所有的比较大块的矩形分成比较小的几块 \(5\times 5\) 拼起来。

对于多种情况转移就好了，需要对于奇数偶数块数分别判断。。

code

#include <bits/stdc++.h>

#define int long long

#define ull unsigned long long

#define f() cout<<"Failed"<<endl

#define left Left

#define right Right

using namespace std;

inline int read()

{

	int x=0,f=1;char ch=getchar();

	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}

	return x*f;

}

const int N=1e3+10,M=210;

const int up=4,down=3,left=5,right=6;

int n,m,suc,s[N][N],ans[N][N];

int d1[10]={0,-3,3,0,0,-2,-2,2,2};

int d2[10]={0,0,0,3,-3,2,-2,2,-2};

int c[10][5][5]=

{

	{{1,8,16,2,7},{11,19,5,10,18},{22,14,0,21,15},{4,9,17,3,6},{12,20,23,13,0}},

	{{22,3,9,23,2},{16,25,20,17,7},{10,13,1,4,12},{21,18,8,24,19},{15,5,11,14,6}},

	{{1,12,5,2,13},{7,18,15,10,19},{23,3,0,22,4},{16,11,6,17,14},{8,21,24,9,20}},

	{{6,22,14,7,2},{19,9,4,20,12},{24,16,1,23,15},{5,21,13,8,3},{18,10,25,17,11}},

	{{9,22,25,8,2},{17,12,4,20,15},{24,7,1,23,6},{10,21,16,11,3},{18,13,5,19,14}},

	{{9,17,24,8,2},{22,12,4,19,13},{25,7,1,16,6},{10,18,23,11,3},{21,15,5,20,14}},

	{{22,14,7,23,2},{9,19,4,12,18},{6,24,1,15,25},{21,13,8,20,3},{10,16,5,11,17}}

};

struct Node{int base,id;}p[M][M];

void dfs(int x,int y,int cnt)

{

	if(suc) return ;

	s[x][y]=cnt;

	if(cnt==n*n)

	{

		int can=false;

		for(int i=1;i<=8;i++)

		{

			int x2=x+d1[i],y2=y+d2[i];

			if(x2>n||x2<1||y2<1||y2>n) continue;

			if(x2==1&&y2==1){can=true;break;}

		} suc|=can;

		if(can)

			for(int i=1;i<=n;i++)

				for(int j=1;j<=n;j++)

					ans[i][j]=s[i][j];

		return s[x][y]=0,void();

	}

	for(int i=1;i<=8;i++)

	{

		int x2=x+d1[i],y2=y+d2[i];

		if(x2>n||x2<1||y2<1||y2>n) continue;

		if(s[x2][y2]) continue;

		dfs(x2,y2,cnt+1);

	}

	s[x][y]=0;

}

void work(int x,int y,Node temp)

{

	for(int i=1;i<=5;i++)

		for(int j=1;j<=5;j++)

			ans[i+x][j+y]=c[temp.id][i-1][j-1]+temp.base;

}

void Solve_For_Odd()

{

	p[1][1].id=0; p[2][2].id=1; p[m][1].id=right; p[1][2].id=down;

	for(int i=3;i<=m;i++)

		if(i&1)

		{

			p[2][i].id=p[i][m].id=up; p[1][i].id=left;

			for(int j=2;j<m;j++) p[i][j].id=right;

		}

		else

		{

			p[2][i].id=left; p[i][2].id=up; p[1][i].id=down;

			for(int j=3;j<=m;j++) p[i][j].id=left;

		}

	for(int i=2;i<=m-1;i++) p[i][1].id=down;

}

void Solve_For_Even()

{

	p[1][1].id=2; p[m][1].id=right;

	for(int i=2;i<=m;i++)

	{

		if(i!=m) p[i][1].id=down; p[1][i].id=left;

		if(i&1)

		{

			for(int j=3;j<=m;j++) p[i][j].id=left;

			p[i][2].id=up; continue;

		}

		for(int j=2;j<m;j++) p[i][j].id=right;

		p[i][m].id=up;

	}

}

void solve(int x,int y,int base)

{

	while(p[x][y].id&&p[x][y].id!=1&&p[x][y].id!=2)

	{

		p[x][y].base=base; base+=25;

		if(p[x][y].id==down) x++;

		else if(p[x][y].id==up) x--;

		else if(p[x][y].id==right) y++;

		else if(p[x][y].id==left) y--;

	}

	if(p[x][y].id==1) p[x][y].base=base;

	for(int i=1;i<=m;i++)

		for(int j=1;j<=m;j++)

			work((i-1)*5,(j-1)*5,p[i][j]);

}

void print(){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%lld ",ans[i][j]);printf("\n");}}

signed main()

{

	freopen("camel.in","r",stdin); freopen("camel.out","w",stdout);

	n=read(); m=n/5; if(n==5) dfs(1,1,1),print(),exit(0);

	if(m&1) Solve_For_Odd(),solve(2,1,23),ans[5][5]=n*n-1;

	else Solve_For_Even(),solve(2,1,24);

	ans[3][3]=n*n; print();

	return 0;

}

巴特西

NOIP模拟76

前言

T1 洛希极限

解题思路

code

T2 特立独行的图

大坑未补

T3 玩游戏

大坑未补

T4 骆驼

解题思路

code

最新文章

热门文章