Codeforces Round #643 (Div. 2)(C ~ E)
C. Count Triangles
题目链接 :
https://codeforces.com/contest/1355/problem/C
题目大意 :
给你 A , B , C , D
问有多少种方法构造出三角形(X , Y , Z)使得 A ≤ X ≤ B ≤ Y ≤ C ≤ Z ≤ D
解题思路 :
假设我们有了 (X + Y) 的长度时（记 X + Y = i ）
根据三角形两边之和大于第三边的性质 Z 的取值范围我们也能确定了
再根据题意 B <= Y <= C , 我们又能得到 X 的取值范围（即构成 X + Y = i 的方案数）
于是答案 ans += (Z的取值范围 * X的取值范围)
而我们已知 A ≤ X ≤ B ≤ Y ≤ C ≤ Z ≤ D 且 (X , Y , Z) 可构成三角形，那么 X + Y 的可取范围也就已知
所以我们可以通过枚举 X + Y 的长度来操作
AC_Code :
#include<bits/stdc++.h> #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); int a , b , c , d , ans = 0; cin >> a >> b >> c >> d; for(int i = c + 1 ; i <= c + d ; i ++) { int l = max(a , i - c); int r = min(b , i - b); if(r < l) continue; ans += (r - l + 1) * (min(d + 1 , i) - c); } cout << ans << '\n'; return 0; }
D. Game With Array
题目链接 :
https://codeforces.com/contest/1355/problem/D
题目大意 :
问你能否构造一个长度为 N 且和为 S 的序列
使得对于该序列你无法找到一个子序列使得子序列的和等于 K 或 S – K (0 <= K <= S)
解题思路 :
猜结论
我们构造一个前 N – 1项为 1，第 N 项为 S – N + 1 的序列
对于前 N – 1项构成的序列的和我们设为 K，那么第 N 项构成的序列和就为 S – K
这样就很好的使用上了题目给的信息，所以盲猜该构造方法是可行的
那么对于该序列，[ 1 , N – 1 ] 和 [ S – (N – 1) , S ] 的值我们都是可以通过选取子序列得到
而 [ N , S – N ] 的值无法得到，所以只要判断 N 是否小于等于 S – N 即可
AC_Code :
#include<bits/stdc++.h> using namespace std; signed main() { ios::sync_with_stdio(false); int n , s; cin >> n >> s ; int ans = s - n; if(ans >= n) { cout << "YES" << '\n'; for(int i = 1 ; i <= n - 1 ; i ++) cout << "1 "; cout << ans + 1 << '\n' << n << '\n'; } else cout << "NO\n"; return 0; }
E. Restorer Distance
题目链接 :
https://codeforces.com/contest/1355/problem/E
题目大意 :
给你一个长度为 N 的序列 H 和三种操作
①、任选一个 Hi 使得 Hi = Hi + 1，代价为 A
②、任选一个 Hi 使得 Hi = Hi – 1，代价为 R
③、任选一个 Hi、Hj 使得 Hi = Hi + 1 , Hj = Hj – 1 ，代价为 M
现要使整个序列的数的值都相同，问需要花费的最小代价为多少
解题思路 :
操作③ = 操作① + 操作②，如果 A + R <= M，那么对于操作③我们只要用操作① + ②代替即可
因为最后整个序列的值都相同(我们记最后的值为 X)，那么暴力的做法就是枚举 X 然后选择最小代价
显然暴力的做法复杂度是不行的
但是通过枚举我们会发现 , 在 X 的可行域内 F(X) 呈一种单峰函数（F(X)指最后序列值全为 X 的最小代价）
得到了这些信息后这道题就是道三分的裸题了
AC_Code :
#include<bits/stdc++.h> #define int long long using namespace std; const int N = 3e5 + 10; int h[N] , n , a , r , m , ans = 1e18; int check(int mid) { int res = 0 , sum1 = 0 , sum2 = 0; if(a + r <= m) { for(int i = 1 ; i <= n ; i ++) if(h[i] >= mid) res += (h[i] - mid) * r; else res += (mid - h[i]) * a; return res; } for(int i = 1 ; i <= n ; i ++) if(h[i] >= mid) sum1 += h[i] - mid; else sum2 += mid - h[i]; res += min(sum1 , sum2) * m; if(sum1 > sum2) res += (sum1 - sum2) * r; else res += (sum2 - sum1) * a; return res; } signed main() { ios::sync_with_stdio(false); cin >> n >> a >> r >> m; for(int i = 1 ; i <= n ; i ++) cin >> h[i]; int L = 0 , R = 1e9; while(R - L > 10) { int midl = L + (R - L) / 3 , midr = R - (R - L) / 3; if(check(midl) < check(midr)) R = midr; else L = midl; } for(int i = L ; i <= R ; i ++) ans = min(ans , check(i)); cout << ans << '\n' ; return 0; }