Preface

补下好久之前打的比赛博客

这场前面都写的挺稳的，然后一到G就降智了没写出来

A - First ABC

签到

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=105;
int n,t[3]; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%s",&n,s+1),i=1;i<=n;++i)
	{
		++t[s[i]-'A'];
		if (t[0]&&t[1]&&t[2]) return printf("%d",i),0;
	}
	return 0;
}

B - Vacation Together

签到

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=105;
int n,d,c[N],ans; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&d),i=1;i<=d;++i) c[i]=1;
	for (i=1;i<=n;++i)
	{
		for (scanf("%s",s+1),j=1;j<=d;++j) if (s[j]=='x') c[j]=0;
	}
	int lst=0; for (i=1;i<=d;++i)
	if (!c[i]) ans=max(ans,i-lst-1),lst=i;
	ans=max(ans,d-lst);
	return printf("%d",ans),0;
}

C - Find it!

根据置换环这类的东西我们知道这是一定会成环的，因此直接顺着出边走，记录下已经到达的点即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=200005;
int n,a[N],ans[N],cnt,st,vis[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (ans[++cnt]=1,i=a[1],vis[1]=1;i!=1;i=a[i])
	{
		ans[++cnt]=i; vis[i]=cnt;
		if (vis[a[i]]) { st=vis[a[i]]; break; }
	}
	for (printf("%d\n",cnt-st+1),i=st;i<=cnt;++i) printf("%d ",ans[i]);
	return 0;
}

D - Grid Ice Floor

按题意BFS一遍即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=205,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int n,m; char a[N][N]; queue <pi> q; bool vis[N][N],inque[N][N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%s",a[i]+1);
	q.push(pi(2,2)); vis[2][2]=inque[2][2]=1;
	while (!q.empty())
	{
		int x=q.front().fi,y=q.front().se; q.pop();
		for (k=0;k<4;++k)
		{
			int nx=x,ny=y;
			while (a[nx][ny]!='#') vis[nx][ny]=1,nx+=dx[k],ny+=dy[k];
			nx-=dx[k], ny-=dy[k];
			if (!inque[nx][ny]) q.push(pi(nx,ny)),inque[nx][ny]=1;
		}
	}
	int ans=0; for (i=1;i<=n;++i) for (j=1;j<=m;++j) ans+=vis[i][j];
	return printf("%d",ans),0;
}

E - Defect-free Squares

可以枚举左上角的点，然后二分最大延申的长度，检验的话用二位前缀和即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=3005,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int n,m,k,x,y,sum[N][N]; long long ans;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d%d",&n,&m,&k),i=1;i<=k;++i) scanf("%d%d",&x,&y),sum[x][y]=1;
	for (i=1;i<=n;++i) for (j=1;j<=m;++j) sum[i][j]+=sum[i][j-1];
	for (i=1;i<=n;++i) for (j=1;j<=m;++j) sum[i][j]+=sum[i-1][j];
	for (i=1;i<=n;++i) for (j=1;j<=m;++j)
	{
		int l=0,r=min(n-i+1,m-j+1),mid,ret;
		auto calc=[&](CI a,CI b,CI c,CI d)
		{
			if (a>c) return 0; return sum[c][d]-sum[a-1][d]-sum[c][b-1]+sum[a-1][b-1];
		};
		while (l<=r) if (mid=l+r>>1,calc(i,j,i+mid-1,j+mid-1)==0) ret=mid,l=mid+1; else r=mid-1;
		ans+=ret;
	}
	return printf("%lld",ans),0;
}

F - Yet Another Grid Task

首先不难发现这题由于每一列最上方的那个#会直接把这一列下方的格子都变黑，因此我们只关心每列最上方的#的位置，不妨记为\(h_i\)

因此最后合法的矩阵个数可以转化为合法的序列\(\{h_n\}\)的数量，首先不难发现\(h_i\)要大于等于原来每一列最上方的#

同时对于相邻的两列\((i,i+1)\)，显然若\(h_i>h_{i+1}+1\)，则该状态不合法，因为\(h_i\)会扩散到下一列去

那么就很容易想到一个DP，令\(f_{i,j}\)表示从右往左确定了第\(i\)列，\(h_i=j\)的方案数，转移用前缀和优化一下即可

复杂度\(O(n\times m)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=2005,mod=998244353;
int n,m,h[N],f[N][N],g[N][N]; char a[N][N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%s",a[i]+1);
	for (i=1;i<=n;++i) for (j=1;j<=m;++j) if (a[i][j]=='#') h[j]=max(h[j],n-i+1);
	for (i=0;i<=n;++i) g[m+1][i]=1;
	for (i=m;i>=1;--i)
	{
		for (j=h[i];j<=n;++j) f[i][j]=g[i+1][max(0,j-1)];
		for (j=n;j>=0;--j) g[i][j]=(g[i][j+1]+f[i][j])%mod;
	}
	return printf("%d",g[1][0]),0;
}

G - One More Grid Task

二维的问题乍一看不好想，我们先考虑一维的情况，这是个很经典的问题

我们枚举每个位置\(i\)作为最小值，用单调栈求出它为最小值的区间，由于所有数非负因此最大的那个区间一定是最优的，这样的复杂度为\(O(n)\)

那么对于这道题我们枚举两行作为约束，将每列的最小值拿出来跑单调栈即可，总复杂度\(O(n^3)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<limits.h>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=305;
int n,m,a[N][N],mi[N][N][N],sum[N][N][N],L[N],R[N],stk[N],top,pfx[N]; LL ans;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
	for (j=1;j<=m;++j) scanf("%d",&a[i][j]);
	for (k=1;k<=m;++k)
	{
		for (i=1;i<=n;++i) for (mi[k][i][i]=sum[k][i][i]=a[i][k],j=i+1;j<=n;++j)
		mi[k][i][j]=min(mi[k][i][j-1],a[j][k]),sum[k][i][j]=sum[k][i][j-1]+a[j][k];
	}
	for (j=1;j<=n;++j) for (k=j;k<=n;++k)
	{
		for (stk[top=0]=0,i=1;i<=m;++i)
		{
			while (top&&mi[stk[top]][j][k]>mi[i][j][k]) --top;
			L[i]=stk[top]; stk[++top]=i;
		}
		for (stk[top=0]=m+1,i=m;i>=1;--i)
		{
			while (top&&mi[stk[top]][j][k]>=mi[i][j][k]) --top;
			R[i]=stk[top]; stk[++top]=i;
		}
		for (i=1;i<=m;++i) pfx[i]=pfx[i-1]+sum[i][j][k];
		for (i=1;i<=m;++i) ans=max(ans,1LL*mi[i][j][k]*(pfx[R[i]-1]-pfx[L[i]]));
	}
	return printf("%lld",ans),0;
}