A(easy)
签到题写了半个多小时。。。
题目描述:
已知一个数n，和区间[L1, R1],[L2, R2],求所有满足L1 <= a <= R1,L2 <= b <= R2，使得a+b=n的所有的解的选法。对于两种选法，若a,b有任意一个数不同，则算作不同的选法。
输入描述:
对于每组测试数据:
第一行包含一个整数n(1 <= n <= 2·10^5)。
第二行包含两个整数L1，R1（1 <= L1 <= R1 <= 10^5)。
第三行包含两个整数L2, R2(1 <= L2 <= R2 <= 10^5)。
分析:
- 看到区间的数据范围就知道不能暴力两重循环枚举a,b;
- 然后发现n的范围是合规的复杂度(于是可以想到将a+b=n变换成b=n-a),这样最多就只用枚举n次
(其实也想了半天才发现)
Right idea:枚举a=L1到R1，b=n-a,再判断b是否在区间[L2, R2]中，如果是，答案+1；
我的ac code比较混乱，没出题人正解好看。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int cnt = 0;
long long l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
int ans1 = l1;
while(ans1 <= r1){
int ans2 = n - ans1;
if(ans2 >= l2 && ans2 <= r2){
cnt++;
}
ans1++;
}
cout << cnt << endl;
}
return 0;
}
正解code:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve() {
int n;
cin >> n;
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
int cnt = 0;
for (int a = l1; a <= r1; a++) {
int b = n - a;
if (b >= l2 && b <= r2) {
cnt++;
}
}
cout << cnt << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
B(medium)
心路历程:
A题是发现n的范围内复杂度够，到B题，n的数据也大了。。。
输入描述:
对于每组测试数据:
第一行包含一个整数n(1 <= n <= 2·10^9)。
第二行包含两个整数L1，R1（1 <= L1 <= R1 <= 10^9)。
第三行包含两个整数L2, R2(1 <= L2 <= R2 <= 10^9)。
思路:
根据a的取值范围[L1, R1],我们求出能满足a+b=n的b的范围是[n-R1, n - L1],(注意不是[n-L1, n - R1], 题解这里写错了！)，但是合法的b的范围是[L2, R2].所以答案是两个区间取交集后的区间长度。
区间取交集的区间长度计算公式：
两个区间[a, b]，[c, d]取交集的区间长度为:len = max(0, min(d,b) - max(a,c) + 1);
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve() {
int n;
cin >> n;
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
int lb = n - r1, rb = n - l1;
// cout << lb << " " << rb << '\n'; //一开始直接按照题解写满足b = n - a的区间，一直错，好在最后发现了~~（题解不是万能，还是得靠自己想）~~
int ans = max(0, (min(rb, r2) - max(lb, l2) + 1));
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
J(easy-medium)
题目描述:
长度为n的序列a。定义MxAb(i,j)=max(|\(a_i\) - \(a_j\)),|\(a_i\) + \(a_j\)|);
求对于所有的i，j(1<=i，j<=n),MxAb(i, j)的和为多少
\(\sum \limits_{i=1}^{n}\sum \limits_{j=1}^{n}\)MxAb\(（i,j)\)
=\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}(|a_i|+|a_j|)\)
=\(\sum\limits_{i=1}^{n}(n·|a_i|+\sum\limits_{j=1}^{n}|a_j|)\)
=\(\sum\limits_{i=1}^{n}n·|a_i|+n·\sum\limits_{j=1}^{n}|a_j|\)
=\(n·\sum\limits_{i=1}^{n}|a_i|+n·\sum\limits_{i=1}^{n}|a_i|\)
=\(2·n·\sum\limits_{i=1}^{n}|a_i|\)
心路历程:
读完题目，模拟的暴力做法就知道了，但是一看范围，铁定tle，于是想方法优化，结果我那点小优化约等于没有优化。给样例解释仅限于理解题解，按样例模拟的做法会tle，所以优化优化再优化。
思路：
看到带有绝对值的式子，一般先展开绝对值。对a[i]和a[j]的正负进行讨论：
a[i] < 0, a[j] < 0 时，max(|a[i] − a[j]|, |a[i] + a[j]|) = |a[i] + a[j]| = |a[i]| + |a[j]|
a[i] < 0, a[j] > 0 时，max(|a[i] − a[j]|, |a[i] + a[j]|) = |a[i] − a[j]| = |a[i]| + |a[j]|
a[i] > 0, a[j] < 0 时，max(|a[i] − a[j]|, |a[i] + a[j]|) = |a[i] − a[j]| = |a[i]| + |a[j]|
a[i] > 0, a[j] > 0 时，max(|a[i] − a[j]|, |a[i] + a[j]|) = |a[i] + a[j]| = |a[i]| + |a[j]|
所以max(|a[i]-a[j]|, |a[i]+a[j]|)=|a[i]|+|a[j]|
那么答案
\(\sum \limits_{i=1}^{n}\sum \limits_{j=1}^{n}\)MxAb\(（i,j)\)
=\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}(|a_i|+|a_j|)\)
=\(\sum\limits_{i=1}^{n}(n·|a_i|+\sum\limits_{j=1}^{n}|a_j|)\)
=\(\sum\limits_{i=1}^{n}n·|a_i|+n·\sum\limits_{j=1}^{n}|a_j|\)
=\(n·\sum\limits_{i=1}^{n}|a_i|+n·\sum\limits_{i=1}^{n}|a_i|\)
=\(2·n·\sum\limits_{i=1}^{n}|a_i|\)
rk1大佬jiangly的写法
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int a[N];
void solve() {
int n;
cin >> n;
LL ans = 0;
for(int i = 1; i <= n; i++){
int a;
cin >> a;
ans += abs(a);
}
ans *= n * 2;
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}