Pinely Round 3 (Div. 1 + Div. 2)
题意:当前处于(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;
}
题意:给出一个长度为n的正整数数组a,现在必须选择一个正整数k,然后对于数组a中的每一个数将 a i a_i ai?替换为 a i a_i ai?mod 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){
map<int, int> mp;
for(int j = 1; j <= n; j ++)
mp[a[j] % i] ++;
if(mp.size() == 2){
cout << i << endl;
return;
}
}
}
题意:给出左区间数组l和右区间数组r以及每个区间的权值数组c,现在需要将l和r进行任意匹配,保证每个区间的r>l,然后将权值数组c与每个区间进行配对,最终每个区间的权值为( r i r_i ri?- l i l_i li?)* c i c_i ci?,现在需要最小化区间权重的总和。
思路:
首先所有区间的差加起来是恒定的,需要去分配这些差在每个区间的大小,然后在将小区间与大权值进行配对,那么现在问题在于如何找到最佳的区间。
这里需要将大区间尽可能的扩大,从而分配给更小的权值,然后相对的令小区间更小,分配给更大的权值,从而最小化区间权值总和。我们还需要保证每个区间都必须符合r>l的必须条件,所以不能盲目的用最大的r去匹配最小的l来最大化区间。
这里可以以右区间r为基准,因为要保证r>l,可以将左区间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:
#include<bits/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 pair<char, int> PCI;
typedef pair<int, int> PII;
const int N = 3e5+10, M = 2001;
const int INF = 0x3f3f3f3f3f, mod = 998244353;
int T, n;
int l[N], r[N], c[N];
map<int, int> st;
bool cmp(PII a, PII b){
return a.second - a.first < b.second - b.first;
}
void solve(){
vector<PII> 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, greater<int>());
set<int> 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;
}