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;
}
Postscript
接下来就是把一轮剩下的模拟赛补完就完了
标签：AtCoder,typedef,const,Beginner,Contest,int,long,include,define From： https://www.cnblogs.com/cjjsb/p/17604279.html