Znzryb's Blog

CF-1013-(2090)C Dining Hall（小心上界确定问题）

Posted on 2025-04-20 Edited on 2026-02-16

思路讲解

这道题目本身不难，但上界的确定没那么好想

AC代码

源代码

// Problem: C. Dining Hall
// Contest: Codeforces - Codeforces Round 1012 (Div. 2)
// URL: https://codeforces.com/contest/2090/problem/C
// Memory Limit: 512 MB
// Time Limit: 2000 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,5> 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,T,prefer[MAXN];

ll dx[4]={1,2,2,1};
ll dy[4]={1,1,2,2};

bool vis[400][400],visB[2000][2000];

struct cmp{
	bool operator()(const arr &a,const arr &b) const{
		ll xa=a[0],xb=b[0],ya=a[1],yb=b[1],disa=a[4],disb=b[4];
		if(disa!=disb) return disa>disb;
		if(xa!=xb) return xa>xb;
		return ya>yb;
	}
};

// 还是genDis的问题
inline ll genDis(ll fx,ll fy,ll j){
	// if(fx==1 || fy==1) return fx+fy;
	// return fx+fy+2;
	if(j==2) return fx+fy+2;
	return fx+fy;
}

inline void solve(){
	cin>>N;
	for(int i=1;i<=N;++i){
		cin>>prefer[i];
	}
	for(int x=0;x<=sqrtl(2*N)+10;++x){
		for(int y=0;y<=sqrtl(2*N)+10;++y){
			vis[x][y]=false;
			for(int j=0;j<4;++j){
				ll fx=3*x+dx[j],fy=3*y+dy[j];
				visB[fx][fy]=false;
			}
		}
	}
	// pq是用来满足就近原则的东西的
	priority_queue<arr,vector<arr>,cmp> pq,pq1;
	for(int x=0;x<=sqrtl(2*N);++x){
		for(int y=0;y<=sqrtl(2*N);++y){
			vis[x][y]=false;
			for(int j=0;j<4;++j){
				ll fx=3*x+dx[j],fy=3*y+dy[j];
				ll dis=genDis(fx,fy,j);
				pq.push((arr){fx,fy,x,y,dis});
				pq1.push((arr){fx,fy,x,y,dis});
				visB[fx][fy]=false;
			}
		}
	}
	vector<array<ll,2>> ans;
	ll idx=1;
// #ifdef LOCAL
    // cerr << pq.size()<<" "<<pq1.size()<<" "<<N<< '\n';
// #endif
	while(idx<=N){
		if(prefer[idx]){
			while(!pq.empty()){
				ll fx=pq.top()[0],fy=pq.top()[1],x=pq.top()[2],y=pq.top()[3];
				pq.pop();
// #ifdef LOCAL
	// cerr<<"debug1:";
    // cerr << fx<<" "<<fy << '\n';
// #endif
				if(visB[fx][fy]) continue;
				vis[x][y]=true;
				visB[fx][fy]=true;
				ans.pb({fx,fy});
				break;
			}
		}else{
			while(!pq1.empty()){
				ll fx=pq1.top()[0],fy=pq1.top()[1],x=pq1.top()[2],y=pq1.top()[3];
				pq1.pop();
// #ifdef LOCAL
	// cerr<<"debug0:";
    // cerr << fx<<" "<<fy << '\n';
// #endif
				if(vis[x][y]) continue;
				if(visB[fx][fy]) continue;
				visB[fx][fy]=true;
				vis[x][y]=true;
				ans.pb({fx,fy});
				break;
			}
		}
		++idx;
	}
// #ifdef LOCAL
	// cerr<<"debug\n";
	// cerr<<idx<<"\n";
    // cerr << ans.size() << '\n';
// #endif
	for(int i=0;i<ans.size();++i){
		cout<<ans[i][0]<<" "<<ans[i][1]<<"\n";
	}

}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*

*/

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

如果上界是 $sqrt(N)$ 其实桌子是够的，但是不一定能找到最优解。

通过排布规律我们知道他其实是呈三角形排布，所以要变换上界为 $sqrt(2*N)$

for(int x=0;x<=sqrtl(2*N);++x){
		for(int y=0;y<=sqrtl(2*N);++y){
			vis[x][y]=false;
			for(int j=0;j<4;++j){
				ll fx=3*x+dx[j],fy=3*y+dy[j];
				ll dis=genDis(fx,fy,j);
				pq.push((arr){fx,fy,x,y,dis});
				pq1.push((arr){fx,fy,x,y,dis});
				visB[fx][fy]=false;
			}
		}
	}

CF-1013-G. Gleb and Boating

Posted on 2025-04-18 Edited on 2026-02-16

思路讲解

注意到

AC代码

源代码

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

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

Posted on 2025-04-17 Edited on 2026-02-16

思路讲解

感觉是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-02-16

思路讲解

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

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-02-16

思路讲解

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

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
*/