Tokitsukaze and a+b=n (medium)

news/2024/11/19 12:33:39/

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

easy 与 medium 的唯一区别是输入的数据范围。

Tokitsukaze 有一个整数 nnn，以及 222 个区间 [L1,R1][L_1,R_1][L1,R1], [L2,R2][L_2,R_2][L2,R2]。

她想知道有多少种选法，满足：从第一个区间选择一个整数 aaa (L1≤a≤R1L_1 \leq a \leq R_1L1≤a≤R1)，从第二个区间选择一个整数 bbb (L2≤b≤R2L_2 \leq b \leq R_2L2≤b≤R2)，使得 a+b=na+b=na+b=n。

对于两种选法，若 aaa, bbb 中有任意一个数不同，则算作不同的选法。

输入描述:

第一行包含一个整数 TTT (1≤T≤1051 \leq T \leq 10^51≤T≤105)，表示测试数据组数。对于每组测试数据：第一行包含一个整数 nnn (1≤n≤2⋅1091 \leq n \leq 2 \cdot 10^91≤n≤2⋅109)。第二行包含两个整数 L1L_1L1, R1R_1R1 (1≤L1≤R1≤1091 \leq L_1 \leq R_1 \leq 10^91≤L1≤R1≤109)。第三行包含两个整数 L2L_2L2, R2R_2R2 (1≤L2≤R2≤1091 \leq L_2 \leq R_2 \leq 10^91≤L2≤R2≤109)。

输出描述:

对于每组测试数据，输出一个整数表示答案。

示例1

输入

4
5
3 5
1 4
1000000000
1 1000000000
1 1000000000
2000000000
1 1000000000
1 1000000000
114
514 1919
8 10

输出

说明

第一组测试数据：共有 222 种选法，分别是 (3+23+23+2), (4+14+14+1)。

Tokitsukaze and a+b=n (easy)_星河欲转。的博客-CSDN博客

//前面的这道题或许暴力循环即可，后面这道因为数据范围的原因我们只能去寻找其规律，如果说我们做第一题可以理解为模拟得出结果，那么第二题就需要思维了。

//我们所要求的即是l1-r1这个区间的数加上l2-r2这个区间的数，如果等于给定的n，那么就计数一次，那么我们可以理解为求l1-r1这个区间和（n-r2）-（n-l2）这个区间的交集。

注：为什么那里是0ll，因为需要统一max里面的数据类型，均为longlong型

题解 | #B Tokitsukaze and a+b=n (medium)#2023牛客寒假算法基础集训营2_牛客博客 (nowcoder.net)

牛客 ABCDEHJL. 牛客寒假集训2 - AcWing

#include<bits/stdc++.h>
using namespace std;
int main(){long long t,n,l1,r1,l2,r2;cin>>t;while(t--){long long s=0;cin>>n;cin>>l1>>r1;cin>>l2>>r2;      s=max(0ll,min(r1,n-l2)-max(l1,n-r2)+1);cout<<s<<endl;}return 0;
}