更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19369035

思路

那么，相当于每个党派的两个代表就是两种情况，然后直接按其说的厌恶的关系建边跑 $\text{2 - SAT}$ 即可。

每个党派 $i$ 对应2-SAT的一个布尔变量，其两个代表 $2i$、$2i+1$ 分别对应「变量为真」「变量为假」，题目中“代表a和b互相厌恶” $\to$ 约束：**不能同时选 a 和 b**，即选 a 则必须选 b 的对立代表，选 b 则必须选 a 的对立代表。

先将代表编号转为 $0$ 起始（$a \rightarrow a - 1$），记a对应节点 $u$，b 对应节点 $v$；

互斥约束转化为两条有向边：

 1. $u \rightarrow v \oplus 1$（选 a → 必须选 b 的对立代表）

 2. $v \rightarrow u \oplus 1$（选 b → 必须选 a 的对立代表）

 （$\oplus 1$ 是异或操作，可快速找到每个代表的“对立代表”：偶数变奇数，奇数变偶数）。

代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

const int MAXN = 16005;
int n, m;
vector<int> g[MAXN];
bool vis[MAXN];
int S[MAXN], c = 0;

inline int get_id(int x) {
    x--;
    return x;
}

bool dfs(int u) {
    if (vis[u ^ 1]) return false;
    if (vis[u]) return true;
    vis[u] = true;
    S[c++] = u;
    for (int v : g[u]) {
        if (!dfs(v)) return false;
    }
    return true;
}

bool Two_SAT() {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < 2 * n; i += 2) {
        if (!vis[i] && !vis[i + 1]) {
            c = 0;
            if (!dfs(i)) {
                while (c > 0) vis[S[--c]] = false;
                if (!dfs(i + 1)) {
                    return false;
                }
            }
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        int u = get_id(a);
        int v = get_id(b);
        g[u].push_back(v ^ 1);
        g[v].push_back(u ^ 1);
    }

    if (!Two_SAT()) {
        cout << "NIE" << endl;
    } else {
        vector<int> ans;
        for (int i = 0; i < 2 * n; i += 2) {
            if (vis[i]) {
                ans.push_back(i + 1);
            } else {
                ans.push_back(i + 2);
            }
        }
        sort(ans.begin(), ans.end());
        for (int x : ans) {
            cout << x << endl;
        }
    }

    return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19361885

思路

这个题目要求我们把给出的状态通过类似华容道的方式，去移动 $0$ 的位置，然后就可以调整其他数的位置。

然后我们考虑把这个棋盘的状态存下来，这样的话我们就可以直接转移，然后我们显然可以把这玩意直接弄成字符串，为了保证答案的最小，直接字符串 $hash$ 存每个字符串的最小值，然后我们每次关注 $0$ 的位置，进行 bfs 即可，新的状态取最小即可。这种已经可以 AC了。

我们继续考虑优化，这里给出 A* 的写法，我们是否有很多没必要的状态呢？A* 的剪枝就很类似于贪心的思路，我们可以维护一个东西，每次在 bfs 的时候取你觉得比较优的答案。这时候我们需要维护一个估价函数，对于这个题的话，我们可以认为，位置正确的越多，那么这个东西显然很优，先对这些正确位置比较多的进行拓展，那么我们有 $F(S)$ 就是表示当前的状态下正确的位置的个数，然后我们去维护一个小根堆，里面的值是 $S_{now} + F(S)$，这个东西越小显然越优，我们优先去拓展，如果已经到了目标状态，那么就没必要继续搜索了，这个答案一定最优。这个东西就很类似最短路的 dijkstra，每次都取最小的。然后显然我们的 $F(S)$ 是要小于等于实际的可能花费的，因此这样的拓展一定最优。

代码

#include<iostream>
#include<cmath>
#include<unordered_map>
#include<queue>
using namespace std;

string s;
int xx[] = {1, 0, 0, 0, 1, 2, 2, 2, 1};
int yy[] = {1, 0, 1, 2, 2, 2, 1, 0, 0};
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int f(string now){
	int sum = 0;
	for(int i = 0;i < 9;i ++){
		int x = i / 3, y = i % 3;
		int p = x * 3 + y;
		int v = now[p] - '0';
		sum += (abs(x - xx[v]) + abs(y - yy[v]));
	}
	return sum;
}

int Astar(string now){
	unordered_map<string, int> d;
	priority_queue<pair<int, string> > q;
	string tag = "123804765";
	q.push(make_pair(-f(now), now));
	d[now] = 0;
	while(!q.empty()){
		string u = q.top().second;
		if(u == tag) return d[tag];
		q.pop();
		int k = u.find('0');
		int x = k / 3, y = k % 3;
		for(int i = 0;i < 4;i ++){
			int nx = x + dx[i], ny = y + dy[i];
			if(nx < 0 || ny < 0 || nx >= 3 || ny >= 3) continue;
			if(nx * 3 + ny > 8 || nx * 3 + ny < 0) continue;
			string t = u;
			swap(t[x * 3 + y], t[nx * 3 + ny]);
			if(!d.count(t)){
				d[t] = d[u] + 1;
				q.push(make_pair(-f(t) - d[t], t));
			}
		}
	}
	return d[tag];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> s;
	cout << Astar(s) << '\n';
	return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19368752

思路

首先就是最大值最小，我们可以考虑进行二分，二分答案 $k$，也就是说当前的所有航线的路程需要小于等于 $k$，我们知道，每次改完，最多能让一个航线的值减去 $1$，我们只需要判断这些大于等于 $k$ 的航线交集最多的那条边即可。

于是我们的思路就出来了，二分 $k$，找交集最大的边，判断是否合法。

然后找交集的过程我们可以采用树上差分。

代码

#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 8 * 1e5 + 5;
const int LOG = 19;

int n, m;

struct node{
	int to, nxt, len;
}e[MAXN];
int tot = 0, h[MAXN], dep[MAXN];
int d[MAXN], f[MAXN][LOG];
int sum[MAXN];
struct N{
	int u, v, val, lca;
}p[MAXN];
void add(int x, int y, int len){
	e[++ tot] = {y, h[x], len};
	h[x] = tot;
}

void dfs(int u, int fa){
	dep[u] = dep[fa] + 1;
	f[u][0] = fa;
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == fa) continue;
		sum[v] = sum[u] + e[i].len;
		dfs(v, u);
	}
}

void I_nt(){
	for(int k = 1;k < LOG;k ++){
		for(int i = 1;i <= n;i ++){
			f[i][k] = f[f[i][k - 1]][k - 1];
		}
	}
}

int LCA(int u, int v){
	if(dep[u] < dep[v]) swap(u, v);
	for(int k = LOG - 1;k >= 0;k --){
		if(dep[f[u][k]] >= dep[v]){
			u = f[u][k];
		}
	}
	if(u == v) return u;
	for(int k = LOG - 1;k >= 0;k --){
		if(f[u][k] != f[v][k]){
			u = f[u][k];
			v = f[v][k];
		}
	}
	return f[u][0];
}

int tmp, ans;

void dfs2(int u, int fa){
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == fa) continue;
		dfs2(v, u);
		d[u] += d[v];
	}
	if(d[u] == tmp){
		ans = max(ans, sum[u] - sum[f[u][0]]);
	}
}

bool check(int mid){
	for(int i = 1;i <= n;i ++) d[i] = 0;
	tmp = 0;
	for(int i = 1;i <= m;i ++){
		if(p[i].val > mid){
			tmp ++;
			d[p[i].u] ++;
			d[p[i].v] ++;
			d[p[i].lca] -= 2;
		}
		else break;
	}
    if(!tmp) return 1;
	ans = -1e9;
	dfs2(1, 0);
	if(p[1].val - ans > mid){
		return false;
	}
	return true;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

	cin >> n >> m;

	for(int i = 1;i < n;i ++){
		int u, v, w; cin >> u >> v >> w;
		add(u, v, w), add(v, u, w);
	}

	dfs(1, 0);I_nt();
	int l = 0, r = 0;
	for(int i = 1;i <= m;i ++){
		cin >> p[i].u >> p[i].v;
		p[i].lca = LCA(p[i].u, p[i].v);
		p[i].val = (sum[p[i].u] + sum[p[i].v] - 2 * sum[p[i].lca]);
		r = max(r, p[i].val);
	}
	sort(p + 1, p + m + 1, [](N a, N b){
		return a.val > b.val;
	});
	while(l < r){
		int mid = (l+r)>>1;
		if(check(mid)){
			//mid is ok
			r = mid ;
		}
		else{
			l = mid + 1;
		}
	}
	cout << r << '\n';
	return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19369112

思路

要求满足不回家的人和外校的人都有床睡，一个人只会睡自己认识的人的床。

考虑二分图最大匹配。

然后，这个点 $u \to v$ 连边的前置条件是 $v$ 是在校学生，且 $v$ 回家睡觉。

需要注意的是，自己显然是可以睡自己的床的（并非废话），只要这个学生在校且不回家，就可以 $u \to u$。

将图建出来之后，直接跑二分图最大匹配即可。

代码

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

const int MAXN = 55;
int n;
int T;
bool at[MAXN];
int home[MAXN];
vector<int> g[MAXN];
int mac[MAXN];
bool vis[MAXN];

bool dfs(int u){
	for(int &v : g[u]){
		if(!vis[v]){
			vis[v] = 1;
			if(mac[v] == -1 || dfs(mac[v])){
				mac[v] = u;
				return true;
			}
		}
	}
	return false;
}

int hungary(int n){
	int cnt = 0;
	memset(mac, -1, sizeof(mac));
	for(int i = 1;i <= n;i ++){
		memset(vis, 0, sizeof(vis));
		if(!at[i] || (at[i] && !home[i])) cnt += dfs(i);
	}
	return cnt;
}

int main(){

	cin >> T;

	while(T --){
		int sum = 0;
		cin >> n;
		for(int i = 1;i <= n;i ++) g[i].clear();
		for(int i = 1;i <= n;i ++){
			cin >> at[i];
		}
		for(int i = 1;i <= n;i ++){
			cin >> home[i];
			if(!home[i] && at[i]){
				g[i].push_back(i);
			}
        }
        for(int i = 1;i <= n;i ++){
            if(!at[i] || (at[i] && !home[i])) sum ++;
        }
		for(int i = 1;i <= n;i ++){
			for(int j = 1;j <= n;j ++){
				bool rela; cin >> rela;
				if(rela && at[j]){
					g[i].push_back(j);
				}
			}
		}
		if(hungary(n) == sum){
			cout << "^_^\n";
		}
		else{
			cout << "T_T\n";
		}
	}


	return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19343265

思路

首先考虑用线段树做。

发现数据范围很大，但是实则不需要考虑啊，因为我们的海报的数量一定，可以考虑离散化去重，然后用线段树做。

每次更改一段区间的话，采用标记延迟下传的方式，如果在目标区间就先打上懒标记，如果以后访问到了再下传，这样就不必要每次放到叶子上了。

最终查询就直接访问所有叶子就好，用个 set 去重海报。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int a[N], lazy[N], n, c;

set<int> cnt;

void update(int rt, int l, int r, int L, int R, int x) {
    if (L > r || R < l) return;
    if (L <= l && r <= R) {
        lazy[rt] = x;
        a[rt] = x;
        return;
    }
    int mid = (l + r) / 2;
    if (lazy[rt]) {
        lazy[rt * 2] = lazy[rt * 2 + 1] = lazy[rt];
        a[rt * 2] = a[rt * 2 + 1] = lazy[rt];
        lazy[rt] = 0;
    }
    update(rt * 2, l, mid, L, R, x);
    update(rt * 2 + 1, mid + 1, r, L, R, x);
}

void query(int rt, int l, int r) {
    if (l == r) {
        if (a[rt]) cnt.insert(a[rt]);
        return;
    }
    int mid = (l + r) / 2;
    if (lazy[rt]) {
        lazy[rt * 2] = lazy[rt * 2 + 1] = lazy[rt];
        a[rt * 2] = a[rt * 2 + 1] = lazy[rt];
        lazy[rt] = 0;
    }
    query(rt * 2, l, mid);
    query(rt * 2 + 1, mid + 1, r);
}

int l[N], r[N];

int main() {
    int c;
        cin >> c >> n;
        memset(a, 0, sizeof(a));
        memset(lazy, 0, sizeof(lazy));
        set<int> uniq;
        map<int, int> d;
        for (int i = 1; i <= n; i++) {
            cin >> l[i] >> r[i];
            uniq.insert(l[i]);
            uniq.insert(r[i]);
            uniq.insert(l[i] - 1);
            uniq.insert(r[i] + 1);
        }
        int now = 0;
        for (auto x: uniq) {
            d[x] = ++ now;
        }
        for (int i = 1; i <= n; i++) {
            l[i] = d[l[i]];
            r[i] = d[r[i]];
            update(1, 1, now, l[i], r[i], i);
        }
        cnt.clear();
        query(1, 1, now);
        cout << cnt.size() << endl;

    return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19346416

思路

首先考虑 $\mathcal{O}(n ^ 2)$ 的解法。

枚举每条边，然后分别统计左右子树的重心，然后想加即可。

然后考虑优化，显然我们的复杂度浪费在了找重心的地方。

“一棵有根树的重心一定在根结点所在的重链上。一棵树的重心一定是该树根结点重子结点对应子树的重心的祖先。”——OIwiki

有关树的重心的内容见OI-wiki/树的重心

重心必在节点的「重儿子链」上（重儿子指子树大小最大的子节点），因此可通过倍增沿重儿子链快速定位重心候选。

删除边 $(u, v)$ 后，$u$ 所在的大子树（大小 $n - sz_v$）需要「换根」更新重儿子（原重儿子可能是 $v$，需替换为次重儿子或父方向），而 $v$ 所在的小子树（大小 $sz_v$)）是原树的子树，无需换根。

节点最大子树（含父方向）≤ 总大小 / $2$ 则为重心。

递归算每个节点的子树大小，记录重 / 次重儿子（子树最大 / 次大的子节点），构建倍增数组（沿重儿子链跳，$\mathcal{O}(\log n)$ 找重心）。

然后累加答案即可。

代码

#include<iostream>
#include<cstring>
using namespace std;

const int MAXN = 3e5 + 5;
const int LOG = 18;

struct node{
    int to, nxt;
}e[MAXN * 2];

int h[MAXN], tot;
int T, n;
int son1[MAXN], son2[MAXN];
int f[MAXN], up[MAXN][LOG + 1];
int son3[MAXN];
int fu[MAXN];
int sz[MAXN], csz[MAXN];
long long ans;

void add(int x, int y){
	e[++ tot] = {y, h[x]};
    h[x] = tot;
}

void dfs1(int u, int fa){
    sz[u] = 1;
    f[u] = fa;
    son1[u] = son2[u] = 0;
    for(int i = h[u];i;i = e[i].nxt){
        int v = e[i].to;
        if(v == fa) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[son1[u]]){
            son2[u] = son1[u];
            son1[u] = v;
        }
        else if(sz[v] > sz[son2[u]]){
            son2[u] = v;
        }
    }
    up[u][0] = son1[u];
    for(int i = 1;i <= LOG;i ++){
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
}

int check(int x, int sum, int maxx){
    if(!x) return 0;
    return (max(maxx, sum - csz[x]) <= sum / 2) ? x : 0;
}

void dfs2(int u, int fa){
    for(int i = h[u];i;i = e[i].nxt){
        int v = e[i].to;
        if(v == fa) continue;
        //处理大子树u
        csz[u] = n - sz[v];
        son3[u] = (son1[u] == v) ? son2[u] : son1[u];
        if(fa && csz[fa] > csz[son3[u]]) son3[u] = fa;
        up[u][0] = son3[u];
        for(int j = 1;j <= LOG;j ++){
            up[u][j] = up[up[u][j - 1]][j - 1];
        }
        int hav1 = u;
        for(int j = LOG;j >= 0;j --){
            if(csz[u] - csz[up[hav1][j]] <= csz[u] / 2){
                hav1 = up[hav1][j];
            }
        }
        ans += check(son3[hav1], csz[u], csz[son3[son3[hav1]]]);
        ans += check(hav1, csz[u], csz[son3[hav1]]);
        ans += check(fu[hav1], csz[u], csz[son3[fu[hav1]]]);
        //处理小子树v
        csz[v] = sz[v];
        int hav2 = v;
        for(int j = LOG;j >= 0;j --){
            if(csz[v] - csz[up[hav2][j]] <= csz[v] / 2){
                hav2 = up[hav2][j];
            }
        }
        ans += check(son1[hav2], csz[v], csz[son1[son1[hav2]]]);
        ans += check(hav2, csz[v], csz[son1[hav2]]);
        ans += check(fu[hav2], csz[v], csz[son1[fu[hav2]]]);
        //递归处理子节点，维护临时父方向
        fu[u] = v;
        dfs2(v, u);
        //恢复原状态
        son3[u] = son1[u];
        up[u][0] = son1[u];
        for(int j = 1;j <= LOG;j ++){
            up[u][j] = up[up[u][j - 1]][j - 1];
        }
        csz[u] = sz[u];
        fu[u] = f[u];
    }
    son3[u] = son1[u];
    up[u][0] = son1[u];
    for(int j = 1;j <= LOG;j ++){
        up[u][j] = up[up[u][j - 1]][j - 1];
    }
    csz[u] = sz[u];
    fu[u] = f[u];
}

void init(){
    tot = 0; ans = 0;
    memset(h, 0, sizeof(h));
    memset(son1, 0, sizeof(son1));
    memset(son2, 0, sizeof(son2));
    memset(son3, 0, sizeof(son3));
    memset(f, 0, sizeof(f));
    memset(fu, 0, sizeof(fu));
    memset(sz, 0, sizeof(sz));
    memset(csz, 0, sizeof(csz));
    memset(up, 0, sizeof(up));
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> T;
    while(T --){
        init();
		cin >> n;
        for(int i = 1;i < n;i ++){
            int u, v; cin >> u >> v;
            add(u, v), add(v, u);
        }
        dfs1(1, 0);
        memcpy(csz, sz, sizeof(sz));
        memcpy(son3, son1, sizeof(son1));
        memcpy(fu, f, sizeof(f));
        dfs2(1, 0);
        cout << ans << '\n';
    }
    return 0;
}