C. Messenger in MAC
给两个数组 a,b 和 一个整数L.寻找一个关于a,b下标的序列p,使得 \(\sum a_{p_i} + \sum |b_{p_i}-b_{p_{i+1}}| \leq L\)
Solution
Key1: 按照 b 从小到大排序一定是最优的.
Key2: 固定 \(b_l\) ,\(b_r\) ,那么 \(\sum^r_l |b_{p_i}-b_{p_{i+1}}| = b_r - b_l\) ,是一个固定值,就可以随便删中间的a_i 和 b_i ,只需使 \(\sum a \leq L - (b_r - b_l)\) .
只需要固定 \(l\) ,然后从左到右扩展.优先队列维护当前 a 的最大值,如果sum超出,就删去最大元素.
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n,L;
cin>>n>>L;
vector<pair<int,int> >a(n);
for(int i=0;i<n;i++)
cin>>a[i].second>>a[i].first;
// b:first a:second
sort(a.begin(),a.end());
int ans = 0;
for(int l=0;l<n;l++){
priority_queue<int> q;
int sum = 0;
for(int r =l;r<n;r++){
q.push(a[r].second);
sum+=a[r].second;
while(q.size()&&sum > L -(a[r].first-a[l].first)){
sum -= q.top();
q.pop();
}
ans = max(ans,(int)q.size());
}
}
cout<<ans<<'\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin>>T;
while(T--)
solve();
return 0;
}
\(O(n^2logn)\)
D. Exam in MAC
给一个集合 \(s\) 和正整数 \(c\) 问 \(0~c\) 中有多少个数对 \((x,y)\) , \(x\leq y\) 满足 x+y not in s,且 y-x not in s.
Solution
直接计算满足条件的 \(x,y\) 是困难的,因为判断满足条件则需要挨个条件都判断,集合 \(s\) 的大小为1e5.
但只要算出所有情况减去不合法的情况数就可以了.
所有情况数为 \(C^{2}_{n+2}\) (可以列一下情况看看)
不妨假设 \(x+y = t \in s\) ,那么就有 \(t/2+1\) 种情况.
再若 \(y-x = t \in s\),那么就有 \(c - t + 1\) 种情况.
然而考虑到上述两种情况是会有重复的:比如 \(1+2=3,2-1=1\) ,在考虑\(s_i=3\) 时过滤掉 \((1,2)\), \(s_i = 1\) 又会再去掉一次这种情况.这样就计算重复了.
第一遍做的时候思路卡在这里了,于是看了一下题解的Hint.说对于方程组 \(x+y = s_i,y-x = s_j\) ,其解只会有0或1个.
也就是说,重复情况只会多算0次或1次.
考虑上述方程组的解为 \(x = (s_i-s_j)/2\), \(y = (s_i+s_j)/2\) ,又 \(x\) 和 \(y\) 均为整数,那么只有 \(s_i\) 和 \(s_j\) 奇偶性相同时才会有整数解.
那么不妨将这些数按奇偶分成左右两组.重复计算的情况一定是从左边挑出两个或者从右边挑出两个.(为了保证0<=x<=y<=c,我们每次从集合中按照组合的方式挑出两个,而不是有放回的挑出两个,这样可以避免出现x<0或者x>y的情况.不要忘了两个数若为同一个也是可以的.所以最后答案加上集合s的所有数的个数)
并且上述方程组解出来的x和y一定是有效的(都小于等于c,显然).
那么最后答案显然为
$ans = C^{2}_{n+2} - \sum {\forall t \in S} (t/2+1) - \sum {\forall t \in S} (n - t + 1) + C^{2} + C^{2} + n $.
最后交上一发过掉,hh.(你说得对但是t宝是怎么做到4分钟读题+1A的...!!!)
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n,c;
cin>>n>>c;
int odd = 0,even = 0;
vector<int>a(n);
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]%2){
odd++;
}
else
even++;
}
int res = (c+1)*(c+2)/2;
for(int i=0;i<n;i++){
res -= a[i]/2+1;
res -= (c-a[i]+1);
}
// cout<<res<<' ';
res += (odd*(odd-1))/2 + (even*(even-1))/2;
res += n;
cout<<res<<'\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin>>T;
while(T--)
solve();
return 0;
}