dede调用网站名称,网站建设哪家公司好,昆山 网站设计,wordpress 代做网站Pinely Round 3 (Div. 1 Div. 2)
Pinely Round 3 (Div. 1 Div. 2)
A. Distinct Buttons
题意#xff1a;当前处于(0, 0)原点#xff0c;给出若干个平面坐标轴上的点#xff0c;是否可以仅选择三个方向便可以到达所有给出的点。
思路#xff1a;到达单一坐标点最多需要…
Pinely Round 3 (Div. 1 Div. 2)
Pinely Round 3 (Div. 1 Div. 2)
A. Distinct Buttons
题意当前处于(0, 0)原点给出若干个平面坐标轴上的点是否可以仅选择三个方向便可以到达所有给出的点。
思路到达单一坐标点最多需要两个方向记录到达每个点需要的方向若四个方向都需要用到则不可能仅选择三个方向。
AC code
void solve(){cin n;int x 0, y 0;int l 0, r 0, u 0, d 0;for(int i 0; i n; i ){int t, v; cin t v;if(t 0) l ;if(t 0) r ;if(v 0) u ;if(v 0) d ;}if(l r u d){cout NO endl;return;}cout YES endl;
}B. Make Almost Equal With Mod
题意给出一个长度为n的正整数数组a现在必须选择一个正整数k然后对于数组a中的每一个数将 a i a_i ai替换为 a i a_i aimod k该操作有且只有一次在操作后数组a中的元素必须有且仅有两个数不同找出可能的k值。
思路从二进制低位开始考虑k值即从2开始考虑 2的余数只有0或1两种可能即二进制最低位是否为1若2取余后均为同一数说明二进制最低位要么全是0要么全是1我们开始考虑次低位以此类推题目保证一定存在k值所以从二进制最低位开始遍历。
k最大可能为1e18则遍历的不会超过60位。
AC code
void solve(){cin n;int x 0, y 0;int mn 1e18;for(int i 1; i n; i ){cin a[i];}for(int i 1; i 1e18; i * 2){mapint, int mp;for(int j 1; j n; j )mp[a[j] % i] ;if(mp.size() 2){cout i endl;return;}}
}C. Heavy Intervals
题意给出左区间数组l和右区间数组r以及每个区间的权值数组c现在需要将l和r进行任意匹配保证每个区间的rl然后将权值数组c与每个区间进行配对最终每个区间的权值为( r i r_i ri- l i l_i li)* c i c_i ci现在需要最小化区间权重的总和。
思路
首先所有区间的差加起来是恒定的需要去分配这些差在每个区间的大小然后在将小区间与大权值进行配对那么现在问题在于如何找到最佳的区间。
这里需要将大区间尽可能的扩大从而分配给更小的权值然后相对的令小区间更小分配给更大的权值从而最小化区间权值总和。我们还需要保证每个区间都必须符合rl的必须条件所以不能盲目的用最大的r去匹配最小的l来最大化区间。
这里可以以右区间r为基准因为要保证rl可以将左区间l排序后找到第一个小于r的数然后将该数从l区间中删除两种操作的最佳选择是set中的*prev(s.lower_bound®)反转lower_bound函数从寻找大于等于r的第一个元素变为寻找第一个小于r的元素。
在匹配到每一对合法区间后可以用pair进行存取然后根据区间差进行升序排序当然可以直接存区间差进行排序然后对权值数组c进行降序排序一一对应通过( r i r_i ri- l i l_i li)* c i c_i ci得到最后的最小区间权值和。
AC code
#includebits/stdc.h
#define endl \n
#define int long long
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;typedef long long LL;
typedef pairchar, int PCI;
typedef pairint, int PII;
const int N 3e510, M 2001;
const int INF 0x3f3f3f3f3f, mod 998244353;
int T, n;
int l[N], r[N], c[N];
mapint, int st;bool cmp(PII a, PII b){return a.second - a.first b.second - b.first;
}void solve(){vectorPII cnt;cin n;for(int i 1; i n; i ) cin l[i];for(int i 1; i n; i ) cin r[i];for(int i 1; i n; i ) cin c[i];sort(l 1, l n 1);sort(r 1, r n 1);sort(c 1, c n 1, greaterint());setint s(l 1, l n 1);for(int i 1; i n; i ){auto it prev(s.lower_bound(r[i]));cnt.push_back({*it, r[i]});s.erase(it);}sort(cnt.begin(), cnt.end(), cmp);int ans 0, t 1;for(auto [x, y] : cnt){ans (y - x) * c[t ];}cout ans endl;
}signed main(){fast();T 1;cin T;while(T --){solve();}return 0;
}
