Solution Set - Atcoder (on scene)

ABC260

2022-7-17

Solved:7/8

Rank98！

1908->1973

E(Medium-,1692)

给定\(n\)个二元组，值域为\([1,m]\)，求长度为\(k\)，包含每个二元组中至少一个数的区间数目，这里\(k\)需取遍\(1,...,m\)。

Solution:考虑每个左端点，求出使其满足条件的最小右端点，用双指针。双指针时有一个方法：将所有数塞到一个数组中，维护出现的二元组数目。

若\([l,r]\)可行，则\([l,t],r \le t \le m\)可行，从而差分。最后求一次前缀和。

F(Medium,1995)

给定一个二分图，求其中是否有长为\(4\)的环。特殊限制：右部点数\(t \le 3000\)。

Solution:对每个右部点，从它出发走两步，如果两次走到同一个点则得到解。若没有走到，则每次时间为\(O(t)\)，总时间不超过\(O(t^2)\)。

G(Medium+,2339)

给定一个\(n \times n\) 的OX矩阵和\(m\)，给出\(q\)个询问\((x,y)\)，求满足\(s \le x \le n,t \le y \le n,(x-s)+\frac{y-t}{2} \lt m\)且填O的点\((s,t)\)数目。

Solution:一个裸的模板题：二维斜向差分，和P8228类似。首先对斜率为\(\frac{1}{2}\)方向差分，对这个差分数组，再从横向和斜率\(\frac{1}{2}\)方向差分。对每个\(O\)转化一下，再求前缀和就可以了。（为什么又是差分）

说着不难，实际上还是有一些细节要处理的。

ABC258

2022-7-2

Solved:6/8

1864->1908

E(Medium-,1545)

给定周期为\(n\)的序列的一个周期，从第一个开始加和，和超过\(x\)就计一段。求第\(k\)段的长。

Solution:考虑从每个位置出发会到达哪里。用双指针。再由此建立段开头的周期即可。

G(Medium,1944)

给定一张图，求三角形数目。

Solution:枚举一条边，计算其两个端点所连点的集合之交的大小。用 bitset 。

ARC142

2022-6-19

Solved:3/6

1880->1864

B(Medium+,692)

构造 \(n \times n\) 的矩阵，填入从 \(1\) 开始的连续整数，使得对任意一格，其周围（八连通）比它大的个数和比它小的个数不相同。

Solution:首先，边界的格子有奇数个邻格，不用考虑。

其次，如果能保证每个格周围有至少 \(5\) 个格与其大小关系相同，就解决了题目。由此可以想到按照圈来填，外圈所填一定大于内圈。

如果 \(n\) 为奇数，直接让每一圈大小相间即可。如果 \(n\) 为偶数，先让角落处为该圈最大，然后让边角处连续，其它地方大小相间。倒数第二圈单独构造，可以完成。

题解的做法简单：按行考虑，每行大小交替，各行递减。

C(Medium,1347)

\(n\) 个点的树，可以询问除 \(1\) 和 \(2\) 之外任意两点间距离，要求用不超过 \(2n\) 次询问确定 \(1\) 和 \(2\) 的距离。

Solution:先找出所有与 \(1\) 相距 \(1\) 的点。若一个没有，则答案为 \(1\)。若至少两个，询问这两个与 \(2\) 的距离即可判断。

若恰有一个，询问这个与 \(2\) 的距离。若不为 \(2\)，则 \(1\) 为叶子结点，直接确定。否则，对 \(2\) 重复上述操作，假如也没有确定，询问两次得到的点的间距即可。

ABC256

2022-6-18

Solved:6/8

1839->1880

ABC251

2022-5-14

Solved:6/8

1816->1839

D(Easy+,1463)

构造长不超过\(300\)的数列，使得\(1\)到\(10^6\)中的整数都可以从该数列中取出不超过三个做和得到。

Solution:需要一点想法。我的做法是按照进制的思想，数列包含\(1,2,...,99\),\(100,200,...,9900\),\(10000,20000,...,990000\).

F(Easy+,1703)

求给出的图中两棵生成树，其一满足以\(1\)为根时，图中非树边的端点有祖先关系，另一恰好相反。

Solution：第一棵树最直接的情况是一条链，所以尝试构造链，贪心地连边。也就是直接dfs，看到未加入生成树的点就连边。

第二棵树最直接的情况是一个菊花，所以dfs时遇到一个点就把它所有的边都加入生成树。

ABC242

2022-3-5

Solved：7/8

Rank89！（第一次进前100）

1711->1816

D(Easy,1286)

给定字符串\(S\)，只包含\(A\),\(B\),\(C\)，一次变换将\(A\)变为\(BC\)，\(B\)变为\(CA\)，\(C\)变为\(AB\)。求\(t\)次变换后第\(l\)个位置的字符。多组询问，\(t\)，\(l\)在$ \ long \ long $范围内。

Solution：还是挺有意思的。

可以在模\(3\)意义下考虑。每一个位置变为它加\(1\)和它加\(2\)。二进制转一下就搞完了。

E(Easy,1365)

给定整数\(n\)及长为\(n\)的字符串\(S\)，求满足\(X \le S\)的回文串\(X\)个数。

Solution：按位考虑，前\([\dfrac{n+1}{2}]\)位直接贪心，然后特判前一半全部一样的情况。

F(Medium+,2268)

在\(n \times m\)的棋盘上放置\(b\)个黑車和\(w\)个白車，求使得黑白之间互不攻击的放法数。

Solution：先考虑黑棋，设\(k\)个黑棋占据\(i\)行\(j\)列的方案数为\(dp[k][i][j]\)。这里把\(k\)作为阶段进行递推。

状态转移方程为

然后枚举黑棋占领的行列数，剩下的行列都可以放白棋。

预处理阶乘，阶乘逆元，逆元等。

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,N=55,M=2505;
int n,m,b,w,fac[M],fac_inv[M],inv[M],dp[M][N][N],ans;
int power(int a,int b){
	int c=1;
	for(;b;b>>=1){
		if(b&1)c=1ll*c*a%mod;
		a=1ll*a*a%mod;
	}
	return c;
}
int C(int n,int m){
	if(n<m||n<0||m<0)return 0;
	return 1ll*fac[n]*fac_inv[m]%mod*fac_inv[n-m]%mod;
}
int main(){
	fac[0]=1;
	for(int i=1;i<=M-5;i++)fac[i]=1ll*i*fac[i-1]%mod;
	for(int i=0;i<=M-5;i++)fac_inv[i]=power(fac[i],mod-2);
	for(int i=1;i<=M-5;i++)inv[i]=power(i,mod-2);
	scanf("%d%d%d%d",&n,&m,&b,&w);
	dp[1][1][1]=1;
	for(int k=2;k<=n*m;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				//if(i*j<=k)continue;
				dp[k][i][j]=(1ll*dp[k-1][i-1][j-1]*i*j%mod+1ll*dp[k-1][i-1][j]*i*j%mod+
							1ll*dp[k-1][i][j-1]*i*j%mod+1ll*dp[k-1][i][j]*(i*j-k+1)%mod)*inv[k]%mod;
			}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			ans=(ans+1ll*dp[b][i][j]*C(n,i)%mod*C(m,j)%mod*C((n-i)*(m-j),w)%mod)%mod;
	printf("%d\n",ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m,dp[1005][12][12][12],ans;
int main(){
	scanf("%d%d",&n,&m);
	dp[0][m+1][m+1][m+1]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m+1;j++)
		for(int k=1;k<=m+1;k++)
		for(int l=1;l<=m+1;l++){
			if(j>k||k>l||j>l)continue;
			if(j==k&&k!=m+1)continue;
			if(k==l&&k!=m+1)continue;
			for(int c=1;c<=m;c++){
				if(c<=j)dp[i][c][k][l]=(dp[i][c][k][l]+dp[i-1][j][k][l])%mod;
		   		else if(c<=k)dp[i][j][c][l]=(dp[i][j][c][l]+dp[i-1][j][k][l])%mod;
		   		else if(c<=l)dp[i][j][k][c]=(dp[i][j][k][c]+dp[i-1][j][k][l])%mod;
			}
		}
	for(int j=1;j<=m;j++)
		for(int k=j+1;k<=m;k++)
			for(int l=k+1;l<=m;l++){
				ans=(ans+dp[n][j][k][l])%mod;
			}
	printf("%d\n",ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,mod=998244353,INF=1<<30;
struct rec{int l,r,val;};
int n,a[N],dp[N],s[N],sum,tmp,maxn,minn=INF;
stack<rec> MX,MN;
int main(){
	scanf("%d",&n);
	for(int i=2;i<=n+1;i++)scanf("%d",a+i);
	maxn=minn=a[2];
	s[1]=dp[1]=1;
	for(int i=2;i<=n+1;i++){
		maxn=max(maxn,a[i]);minn=min(minn,a[i]);
		tmp=i-1;
		while(!MX.empty()&&MX.top().val<=a[i]){
			rec tt=MX.top();tmp=tt.l;
			sum=(sum+1ll*(s[tt.r]-s[tt.l-1]+mod)%mod*(a[i]-tt.val))%mod;
			MX.pop();
		}
		MX.push(rec{tmp,i-1,a[i]});
		tmp=i-1;
		while(!MN.empty()&&MN.top().val>=a[i]){
			rec tt=MN.top();tmp=tt.l;
			sum=(sum+1ll*(s[tt.r]-s[tt.l-1]+mod)%mod*(tt.val-a[i]))%mod;
			MN.pop();
		}
		MN.push(rec{tmp,i-1,a[i]});
		dp[i]=sum;
		s[i]=(s[i-1]+dp[i])%mod;
	}
	printf("%d\n",dp[n+1]);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10,mod=998244353;
ll n,a,s[N],dp[N],b[N];
map<ll,vector<ll> > M;
map<ll,ll> pos;
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a);
		s[i]=s[i-1]+a;
		if(i!=n)M[s[i]].push_back(i);
	}
	for(int i=1;i<n;i++)pos[s[i]]++;
	b[n-1]=dp[n-1]=1;pos[s[n-1]]--;
	for(int i=n-2;i>=1;i--){
		int x=--pos[s[i]],y=n-1,f=1;
		if(x+1!=M[s[i]].size())y=M[s[i]][x+1],f=0;
		dp[i]=(b[i+1]-b[y+1]+f+mod)%mod;
		b[i]=(b[i+1]+dp[i])%mod;
	}
	printf("%lld\n",(b[1]+1)%mod);
	return 0;
}