abc 366 E+F(曼哈顿距离 x y 两个坐标分别计算)(贪心+01背包)

本文主要是介绍abc 366 E+F(曼哈顿距离 x y 两个坐标分别计算)(贪心+01背包)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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;
}