2021-11-13 半期考试

2021-11-13 半期考试 果果系统2

solution：

这个题目极其阴间，T1打磨你，全场没有a
首先对于有对角线的方块我们可以直接确定位置，然后可以直接将在他 2 ∗ 2 2*2 2∗2的矩阵内建立一个拓扑图，那么还剩一些 1 ∗ 2 1*2 1∗2的长条，怎么办呢，首先每当我们删除一个 2 ∗ 2 2*2 2∗2之后，我们将格子都赋值为 − 1 -1 −1，然把周围的12个格子全部遍历，再去判断是否能构出一个新的 2 ∗ 2 2*2 2∗2

#include
#define ll long long
using namespace std;
const int N = 1e6+10;
int n,m,K,a[505][505],tx[4]={0,0,1,1},ty[4]={0,1,0,1};
int X[12]={-1,-1,-1,-1,0,0,1,1,2,2,2,2},Y[12]={-1,0,1,2,-1,2,-1,2,-1,0,1,2};
int ans[N],ct,vis[N];
struct node{
	int cnt,x[6],y[6];
}p[N];
int en[N],nex[N],lst[N],tot,du[N];
void add(int x,int y){en[++tot]=y;nex[tot]=lst[x];lst[x]=tot;}
queueq;
void check(int u){
	int fx=p[u].x[1],fy=p[u].y[1];
	if(p[u].x[1]==p[u].x[2]){
		if(p[u].x[1]>1){
			if(a[fx-1][fy]==-1&&a[fx-1][fy+1]==-1){
				q.push(u);vis[u]=1;p[u].x[0]=fx-1;p[u].y[0]=fy;
				return;
			}
		}
		if(p[u].x[1]1){
			if(a[fx][fy-1]==-1&&a[fx+1][fy-1]==-1){
				q.push(u);vis[u]=1;p[u].x[0]=fx;p[u].y[0]=fy-1;
				return;
			}
		}
		if(p[u].y[1]n||fy<1||fy>m)continue;
			if(v<1||vis[v]||p[v].x[0])continue;
			check(v);
		}
	}
	for(int i=ct;i>=1;i--){
		int id=ans[i];
		printf("%d %d %dn",id,p[id].x[0],p[id].y[0]);
	}return 0;
}

大冒险

solution:

阴间模板题，数据结构，扫描线，，，
首先做法很显然，我们知道这个肯定是在取模意义下来搞。
所以相当于我们把每个矩形所覆盖的区间都转化到取模意义下，所以区间覆盖，使用扫描线，类似于差分思想，只不过每一个位置都是一棵线段树来维护。
然后就是比较阴间的边界问题，有最显然暴力的直接拆分，也有找性质的比较简便的拆分，本代码即使用的是后者。

#pragma GCC optimize(3)
#pragma GCC optimize(2)
#include
#define ll long long
using namespace std;
const int N = 2e5+10;
int n,m;
struct node{
	int x,y,z;
};
vectorv[N];
void add(int x,int y,int z,int w){
	if(x<=y)v[z].push_back((node){x,(y-1+m)%m,w});
	else v[z].push_back((node){0,m-1,w}),v[z].push_back((node){y,(x-1+m)%m,-w});
}
int w[N<<2][2],lzy[N<<2];
void update(int p){
	int ls=p<<1,rs=p<<1|1;
	if(w[ls][0]<=w[rs][0])w[p][1]=w[ls][1],w[p][0]=w[ls][0];
	else w[p][1]=w[rs][1],w[p][0]=w[rs][0];
}
void pushdown(int p){
	int ls=p<<1,rs=p<<1|1;
	lzy[ls]+=lzy[p];lzy[rs]+=lzy[p];
	w[ls][0]+=lzy[p];w[rs][0]+=lzy[p];
	lzy[p]=0;
}
void build(int p,int l,int r){
	lzy[p]=0;if(l==r){w[p][0]=0;w[p][1]=l;return;}
	int mid=(l+r)>>1,ls=p<<1,rs=p<<1|1;
	build(ls,l,mid);build(rs,mid+1,r);update(p);
}
void modify(int p,int l,int r,int x,int y,int z){
	if(l>=x&&r<=y){
		w[p][0]+=z;lzy[p]+=z;return;
	}if(l==r)return;
	if(lzy[p])pushdown(p);
	int mid=(l+r)>>1,ls=p<<1,rs=p<<1|1;
	if(x<=mid)modify(ls,l,mid,x,y,z);
	if(y>mid)modify(rs,mid+1,r,x,y,z);
	update(p);
}
void work(){
	build(1,0,m-1);
	for(int i=0;i=m)p[4]=m,p[2]=0;
			if(p[3]-p[1]>=m)p[3]=m,p[1]=0;
			for(int j=1;j<=4;j++)p[j]=(p[j]%m+m)%m;
			add(p[1],p[3],p[2],1);add(p[1],p[3],p[4],-1);
			if(p[2]>=p[4])add(p[1],p[3],0,1);
		}work();init();
	}
	return 0;
} 

单调栈

solution：

引荐题目
首先对于没有-1的情况，我们要先找到区间的最小值（且在最右边的），因为后入栈一定是更小的。然后我们将序列分成两个不同的区间，这样我们就知道了左右两边的排名，那么数字的分配就有 C l e n l e n 左 C_{len}^{len左} Clenlen左​，再分别往左右两边递归。
有-1的情况就是，当-1处在上述最小值的右边，都有可能代替最小值成为新的最小值，所以每一个-1都要去重复上述 *** 作递归讨论即可
可以选择记搜，或者是直接DP，但是阴间在于，同样的记搜，本蒟蒻的就会T，最后只有用循环的方式，，，

#pragma GCC optimize(3)
#pragma GCC optimize(2)
#include
#define ll long long
const ll mo = 1e9+7;
int n,m,a[105];
ll C[105][105],f[105][105][105];
inline void init(){
	C[0][0]=1;
	for(int i=1;i<=100;i++)
	for(int j=0;j<=i;j++)
	if(i==j||!j)C[i][j]=1;
	else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mo;
}signed main(){
	init();int T;
	scanf("%d",&T);
	while(T--){
		for(int i=0;i<=n;i++)
		for(int j=i;j<=n;j++)
		for(int k=0;k<=n;k++)f[i][j][k]=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",a+i);
		for(int len=1;len<=n;len++)
		for(int i=1,j=len;j<=n;i++,j++)
		for(int k=i;k<=j;k++){
			int l,r;
			if(a[k]==-1)l=1,r=i;
			else l=r=a[k];
			for(int x=l;x<=r;x++){
				f[i][j][x]+=(i<=k-1?f[i][k-1][x]:1)*(k+1<=j?f[k+1][j][x+1]:1)%mo*C[j-i][k-i]%mo;
				if(f[i][j][x]>=mo)f[i][j][x]%=mo;
			}
		}
		printf("%I64dn",f[1][n][1]);
	}
	return 0;
}