CCPC- 网赛重赛（补题）
发布时间
阅读量：
阅读量
Monopoly
小兔子喜欢按照数组的顺序行走，在到达a[i]时会获得a[i]分；如果走到n则会回到起点1处。请问小兔子想要获得分数x最少需要几步？
做法：
假设它绕行k圈后再行走t步，则有sum[n]*k + sum[t] = x成立。
为了计算方便需对前缀和数组进行sum[n]取模运算，并将结果存储于向量中以便后续二分搜索查找。
需要注意的是：
- 由于答案可能较大，请将ans初始化为一个足够大的值如1e18。
- 在计算正负数时需注意它们在进行sum[n]取模时结果不同，请在计算前确保结果非负或适当调整范围。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int a[N], sum[N];
unordered_map<int, int> f, tong;
struct node{
int val, t;
bool operator < (const node &k) const {
if (val != k.val)
return val < k.val;
return t < k.t;
}
};
vector<node> v[N];
void solve()
{
int n, m;
scanf("%lld%lld", &n, &m);
int cnt = 0;
for (int i = 1; i <= n; i++){
scanf("%lld", &a[i]);
sum[i] = sum[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) {
if (sum[n] != 0) {
int mo = (sum[i] % sum[n] + sum[n]) % sum[n];
if (!f.count(mo)){
f[mo] = ++cnt;
v[cnt].push_back(node{sum[i], i});
}
else {
v[f[mo]].push_back(node{sum[i], i});
}
}
else {
if (!tong.count(sum[i]))
tong[sum[i]] = i;
}
}
for (int i = 1; i <= cnt; i++) {
sort(v[i].begin(), v[i].end());
}
while(m--)
{
int x;
scanf("%lld", &x);
if (x == 0) {
puts("0");
continue;
}
if (sum[n] == 0) {
if (!tong.count(x))
puts("-1");
else {
printf("%lld\n", tong[x]);
}
}
else {
int mo = (x % sum[n] + sum[n]) % sum[n];
mo = f[mo];
if (sum[n] < 0) {
auto p = lower_bound(v[mo].begin(), v[mo].end(), node{x, 0});
if (p != v[mo].end()) {
printf("%lld\n", (x - (*p).val) / sum[n] * n + (*p).t);
}
else
puts("-1");
}
else {
int ans = 1e18;
auto pp = lower_bound(v[mo].begin(), v[mo].end(), node{x, 0});
if (pp != v[mo].end() && (*pp).val == x) {
ans = (x - (*pp).val) / sum[n] * n + (*pp).t;
}
int l = 0, r = v[mo].size() - 1;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if (v[mo][mid].val < x)
l = mid;
else
r = mid - 1;
}
if (!v[mo].empty() && v[mo][l].val < x) {
auto p = lower_bound(v[mo].begin(), v[mo].end(), node{v[mo][l].val, 0});
ans = min(ans, (x - (*p).val) / sum[n] * n + (*p).t);
}
if (ans != 1e18)
printf("%lld\n", ans);
else
puts("-1");
}
}
}
for (int i = 1; i <= cnt; i++) {
v[i].clear();
}
f.clear();
tong.clear();
}
signed main()
{
int tt = 1;
cin >> tt;
while(tt--) solve();
return 0;
}Jumping Monkey
一只猴子会在树上从节点u往节点v跳，当u到v的最短路径上,v的权值是最大的时候。问猴子从每个点开始跳，最多能跳几个点。
做法：
从最大的节点开始考虑，他所在的连通块每个节点都能跳到他上面，他对连通块内的点贡献+1，然后删除这个节点。次大的也是如此考虑…都是对自身所在连通块贡献+1。
但是删点并不好做。所以顺序考虑，从权值最小的点开始，不断地把当前点加入他应该所在的连通块，然后连通块所有点权值+1。
访问当前点的所有出边，他连接的点所在的连通块最大的值如果小于当前点，就可以合并了。并查集的时候，一直把权值大的点作为父亲即可。
权值+1，重构一棵树，当前点连一条边到那些连通块里去，实现连通块的深度+1，就相当于是权值+1了。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
vector<int> v[N], g[N];
struct node{
int val, x;
bool operator <(const node &k) const {
return val < k.val;
}
} a[N];
int b[N], fa[N];
int ans[N];
int getf(int k)
{
if (k == fa[k])
return k;
return fa[k] = getf(fa[k]);
}
void merge(int x, int y)
{
int fx = getf(x), fy = getf(y);
if (fx == fy) return;
fa[fy] = fx;
}
void dfs(int k, int step)
{
ans[k] = step;
for (auto i : g[k]) {
dfs(i, step + 1);
}
}
void solve()
{
int n;
scanf("%lld", &n);
for (int i = 1; i <= n - 1; i++) {
int x, y;
scanf("%lld%lld", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
for (int i = 1; i <= n; i++){
scanf("%lld", &a[i].val);
b[i] = a[i].val;
a[i].x = i;
fa[i] = i;
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
for (auto j : v[a[i].x]) {
int f = getf(j);
if (b[f] < a[i].val) {
g[a[i].x].push_back(f);
merge(a[i].x, f);
}
}
}
dfs(a[n].x, 1);
for (int i = 1; i <= n; i++)
printf("%lld\n", ans[i]);
for (int i = 1; i <= n; i++) {
v[i].clear();
g[i].clear();
}
}
signed main()
{
int tt = 1;
cin >> tt;
while(tt--) solve();
return 0;
}全部评论 (0)
还没有任何评论哟~