专栏文章

题解：P14304 【MX-J27-T1】分块

CCute_OIer
P14304题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mini7w6s
此快照首次捕获于
2025/12/02 02:50
3 个月前
此快照最后确认于
2025/12/02 02:50
3 个月前
查看原文
核心思想：找规律。

Part 1 暴力做法

直接按照题意模拟，可以获得 3030 分（提交记录）。
这一部分非常简单，观察题目发现要找满足 1≤x≤n1\le x\le n 并且 ⌊x⌋\lfloor\sqrt{x}\rfloor 为 xx 的因数的整数 xx 的数量。直接看代码（如下）。
CPP
#include<bits/stdc++.h>
#define int long long
#define INF 1145141919810
using namespace std;
int q,n;
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>q;//多测
	while(q--){
		cin>>n;
		int ans=0;//统计
		for(int i=1;i<=n;i++)
			if(i%((int)sqrt(i))==0)
				ans++;//符合条件
		cout<<ans<<"\n";
	}
	return 0;
}

Part 2 正解观察

看着这道题就感觉有规律可循，所以我们直接弄一组 q=50,ni=iq=50,n_i=i 的数据。
跑出来：
CPP
1
2
3
4
4
5
5
6
7
7
7
8
8
8
9
10
10
10
10
11
11
11
11
12
13
13
13
13
13
14
14
14
14
14
15
16
16
16
16
16
16
17
17
17
17
17
17
18
19
19
稍加观察，就可以发现一定规律并对其进行分组：
CPP
1 2 3
4 4 5 5 6
7 7 7 8 8 8 9
10 10 10 10 11 11 11 11 12
13 13 13 13 13 14 14 14 14 14 15
16 16 16 16 16 16 17 17 17 17 17 17 18
19 19 ...
...
发现对于第 ii 行（第 ii 组），共有 2×i+12\times i+1 个数字，其中前面 ii 个为 3×i−23\times i-2，中间 ii 个为 3×i−13\times i-1，最后一个为 3×i3\times i。然后就可以差不多写出正解了。

Part 3 半个正解

按照上文去枚举 ii，即可获得 5050 分（提交记录）。这里来详细讲一下，假设我们已经知道了 nn 位于第 ii 行，我们如何推出答案。
我们需要确定 nn 在第 ii 行中的位置。显然，我们需要去除 nn 在前面 i−1i-1 行中的部分；运用高斯求和（对于前面 ii 行包含的数字数量，可以表示为 12×(3+2×i+1)×i=i×(i+2)\frac{1}{2}\times(3+2\times i+1)\times i=i\times(i+2)）可知前面 i−1i-1 行共有 (i+1)(i−1)(i+1)(i-1) 个数字，所以需要让 nn 变为 n−(i+1)(i−1)n-(i+1)(i-1) 之后进行取模。然后按照上文去判断即可，注意如果是最后一个那么取模后的结果是 00（可以发现，其实是不需要取模的，不过我就按照赛时取模的想法写出来了）。
如果 nn 位于第 ii，那么显然 nn 有一个限定范围的区间。上面已经求出前面 i−1i-1 行共有 (i+1)(i−1)(i+1)(i-1) 个数字，前 ii 行共有 i×(i+2)i\times(i+2) 个数字，所以 ii 要满足 (i+1)(i−1)<n≤i×(i+2)(i+1)(i-1)<n\le i\times(i+2)。这样就能找到 ii 了。
代码如下。
CPP
#include<bits/stdc++.h>
#define int long long
#define INF 1145141919810
using namespace std;
int q,n;
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>q;
	while(q--){
		cin>>n;
		int ans=0,kkl=0;
		for(int i=0;;i++){
			int x=i;
			if((x+1)*(x-1)<n&&n<=(x+2)*x){
				ans=x;//找出 i，用 ans 表示
				break;
			}
		}
		int modu=(n-(ans+1)*(ans-1))%(ans*2+1);//位置
		if(modu==0)kkl=3;
		else if(modu<=ans)kkl=1;
		else kkl=2;//判断
		cout<<(ans-1)*3+kkl<<"\n";//输出
	}
	return 0;
}

Part 4 正解

我们发现 Part 3 时间复杂度太高，达到了 O(n)O(\sqrt{n})（因为 i×(i+2)i\times(i+2) 大概在 i2i^2 级别），而我们发现，ii 大概就在 n\sqrt{n} 附近。所以可以优化。
一个无脑做法：直接从 n\sqrt{n} 开始往两边扫。
……

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...