专栏文章

题解：P11495 [ROIR 2019 Day 1] 两次测量

封封禁用户
P11495题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqlo8jz
此快照首次捕获于
2025/12/04 06:50
3 个月前
此快照最后确认于
2025/12/04 06:50
3 个月前
查看原文
这道题题意是在区间区间[l,r] [l, r]中，有多少个对 (i,j)(i, j)满足j−ij-i是aa的倍数。这道题要是枚举只能30分，想得满分只能O(1)O(1)时间复杂度，只能推公式。
t=r−l+1t = r - l + 1 表示时间段 [l,r][l, r] 的总小时数。它表示从ll到rr包括了多少个整点时刻。
(t−t mod a)÷a(t - t \bmod a) \div a 计算的是从 ll 到 rr 时间段中完整的 a 个小时的数量。例如，假设 t=10，a=3t = 10，a = 3,那么 (t−t mod a)÷a=(10−1)÷3=3(t - t \bmod a) \div a = (10 - 1) \div 3 = 3,意味着在这个时间段内完整的自转圈数有 3 个。
t÷a−1t \div a - 1 计算的是从ll到rr时间段内的测量间隔数((即跳过步长为aa的可能测量对数))如果t=10,a=3 t = 10,a = 3,那么 t÷a−1=10÷3−1=2t \div a - 1 = 10 \div 3 - 1 = 2,表示从ll到rr的有效测量区间对数。
t mod at \bmod a 计算的是不能构成完整自转周期的剩余时间。例如，如果 t=10，a=3t = 10，a = 3,那么 t mod a=1t \bmod a = 1,即剩余 11 小时没有组成完整的周期。
t÷at \div a 是时间段内完整的周期数。
(t−t mod a)÷a×(t÷a−1)÷2×a(t - t \bmod a) \div a \times (t \div a - 1) \div 2 \times a 计算的是从完整周期中可以获得的所有合法的 (i,j)(i, j) 对数。
剩余部分的合法对数是 t mod a×(t÷a)t \bmod a \times (t \div a)。

ACcodeAC code

CPP
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using std::cin;
using std::cout;
using std::vector;
const int MAXN = 1e5 + 10;

void solve();
signed main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int _T = 1;
	/*cin >> _T;*/
	while (_T--) {
		solve();
	}

	return 0;
}

void solve(){
	int l, r, a ,t;
    cin>>l>>r>>a;
	t=r-l+1;
	cout<<(t-t%a)/a*(t/a-1)/2*a+t%a*(t/a);

}

评论

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

正在加载评论...