首页 > 其他分享 >AtCoder Regular Contest 115 F Migration

AtCoder Regular Contest 115 F Migration

时间:2023-04-25 13:11:24浏览次数:50  
标签:AtCoder return val long 115 Regular maxn && const

洛谷传送门

AtCoder 传送门

这种最大值最小化的题一般可以先考虑二分。设二分了一个 \(mid\)。

记 \(A = (a_1,a_2,...,a_k)\) 为表示每个棋子的位置的状态,如果 \(A,B\) 可以互相到达,就在它们之间连一条无向边。则要判断的是 \(S = (s_1,s_2,...,s_k)\) 和 \(T = (t_1,t_2,...,t_k)\) 是否在同一连通块内。

记 \(f(A)\) 为 \(\sum\limits_{i=1}^k a_{A_i}\),那我们不妨让 \(S\) 和 \(T\) 都到达一个 \(f(A)\) 最小的状态 \(A\)(如果 \(f(A)\) 相同则比较字典序)。如果两个 \(A\) 都相同,则 \(S,T\) 在同一连通块内,否则不在。

设 \(g(A)\) 为 \(A\) 能到达的最小状态,则问题转化成了求 \(g(A)\)。

考虑一个暴力做法:每次找到能移的棋子中造成的贡献最大的,移动这个棋子(需要预处理点 \(u\) 经过权值不超过 \(D\) 的点能到达的所有点的点权最小值)。因为每个棋子的移动不会重复经过某个点,所以最多移动 \(O(nk)\) 次。时间复杂度是 \(O(nk^2 \log n \log ans)\),显然会 T

考虑加点优化。用堆维护下一个贡献最大的操作。每次 \(\sum\limits_{i=1}^k a_i\) 变小时,一些点的移动会变得合法,将它们加入堆中即可。需要精细实现,复杂度 \(O(\text{可过})\)。

code
// Problem: F - Migration
// Contest: AtCoder - AtCoder Regular Contest 115
// URL: https://atcoder.jp/contests/arc115/tasks/arc115_f
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

namespace IO {
    char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
    inline long long read() {
        char ch = gh();
        long long x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    template <typename _Tp>
    inline void write(_Tp x) {
    	static char stk[64], *top = stk;
        if (x < 0) {
            x = ~(x - 1);
            putchar('-');
        }
        do *top++ = x % 10, x /= 10;
        while (x);
        while (top != stk) putchar((*--top) | 48);  
    }
}

using IO::read;
using IO::write;

const int maxn = 2020;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;

ll n, m, a[maxn], head[maxn], len, lsh[maxn], tot;
int c[maxn], d[maxn], p[maxn], e[maxn], to[maxn << 1], nxt[maxn << 1];
pii f[maxn][maxn];
bool vis[maxn];
int stk[maxn];

struct piece {
	ll s, t;
} b[maxn];

inline void add_edge(int u, int v) {
	to[++len] = v;
	nxt[len] = head[u];
	head[u] = len;
}

struct node {
	int u;
	ll val;
	int t, i, j;
} h[maxn];

unordered_set<int> st[maxn];

inline bool operator < (const node &a, const node &b) {
	if (a.val != b.val) {
		return a.val < b.val;
	}
	bool x = (a.t < a.u), y = (b.t < b.u);
	if (x && y) {
		return a.i > b.i;
	} else if (!x && !y) {
		return a.i < b.i;
	} else {
		return !x;
	}
}

struct wwh {
	ll x;
	int y, z;
} g[maxn * maxn];

inline bool operator < (const wwh &a, const wwh &b) {
	return a.x > b.x;
}

namespace SGT {
	node tree[maxn << 2];
	
	void build(int rt, int l, int r) {
		if (l == r) {
			tree[rt] = h[c[l]];
			tree[rt].i = l;
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid);
		build(rt << 1 | 1, mid + 1, r);
		tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
	}
	
	void update(int rt, int l, int r, int x, node &y) {
		if (l == r) {
			tree[rt] = y;
			tree[rt].i = l;
			return;
		}
		int mid = (l + r) >> 1;
		(x <= mid) ? update(rt << 1, l, mid, x, y) : update(rt << 1 | 1, mid + 1, r, x, y);
		tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
	}
}

inline void work(ll x) {
	ll s = 0;
	for (int i = 1; i <= n; ++i) {
		st[i].clear();
	}
	for (int i = 1; i <= m; ++i) {
		s += a[c[i]];
		st[c[i]].insert(i);
	}
	int tt = 0;
	for (int i = 1; i <= n; ++i) {
		node mx = (node){i, -1, 0, i, -1};
		for (int j = 1; j <= tot; ++j) {
			if (f[i][j].scd == -1) {
				continue;
			}
			node t = (node){i, a[i] - f[i][j].fst, f[i][j].scd, i, j};
			if (lsh[j] + s - a[i] <= x) {
				p[i] = j;
				mx = max(mx, t);
			} else if (x + a[i] - lsh[j] > 0 && mx < t) {
				g[++tt] = (wwh){x + a[i] - lsh[j], i, j};
			}
		}
		h[i] = mx;
	}
	sort(g + 1, g + tt + 1);
	SGT::build(1, 1, m);
	int pos = 1;
	while (1) {
		node u = SGT::tree[1];
		if (u.val < 0 || (u.val == 0 && c[u.i] <= u.t)) {
			break;
		}
		s -= u.val;
		st[u.u].erase(u.i);
		c[u.i] = u.t;
		st[u.t].insert(u.i);
		SGT::update(1, 1, m, u.i, h[u.t]);
		int top = 0;
		while (pos <= tt && s <= g[pos].x) {
			int i = g[pos].y, j = g[pos].z;
			p[i] = j;
			node t = (node){i, a[i] - f[i][j].fst, f[i][j].scd, i, j};
			if (h[i] < t) {
				h[i] = t;
				if (!vis[i]) {
					vis[i] = 1;
					stk[++top] = i;
				}
			}
			++pos;
		}
		for (int _ = 1; _ <= top; ++_) {
			int i = stk[_];
			vis[i] = 0;
			for (int x : st[i]) {
				 SGT::update(1, 1, m, x, h[i]);
			}
		}
	}
}

inline bool check(ll x) {
	for (int i = 1; i <= m; ++i) {
		c[i] = b[i].s;
	}
	work(x);
	for (int i = 1; i <= m; ++i) {
		d[i] = c[i];
		c[i] = b[i].t;
	}
	work(x);
	for (int i = 1; i <= m; ++i) {
		if (c[i] != d[i]) {
			return 0;
		}
	}
	return 1;
}

void dfs(int u, int fa, int mx, int rt) {
	f[rt][mx] = min(f[rt][mx], make_pair(a[u], 1LL * u));
	for (int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if (v == fa) {
			continue;
		}
		dfs(v, u, max(mx, e[v]), rt);
	}
}

void solve() {
	n = read();
	for (int i = 1; i <= n; ++i) {
		a[i] = read();
		lsh[++tot] = a[i];
	}
	sort(lsh + 1, lsh + tot + 1);
	tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
	for (int i = 1; i <= n; ++i) {
		e[i] = lower_bound(lsh + 1, lsh + tot + 1, a[i]) - lsh;
	}
	for (int i = 1, u, v; i < n; ++i) {
		u = read();
		v = read();
		add_edge(u, v);
		add_edge(v, u);
	}
	m = read();
	ll s1 = 0, s2 = 0;
	for (int i = 1; i <= m; ++i) {
		b[i].s = read();
		b[i].t = read();
		s1 += a[b[i].s];
		s2 += a[b[i].t];
	}
	for (int u = 1; u <= n; ++u) {
		for (int i = 0; i <= tot; ++i) {
			f[u][i] = make_pair(inf, -1);
		}
		dfs(u, -1, e[u], u);
		for (int i = 1; i <= tot; ++i) {
			f[u][i] = min(f[u][i], f[u][i - 1]);
		}
	}
	ll l = max(s1, s2), r = *max_element(a + 1, a + n + 1) * m, ans = -1;
	while (l <= r) {
		ll mid = (l + r) >> 1;
		if (check(mid)) {
			ans = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	write(ans);
}

int main() {
	solve();
	return 0;
}

标签:AtCoder,return,val,long,115,Regular,maxn,&&,const
From: https://www.cnblogs.com/zltzlt-blog/p/17352300.html

相关文章

  • Codeforces Round #306 (Div. 2) D. Regular Bridge 构造
    Anundirectedgraphiscalledk-regular,ifthedegreesofallitsverticesareequalk.Anedgeofaconnectedgraphiscalledabridge,ifafterremovingitthegraphisbeingsplitintotwoconnectedcomponents.Buildaconnectedundirectedk-regularg......
  • AtCoder Beginner Contest 158
    AtCoderBeginnerContest158https://atcoder.jp/contests/abc158基础不牢,地动山摇D-StringFormation一个小小的STL应用#include<bits/stdc++.h>#definelllonglongusingnamespacestd;strings;intq,t,f;charc;intmain(){cin>>s>>q......
  • AtCoder Problem Difficulty
    ABC299之前.......
  • AtCoder Regular Contest 111 F Do you like query problems?
    洛谷传送门AtCoder传送门挺有意思的计数。计数感觉很难做,不妨转成期望,期望又可以转成概率之和。考虑枚举\(w\in[0,m-1]\),把\(>w\)的数设为\(1\),\(\lew\)的数设为\(0\)。那么期望就是所有\(w\),\(a_i\)为\(1\)的概率之和。对于一个\(i\),只有以下的操作能改变\(......
  • AtCoder ABC 299 ABCDEFG
    A-TreasureChest题意给定由\(\texttt{.}\)、\(\texttt{|}\)、\(\texttt{*}\)三种字符组成的长度为\(n\)的字符串\(s\),保证\(\texttt{|}\)的个数为\(2\),\(\texttt{*}\)的个数为\(1\)。判断\(\texttt{*}\)是否在两个\(\texttt{|}\)之间。代码#include<cstrin......
  • Atcoder Beginner Contest 299 G
    对于要打印的\(B\),我们首先尝试确定\(B_1\)。让\(f(x)(1≤x≤M)\)是最大的\(i\),使\(A_i=x\)。对于\(r:=\underset{{{1≤x≤M}}}{\min}f(x)\),我们可以证明\(B_1\)是\(A_1,A_2,...,A_r\)中的一个(否则,\(B\)是\(A_{>r}:=(A_r+1,Ar+2,...,A_N)\)的一个子序列,但......
  • AtCoder Beginner Contest 283 Ex Popcount Sum
    洛谷传送门AtCoder传送门记录一下这个神奇的套路。首先有\(\operatorname{popcount}(n)=n-\sum\limits_{i=1}^{\infty}\left\lfloor\frac{n}{2^i}\right\rfloor\)。证一下:\[\operatorname{popcount}(n)=\sum\limits_{i=0}^{\infty}\left\lfloor\dfrac{n}{2^i}\right......
  • 论文解读(VAT)《Virtual Adversarial Training: A Regularization Method for Supervise
    论文信息论文标题:VirtualAdversarialTraining:ARegularizationMethodforSupervisedandSemi-SupervisedLearning论文作者:TakeruMiyato,S.Maeda,MasanoriKoyama,S.Ishii论文来源:2020ECCV论文地址:download 论文代码:download视屏讲解:click1前言提出问题:在......
  • AtCoder Regular Contest 115 D Odd Degree
    洛谷传送门AtCoder传送门若连通块是一棵树,考虑钦定\(k\)个点为奇度点,方案数为\(\binom{n}{k}\)。对于叶子,如果它是奇度点,那么连向它父亲的边要保留,否则不保留。这样自底向上考虑,任意一条边的保留情况都可以唯一确定,所以最后方案数就是\(\binom{n}{k}\)。若连通块存在环,仍......
  • AtCoder Regular Contest 114 F Permutation Division
    洛谷传送门AtCoder传送门这题居然是之前某场模拟赛(contest701)的T1……(@Vidoliga场切但是被卡常/bx)下面记\(m\)为原题面中的\(K\),\(a_i\)为原题面中的\(P_i\)。不难发现后手的策略是把所有段按照段的第一个数从大到小排序接在一起。考虑若\(a_1\lem\),则先手能把所......