Educational Codeforces Round 172 (Rated for Div. 2)
广告:starrycoding九折优惠码(FV7B04LL)
A
思路
- 需要拿至少 \(k\) 枚硬币.
- 从大到小拿.
- 拿到的硬币最少.
题目没有要求补硬币的数目, 要求回答的是拿最少硬币时至少补多少.
而拿取的最小值最少为 \(k\).
求从大到小拿取到哪个箱子时, 再拿下一个箱子就超过 \(k\), 补足此时的硬币即可.
代码
void func(void)
{
int n,k;
cin >> n >> k;
vector<int> a(n+1);
for(int i=1;i<=n;++i) cin >> a[i];
sort(a.begin()+1,a.end(),greater<int>());
int sum = 0;
for(int i=1;i<=n;++i)
{
if(sum + a[i] > k)
{
cout << k - sum << '\n';
return ;
}
sum += a[i];
}
cout << (k-sum > 0 ? k-sum : 0) << '\n';
}
B
思路
对于每种弹珠, 最多拿 \(2\) 分, 设此种弹珠总数 \(cnt\) 可以计算.
- \(cnt = 1\)
- \(2\) 分需要 \(1\) 次.
- \(cnt > 1\)
- \(1\) 分需要 \(1\) 次.
- \(2\) 分需要 \(cnt > 1\) 次.
对于有 \(cnt > 1\) 的弹珠, A 拿取 \(1\) 个后, B 可以再拿 \(1\), 使得 A 无法拿到所有.
最佳策略为:
AB均抢占 \(cnt = 1\), 的弹珠, 然后 \(cnt > 1\) 的弹珠各拿一个.
总得分为 \(<cnt_1/2> + cnt_{>1}\)(\(<>\) 为向上取整, 因为奇数个时必然是 A 拿到).
代码
void func(void)
{
int n;
cin >> n;
map<int,int> cnt;
for(int i=0;i<n;++i)
{
int X; cin >> X;
cnt[X] ++;
}
int cnt1 = 0, cnt2 = 0;
for(auto &i : cnt)
{
if(i.y == 1) cnt1 ++;
else cnt2 ++;
}
cout << ((cnt1+1)/2 * 2 + cnt2) << '\n';
}
C
思路
对于字符串的 \(01\), \(1\) 可视为抵消 \(0\), 那么将 \(0\) 视为 \(-1\).
- 假设起始只有 \(1\) 个区间.
- 每次增加区间, 就是分割了某个区间.
每次分割操作会使得分割点之右的点贡献 \(+1\).
那么只需要每次贪心贡献最大的分割点, 当总贡献 \(\ge k\) 时输出分割次数即可.
因为每次分割点的贡献是其右侧的贡献之和, 所以使用 后缀和.
将所有后缀和加入一个 大根堆, 每次取出最大的 后缀和, 即分割此处.
大根堆使用 stl 的priority_queue.
代码
void func(void)
{
int n,k;
cin >> n >> k;
string st;
cin >> st;
st = '0' + st;
vector<int> s(n+2);
priority_queue<int> pq;
for(int i=n;i>=2;--i)
{
s[i] = s[i+1] + (st[i] == '0' ? -1 : 1);
pq.push(s[i]);
}
int ans = 1, sum = 0;
while(pq.size())
{
int X = pq.top(); pq.pop();
sum += X;
ans ++;
if(sum >= k)
{
cout << ans << '\n';
return ;
}
}
cout << -1 << '\n';
}
D
思路
题意: 用户\(j\)有一个偏好区间\((L_j,R_j)\). 他需要找到另一些用户\(i\), 他们的区间\((L_i,R_i)\)包含该用户的区间(\(L_i \le L_j \le R_j \le R_i\)). 然后用户\(i\) 们会找到他们区间的共同部分, 将其中 \(j\) 没有的部分推荐给 \(j\). 每次需要回答推荐的次数. 若是 \(i\) 不存在或者不存在推荐部分, 则输出 \(0\).
因为 \(n \le 10^5\), 所以对每个元素的操作应该为 \(logn\).
分析题面后, 我们实际上需要求包含 \(j\) 的区间的最大 \(L\) 和 最小 \(R\).
我们可以分别处理.
\(L\):
先根据区间的 \(R\) 从大到小排序(\(R\) 相同时根据 \(L\)从小到大排, 保证大区间先加入, 小区间可以被包含), 将区间顺序(实际加入的是 \(L\))加入一个容器.
- 先加入的元素 \(R\) 一定大于后加入的元素的 \(R\).
- 那么后加入的元素不可能包含先加入的
然后判断当前容器中有没有小于等于 \(L_j\) 的, 最大的值即为该 \(j\) 的 \(ans_L\)
\(R\):
同理, 按区间 \(L\) 从小到大排序.
- 后加入的元素不可能包含先加入的
然后判断当前容器中有没有大于等于 \(R_j\) 的, 最小的值即为 \(j\) 的 \(ans_j\).
注意:
- 如果有完全相同的区间, 若是代码有漏网之鱼, 需要将其单独处理掉.
- 排序后的插入, 保证先插入大区间, 小区间可以被大区间包含.
因为对于每个元素查找 \(ans_L, ans_R\)需要 \(log\)级别, 所以需要用 二分查找.
而 set 的插入也只是 \(log\), 且自动排序和支持二分 所以上述的容器可以使用 set.
代码
#include<bits/stdc++.h>
#define Start cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define PII pair<int,int>
#define x first
#define y second
#define ull unsigned long long
#define ll long long
using namespace std;
struct sth
{
int x,y,z;
bool operator < (const sth &i) const
{
return(z == i.z ? (y == i.y ? x < i.x : y < i.y) : z < i.z);
}
};
const int M = 1000000007;
const int N = 2e5 + 10;
bool cmp1(sth a,sth b)
{
return (a.y == b.y ? a.x < b.x : a.y > b.y);
}
bool cmp2(sth a,sth b)
{
return (a.x == b.x ? a.y > b.y : a.x < b.x);
}
void func(void);
signed main(void)
{
Start;
int _ = 1;
cin >> _;
while(_--) func();
return 0;
}
void func(void)
{
int n;
cin >> n;
vector<sth> a(n+1);
vector<PII> ans(n+1,{-1,-1});
map<PII,vector<int>> check;// 处理完全重复的结果
for(int i=1;i<=n;++i)
{
cin >> a[i].x >> a[i].y;
a[i].z = i;
check[{a[i].x,a[i].y}].push_back(i);
}
set<int,greater<int>> s1;
sort(a.begin()+1,a.end(),cmp1);// 第一次排序
for(int i=1;i<=n;++i)
{
auto X = s1.lower_bound(a[i].x);
if(X != s1.end()) ans[a[i].z].x = *X;
s1.insert(a[i].x);
}
set<int> s2;
sort(a.begin()+1,a.end(),cmp2);// 第二次排序
for(int i=1;i<=n;++i)
{
auto X = s2.lower_bound(a[i].y);
if(X != s2.end()) ans[a[i].z].y = *X;
s2.insert(a[i].y);
}
sort(a.begin()+1,a.end());// 恢复区间, 按顺序输出
for(auto &i : check)
{
if(i.y.size() > 1)
{
for(auto &j : i.y) ans[j] = {-1,-1};// 处理重复区间
}
}
for(int i=1;i<=n;++i)
{
int X = (ans[i].y - ans[i].x - (a[i].y - a[i].x));
if(ans[i].x == -1 || ans[i].y == -1 || X < 0) cout << 0 << '\n';
else cout << X << '\n';
}
}