Znzryb's Blog

Starters 188-Swaps in a String

Posted on 2025-06-22 Edited on 2026-02-17

思路讲解

我感觉可以搞dp（结果看了第二个样例觉得不太行）。

那么其实就是局部最优可以推得全局最优，非常经典的贪心。

那么为什么说这个B朝右朝左选一个最大的就最优了？不会相互影响吗？

那我们来看一个你认为会相互影响的，可以看到，这个是矛盾的。所以不会相互影响

FOR(i,1,N){
	++cnt[S[i]-'A'];
	if(S[i]=='B'){
		L[i]=cnt[0];
	}else if(S[i]=='C'){
		cnt[0]=0;
	}else{
		
	}
}
cnt.assign(10,0);
ROF(i,N,1){
	++cnt[S[i]-'A'];
	if(S[i]=='B'){
		R[i]=cnt[2];
	}else if(S[i]=='A'){
		cnt[2]=0;
	}else{
		
	}
}
FOR(i,1,N){
	if(S[i]=='B'){
		ans+=max(L[i],R[i]);
	}
}

AC代码

https://www.codechef.com/viewsolution/1167971455

源代码

// Problem: Swaps in a String
// Contest: CodeChef - START188
// URL: https://www.codechef.com/problems/SWAPSTR?tab=statement
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT;
char S[MAXN];
/*

*/
inline void init(){
	
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>S[i];
	}
	vector<ll> L(N+5,0),R(N+5,0),cnt(10,0);
	ll ans=0;
	FOR(i,1,N){
		++cnt[S[i]-'A'];
		if(S[i]=='B'){
			L[i]=cnt[0];
		}else if(S[i]=='C'){
			cnt[0]=0;
		}else{
			
		}
	}
	cnt.assign(10,0);
	ROF(i,N,1){
		++cnt[S[i]-'A'];
		if(S[i]=='B'){
			R[i]=cnt[2];
		}else if(S[i]=='A'){
			cnt[2]=0;
		}else{
			
		}
	}
	FOR(i,1,N){
		if(S[i]=='B'){
			ans+=max(L[i],R[i]);
		}
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC https://www.codechef.com/viewsolution/1167971455

*/

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

写了一个下午，一直WA，思路错了。

源代码

// Problem: Swaps in a String
// Contest: CodeChef - START188
// URL: https://www.codechef.com/problems/SWAPSTR?tab=statement
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT;
char S[MAXN];
/*

*/
inline void init(){
	
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>S[i];
	}
	vector<ll> cnt(10,0);
	ll ans=0;
	vector<bool> vis(N+5,false);
	set<ll> s;vector<ll> wp;
	// just process the part of string like "AABBCC" "ABC" "AABC"
	// make these parts vis[i]=true;
	FOR(i,1,N){		
		if(s.empty() && S[i]!='A'){
			s.clear();wp.clear();
			cnt[0]=0;cnt[1]=0;cnt[2]=0;
			continue;
		}
		if(SZ(s)==1 && S[i]=='C'){
			s.clear();wp.clear();
			cnt[0]=0;cnt[1]=0;cnt[2]=0;
			continue;
		}
		if(SZ(s)==2 && S[i]=='A') {
			s.clear();wp.clear();
			cnt[0]=0;cnt[1]=0;cnt[2]=0;
			s.insert('A'),++cnt[S[i]-'A'];
			continue;
		}
		if(SZ(s)==3 && S[i]!='C'){
			s.clear();
			ans+=max(cnt[0]*cnt[1],cnt[1]*cnt[2]);
			cnt[0]=0;cnt[1]=0;cnt[2]=0;
			if(S[i]=='A') s.insert('A'),++cnt[S[i]-'A'];
			FOR(i,0,SZ(wp)-1){
				vis[wp[i]]=true;
			}
			wp.clear();
			continue;
		}
		s.insert(S[i]);
		wp.pb(i);
		++cnt[S[i]-'A'];
	}
	if(SZ(s)==3){
		FOR(i,0,SZ(wp)-1){
			vis[wp[i]]=true;
		}
		ans+=max(cnt[0]*cnt[1],cnt[1]*cnt[2]);
	}
	
#ifdef LOCAL
    FOR(i,1,N){cerr<<vis[i];}
    cerr<<"\n";
    debug(cnt[0]);debug(cnt[1]);debug(cnt[2]);
    debug(ans);
#endif
	cnt.assign(10,0);
	s.clear();
	// process part of string like "ABAB" "AB" "AABB"
	ROF(i,N,1){
		if(vis[i]){
			s.clear();
			cnt[0]=0;cnt[1]=0;cnt[2]=0;
			continue;
		}
		if(S[i]=='C'){
			s.clear();
			cnt[0]=0;cnt[1]=0;cnt[2]=0;
			continue;
		}
		if(S[i]=='A'){
			ans+=cnt['B'-'A'];
		}
		++cnt[S[i]-'A'];
	}
	cnt.assign(10,0);
	ROF(i,N,1){
		if(vis[i]){
			s.clear();
			cnt[0]=0;cnt[1]=0;cnt[2]=0;
			continue;
		}
		if(S[i]=='A'){
			s.clear();
			cnt[0]=0;cnt[1]=0;cnt[2]=0;
			continue;
		}
		vis[i]=true;
		if(S[i]=='B'){
			ans+=cnt['C'-'A'];
		}
		++cnt[S[i]-'A'];
	}
#ifdef LOCAL
    debug(ans);
    FOR(i,0,3){
    	cerr<<cnt[i]<<" ";
    }
    cerr<<"\n";
#endif
	cout<<ans<<"\n";
}

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

1
4
AABC

*/

Starter 189-Avoid Primes

Posted on 2025-06-22 Edited on 2026-02-17

思路讲解

~~主要的收获就是打表~~

ll Ans[MAXN]={0,2,1,3,5,4};

最重要的就是想出来这个，让3，5靠在一起，这样就直接搞定了，后面的构造是很容易的。

AC代码

https://www.codechef.com/viewsolution/1167807254

源代码

// Problem: Avoid Primes
// Contest: CodeChef - START189
// URL: https://www.codechef.com/problems/AVOIDPRIME
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
struct PRIME{		// 1299709 结构体可以命名为pr 一般在全局定义
// AC https://www.luogu.com.cn/record/221212624  (uva 上面的一道题目)
	int n;
	vector<ll> primes;
	vector<bool> isprime;
	PRIME(int n_){
		n=n_;
		isprime.resize(n+5,true);
		isprime[1]=false;isprime[0]=false;
		for(int i=2;i*i<=n;++i){
			if(isprime[i]){
				for(int j=2;j*i<=n;++j){
					isprime[i*j]=false;
				}
			}
		}
		for(int i=2;i<=n;++i){
			if(isprime[i]) primes.pb(i);
		}
	}
};
PRIME pr(MAXN);
ll Ans[MAXN]={0,2,1,3,5,4};
bool isUse[MAXN]={1,1,1,1,1,1};
inline void init(){
	FOR(i,6,N) Ans[i]=0;//isUse[i]=false;
}
// vector<vector<ll> > g={{0},{1,2},{2,1,3},{2,1,3,4},{2,1,3,4,5},{2,1,3,6,4,5},{2,1,3,4,6,4,7}};
inline void solve(){
	cin>>N;
	init();
	// f(p) 就是指的是可以让min(Pi,Pi+1)=素数的i的数量
	
	// if(N>=5) Ans[N]=5,isUse[5]=true,Ans[N-1]=4,isUse[4]=true;
	if(N==2){
		cout<<"2 1\n";return;
	}else if(N==3){
		cout<<"2 1 3\n";return;
	}else if(N==4){
		cout<<"2 1 3 4\n";
		return;
	}
	deque<ll> q;
	FOR(i,3,N){
		ll p=pr.primes[i];
		if(p>N) break;
		q.pb(p);
	}
	ll idx=6;
	FOR(i,6,N){
		if(i%2==0 && q.empty()==false)Ans[i]=q.front(),q.pop_front();
		else{
			while(pr.isprime[idx]){
				++idx;
			}
			Ans[i]=idx;
			++idx;
		}
	}
	FOR(i,1,N){
		cout<<Ans[i]<<" ";
	}
	cout<<"\n";
}

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

*/

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

ABC-411-D - Conflict 2

Posted on 2025-06-22 Edited on 2026-02-17

思路讲解

通过倒序遍历，就可以提前知道这个操作是否会影响最终的服务器端字符串。

ROF(i,Q,1){
	if(op[i]==1){
		if(idx==pos[i]){
			// 那么为什么将服务器字符串赋值给电脑端的操作需要重置字符串为0？
			// 其实答案就藏在上面这个if条件中
			idx=0;
		}
	}else if(op[i]==2){		
		if(idx==pos[i]){	//  那么当我们发现改变该字符串会改变最终状态
			ans+=S[i];
		}
	}else{
		// 比较好理解，就是说当发现sever发现其是来自于pos[i]的时候将idx设置为pos[i]
		if(idx==0){		
		// 这个条件就是说如果pos[i]其会改变最终状态，前面这个pos[i]必须是白板
			idx=pos[i];
		}
	}
}

AC代码

https://atcoder.jp/contests/abc411/submissions/66994292

源代码

// Problem: D - Conflict 2
// Contest: AtCoder - UNIQUE VISION Programming Contest 2025 Summer (AtCoder Beginner Contest 411)
// URL: https://atcoder.jp/contests/abc411/tasks/abc411_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
inline void init(){
	
}
inline void solve(){
	cin>>N>>Q;
	init();
	vector<string> S(Q+5);
	vector<ll> op(Q+5);
	vector<ll> pos(Q+5);
	FOR(i,1,Q){
		cin>>op[i]>>pos[i];
		if(op[i]==2) {cin>>S[i];reverse(S[i].begin(),S[i].end());}
	}
	string ans;ll idx=0;
	ROF(i,Q,1){
		if(op[i]==1){
			if(idx==pos[i]){
				// 那么为什么将服务器字符串赋值给电脑端的操作需要重置字符串为0？
				// 其实答案就藏在上面这个if条件中
				idx=0;
			}
		}else if(op[i]==2){		
			if(idx==pos[i]){	//  那么当我们发现改变该字符串会改变最终状态
				ans+=S[i];
			}
		}else{
			// 比较好理解，就是说当发现sever发现其是来自于pos[i]的时候将idx设置为pos[i]
			if(idx==0){		
			// 这个条件就是说如果pos[i]其会改变最终状态，前面这个pos[i]必须是白板
				idx=pos[i];
			}
		}
	}
	reverse(ans.begin(),ans.end());
	cout<<ans<<"\n";
	
	cout<<S[0]<<"\n";
}

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

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

ABC-411-E - E [max]

Posted on 2025-06-21 Edited on 2026-03-23

思路讲解

在竞技编程中，对于求解概率或期望值的问题，通常可以运用以下技巧：与其求某个最大值与某个特定值重合的概率，不如求该最大值小于或等于该特定值的概率。这个技巧也适用于这个问题：

说实话，这个我确实想到了，但是这个想法被我pass了。其实不应该忽视求什么比较容易的想法的，或者说想到了一些可以求的量，应该去想怎么样。

那么注意到那，我们可以先求概率，接着再求期望，那么P(K)表示≤k最大值小于等于K的概率

这个就是Pk-1和Pk的关系，那么我们现在的重点就是说我们如何快速计算这个，快速完成递推那？

那么这个办法就有很多，我选择是使用优先队列。

AC代码

https://atcoder.jp/contests/abc411/submissions/66998392

源代码

// Problem: E - E [max]
// Contest: AtCoder - UNIQUE VISION Programming Contest 2025 Summer (AtCoder Beginner Contest 411)
// URL: https://atcoder.jp/contests/abc411/tasks/abc411_e
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=998244353;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN][10];
/*

*/
inline void init(){
	
}
ll binpow(ll a,ll k,const ll &p){	// 迭代快速幂
	ll res=1;
	while(k>0){
		if((k&1)==1) res=a*res%p;
		a=a*a%p;
		k>>=1;
	}
	return res;
}
inline void solve(){
	cin>>N;
	init();
	vector<ll> li;
	li.pb(-INF);
	priority_queue<arr2> pq;
	FOR(i,1,N){
		FOR(j,1,6){
			cin>>A[i][j];
			li.pb(A[i][j]);
			pq.push({A[i][j],i});
		}
	}
	sort(all(li));
	li.resize(unique(all(li))-li.begin());
	ll lsz=SZ(li)-1;
	vector<arr2> dp(lsz+5,{0,0});		// dp[i]指的是max值大于i的概率（i是经过离散化的）
	dp[lsz][0]=1,dp[lsz][1]=1;
	vector<ll> cnt(N+5,6);
	vector<ll> org(N+5,0);
	ROF(_,lsz-1,1){
		ll val=li[_+1];ll fac1=1,fac2=1;
		vector<ll> wp;
		while(pq.empty()==false && pq.top()[0]==val){
			ll id=pq.top()[1];
			pq.pop();
			org[id]=max(cnt[id],org[id]);
			cnt[id]--;
			wp.pb(id);
		}
		sort(all(wp));wp.resize(unique(all(wp))-wp.begin());
		FOR(i,0,SZ(wp)-1){
			ll id=wp[i];	// 含有k的面<=k-1的面数
			fac1*=cnt[id];fac1%=mod;
			fac2*=org[id];fac2%=mod;
			org[id]=0;
		}
		// 分子
		dp[_][0]=dp[_+1][0]*fac1%mod;
		dp[_][1]=dp[_+1][1]*fac2%mod;	// 分母
#ifdef LOCAL
    debug(_);
    debug(dp[_][0]);
    debug(dp[_][1]);
    debug(fac1);debug(fac2);debug(val);
#endif
	}
	ll ans=0;
	dp[0][1]=1;	// 避免分母为0导致问题
	ROF(i,lsz,1){
		ll lans=0;
		ll fac1=dp[i][0]*dp[i-1][1]-dp[i-1][0]*dp[i][1];fac1%=mod;
		ll fac2=dp[i][1]*dp[i-1][1];fac2%=mod;
#ifdef LOCAL
	cerr<<"---------\n";
    debug(fac1);debug(fac2);
#endif
		fac2=binpow(fac2,mod-2,mod);
		lans=fac1*fac2%mod*li[i]%mod;	// 变为期望值
		ans+=lans;ans%=mod;
	}
	if(ans<0) ans+=mod;
	cout<<ans<<"\n";
	// cout<<10*binpow(3,mod-2,mod)%mod<<"\n";
}

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

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

没有提交之前WA了几次，其实是因为溢出了，那么我们的binpow模版需要在进入前就对a进行取模。

ll binpow(ll a,ll k,const ll &p){	// 迭代快速幂
	ll res=1;
	a%=mod;
	while(k>0){
		if((k&1)==1) res=a*res%p;
		a=a*a%p;
		k>>=1;
	}
	return res;
}

Starters 189-Number Walks

Posted on 2025-06-20 Edited on 2026-02-17

思路讲解

题面总结

给定一个长度为 N 的数组 A，其中 A[i] ∈ [1, K]。需要构造一个排列 B（1 到 N 的排列），使得对于所有 i ∈ [1, K]，满足 A[B[i]] = i。

对于每个起始位置 i（1 ≤ i ≤ N），求出从位置 i 开始构造满足条件的排列 B 时，相邻元素差值绝对值之和的最小值。

换句话说，要最小化 ∑|B[j] - B[j-1]|，其中 B[1] = i，且 A[B[j]] = j。

输入格式：

第一行：测试用例数 T
每个测试用例：
- 第一行：N 和 K
- 第二行：N 个整数表示数组 A

输出格式：

对于每个测试用例，输出 N 个整数，第 i 个整数表示从位置 i 开始的最小代价。

约束条件：

1 ≤ T ≤ 10³
1 ≤ K ≤ N ≤ 10⁶
1 ≤ A[i] ≤ K
保证至少存在一个满足条件的排列 B

虽然不一定选择最靠近的，但是一定是选择右端最靠近或者左端最靠近点的一侧。

这个如何证明那？

那么我们感性的理解，如果在最优序列中，再次移动需要到 j 的各种情况。

那么我们发现，这个 j 落在外面，l，r 中还是必有一个最优，落在里面那更不必多说了。

okay，那我们也算是成功减小了范围，但是还是不知道怎么做呀？~~继续读题解~~

啊哈，那么我们发现那，这其实是一个前缀dp，即状态转移只和前面一个状态相关，那么前面一个状态里只有 l 和 r，那么答案就呼之欲出了，从前面这个来转移。

那么我们用记忆化搜索，可能这个让人更好理解一点。

那么这个正难则反思想是应用于dp的，但是这个dp也有点难写，过了就行，开摆。

AC代码

https://www.codechef.com/viewsolution/1167791134

源代码

// Problem: Number Walks
// Contest: CodeChef - START189
// URL: https://www.codechef.com/problems/NUMBERWALK
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
inline void init(){
	
}
inline void solve(){
	cin>>N>>K;
	init();
	vector<vector<int>> g(K+5);
	FOR(i,1,N){
		cin>>A[i];
		g[A[i]].pb(i);
	}
	// 要求A[B[i]]==i ，并且使B[i]数组中的数的差值绝对值最小
	vector<ll> memo(N+5,INF);
	auto dfs=[&](auto &&dfs,ll node,ll val)->ll{
		if(memo[node]!=INF) return memo[node];
		if(val==K){
			memo[node]=0;
			return 0;
		}
		ll v=node;
// #ifdef LOCAL
   	// debug(node);debug(val);
// #endif
		auto it=lower_bound(all(g[val+1]),v);
		if(it!=g[val+1].begin()){
			auto it_=prev(it);
			ll diff=abs(*it_-v);
			ll res=dfs(dfs,*it_,val+1);
			memo[node]=min(memo[node],diff+res);
		}
		if(it!=g[val+1].end()){
			ll diff=abs(*it-v);
			ll res=dfs(dfs,*it,val+1);
			memo[node]=min(memo[node],diff+res);
		}
		return memo[node];
	};
	FOR(i,1,N){
		auto it=lower_bound(all(g[1]),i);
		ll ans=INF;
		if(it!=g[1].begin()){
			auto it_=prev(it);
			ll diff=abs(*it_-i);
			ll res=dfs(dfs,*it_,1);
			ans=min(diff+res,ans);
		}
		if(it!=g[1].end()){
			ll diff=abs(*it-i);
			ll res=dfs(dfs,*it,1);
			ans=min(diff+res,ans);
		}
		cout<<ans<<" ";
	}
// #ifdef LOCAL
    // FOR(i,1,N){
    	// cerr<<memo[i]<<" ";
    // }
    // cerr<<"\n";
// #endif
	cout<<"\n";
}

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

*/

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

调试的时候发现这里写错了，应该写1，我写成2了。

FOR(i,1,N){
	auto it=lower_bound(all(g[1]),i);
	ll ans=INF;
	if(it!=g[1].begin()){
		auto it_=prev(it);
		ll diff=abs(*it_-i);
		ll res=dfs(dfs,*it_,1);
		ans=min(diff+res,ans);
	}
	if(it!=g[1].end()){
		ll diff=abs(*it-i);
		ll res=dfs(dfs,*it,1);
		ans=min(diff+res,ans);
	}
	cout<<ans<<" ";
}