Znzryb's Blog

ABC-400-E - Ringo's Favorite Numbers 3

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

思路讲解

约数个数定理

ABC-383-D - 9 Divisors

其实这个约数个数定理是显然的

你想p1的指数有 $0～e_1$ 也就是 $e_1+1$ 种选择，同理，每种都有 $e_k+1$ 种选择

那么根据乘法原理，约束个数也就是 $d(n)=(e_1+1)(e_2+1)…(e_k+1)$

当然喽，只有素因子可以这么玩，非素因子这么玩可能会有重复

当然这道题目关键点不在上面。

$N=p_1^{e_1}p_2^{e_2}$ 由题意可得，e1为偶数，e2也为偶数。所以其实400数要求是完全平方数，而且是只由两个素因子构成。那么其实也就是要求平方数由两个素因子组成。

哈哈，其实这种也是有点套路，一般来说这种都是直接枚举素因子的

我们用埃氏筛筛出所有1e6以内的素数，存储在primes中。然后就枚举就完了。

枚举代码

for(int i=0;i<primes.size();++i){
	ll p=primes[i];
	for(ll j=p;j<=MAXN-10;j*=p){
		for(int k=i+1;k<primes.size();++k){
			ll pk=primes[k];
			if(pk*j>MAXN-10) break;
			for(ll p_k=pk;p_k<=MAXN-10;p_k*=pk){
				if(p_k*j>MAXN-10) break;
				fitNum.pb(p_k*j);
			}
		}
	}
}

AC代码

源代码

// Problem: E - Ringo's Favorite Numbers 3
// Contest: AtCoder - AtCoder Beginner Contest 400
// URL: https://atcoder.jp/contests/abc400/tasks/abc400_e
// Memory Limit: 1024 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>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T;
bool isPrime[MAXN];
vector<ll> primes;
vector<ll> fitNum;	// 符合含有两个素因子的数

inline void solve(){
	cin>>N;
	ll sqN=sqrtl(N);
// #ifdef LOCAL
    // cerr << sqN << '\n';
// #endif
	ll sqAns=*prev(upper_bound(all(fitNum),sqN));
	cout<<sqAns*sqAns<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// 先进行预处理
	for(int i=2;i<=MAXN-10;++i){
		isPrime[i]=true;
	}
	// 埃氏筛
	// 假设MAXN-10以内有一个合数没有标记，那么他必然有一个小于sqrt(MAXN-10)的因子
	for(int i=2;i*i<=MAXN-10;++i){
		if(isPrime[i]){
			for(int j=2*i;j<=MAXN-10;j+=i){
				isPrime[j]=false;
			}
		}
	}
	for(int i=2;i<=MAXN-10;++i){
		if(isPrime[i]) primes.pb(i);
	}
	
	for(int i=0;i<primes.size();++i){
		ll p=primes[i];
		for(ll j=p;j<=MAXN-10;j*=p){
			for(int k=i+1;k<primes.size();++k){
				ll pk=primes[k];
				if(pk*j>MAXN-10) break;
				for(ll p_k=pk;p_k<=MAXN-10;p_k*=pk){
					if(p_k*j>MAXN-10) break;
					fitNum.pb(p_k*j);
				}
			}
		}
	}
	sort(all(fitNum));
// #ifdef LOCAL
    // for(int i=0;i<=10;++i){
    	// cerr<<fitNum[i]<<" ";
    // }
    // cerr<<"\n";
// #endif
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc400/submissions/64639281
*/

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

这个ll是非常需要的，写成int以后就TLE了，可能是因为溢出了。

for(int i=0;i<primes.size();++i){
	ll p=primes[i];
	for(ll j=p;j<=MAXN-10;j*=p){
		for(int k=i+1;k<primes.size();++k){
			ll pk=primes[k];
			if(pk*j>MAXN-10) break;
			for(ll p_k=pk;p_k<=MAXN-10;p_k*=pk){
				if(p_k*j>MAXN-10) break;
				fitNum.pb(p_k*j);
			}
		}
	}
}

ABC-400-C - 2^a b^2 （使用sqrtl）

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

思路讲解

赛时想到思路了，也写出来了，但是死活都会WA四个点。

这种问题一般就是转化成二进制想，其实2^a就是二进制下右移a位。

最后靠AI手写了个二分的开方程序过了，这个是在有点离谱，现在在想我的程序为什么会WA。

找到一个博客，说sqrt是有点问题。

https://codeforces.com/blog/entry/107717

利用sqrtl就过了，离谱，floor(sqrt(i))就不行。

其实sqrtl其实是传入参数为long double，那么其实还是精度问题。我直接这么调用其实还有一个自动向下的隐式转换。

https://en.cppreference.com/w/c/numeric/math/sqrt

AC代码

https://atcoder.jp/contests/abc400/submissions/64576953

源代码

// Problem: C - 2^a b^2
// Contest: AtCoder - AtCoder Beginner Contest 400
// URL: https://atcoder.jp/contests/abc400/tasks/abc400_c
// Memory Limit: 1024 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>(1e6)+10,INF=static_cast<ll>(5e18)+3;

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

inline void solve(){
	cin>>N;
	// ll cnt=0;
	// for(ll i=N;i>0;i/=2){
		// ++cnt;
	// }
// #ifdef LOCAL
    // cerr << cnt << '\n';
// #endif	
	ll ans=0;
	// ll cnt=0;
	// ll upRes=0;
	for(ll i=N>>1;i>0;i>>=1){
		ll res=sqrtl(i); //-floor(sqrt(i>>1));
		res=ceil(res*1.0l/2);
		// ++cnt;
// #ifdef LOCAL
    // cerr<<i<<" " << res << '\n';
// #endif
		ans+=res; // *cnt
	}
	cout<<ans<<"\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……）

666

ABC-400-D - Takahashi the Wall Breaker（BFS双段队列优化or堆优化）

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

思路讲解

双段队列优化，让cnt比较低的先走，这样子保证可以被比较好的剪枝

也可以使用堆优化，比双段队列deque稍慢，但也还行。

AC代码

https://atcoder.jp/contests/abc400/submissions/64555057

双段队列优化源代码

// Problem: D - Takahashi the Wall Breaker
// Contest: AtCoder - AtCoder Beginner Contest 400
// URL: https://atcoder.jp/contests/abc400/tasks/abc400_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h> // Includes <deque>
#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; // Consider if __int128 is really needed, ll might suffice.
typedef pair<ll,ll> pll;
typedef array<ll,3> arr; // {cost, row, col}
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e3)+10;
// Using long long INF is good practice for large grids or costs
constexpr ll INF=static_cast<ll>(4e18); // Adjusted INF to avoid overflow if summing costs many times, though 5e18 is likely fine too.

ll N,M,T,A,B,C,D;
char maze[MAXN][MAXN];
ll vis[MAXN][MAXN]; // Stores minimum cost (spells) to reach cell (i, j)

// Directions for normal moves (cost 0)
ll dx[4]={1,0,-1,0};
ll dy[4]={0,-1,0,1};

// Relative coordinates for magic moves (cost 1)
// This covers adjacent cells (dist 1) and jumps (dist 2) in the 5x5 area
// A more explicit approach with separate loops for adjacent and jumps is also fine.
// Let's stick to the explicit approach for clarity, matching the original intent better.
ll magic_dx[] = {1, 0, -1, 0,  2, 0, -2, 0}; // Adjacent + Jumps X
ll magic_dy[] = {0, -1, 0, 1,  0, 2, 0, -2}; // Adjacent + Jumps Y


inline void solve(){
	cin>>N>>M;
	FOR(i,1,N){
		FOR(j,1,M){
			cin>>maze[i][j];
			vis[i][j]=INF; // Initialize costs to infinity
		}
	}
	cin>>A>>B>>C>>D;

	deque<arr> q; // Use deque for 0-1 BFS

	vis[A][B]=0;
	q.push_front({0,A,B}); // Start with 0 cost, push to front

	while(!q.empty()){
		arr current = q.front();
		q.pop_front();

		ll cnt=current[0];
        ll x=current[1];
        ll y=current[2];

        // Optimization: If we found a shorter path to (x, y) already, skip processing this one.
        if (cnt > vis[x][y]) {
            continue;
        }

		// --- Explore Cost 0 Moves (Normal adjacent moves to '.') ---
		FOR(i,0,3){
			ll fx=x+dx[i];
            ll fy=y+dy[i];

			// Check boundaries
			if(fx<1 || fx>N || fy<1 || fy>M) continue;
            // Can only move normally into empty cells
			if(maze[fx][fy]=='#') continue;

            // If we found a path with the same or lower cost (cnt)
			if(vis[fx][fy] > cnt) { // Use '>' because cost is the same (cnt)
				vis[fx][fy]=cnt;
				q.push_front({cnt, fx, fy}); // Push to FRONT for cost 0
			}
		}

		// --- Explore Cost 1 Moves (Magic: Adjacent or Jump) ---
        ll next_cost = cnt + 1;
        // Iterate through all 8 possible magic moves (4 adjacent, 4 jumps)
		FOR(i,0,7){ // Use the combined magic_dx/dy arrays
			ll fx=x+magic_dx[i];
            ll fy=y+magic_dy[i];

			// Check boundaries
			if(fx<1 || fx>N || fy<1 || fy>M) continue;
            // Can use magic on '#' or '.'

            // If we found a path with lower cost (next_cost)
			if(vis[fx][fy] > next_cost){
				vis[fx][fy]=next_cost;
				q.push_back({next_cost, fx, fy}); // Push to BACK for cost 1
			}
		}
	}

    // Output result
    if (vis[C][D] == INF) {
        // Depending on problem statement, output -1 or the INF value if unreachable
        // Sticking to original behavior: print the value in vis[C][D]
        cout << -1 << "\n"; // Common practice if unreachable needs specific output
    } else {
	    cout<<vis[C][D]<<"\n";
    }
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T; // Uncomment if there are multiple test cases
	// while(T--){
		// solve();
	// }
	solve(); // Call solve once if only one test case
	return 0;
}

https://atcoder.jp/contests/abc400/submissions/64575744

堆优化源代码

// Problem: D - Takahashi the Wall Breaker
// Contest: AtCoder - AtCoder Beginner Contest 400
// URL: https://atcoder.jp/contests/abc400/tasks/abc400_d
// Memory Limit: 1024 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>(1e3)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A,B,C,D;
char maze[MAXN][MAXN];
ll vis[MAXN][MAXN];

ll dx[4]={1,0,-1,0};
ll dy[4]={0,-1,0,1};
ll kx[4]={2,0,-2,0};
ll ky[4]={0,-2,0,2};

struct cmp{
	bool operator()(arr a,arr b){
		return a[0]>b[0];
	}
};

inline void solve(){
	cin>>N>>M;
	FOR(i,1,N){
		FOR(j,1,M){
			cin>>maze[i][j];
			vis[i][j]=INF;
		}
	}
	cin>>A>>B>>C>>D;
	priority_queue<arr,vector<arr>,cmp> q;
	q.push({0,A,B});
	vis[A][B]=0;
	while(!q.empty()){
		ll cnt=q.top()[0],x=q.top()[1],y=q.top()[2];
		q.pop();
		FOR(i,0,3){
			ll fx=x+dx[i],fy=y+dy[i];
			if(fx<1 || fx>N) continue;
			if(fy<1 || fy>M) continue;
			if(vis[fx][fy]<=cnt) continue;
			if(maze[fx][fy]=='#') continue;
			vis[fx][fy]=cnt;
			q.push({cnt,fx,fy});
		}
		FOR(i,0,3){
			ll fx=x+dx[i],fy=y+dy[i];
			if(fx<1 || fx>N) continue;
			if(fy<1 || fy>M) continue;
			if(vis[fx][fy]<=cnt+1) continue;
			vis[fx][fy]=cnt+1;
			q.push({cnt+1,fx,fy});
		}
		FOR(i,0,3){
			ll fx=x+kx[i],fy=y+ky[i];
			if(fx<1 || fx>N) continue;
			if(fy<1 || fy>M) continue;
			if(vis[fx][fy]<=cnt+1) continue;
			vis[fx][fy]=cnt+1;
			q.push({cnt+1,fx,fy});
		}
	}
	cout<<vis[C][D]<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc400/submissions/64575744
*/

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

zkw线段树详细介绍（zkw线段树实现区间修改，区间查询最值）

Posted on 2025-04-04 Edited on 2026-03-14

思路讲解

原来是想用zkw线段树写P1253，但是zkw写懒标记顺序不可调换的题目还是比较难的，我们要顺势而为，这个写zkw就是为了简单，写着反而复杂就干脆不写了。

参考讲解

https://www.cnblogs.com/Judge/p/9514862.html

https://www.cnblogs.com/zsc985246/p/16112689.html

参考这段建树程序

inline void build(){
	for(M=1;M<=N;M<<=1);
	for(int i=M+1;i<=M+1+N;++i){
		cin>>tr[i];
	}
	for(int i=M-1;i;--i){
		tr[i]=max(tr[i<<1],tr[i<<1|1]);
		// 相当于子节点里装的值需要不断+母节点的值+母母节点的值+...+根节点的值
		// 才是真实的值，这样子可以比较好的实现bottom-up修改
		tr[i<<1]-=tr[i],tr[i<<1|1]-=tr[i];
	}
}

这个线段树（求最大值的话）子节点里装的值需要不断+母节点的值+母母节点的值+…+根节点的值才是真实的值，这样子可以比较好的实现bottom-up修改。

加法用这套东西是没有问题的，但容易发现，覆盖用这套操作会稍微有点问题。

https://blog.csdn.net/weixin_43960287/article/details/108246164

看过了，这个问题基本上可以说无解了。

AC代码

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

307. 区域和检索 - 数组可修改（zkw线段树单点修改区间查询）

Posted on 2025-04-04 Edited on 2026-03-14

思路讲解

参考题解以及视频讲解

【数据结构扩展(二) --线段树 (普通+zkw)】【精准空降到 18:48】 https://www.bilibili.com/video/BV1gy4y1D7dx/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=1128

https://www.cnblogs.com/Judge/p/9514862.html

AC代码

https://leetcode.cn/problems/range-sum-query-mutable/submissions/618952189

class NumArray {
public:
    typedef long long ll;
    vector<ll> tree;
    ll N;
    void update(int index, int val) {
        ll diff=val-tree[index+N];
        for(int i=index+N;i>0;i>>=1){
            tree[i]+=diff;
        }
    }
    int sumRange(int left, int right) {
        ll res=0;
        for(int i=left+N,j=right+N;i<=j;i>>=1,j>>=1){
            if(i%2==1) res+=tree[i++];
            if(j%2==0) res+=tree[j--];
        }
        return res;
    }
    NumArray(vector<int>& nums) {
        // for(int i=0;i<nums.size();++i){
        //     lnum.push_back(nums[i]);
        // }
        N=nums.size();
        tree.resize(2*N+5,0);
        for(int i=0;i<nums.size();++i){
            update(i,nums[i]);
        }
        // for(int i=0;i<tree.size();++i){
        //     cout<<i<<": "<<tree[i]<<"\n";
        // }
    }
    
};