2022/1/5

[ Paimon Sorting ]( D (codeforces.com) )

思路

设前i-1个数的最大值是 Max

1. 当a[i]<Max 时，只有在最后一轮交换时才产生贡献，贡献为前i个大于a[i]的数量，（去重后
2. 当a[i]==Max时，不产生贡献
3. 当a[i]>Max时，产生的贡献为 2+cnt. cnt为第二次出现Max的位置到i的数个数。

参考代码

#include<bits/stdc++.h>
#define ll  long long
#define pii pair<int, int >
#define se second
#define pb push_back
#define pf push_front
#define si size()
#define db double
#define ls (p<<1)
#define rs (p<<1|1)

#define fi first
#define se second
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}

const int qs=2e5+7;
const ll mod=998244353;


ll T,n,k,u[qs],c[qs],a[qs]; 

ll lb(ll x){
	return x&(-x);
}

void add(ll x,ll val){
	for(;x<=n;x+=lb(x)) c[x]+=val;
}

ll ask(ll x){
	ll ret=0;
	for(;x>0;x-=lb(x)) ret+=c[x];
	return ret; 
}

int main(){
	T=read();
	while(T--){
		n=read();
		for(int i=1;i<=n;++i) a[i]=read(),u[i]=0,c[i]=0;
		ll Max=-1,ans=0,flag=0,cnt=0;
		for(int i=1;i<=n;++i) {
			if(!u[a[i]]) add(a[i],1),u[a[i]]=1;
			if(i==1){
				Max=a[i];
				cout<<"0";
				continue; 
			}
			if(a[i]==Max||flag) cnt++;
			if(a[i]>Max){
				flag=0;
				ans=ans+2+(cnt ? cnt-1 : 0);
				Max=a[i];
				cnt=0;
			}	
			else if(a[i]==Max) {
				//cout<<"i="<<i<<" Max="<<Max<<"\n";
				flag=1;
			}
			else{
				ans=ans+ask(Max)-ask(a[i]);
			}
			cout<<" "<<ans;
		}
		cout<<"\n";
		
	}

	return 0;
}

[ J. Xingqiu's Joke ]( Problem - J - Codeforces )

思路

设 a<b ,c=b-a，g是c的质因子。

根据同余定理有: \(a \equiv b(modg)\)

那么对于\((a,b,c)\),我们需要将其转换为$ (\lfloor { \frac ag } \rfloor ,\lfloor { \frac bg } \rfloor,\frac cg)$ 或者我们需要将其转换为$ (\lceil { \frac ag } \rceil ,\lceil { \frac bg } \rceil,\frac cg)$ 。

在两者中取步数小的。

注意用unordered_map,map会超时。

unordered_map 对 pair 存储

struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
}; 
unordered_map< pii ,ll,hash_pair> mp;

参考代码

#include<bits/stdc++.h>
#define ll  long long
#define pii pair<int, int >
#define se second
#define pb push_back
#define pf push_front
#define si size()
#define db double
#define ls (p<<1)
#define rs (p<<1|1)

#define fi first
#define se second
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}

const int qs=2e5+7;
const ll mod=998244353;
struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
}; 

ll T; 
vector<ll> v;
unordered_map< pii ,ll,hash_pair> mp;
ll dfs(ll a,ll c){
	if(a==1) return 0;
	if(c==1) return a-1;
	if(mp[{a,c}]) return mp[{a,c}];
	ll Min=a-1;
	for(int i=0;i<v.si;++i){
		ll p=v[i];
		if(c%p==0){
			ll x=a%p;
			Min=min(Min,min(x+1+dfs(a/p,c/p),p-x+1+dfs(a/p+1,c/p)));
		}
	}	
	return mp[{a,c}]=Min; 
}

int main(){
	T=read();
	while(T--){
		v.clear();
		ll a,b,c;
		a=read(),b=read();
		if(a<b) swap(a,b);
		c=a-b;
		for(int i=2;i*i<=c;++i){
			if(c%i==0){
				v.pb(i);
				while(c%i==0) c/=i;
			}
		}
		if(c>1) v.pb(c);
		cout<<dfs(b,a-b)<<"\n";
		
	}

	return 0;
}