Znzryb's Blog

CF-1013-G. Gleb and Boating

Posted on 2025-04-18 Edited on 2026-04-06

思路讲解

注意到

AC代码

源代码

心路历程（WA，TLE，MLE……）

CF-1013-F. Igor and Mountain（计数类dp）

Posted on 2025-04-17 Edited on 2026-04-06

思路讲解

感觉是dp，因为是计算路径数量。

首先我们将dp状态定义为到达该点的路径数量（其实也就是同一行之间只能从右往左转移）

然后转移方式如上图所示。

具体转移逻辑（代码）

	// dp指的是到达该点有多少种路径
	for(int i=N;i>=1;--i){
		sum[0]=0;
		// sum下面一行dp形成的前缀和
		for(int j=1;j<=M;++j){
			sum[j]=sum[j-1]+dp[i+1][j];
		}
		sumCur[0]=0;
		// sumCur为这一行形成的前缀和
		for(int j=1;j<=M;++j){
			if(maze[i][j]=='X'){
				dp[i][j]=dp[i][j]+sum[min(reachDis+j,M)]-sum[max(0ll,j-reachDis-1)];
				dp[i][j]%=mod;
				sumCur[j]=sumCur[j-1]+dp[i][j];
				sumCur[j]%=mod;
			}else{
				sumCur[j]=sumCur[j-1];
			}
		}
// #ifdef LOCAL
	// cerr<<"sumCur:";
    // for(int j=1;j<=M;++j){
    	// cerr<<sumCur[j]<<" ";
    // }
    // cerr<<"\n";
// #endif
		for(int j=1;j<=M;++j){
			if(maze[i][j]=='X'){
				// 相当于对这段区间进行了区间查询，但因为不能包括自己，所以还要减掉自己
				dp[i][j]=dp[i][j]+sumCur[min(D+j,M)]-sumCur[max(0ll,j-D-1)]-dp[i][j];
				dp[i][j]%=mod;
			}
		}
	}

AC代码

源代码

// Problem: F. Igor and Mountain
// Contest: Codeforces - Codeforces Round 1013 (Div. 3)
// URL: https://codeforces.com/contest/2091/problem/F
// Memory Limit: 512 MB
// Time Limit: 5000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e3)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=998244353;

ll N,M,D,T;
char maze[MAXN][MAXN];
// dpr指的是从右边到达该点有多少种状态 
// ll dpr[MAXN][MAXN],dpl[MAXN][MAXN];
ll dp[MAXN][MAXN];
ll sum[MAXN],sumCur[MAXN];

inline void solve(){
	cin>>N>>M>>D;
	// init
	for(int i=0;i<=N+5;++i){
		for(int j=0;j<=M+5;++j){
			dp[i][j]=0;
		}
	}
	bool haveAns=true;
	for(int i=1;i<=N;++i){
		bool haveHold=false;
		for(int j=1;j<=M;++j){
			cin>>maze[i][j];
			if(maze[i][j]=='X') haveHold=true;
		}
		if(!haveHold) haveAns=false;
	}
// #ifdef LOCAL
    // cerr << "OK1" << '\n';
// #endif
	if(!haveAns){
		cout<<0<<"\n";
		return;
	}
	for(int i=1;i<=M;++i){
		if(maze[N][i]=='X') dp[N][i]=1;
	}
	// 1^2+?^2=d^2
	ll reachDis=sqrtl(D*D-1);	// 使用sqrtl保证精度
// #ifdef LOCAL
    // cerr << reachDis << '\n';
// #endif
	// dp指的是到达该点有多少种路径
	for(int i=N;i>=1;--i){
		sum[0]=0;
		// sum下面一行dp形成的前缀和
		for(int j=1;j<=M;++j){
			sum[j]=sum[j-1]+dp[i+1][j];
		}
		sumCur[0]=0;
		// sumCur为这一行形成的前缀和
		for(int j=1;j<=M;++j){
			if(maze[i][j]=='X'){
				dp[i][j]=dp[i][j]+sum[min(reachDis+j,M)]-sum[max(0ll,j-reachDis-1)];
				dp[i][j]%=mod;
				sumCur[j]=sumCur[j-1]+dp[i][j];
				sumCur[j]%=mod;
			}else{
				sumCur[j]=sumCur[j-1];
			}
		}
// #ifdef LOCAL
	// cerr<<"sumCur:";
    // for(int j=1;j<=M;++j){
    	// cerr<<sumCur[j]<<" ";
    // }
    // cerr<<"\n";
// #endif
		for(int j=1;j<=M;++j){
			if(maze[i][j]=='X'){
				// 相当于对这段区间进行了区间查询，但因为不能包括自己，所以还要减掉自己
				dp[i][j]=dp[i][j]+sumCur[min(D+j,M)]-sumCur[max(0ll,j-D-1)]-dp[i][j];
				dp[i][j]%=mod;
			}
		}
	}
	ll ans=0;
	for(int i=1;i<=M;++i){
		ans+=dp[1][i];
	}
	ans%=mod;
	if(ans<0) ans+=mod;
	cout<<ans<<"\n";
// #ifdef LOCAL
   	// for(int i=1;i<=N;++i){
   		// for(int j=1;j<=M;++j){
   			// cerr<<dp[i][j]<<" ";
   		// }
   		// cerr<<"\n";
   	// }
   	// cerr<<"\n";
// #endif
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2091/submission/316079969
*/

心路历程（WA，TLE，MLE……）

这个测试组数7有点问题

https://codeforces.com/contest/2091/submission/316079483

最后发现是没取模，6.

CF-1013-E. Interesting Ratio

Posted on 2025-04-17 Edited on 2026-04-06

思路讲解

解释最小公倍数的计算原理

a \cdot b = lcm(a, b) \cdot gcd(a, b)

这个可以用质因数唯一分解定理解释

或者用上面这张图来解释，product相当于就是把交集部分再乘了一遍，一共乘了两遍。那么 $lcm=product/gcd(a,b)$ ，相当于就是把多乘的交集部分给去掉了。

上面其实只是介绍了一下题目背景。

理解了上面这张图，那么其实就好搞多了， $F(a,b)=lcm(a,b)/gcd(a,b)$ 其实就是去掉中间的交集两边省的东西。按照题目要求 $F(a,b)$ 必须为质数。那么其实就是要求两遍剩的，一边是1，一边是一个质数。

AC代码

https://codeforces.com/contest/2091/submission/315904464

源代码

// Problem: E. Interesting Ratio
// Contest: Codeforces - Codeforces Round 1013 (Div. 3)
// URL: https://codeforces.com/contest/2091/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e7)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,T,A[MAXN];
vector<ll> primes;
bool isPrime[MAXN];

inline void genPrime(){
	
	for(int i=2;i<=MAXN-5;++i){
		isPrime[i]=true;
	}
	for(int i=2;i<=MAXN-5;++i){
		if(isPrime[i]){
			for(int j=2*i;j<=MAXN-5;j+=i){
				isPrime[j]=false;
			}
		}
	}
	for(int i=2;i<=MAXN-5;++i){
		if(isPrime[i]) primes.pb(i);
	}
}

inline void solve(){
	cin>>N;
	ll ans=0;
	for(int i=0;i<primes.size();++i){
		if(primes[i]>N) break;
		ans+=N/primes[i];
	}
	cout<<ans<<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	genPrime();
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2091/submission/315904464
*/

心路历程（WA，TLE，MLE……）

CF-1013-D. Place of the Olympiad

Posted on 2025-04-16 Edited on 2026-04-06

思路讲解

这个还是要写的更细致一点，检查函数

inline bool check(ll x){
	// ll res=ceil((M*N)*1.0l/(x+1));
	// ll rem=K%x;
	ll res=x*(M/(x+1));
	ll usedBlock=(x+1)*(M/(x+1));
	res+=max(0ll,(M-usedBlock));
// #ifdef LOCAL
    // cerr << x<<" "<< res << '\n';
// #endif
	if(res*N>=K){
		return true;
	}
	return false;
}

AC代码

源代码

// Problem: D. Place of the Olympiad
// Contest: Codeforces - Codeforces Round 1013 (Div. 3)
// URL: https://codeforces.com/contest/2091/problem/D
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,K,T,A[MAXN];

inline bool check(ll x){
	// ll res=ceil((M*N)*1.0l/(x+1));
	// ll rem=K%x;
	ll res=x*(M/(x+1));
	ll usedBlock=(x+1)*(M/(x+1));
	res+=max(0ll,(M-usedBlock));
// #ifdef LOCAL
    // cerr << x<<" "<< res << '\n';
// #endif
	if(res*N>=K){
		return true;
	}
	return false;
}

inline void solve(){
	cin>>N>>M>>K;
	ll l=0,r=K;
	while(l<r){
		ll mid=l+r>>1;
		if(check(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	cout<<l<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2091/submission/315860650
*/

心路历程（WA，TLE，MLE……）

CF-1014-E. She knows…

Posted on 2025-04-15 Edited on 2026-04-06

思路讲解

【Codeforces Round 1014 (Div. 2) 题目讲解 ABCDE (CF2092)】 https://www.bilibili.com/video/BV1koZBYhEH1/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37

在这种问题当中，往往需要把这个格子的周围4个格子确定了。而不是先确定这个格子填什么

如上图，无论这个格子填黑还是填白，所贡献的都是奇数。

同理，如果周围的4个格子两黑两白，那么无论这个格子填什么，一定会贡献一个偶数。

由于在这种格子中，奇偶性会发生反转，所以说你可以其他格子随便填，但是你选择的这个格子（比如图中画橙圈的）一定是确定的颜色，一个数加上偶数或者奇数总能是偶数是吧。

那么有种特殊情况，就是这种既能是偶数，也能是奇数的点全部被占了怎么办？这真不会了。

其实也不难，假设其他点全部为白色，算就完了。

AC代码

https://codeforces.com/contest/2092/submission/315721639

源代码

// Problem: E. She knows...
// Contest: Codeforces - Codeforces Round 1014 (Div. 2)
// URL: https://codeforces.com/contest/2092/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,T,K,A[MAXN];
arr xyc[MAXN];
ll dx[4]={1,0,-1,0};
ll dy[4]={0,-1,0,1};
// ll dy[2]={1,-1};

inline bool isEff(ll x,ll y){
	if(x==1 || x==N){
		if(y!=1 && y!=M){
			return true;
		}
	}else if(y==1 || y==M){
		if(x!=1 && x!=N){
			return true;
		}
	}
	return false;
}
inline ll binpow(ll x,ll k){
	ll res=1;
	if(k<0) return -1;// 相当于抛出错误，快速幂是无法处理负数指数的
	while(k){
		if(k&1) res*=x;
		res%=mod;
		x*=x;
		x%=mod;
		k>>=1;
	}
	return res;
}

inline void solve(){
	cin>>N>>M>>K;
	ll cnt=0;
	vector<arr> effNode;
	map<pll,ll> dicNode;
	FOR(i,1,K){
		cin>>xyc[i][0]>>xyc[i][1]>>xyc[i][2];
		if(isEff(xyc[i][0],xyc[i][1])){
			++cnt;
			effNode.pb(xyc[i]);
			dicNode[(pll){xyc[i][0],xyc[i][1]}]=xyc[i][2];
		}
	}
	ll res=0;
#ifdef LOCAL
    cerr << cnt << '\n';
#endif
	if(cnt<2*N+2*M-8){
// #ifdef LOCAL
    // cerr << "OK1" << '\n';
// #endif
		cout<<binpow(2,N*M-K-1)<<"\n";
// #ifdef LOCAL
    // cerr << "OK2" << '\n';
// #endif
	}else{
		for(int i=0;i<effNode.size();++i){
			ll x=effNode[i][0],y=effNode[i][1],c=effNode[i][2];
			if(c==1){
				// res+=1;
				for(int j=0;j<4;++j){
					ll ux=x+dx[j],uy=y+dy[j];
					if(ux<1 || ux>N) continue;
					if(uy<1 || uy>M) continue;
					if(dicNode.find((pll){ux,uy})!=dicNode.end()){
						if(dicNode[(pll){ux,uy}]==0) ++res;
					}else{
						++res;
					}
				}
				
			}

		}
// #ifdef LOCAL
    // cerr << res << '\n';
// #endif
		if(res%2==0){
			cout<<binpow(2,N*M-K)<<"\n";
		}else{
			cout<<0<<"\n";
		}
	}

}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2092/submission/315721639
*/