源代码:https://github.com/abmcar/ACM/tree/master/OpenjudgeNow/Codeforces/Codeforces%20Round%20%23763%20(Div.%202)
cf合集:https://github.com/abmcar/ACM/tree/master/OpenjudgeNow/Codeforces
A. Robot Cleaner
题目大意:给你一个n*m的网格,给你一个扫地机器人的坐标和垃圾坐标,扫地机器人每次可以清理和他同行和同列的的垃圾,每次机器人会向右下移动,遇到墙会反弹,问它移多少次可以清扫到垃圾
思路:分别在x、y轴判断机器人到达同行或者同列的时间,只需要判断是否会反弹回来即可
代码:
void work()
{
cin >> n >> m;
cin >> rb >> cb >> rd >> cd;
int ans = 1e9;
if (rb > rd)
ans = 2 * n - rb - rd;
else
ans = rd - rb;
if (cb > cd)
ans = min(ans, 2 * m - cb - cd);
else
ans = min(ans, cd - cb);
cout << ans << endl;
}
B. Game on Ranges
题目大意:给你一个数组,你可以选择一个区间[L,R]并选择一个K使其分裂为[L,K-1]和[K+1,R],现在给你数组的长度和每次选择的区间,求每次选择的K
思路:
记录下每个区间的L,R,对区间的大小排序,因为每次分裂选择一个数,所以我们从小到大即可保证分裂的子区间已经计算过
我们用一个数组num来记录是否这个位置的已经被分裂过
对于长度为1的区间,K既是它本身,此时num[k] += k
对于长度不为1的区间,因为之前的区间已经处理过,此时我们知道k = 原区间和-num的区间和,得到k后继续num[k] += k
至于这个求和和修改操作,我们可以用树状数组解决
代码:
template <typename T>
class Fenwick
{
public:
vector<T> fenw;
int n;
Fenwick(int _n) : n(_n)
{
fenw.resize(n + 1);
}
void modifty(int x, int val)
{
while (x <= n)
{
fenw[x] += val;
x |= (x + 1);
}
}
T get(int x)
{
T cnt{};
while (x >= 0)
{
cnt += fenw[x];
x = (x & (x + 1)) - 1;
}
return cnt;
}
};
int t, n;
struct Edge
{
int from, to;
int size;
bool operator<(Edge b) const
{
return size < b.size;
}
} edges[Maxn];
void work()
{
cin >> n;
unordered_map<int, int> M[Maxn];
vector<int> r(n + 1);
vector<int> tx, ty;
vector<int> g[Maxn];
int cnt = 0;
for (int i = 1; i <= n; i++)
{
int t1, t2;
cin >> t1 >> t2;
tx.push_back(t1);
ty.push_back(t2);
M[t1][t2] = ++cnt;
edges[cnt].from = t1;
edges[cnt].to = t2;
edges[cnt].size = t2 - t1 + 1;
}
Fenwick<int> fen(n);
sort(edges + 1, edges + 1 + cnt);
for (int i = 1; i <= cnt; i++)
{
int l = edges[i].from;
int r = edges[i].to;
int nowAns = fen.get(r) - fen.get(l - 1);
nowAns = edges[i].size * (l + r) / 2 - nowAns;
fen.modifty(nowAns, nowAns);
cout << l << " " << r << " " << nowAns << endl;
}
cout << endl;
}
树状数组板子:https://blog.csdn.net/qq_23323539/article/details/122277303
C. Balanced Stone Heaps
题目大意:给你n堆石子的数量h1,h2--hn,你可以从第3堆到第n堆对这些石子进行一些操作,你可以选择一个d,0 <= 3d <= hi,把第i堆的d个石子给第i-1堆,把2d个石子给第i-2堆,问操作后最小的石子堆中的最大石子数使多少
思路:最小找最大,是很常见的二分,如果没有顺序限制,这就是一个二分答案板子题,从n到3判断时候大于mid,是则移动n-mid个石子给前面,但实际上,这道题虽然要求了顺序,但我们发现并不影响二分答案的正确性,只需要给每次移动的石子一个限制,即每次移动的石子是<hi的即可
代码:
bool check(int x)
{
vector<int> nowH(n + 1);
nowH = h;
for (int i = n; i >= 1; i--)
{
if (nowH[i] < x)
return false;
if (i < 3)
continue;
int nowMore = nowH[i] - x;
int nowD = nowMore / 3;
int oriMax = h[i]/3;
nowD = min(oriMax,nowD);
nowH[i] = nowH[i] - 3*nowD;
nowH[i - 1] += nowD;
nowH[i - 2] += 2 * nowD;
}
// for (int i = 1; i <= n; i++)
// cout << nowH[i] << " ";
// cout << endl;
return true;
}
void work()
{
cin >> n;
h.resize(n+1);
for (int i = 1; i <= n; i++)
cin >> h[i];
int l = 0;
int r = h[n];
int ans;
while (l <= r)
{
int mid = (l + r) / 2;
if (check(mid))
{
l = mid + 1;
ans = mid;
}
else
r = mid - 1;
}
cout << ans << endl;
}