2025.2.20 鮮花

ABC221G 和 P5163 題解

命に嫌われている。

「死にたいなんて言うなよ。」
「諦めないで生きろよ。」
そんな歌が正しいなんて馬鹿げてるよな。
実際自分は死んでもよくて
周りが死んだら悲しくて
「それが嫌だから」っていうエゴなんです。
他人が生きてもどうでもよくて
誰かを嫌うこともファッションで
それでも「平和に生きよう」なんて
素?cái)长胜长趣扦筏绀Α?畫面の先では誰かが死んで
それを嘆いて誰かが歌って
それに感化された少年がナイフを持って走った。
僕らは命に嫌われている。
価値観もエゴも押し付けて
いつも誰かを殺したい歌を
簡単に電波で流した。
僕らは命に嫌われている。
軽々しく死にたいだとか
軽々しく命を見てる 僕らは命に嫌われている。
お金がないので今日も 一日中惰眠を謳歌する。
生きる意味なんて見出せず、
無駄を自覚して息をする。
「寂しい」なんて言葉でこの傷が表せていいものか
そんな意地ばかり抱え今日も一人ベッドに眠る
少年だった僕たちはいつか青年に変わってく。
年老いていつか枯れ葉のように
誰にも知られず朽ちていく。
不死身の身體を手に入れて、
一生死なずに生きていく。
そんなSFを妄想してる
自分が死んでもどうでもよくて
それでも周りに生きて欲しくて
矛盾を抱えて生きてくなんて怒られてしまう。
「正しいものは正しくいなさい。」
「死にたくないなら生きていなさい。」
悲しくなるならそれでもいいなら
ずっと一人で笑えよ。
僕らは命に嫌われている。
幸福の意味すらわからず
生まれた環(huán)境ばかり憎んで
簡単に過去ばかり呪う。
僕らは命に嫌われている。
さよならばかりが好きすぎて
本當(dāng)の別れなど知らない 僕らは命に嫌われている。
幸福も別れも愛情も友情も
滑稽な夢(mèng)の戯れで全部カネで買える代物。
明日死んでしまうかもしれない。
すべて無駄になるかもしれない。
朝も 夜も 春も 秋も
変わらず誰かがどこかで死ぬ。
夢(mèng)も明日も何もいらない。
君が生きていたならそれでいい。
そうだ。本當(dāng)はそういうことが歌いたい。
命に嫌われている。
結(jié)局いつかは死んでいく。
君だって僕だっていつかは枯れ葉のように朽ちてく。
それでも僕らは必死に生きて
命を必死に抱えて生きて
殺して、足掻いて、笑って、抱えて
生きて、生きて、生きて、生きて、生きろ。

ABC221G

省流：可以直接看最下面 wang54321 的寫法，應(yīng)該是最簡潔的。

2025.7.25 Upd：別省了，好像假了，具體可以看下面。

首先假裝大家都會(huì) \(n^2D\) 的做法，簡單說就是考慮分別計(jì)算出 \(X + Y\) 和 \(X - Y\) 的方案（也可以說是轉(zhuǎn)坐標(biāo)軸），然后就可以得 \(X\) 和 \(Y\) 并推出方案。

經(jīng)過一些轉(zhuǎn)化問題成功變成了如下經(jīng)典問題：

有 \(n\) 個(gè)物品，每個(gè)的重量 \(w \le D\) 求是否可以選出若干個(gè)使其重量是 \(T\)。

使用 bitset 不難給出 \(\mathcal{O}(\frac{nT}w)\) 的做法，但在這個(gè)題 \(T\sim nD\) 并不足夠優(yōu)秀。

考慮能否 \(nD\) 解決問題。

容易想到經(jīng)典結(jié)論，先從前往后盡可能多的取，設(shè)取到位置 \(p\) 和為 \(S\)，顯然有 \(S\in(T - D, T]\)，然后考慮背包微調(diào)，有結(jié)論其在微調(diào)的任意時(shí)刻一定可以滿足 \(S\in(T - D, T + D]\)，證明不太難。

設(shè) \(f_{l, r, w} = 0/1\) 表示在 \(l \le p \le r\) 中微調(diào)能否達(dá)到 \(w\) 的權(quán)值，顯然 \(w\) 的范圍只有 \(2D\)，每次分討向左是否扔掉和向右拿上即可轉(zhuǎn)移，設(shè)序列為 \(a\)，給個(gè)方程。

\[f_{l - 1, r, w} \gets f_{l, r, w} \]

\[f_{l - 1, r, w - a_{l - 1}} \gets f_{l, r, w} \]

\[f_{l, r + 1, w} \gets f_{l, r, w} \]

\[f_{l, r + 1, w + a_{r + 1}} \gets f_{l, r, w} \]

其依然是 \(n^2D\) 的，考慮優(yōu)化，發(fā)現(xiàn)當(dāng) \(r, w\) 固定時(shí) \(f_{l, r, w}\) 為 \(1\) 是 \(l\) 的一段前綴，于是轉(zhuǎn)而設(shè) \(g_{r, w} = l\) 表示最大的 \(l\) 滿足 \(f_{l, r, w} = 1\)，若沒有就是 \(0\)。

轉(zhuǎn)移依然分討左右是否改變，這里由于是最大所以不用考慮向左但不扔的轉(zhuǎn)移，方程：

\[g_{r, w} \gets g_{r - 1, w} \]

\[g_{r, w - a_{r}} \gets g_{r - 1, w} \mid w \ge T \]

\[g_{r, w + a_{l}} \gets l \mid w \le T \And l < g_{r, w} \]

由于第三個(gè)轉(zhuǎn)移，我們依然要枚舉 \(l\)，復(fù)雜度沒變。

但是我們驚奇的發(fā)現(xiàn)，對(duì)于 \(l < g_{r - 1, w}\) 的 \(l\)，其可以通過 \(l \to g_{r - 1, w} \to g_{r, w}\) 轉(zhuǎn)移，于是我們的 \(l\) 只用枚舉 \([g_{r - 1, w}, g_{r, w})\) 的了。

顯然將 \(w\) 相等的拼起來其最多是 \(\mathcal{O}(n)\) 的，于是我們成功做到了 \(nD\)。

主播主播，上面的一堆推導(dǎo)還是太需要操作了，有沒有簡單無腦還快的做法呢？

還真有，考慮 wang54321 的簡單做法。

依然是先盡可能多選，根據(jù)結(jié)論這時(shí)我們只會(huì)在值域 \((T - D, T + D]\) 上跳，并且我們已經(jīng)跳到一個(gè)點(diǎn)上了。

于是乎我們直接暴力枚舉序列中每個(gè)數(shù)，以此取反其選取情況，就會(huì)得到 \(n\) 個(gè)新狀態(tài)，每次擴(kuò)展到?jīng)]有被跳過的點(diǎn)上再次暴力即可，容易發(fā)現(xiàn)一共只有 \(\mathcal{O}(D)\) 個(gè)點(diǎn)，每個(gè)點(diǎn)擴(kuò)展 \(n\) 次，復(fù)雜度依然是 \(nD\) 的。原理其實(shí)和上面的很類似。

2025.7.25 Upd 今天又看了這個(gè)做法，感覺沒什么道理，一拍果然掛了……
給出過程，大家可以看看是不是我寫的問題

點(diǎn)擊查看

brute:

/*
ulimit -s 128000 && clear && g++ % -o %< -O2 -std=c++14 -DLOCAL -Wall -Wextra && time ./%< && size %<
ulimit -s 128000 && clear && g++ % -o %< -O2 -std=c++14 -DLOCAL -Wall -Wextra -fsanitize=address,undefined -g && time ./%< && size %<
echo && cat out.out && echo
*/
#include <bits/stdc++.h>
using namespace std;
using llt = long long;
using llf = long double;
using ull = unsigned long long;
#define endl '\n'
#ifdef LOCAL
FILE *InFile = freopen("in.in", "r", stdin), *OutFile = freopen("out.out", "w", stdout);
#endif

const int M = 103, N = 103, V = N * M;
bitset<V> f; int n;

int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n; int s = 0;
	f[0] = 1; for(int i = 1, v; i <= n; ++i) cin >> v, f = f | f << v, s += v;
	for(int i = 1; i <= s; ++i) if(f[i]) cout << i << endl;
}

wang54321's trick

/*
ulimit -s 128000 && clear && g++ % -o %< -O2 -std=c++14 -DLOCAL -Wall -Wextra && time ./%< && size %<
ulimit -s 128000 && clear && g++ % -o %< -O2 -std=c++14 -DLOCAL -Wall -Wextra -fsanitize=address,undefined -g && time ./%< && size %<
echo && cat ans.ans && echo
*/
#include <bits/stdc++.h>
using namespace std;
using llt = long long;
using llf = long double;
using ull = unsigned long long;
#define endl '\n'
#ifdef LOCAL
FILE *InFile = freopen("in.in", "r", stdin), *OutFile = freopen("ans.ans", "w", stdout);
#endif

const int M = 103, N = 103, V = N * M;
int n, _v[N], s = 0; bool vis[V];
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> _v[i], s += _v[i];
	queue<pair<array<bool, N>, int>> que;
	que.emplace(array<bool, N>{0}, 0);
	while(!que.empty()){
		auto [f, v] = que.front(); que.pop();
		if(vis[v]) continue; else vis[v] = 1;
		for(int i = 1; i <= n; ++i) f[i] ^= 1, que.emplace(f, v + (f[i] ? _v[i] : -_v[i])),f[i] ^= 1;
	}
	for(int i = 1; i <= s; ++i) if(vis[i]) cout << i << endl;
}

可以看出是以 01 串輸出求的 \(n\) 個(gè)數(shù)能組成的大小。

hack:

10
12 38 11 28 49 4 9 41 38 42

wang54321's trick 輸出 \(109\) 是 \(0\)，實(shí)際是 \(1\)。

這里給出第一種做法的代碼。

Code

/* Local File
in_out/in.in
in_out/out.out
*/
#include <bits/stdc++.h>
using namespace std;
using llt = long long;
using llf = long double;
using ull = unsigned long long;
#ifndef LOCAL
#undef assert
#define assert 0 &&
#define cerr 0 && cerr
#endif

const int N = 2003, D = 1803;
int n, cx, cy, cd[N];
bool cv1[N], cv2[N];

int _f[D * 2], *const f = _f + D, _g[D * 2], *const g = _g + D, chs[N][D * 2];
/*
for : r
g_w <- f_w
g_{w + v_r} <- f_w  |  w <= 0
g_{w - v_l} <- l  |  f_w < l < g_w && w >= 0
*/
bool Dp(int tw, bool *ans){
	int p = 1, s = 0;
	while(p <= n && s + cd[p] <= tw)
		s += cd[p++];
	memset(_f, 0, sizeof _f), memset(_g, 0, sizeof _g), memset(chs, 0, sizeof chs);
	g[s - tw] = f[s - tw] = p;
	for(int r = p; r <= n; ++r){
		auto nc = chs[r] + D;
		auto Upd = [&](int p, int v, int f){
			if(g[p] < v)
				g[p] = v, nc[p] = f;
		};
		for(int w = -D + 3; w <= 0; ++w)
			Upd(w + cd[r], f[w], -1);
		for(int w = D - 3; ~w; --w)
			for(int l = f[w]; l < g[w]; ++l)
				Upd(w - cd[l], l, l);
		memcpy(_f, _g, sizeof _f);
	}
	if(!g[0]) return 0;
	for(int i = 1; i < p; ++i)
		ans[i] = 1;
	int r = n, v = 0;
	while(r >= p){
		int f = chs[r][v + D];
		if(f == 0) --r;
		else if(f == -1)
			ans[r] = 1, v -= cd[r], --r;
		else if(f > 0)
			ans[f] = 0, v += cd[f];
	}
	return 1;
}

int main(){
	cin >> n >> cx >> cy; int s = 0;
	for(int i = 1; i <= n; ++i)
		cin >> cd[i], s -= cd[i];
	int b1 = cx + cy - s, b2 = cx - cy - s;
	if(b1 < 0 || b2 < 0 || b1 % 2 || b2 % 2 || !Dp(b1 / 2, cv1) || !Dp(b2 / 2, cv2))
		cout << "No" << endl;
	else{
		cout << "Yes" << endl;
		for(int i = 1; i <= n; ++i)
			if(cv1[i] == cv2[i])
				cout << (cv1[i] ? 'R' : 'L');
			else
				cout << (cv1[i] ? 'U' : 'D');
	}
}

P5163

如果是無向邊是顯的。

考慮有向邊和無向邊的區(qū)別是什么，其實(shí)沒什么區(qū)別，只是我們需要知道每個(gè)邊歸到連通分量的時(shí)間。

考慮對(duì)于一條邊如何確定，可以二分，每次判斷加入 mid 之前的邊自己是否歸于一個(gè)連通分量。對(duì)于所有邊，容易想到整體二分。

考慮 check，如果是暴力 tarjan 復(fù)雜度并不正確，容易想到的是先處理左邊，在將左邊處理剩下的殘圖加邊接著跑，很可惜復(fù)雜的依然是錯(cuò)的，考慮若沒有強(qiáng)連通分量，則每次最壞依然是 \(\mathcal{O}(n)\) 的。

這里有一個(gè)比較牛的做法，考慮每次先縮點(diǎn)，在將縮了的點(diǎn)放到左邊，不屬于連通分量的邊放到右邊。考慮這樣我們和上面的區(qū)別，我們每次把邊分成了兩邊，避免了不能縮的邊在左邊繼續(xù)計(jì)算，于是只要我們 tarjan 只做非孤立點(diǎn)，復(fù)雜度就是對(duì)的。

每層右邊需要重標(biāo)號(hào)，可以用并查集，也可以每次暴力整。

然后就是板子大戰(zhàn)了。

Code

/* Local File
in_out/in.in
in_out/out.out
*/
#include <bits/stdc++.h>
using namespace std;
using llt = long long;
using llf = long double;
using ull = unsigned long long;
#ifndef LOCAL
#undef assert
#define assert 0 &&
#define cerr 0 && cerr
#endif

const int N = 2e6 + 3;
int n, m, q, cs[N];

struct Gph{
	vector<int> to[N];
	void Add(int u, int v){
		to[u].emplace_back(v);
	}
	void ADD(int u, int v){
		Add(u, v), Add(v, u);
	}
	void Clr(int u){
		to[u].clear();
	}
#define For_to(i, u, v, g) for(int v : g.to[u])
}g;

class TAR{
private:
	int dfn[N], low[N], stk[N], *top = stk, tdn, tco = 1e5, col[N];
	bool isk[N];
	void Dfs(int u){
		dfn[u] = low[u] = ++tdn;
		isk[*++top = u] = 1;
		For_to(i, u, v, g){
			if(!dfn[v]) Dfs(v), low[u] = min(low[u], low[v]);
			else if(isk[v]) low[u] = min(low[u], dfn[v]);
		}
		if(dfn[u] == low[u]){
			++tco; int v;
			do{
				v = *top--;
				col[v] = tco, isk[v] = 0;
			}while(v != u);
		}
	}
public:
	void In(int u){
		if(!dfn[u]) Dfs(u);
		assert(top == stk);
	}
	int operator()(int u){
		return col[u];
	}
	void Clr(int u){
		dfn[u] = low[u] = col[u] = 0;
	}
} Tar;

struct E{
	int u, v, t, tc, uu, vv;
} ce[N];
bool Chk(const E &e){
	return Tar(e.u) == Tar(e.v);
}
void Cdq(int l, int r, int ll, int rr){
	if(l == r){
		for(int i = ll; i <= rr; ++i)
			ce[i].tc = l;
		return ;
	}
	int mid = l + r >> 1, mmd;
	vector<int> nd;
	for(mmd = ll; mmd <= rr; ++mmd){
		auto &[u, v, t, tc, uu, vv] = ce[mmd];
		if(t > mid) break;
		else{
			g.Add(u, v);
			nd.emplace_back(u), nd.emplace_back(v);
		}
	}
	--mmd;
	for(auto k : nd) Tar.In(k);
	vector<E> tp;
	int p = ll - 1;
	for(int i = ll; i <= mmd; ++i){
		if(!Chk(ce[i]))
			tp.emplace_back(ce[i]);
		else
			ce[++p] = ce[i];
	}
	mmd = p;
	for(auto &k : tp) ce[++p] = k;
	auto Id = [](int &u){
		if(Tar(u)) u = Tar(u);
	};
	for(int i = mmd + 1; i <= rr; ++i)
		Id(ce[i].u), Id(ce[i].v);
	for(auto k : nd)
		Tar.Clr(k), g.Clr(k);
	Cdq(l, mid, ll, mmd), Cdq(mid + 1, r, mmd + 1, rr);
}

namespace SEG{
	const int D = 1e7 + 3, V = 1e9;
	int sz[D], ls[D], rs[D], tot; llt sm[D];
#define lson ls[t]
#define rson rs[t]
#define mid (l + r >> 1)
	void Upd(int t){
		sz[t] = sz[lson] + sz[rson];
		sm[t] = sm[lson] + sm[rson];
	}
	llt qry(int l, int r, int k, int t){
		if(!t)
			return 0;
		if(l == r)
			return 1ll * l * k;
		else{
			if(k <= sz[rson]) return qry(mid + 1, r, k, rson);
			else return qry(l, mid, k - sz[rson], lson) + sm[rson];
		}
	}
	void add(int l, int r, int p, int v, int &t){
		if(!t) t = ++tot;
		if(l == r)
			sz[t] += v, sm[t] += 1ll * l * v;
		else{
			if(p <= mid) add(l, mid, p, v, lson);
			else add(mid + 1, r, p, v, rson);
			Upd(t);
		}
	}
	void mrg(int l, int r, int _, int &t){
		if(!_ || !t) t += _;
		else if(l == r){
			sz[t] += sz[_], sm[t] += sm[_];
		}else{
			mrg(l, mid, ls[_], lson);
			mrg(mid + 1, r, rs[_], rson);
			Upd(t);
		}
	}
#undef lson
#undef rson
#undef mid
	class Seg{
	private:
		int rt = 0;
	public:
		void Add(int a, int v){
			add(0, V, a, v, rt);
		}
		llt Qry(int k){
			return qry(0, V, k, rt);
		}
		void Mrg(const Seg &_){
			mrg(0, V, _.rt, rt);
		}
	};
} using SEG::Seg;
Seg seg[N];

class Dsu{
private:
	int fa[N];
public:
	int Fa(int u){
		return fa[u] ? fa[u] = Fa(fa[u]) : u;
	}
	void Uni(int fu, int fv){ // fu -> fv
		fa[fu] = fv;
	}
} uf;

stack<tuple<int, int, int, int>> cq;

int main(){
	cin >> n >> m >> q;
	{
		map<pair<int, int>, int> eid;
		for(int i = 1; i <= n; ++i)
			cin >> cs[i];
		for(int i = 1; i <= m; ++i){
			int u, v; cin >> u >> v;
			ce[i] = {u, v, 0, 0, u, v}, eid[{u, v}] = i;
		}
		for(int i = 1; i <= q; ++i){
			int op, a, b; cin >> op >> a >> b;
			int t = q - i + 1;
			if(op == 1)
				ce[eid[{a, b}]].t = t;
			else{
				cq.emplace(t, op - 1, a, b);
				if(op == 2)
					cs[a] += b;
			}
		}
		for(int i = 1; i <= n; ++i) seg[i].Add(cs[i], 1);
	}
	
	sort(ce + 1, ce + m + 1, [](const E &a, const E &b){return a.t < b.t;});
	Cdq(0, q + 1, 1, m);
	for(int i = 1; i <= m; ++i)
		ce[i].u = ce[i].uu, ce[i].v = ce[i].vv;
	
	auto ne = ce + 1;
	stack<llt> aas;
	for(int t = 0; t <= q; ++t){
		while(ne->tc == t){
			int fu = uf.Fa(ne->u), fv = uf.Fa(ne->v);
			if(fu != fv) uf.Uni(fu, fv), seg[fv].Mrg(seg[fu]);
			++ne;
		}
		while(!cq.empty() && get<0>(cq.top()) == t){
			auto [t, op, a, b] = cq.top(); cq.pop();
			int f = uf.Fa(a);
			if(op == 1)
				seg[f].Add(cs[a], -1), seg[f].Add(cs[a] -= b, 1);
			else
				aas.emplace(seg[f].Qry(b));
		}
	}
	while(!aas.empty())
		cout << aas.top() << endl, aas.pop();
}

posted @ 2025-02-19 21:06 xrlong 閱讀(93) 評(píng)論(6) 收藏舉報(bào)

刷新頁面返回頂部

xrlong

博客密碼是 K8 色號(hào)

2025.2.20 鮮花

ABC221G 和 P5163 題解

ABC221G

P5163

公告

Loading