题解：CF2157F Git Gud

令操作次数

M = 10^6

, 则

1000=\sqrt{M}

，

N=\frac{M}{4}

。后续会用这些分析次数。

$1.5\times 10^6$ 做法

假设没有

+1000

的代价，那么很自然会想到从小到大枚举

y

并将

l

设为

1

，次数

N

。

进一步，看到

\sqrt{M}=1000

自然会联想到根号分块做法。我们不妨每

B

个数字分成一个块，然后对于每个块所代表的区间

[kB+1,(k+1)B]

，让它们都变成

(k+1)B

。这里，可以用类似前文所提到的操作，有一点不一样的是你要把从后往前的每一块一起做。这一步的操作次数是

N+B\sqrt{M}

。这一步操作我们称之为“基本操作”。

此时，我们剩下了

B, 2B, \ldots, N

这

\frac{N}{B}

个数字。再用一次前文所提到的操作。这一步的操作次数是

N+\frac{N\sqrt{M}}{B}

。我们称之为“最终操作”。

B

取

\sqrt{N}

并将两步结合起来得到

2N+2\sqrt{NM}

，无法通过此题。

$O($ 能过 $)$ 做法

只分一次块根本过不了，那我们是否可以多次分块呢？

分块时先分成长度为

K

的块执行一次基本操作，再把剩下的

\frac{N}{K}

个数字分成长

B

的块执行一次，最后执行一次最终操作。操作次数为

N+K\sqrt{M}+N+B\sqrt{M}+N+\frac{N\sqrt{M}}{KB}

。

化一下式子，

3N+(B+K+\frac{N}{BK})\sqrt{M} \geq 3N+3\sqrt[3]{N}\sqrt{M}

当且仅当

B=K=\sqrt[3]{N}

。可以通过此题。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
int n,B;
basic_string<pair<int,int> >ans;
void out(){
	cout<<ans.size()<<"\n";
	for(pair<int,int>p:ans)cout<<p.first<<" "<<p.second<<"\n";
	exit(0);
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n;
	B=pow(n,0.333333333333);
	for(int i=1;i<B;i++){
		basic_string<pair<int,int> >t;
		for(int j=i;j<=n;j+=B)t+={j,1};
		if(t.size()){
			for(int i=t.size()-1;i>=0;i--)ans+=t[i];
		}
	}
	n/=B;
	if(n==0)out();
	for(int i=1;i<B;i++){
		basic_string<pair<int,int> >t;
		for(int j=i;j<=n;j+=B)t+={j*B,B};
		if(t.size()){
			for(int i=t.size()-1;i>=0;i--)ans+=t[i];
		}
	}
	for(int i=B;i<=n;i+=B)ans+={i*B,B*B};
	out();
	return 0;
}

题解：CF2157F Git Gud

文章操作

$1.5\times 10^6$ 做法

$O($ 能过 $)$ 做法

代码

相关推荐

评论

题解：CF2157F Git Gud

文章操作

1.5×1061.5\times 10^61.5×106 做法

O(O(O(能过))) 做法

代码

相关推荐

评论

$1.5\times 10^6$ 做法

$O($ 能过 $)$ 做法