Codeforces Round 932 (Div. 2)
C. Messenger in MAC
题目大意
给定一些\(a_i\)\(和b_i\),选出尽量多的\(a_i 和b_i\)，使得\(\sum_{i=1}^k a_{p_i}+\sum_{i=1}^{k-1}\left|b_{p_i}-b_{p_{i+1}}\right|\)小于给定的\(l\)。
题目解析
由于题目没有要求\(\{ p\}\)是升序排列的序列，因此我们可以改变\(a_i\)的顺序。注意到\(a_i\)的值是无法改变的，$$\sum_{i=1}^{k-1}\left|b_{p_i}-b_{p_{i+1}}\right|$$可以通过改变 \(b_i\)的顺序改变大小。考虑到贪心，最终一定有\(b_{p_i}\leq b_{p_{i+1}}\)。
（假设有 \(a<b<c\)，一定是 \(|a-b|+|b-c|<|a-c|+|b-c|\)）
因此先按照\(b\)的大小对序列 \(\{ab\}\)进行排序，假设选择了从\(l——r\)的若干对 \(ab\)，一定有 \(\sum_{i=1}^{k-1}\left|b_{p_i}-b_{p_{i+1}}\right|=b_r-b_l\)（已经对 \(b\)排序了，所以一定是升序排列），接着只要处理\(\sum_{i=1}^k a_{p_i}\)即可。
我们不妨考虑双指针的写法进行 \(O(N^2)\)遍历：固定住最左边的数字后，不停的向右移动指针。令\(res\)表示当前的\(\sum_{i=1}^k a_{p_i}+\sum_{i=1}^{k-1}\left|b_{p_i}-b_{p_{i+1}}\right|\)，每次向右移动指针时，\(res-b_r+b_{r+1}\)，同时通过优先队列，将所有的\(a_i\)从大到小的排序，每当答案过大时，就从优先队列中排除若干个\(a_i\)，直到小于\(l\)为止。
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2007;
ll a[N] , b[N] ;
void solve() {
int n,L;
scanf("%d%d",&n,&L);
vector<pair<ll,ll> >c(n);
for(auto &[x,y]:c) {
scanf("%lld%lld",&y,&x);
}
ll ans = 0;
// 根据第二元素为关键字
sort(c.begin(),c.end());
for(int i = 1 ; i <= n ; i++) {
b[i] = c[i-1].first;
a[i] = c[i-1].second;
}
for(int l = 1 ; l <= n ; l++) {
priority_queue<ll> q;
ll sum =0;
for(int r = l ; r <= n ; r++) {
q.push(a[r]);
sum += a[r];
while(sum + b[r] - b[l] > L && q.size() ) {
sum -= q.top();
q.pop();
}
ans = max(ans,(ll)q.size());
}
}
printf("%lld\n",ans);
}
int main() {
int tc;
cin >> tc;
while(tc--)
solve();
}
D. Exam in MAC
题目大意
给定一个大小为 n 的集合 s 和一些奇怪的整数 c。对于这个集合，需要计算整数对 (x,y) 的数量，使得 0 ≤ x ≤ y ≤ c，x+y 不包含在集合 s 中，且 y-x 也不包含在集合 s 中。
题目解析
考虑鸽笼原理。我们记"\(x+y\in s\)"为条件一，"\(y-x\in s\)"为条件二，若需要两者都不满足，可以写为：
\[sum-condition1-condition2+(condition1\&condition2) \]即减去满足条件一的的数量、满足条件二的数量后，再加上满足两个条件的数量。
- 对于条件一：假设\(i=x+y,i\in s\)，则满足此条件的\(x,y\)有 \(i/2+1\)对。
- 对于条件二：假设\(i=x-y,i\in s\)，则需要注意，\(x\leq c,y\leq0\)，一共有 \(c-i+1\)对 \((x,y)\)满足此条件。
- 对于条件一和条件二同时满足：假设 \(x+y=i,y-x=j\)，有 \(2y=i+j(j\leq i)\)，且\(i+j\)是偶数，因此必须是奇数加奇数、偶数加偶数的形式。假设\(s\)中有\(n\)个奇数，则只选择奇数作为\(i,j\)会产生\(\frac{(n+1)*n}2\)个符合条件的\((x,y)\)（对于\(s\)中第一个奇数，有\(n\)个数字和其能匹配；对于第二个奇数，由于大于第一个奇数，所以只能和第二个及以后的数字匹配），偶数同理。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
ll n,c;
scanf("%lld%lld",&n,&c);
vector<ll>a(n);
for(auto &i:a) scanf("%lld",&i);
ll ans = (c+1)*(c+2)/2 ,cnt = 0;
for(auto i:a) {
ans -= (c-i+1); // x-y=i
ans -= (i/2+1);// x+y=i
if(i%2) cnt++;
}
auto C = [&](ll n) {// 从n里面选2个
return (n+1)*n/2;
};
ans += C(cnt) + C(n-cnt);
printf("%lld\n",ans);
}
int main() {
#ifdef jhon
freopen("std.in","r",stdin);
#endif
int tc;
cin >> tc;
while(tc--)
solve();
}