E题：
题意：给定的 xi yi 。求有多少点 到给人 若干定点 的曼哈顿距离 和 小于等于D.
因为D 最大时 1e6,-1e6<=xi<=1e6。
所以 可能的 点 的 x 的范围是 [-2e6 2e6]
同理 y 的 范围 一样。
将 x y 分开讨论。
我们可以枚举 某个x 的 个数，找到合法的y 的个数。两者相乘。相乘之后的值累加起来。就是结果。
碰到绝对值，利用排序，来消除绝对值。将 xi yi 都分别排序。
求 f （f的数值最大是1e6，直接开数值桶来维护），我们要遍历 -2e6 到 2e6 的所有范围。
不断的动态维护前缀和后缀。
因为要维护 t 的数值。
所以我们干脆 一个区间一个区间的遍历。（xi 将 [-2e6, 2e6 ]划分成的区间 ）
例如 【-1e6，a[0]）,[a[0],a[1])……因为我们每次搜索的区间是左闭右开的，所以最后一个是2e6+1（多的加1，就是因为右端点是开的）
这样 t 的 数值，很好确定。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int cnt1[N], cnt2[N];
void solve()
{int n;cin >> n;int d;cin >> d;vector<int> a(n + 2);vector<int> b(n + 2);for (int i = 1; i <= n; i++){cin >> a[i] >> b[i];}a[0] = -2e6;a[n + 1] = 2e6 + 1;b[0] = -2e6;b[n + 1] = 2e6+1;auto fun = [&](vector<int> &a, int *cnt) -> void{sort(a.begin(), a.end());int pre = 0;int sub = 0;for (int i = 1; i <= n; i++){sub += a[i];}for (int x = -2e6; x < a[1]; x++){int dis = sub - n * x;if (dis <= d)cnt[dis]++;}for (int i = 1; i <= n; i++){pre += a[i];sub -= a[i];for (int x = a[i]; x < a[i + 1]; x++){int dis = (2 * i - n) * x - pre + sub;if (dis <= d)cnt[dis]++;}}};fun(a,cnt1);fun(b,cnt2);for (int i=1;i<=d;i++){cnt2[i]+=cnt2[i-1];}int ans=0;for (int i=0;i<=d;i++){ans+=cnt1[i]*cnt2[d-i];}cout<<ans<<"\n";
}
signed main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t;t = 1;while (t--){solve();}return 0;
}
F
我们可以猜测，各个函数的嵌套顺序是 可以贪心的。下面是证明。
我们确定了相对的顺序。从 n 个里面选出来k 个，每一个函数有选和不选两种选择。是 01 背包的问题。
dp[0]=1；
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int n,k;cin>>n>>k;vector<pair<int,int>>a(n);for (int i=0;i<n;i++){cin>>a[i].first>>a[i].second;}auto cmp=[&](pair<int,int>&x,pair<int,int>&y)->bool{return (1.0*x.first-1)/(1.0*x.second)<(1.0*y.first-1)/(1.0*y.second);};sort(a.begin(),a.end(),cmp);vector<int>dp(k+1);int ans=0;dp[0]=1;for (int i=0;i<n;i++){for (int j=k;j>=1;j--){dp[j]=max(dp[j],dp[j-1]*a[i].first+a[i].second);}}cout<<dp[k]<<"\n";}
signed main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t;t = 1;// cin>>t;while (t--){solve();}return 0;
}