头像

ytczy666




离线:6小时前



博客食用更佳 https://www.cnblogs.com/czyty114/p/14449737.html

引入

$\;$
假如现在我们得到了一棵$n$个节点的树,每条边都有长度。
现在我们要求这棵树中两个点之间距离小于$k$的点对个数。
$n\leq 4×10^4$

朴素做法

$\;$
先预处理好距离,再$O(n^2)$枚举点对。

重心

$\;$
我们找到这棵树的重心G,把这棵树分为若干个子树,那么发现满足条件的点对只有3种情况:
1.点对在某个子树中(直接递归求解)
2.两个点所构成的路径经过了重心G,但你会发现这两个点一定不能在同一个子树中。
所以我们处理出当前这棵树中每个点的d值,$d_i$表示点$i$到重心G的距离。
那么只需要用$d_i+d_j\leq k$这样$(i,j)$的数量减去$d_i+d_j\leq k$且满足$i,j$在同一个子树中的数量
而你会发现,后者可以在递归子树中处理。
3.这条路经的一个端点是G,那么实质上和2.是一种情况,再加入一个$d_G=0$即可
$\;$

时间复杂度

$\;$
选重心来分割整棵树的目的:
你会发现,这若干棵子树中不会有子树的大小超过原树的一半(否则就与重心的定义不符)
所以最多只会递归$log(n)$层,每一层也是$n$个点。但在递归中还要将处理好的d排序。
总复杂度$O(n log^2 n)$

Code

$\;$
一定要注意:如果在函数里单独开变量而是开全局变量,一定要注意随时清空,防止上一层的答案对下面有影响。

#include <bits/stdc++.h>

const int N = 40010;
int n, k, head[N], tot, f[N], mn, W, vis[N], d[N], ans, q[N], cnt, sz[N];
struct node {
    int to, nxt, val;
}E[N << 1];
void add(int u, int v, int w) {
    E[++tot].to = v; E[tot].nxt = head[u]; E[tot].val = w; head[u] = tot;
}
void dfs(int total, int u, int fa) {
    f[u] = 0; // 一定注意初始化 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(v == fa || vis[v]) continue;
        dfs(total, v, u);
        f[u] = std::max(f[u], sz[v]);
    }
    f[u] = std::max(f[u], total - sz[u]);
    if(f[u] < mn) {
        mn = f[u]; W = u;
    }
}
void dfs0(int u, int fa) {
    sz[u] = 1; q[++cnt] = d[u]; // 这是在减去2那一部分的时候的d值 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(v == fa || vis[v]) continue;
        dfs0(v, u); 
        sz[u] += sz[v];
    }
} 
void getG(int rt) {     
    cnt = 0; // 随时清空 
    dfs0(rt, 0); // 预处理好每个点的子树大小(因为随着划分重心,树的形态会变化) 
    mn = 1e9; // 注意初始化 
    dfs(sz[rt], rt, 0); // DP计算重心 
    vis[W] = 1; // 这个点作为重心,将其打上标记(相当于一个边界条件) 
}
void getd(int u, int fa) {
    q[++cnt] = d[u]; // 在求d值的过程中将其存入q数组中,这里是以这棵树为重心是的d值,与上面的d不一样 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(vis[v] || v == fa) continue;
        d[v] = d[u] + E[i].val; 
        getd(v, u);
    }
}
void solve(int rt) {
    getG(rt);  // 得到重心 
    if(sz[rt] != n) { 
    // 对于2.情况,要减去在相同子树内(i,j)<=k的个数。这个过程是在递归到这个子树中时进行的 
    //但对于一开始整棵树的情况就没必要减了 
        std::sort(q + 1, q + cnt + 1); 
        // q里存储的是这棵子树内的d值
        // 因为树内点的编号不一定是连续的,所以需要开q这个数组存它 
        int e1 = 1, e2 = cnt;
        for(int e1=1;e1<=cnt;e1++) {
            while(e2 > e1 && q[e1] + q[e2] > k) e2 --; // 双指针枚举,复杂度是线性的 
            if(e2 <= e1) break;
            ans -= (e2 - e1);
        }
    }
    d[W] = 0; // 重心的d当然是0 
    cnt = 0; // 一定注意要随时清空 
    getd(W, 0);
    std::sort(q + 1, q + cnt + 1);
    int e1 = 1, e2 = cnt;
    for(int e1=1;e1<=cnt;e1++) {
        while(e2 > e1 && q[e1] + q[e2] > k) e2 --;
        if(e2 <= e1) break;
        ans += (e2 - e1);
    } 
    for(int i=head[W];i;i=E[i].nxt) {
        int v = E[i].to;
        if(!vis[v]) solve(v); // 如果这个点没被打上标记,一定要向下递归 
    }
}
int main() {
    scanf("%d", &n);
    for(int i=1;i<n;i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w); add(v, u, w);
    }
    scanf("%d", &k);
    solve(1);
    printf("%d", ans);
    return 0;
}


分享 点分治

博客食用更佳 https://www.cnblogs.com/czyty114/p/14449737.html

引入

$\;$
假如现在我们得到了一棵$n$个节点的树,每条边都有长度。
现在我们要求这棵树中两个点之间距离小于$k$的点对个数。
$n\leq 4×10^4$

朴素做法

$\;$
先预处理好距离,再$O(n^2)$枚举点对。

重心

$\;$
我们找到这棵树的重心G,把这棵树分为若干个子树,那么发现满足条件的点对只有3种情况:
1.点对在某个子树中(直接递归求解)
2.两个点所构成的路径经过了重心G,但你会发现这两个点一定不能在同一个子树中。
所以我们处理出当前这棵树中每个点的d值,$d_i$表示点$i$到重心G的距离。
那么只需要用$d_i+d_j\leq k$这样$(i,j)$的数量减去$d_i+d_j\leq k$且满足$i,j$在同一个子树中的数量
而你会发现,后者可以在递归子树中处理。
3.这条路经的一个端点是G,那么实质上和2.是一种情况,再加入一个$d_G=0$即可
$\;$

时间复杂度

$\;$
选重心来分割整棵树的目的:
你会发现,这若干棵子树中不会有子树的大小超过原树的一半(否则就与重心的定义不符)
所以最多只会递归$log(n)$层,每一层也是$n$个点。但在递归中还要将处理好的d排序。
总复杂度$O(n log^2 n)$

Code

$\;$
一定要注意:如果在函数里单独开变量而是开全局变量,一定要注意随时清空,防止上一层的答案对下面有影响。

#include <bits/stdc++.h>

const int N = 40010;
int n, k, head[N], tot, f[N], mn, W, vis[N], d[N], ans, q[N], cnt, sz[N];
struct node {
    int to, nxt, val;
}E[N << 1];
void add(int u, int v, int w) {
    E[++tot].to = v; E[tot].nxt = head[u]; E[tot].val = w; head[u] = tot;
}
void dfs(int total, int u, int fa) {
    f[u] = 0; // 一定注意初始化 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(v == fa || vis[v]) continue;
        dfs(total, v, u);
        f[u] = std::max(f[u], sz[v]);
    }
    f[u] = std::max(f[u], total - sz[u]);
    if(f[u] < mn) {
        mn = f[u]; W = u;
    }
}
void dfs0(int u, int fa) {
    sz[u] = 1; q[++cnt] = d[u]; // 这是在减去2那一部分的时候的d值 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(v == fa || vis[v]) continue;
        dfs0(v, u); 
        sz[u] += sz[v];
    }
} 
void getG(int rt) {     
    cnt = 0; // 随时清空 
    dfs0(rt, 0); // 预处理好每个点的子树大小(因为随着划分重心,树的形态会变化) 
    mn = 1e9; // 注意初始化 
    dfs(sz[rt], rt, 0); // DP计算重心 
    vis[W] = 1; // 这个点作为重心,将其打上标记(相当于一个边界条件) 
}
void getd(int u, int fa) {
    q[++cnt] = d[u]; // 在求d值的过程中将其存入q数组中,这里是以这棵树为重心是的d值,与上面的d不一样 
    for(int i=head[u];i;i=E[i].nxt) {
        int v = E[i].to;
        if(vis[v] || v == fa) continue;
        d[v] = d[u] + E[i].val; 
        getd(v, u);
    }
}
void solve(int rt) {
    getG(rt);  // 得到重心 
    if(sz[rt] != n) { 
    // 对于2.情况,要减去在相同子树内(i,j)<=k的个数。这个过程是在递归到这个子树中时进行的 
    //但对于一开始整棵树的情况就没必要减了 
        std::sort(q + 1, q + cnt + 1); 
        // q里存储的是这棵子树内的d值
        // 因为树内点的编号不一定是连续的,所以需要开q这个数组存它 
        int e1 = 1, e2 = cnt;
        for(int e1=1;e1<=cnt;e1++) {
            while(e2 > e1 && q[e1] + q[e2] > k) e2 --; // 双指针枚举,复杂度是线性的 
            if(e2 <= e1) break;
            ans -= (e2 - e1);
        }
    }
    d[W] = 0; // 重心的d当然是0 
    cnt = 0; // 一定注意要随时清空 
    getd(W, 0);
    std::sort(q + 1, q + cnt + 1);
    int e1 = 1, e2 = cnt;
    for(int e1=1;e1<=cnt;e1++) {
        while(e2 > e1 && q[e1] + q[e2] > k) e2 --;
        if(e2 <= e1) break;
        ans += (e2 - e1);
    } 
    for(int i=head[W];i;i=E[i].nxt) {
        int v = E[i].to;
        if(!vis[v]) solve(v); // 如果这个点没被打上标记,一定要向下递归 
    }
}
int main() {
    scanf("%d", &n);
    for(int i=1;i<n;i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w); add(v, u, w);
    }
    scanf("%d", &k);
    solve(1);
    printf("%d", ans);
    return 0;
}



博客食用更佳~ https://www.cnblogs.com/czyty114/p/14443656.html

引入

$\;$
假设现在我们得到了一个$n$次多项式$f(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n$,$n+1$个条件形如$(x_i,y_i)$,表示当$x=x_i$时,多项式的值为$y_i$
求:$a_0,a_1,\cdots,a_n$
对于这类问题,我们当然可以根据$(x_i,y_i)$写出$n+1$个$n+1$次方程组成的线性方程组,然后再$O(n^3)$的时间内用高斯消元求解
但对于$n\leq 2000$这样的范围,高斯消元就不适用了。
接下来介绍的拉格朗日插值法,时间复杂度是$O(n^2)$的
$\;$

拉格朗日插值

$\;$
我们考虑构造出$n+1$个多项式,满足第$i$个多项式只有当自变量取值为$x_i$时,其值为1,否则为0
那么对于第$i$个多项式,其形式即为:
$$fi(k)=\prod_{i\neq j} \frac{k-x_j}{x_i-x_j}$$
显然,上式是满足条件的。
那么对于原多项式,显然:
$$f(k)=\sum_{i=0}^n y_i fi(k)$$
如果题目只是要求这个多项式在给定$k$下的函数值,显然可以$O(n^2)$来解决。
但如果要求每一项系数,仍然是$O(n^3)$
$\;$

特殊情况

$\;$
若给定的$x_i$是连续的数,即:$x_i=i$,我们来看这个东西有什么更好的性质
$fi(k)$可以变为$\prod_{i\neq j} \frac{k-j}{i-j}$
我们把整个柿子抄一遍
$$f(k)=\sum_{i=0}^n y_i \prod_{i\neq j} \frac{k-j}{i-j}$$
设$h(i)=\prod_{j=0}^i (k-j),r(i)=\prod_{j=i}^n (k-j), fac(i)=i!$,那么:
$$f(k)=\sum_{i=0}^n y_i \frac{h(i-1)r(i+1)}{fac(i)fac(n-i)(-1)^{n-i}}$$
那么我们预处理好$h,r,fac$,$f(k)$就可以$O(n)$的算出来了
但是若要求表达式仍是O(n^3)的
$\;$

优化

$\;$
其实也不算是优化,是为了解决另一种更繁琐的情况,若有时候要减少一个或加入一个插值点,即:$(x_i,y_i)$
按原来的式子还必须重新算一遍,如何优化呢?
观察上面的式子:
$f(k)=\sum_{i=0}^n y_i \prod_{i\neq j} \frac{k-x_j}{x_i-x_j}$
我们发现$k-x_j$这里是与$i$无关的,提到前面。
设$g(k)=\prod_{i=0}^n (k-x_i)$
于是原式就变成了:
$f(k)=g(k) \sum_{i=0}^n \frac{y_i}{k-x_i} \prod_{i\neq j} \frac{1}{x_i-x_j}$
设$t(i)= \prod_{i\neq j} \frac{1}{x_i-x_j}$
$f(k)=g(k) \sum_{i=0}^n \frac{y_it_i}{k-x_i}$
我们发现,$t(1),t(2),\cdots,t(n)$是可以$O(n^2)$预处理的,其余用$O(n)$时间即可解决
那么如果我们要加入一个插值点$(x_{n+1},y_{n+1})$,显然只需要把所有的$t(i)$除以$x_i-x_{n+1}$
这样修改的复杂度是$O(n)$的,然后我们再用$O(n)$的时间求值即可

Code

$\;$
求$f(k)$的值。
代码用的是那个支持加入插值点方法(其实第一种也可以做)

#include <bits/stdc++.h>

const int N = 2010, mod = 998244353;
int n, k, g = 1, t[N], x[N], y[N];
int power(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1; 
    }
    return ans;
} 
int main() {
    scanf("%d%d", &n, &k); 
    for(int i=0;i<n;i++) scanf("%d%d", &x[i], &y[i]);
    for(int i=0;i<n;i++) g = 1ll * g * (k - x[i] + mod) % mod;
    for(int i=0;i<n;i++) {
        int now = 1;
        for(int j=0;j<n;j++) {
            if(j == i) continue;
            now = 1ll * now * (x[i] - x[j] + mod) % mod;
        }
        t[i] = power(now, mod - 2);
    }
    int ans = 0;
    for(int i=0;i<n;i++) {
        int tmp = 1ll * y[i] * t[i] % mod * power(k - x[i] + mod, mod - 2) % mod;
        ans = (ans + tmp) % mod;
    }
    printf("%d", 1ll * ans * g % mod);
    return 0;
}


分享 莫队算法

博客食用更佳~ https://www.cnblogs.com/czyty114/p/14432462.html

$\;$
莫队是一类离线区间询问问题,经常应用于需要维护的信息无法合并时(如线段树等)
其核心思想是:维护两个指针$l,r$。在已知$[l,r]$这段区间的信息的前提下,两个指针分别移动到$l’,r’$的过程中,实时地维护答案。从而算出区间$[l,r]的信息$
$\;$

引入

$\;$
因为题目没有强制在线,所以莫队算法是将所有的询问按一定顺序排好序,并且一次询问是以上一次询问为基础。
我们可以把一次询问$l,r$看作二维平面上的一个点$(l,r)$,那我们在两次询问间$l,r$指针一共移动的距离,实质上是$(l_1,r_1)$,$(l_2,r_2)$间的曼哈顿距离
但求最小哈密尔顿路径又是无法做到的。所以我们需要找到一个合适的顺序,使得两指针移动的距离尽可能的小。
$\;$

核心

$\;$
假设现在给定你一个长为$n$的序列,$m$次询问,每次询问求$[l,r]$这段区间不同数的数量。
$n,m\leq 10^5$
对于这个问题来说,用线段树是很难去维护的。因为区间不同数的数量并不能很轻松地由左右子区间转移而来。
考虑将整个序列分块,每段长度为$\sqrt n$
这样每段询问区间的左右端点必定位于某个块中。
我们把区间左端点所属的块的编号作为第一关键字,右端点的位置作为第二关键字,将询问区间排序。
按照莫队的思想,我们按此顺序依次处理每一个区间,在两个指针的移动的过程中维护一个数组cnt,表示每一个数出现的次数。
若发现某个数cnt为由1减为0了,将答案减1,反之则加1
$\;$

时间复杂度

$\;$
我们发现算法中时间的瓶颈就在于,左右指针总共会移动多少次。我们分开来看:
(注意:这里我们假设m与n同阶)

左端点

$\;$
因为第一关键字是按左端点所在块排序的,所以左端点所在块是单调不降的。
对于目前左端点与上一个左端点同属一个块的情况:最多出现$n$次,但每一次两个点之间移动的距离不超过$\sqrt n$
因此:$O(n\sqrt n)$
对于目前左端点与上一个左端点不同属一个块的情况:最多出现$\sqrt n$次,但每一次两个点之间移动的距离不超过$n$
因此:$O(n\sqrt n)$
$\;$

右端点

$\;$
其位置作为第二关键字。因此若左端点有若干个位于同一个块中,此时右端点应该是单调不降的。
因此对于同一个块的左端点,右端点至多移动$n$次,而总共有$\sqrt n$个块
因此:$O(n\sqrt n)$
否则,若左端点不在同一个块中,右端点的位置就无法确定了。这样一次右端点至多移动$n$次
但这种情况至多出现$\sqrt n$次
因此:$O(n\sqrt n)$
$\;$
综上所述,莫队算法的时间复杂度为$O(n\sqrt n)$

Code

#include <bits/stdc++.h>

const int N = 50010, M = 200010;
int n, m, a[N], b[N], ans[M], id[N], sq, nn, cnt[N];
struct node {
    int pos, l, r;
}ask[M];
bool cmp(node a, node b) {
    if(id[a.l] != id[b.l]) return id[a.l] < id[b.l]; // 左端点所属块 
    return a.r < b.r; // 右端点所属位置 
}
int main() {
    scanf("%d", &n);
    sq = (int)sqrt(n);
    for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq); // 预处理每个点所属块的编号 
    for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
    std::sort(b + 1, b + n + 1);
    nn = std::unique(b + 1, b + n + 1) - b - 1;
    for(int i=1;i<=n;i++) a[i] = std::lower_bound(b + 1, b + nn + 1, a[i]) - b;
    //----------------- 上面是离散化部分,不多赘述 
    scanf("%d", &m);
    for(int i=1;i<=m;i++) scanf("%d%d", &ask[i].l, &ask[i].r), ask[i].pos = i;
    std::sort(ask + 1, ask + m + 1, cmp);
    int x = 0, y = 0, res = 0; //x,y维护的是一直在移动两个指针 
    for(int i=1;i<=m;i++) {
        int l = ask[i].l, r = ask[i].r; // l,r是当前询问的两个左右端点 
        while(x < l) { // 左端点向右移,区间缩小 
            cnt[a[x]] --; if(!cnt[a[x]]) -- res;
            x ++;
        }

        while(x > l) { // 左端点向左移,区间变大 
            cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
            x --;
        }

        while(y < r) { // 右端点向右移,区间变大 
            cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
            y ++;
        }

        while(y > r) { // 右端点向左移,区间缩小 
            cnt[a[y]] --; if(!cnt[a[y]]) -- res;
            y --;
        }

        ans[ask[i].pos] = res; // 注意:i是排序后区间的编号,但并不是输入时询问的编号 
    }
    for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
    return 0;
}


活动打卡代码 AcWing 499. 聪明的质监员

ytczy666
23天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 503. 借教室

ytczy666
23天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 257. 关押罪犯

ytczy666
23天前
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=20010,M=100010;
struct edge{
    int to,nxt,value;
}e[M<<1];
int head[N];
int n,m,tot,color[N];
void addedge(int u,int v,int w)
{
    e[++tot].to=v;
    e[tot].nxt=head[u];
    e[tot].value=w;
    head[u]=tot;
}
bool dfs(int u,int c,int mid)
{
    color[u]=c;
    for(int i=head[u];i;i=e[i].nxt)
    {
        if(e[i].value<=mid)continue;
        int v=e[i].to;
        if(color[v])
        {
            if(color[v]==c)return false;
        }
        else if(!dfs(v,3-c,mid))return false;
    }
    return true;
}
bool check(int mid)
{
    memset(color,0,sizeof(color));
    for(int i=1;i<=n;i++)
    {
        if(color[i]==0)
        {
            if(!dfs(i,1,mid))
            return false;
        }
    }
    return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,w);
    }
    int l=0,r=1e9;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    printf("%d",r);
    return 0;
}


分享 RP++

ytczy666
1个月前

明天期末考试RP++!




ytczy666
2个月前

代码可以参考,可以看注释理解

#include <bits/stdc++.h>
using std::string;
using std::cin;
using std::cout;
int n, m;
char card[2020]; // 游戏中的牌堆 
int card_top = 1; // 牌用到哪里了 
bool over; // 游戏是否结束 
bool like[100]; // 主猪眼里的类反猪集合和类反猪数量 
int nxt[100]; // 每只猪的下一只猪 
struct Node
{
    char who, pai[2020]; //身份与手牌 
    int cnt; // 牌的数量
    int xie; // 猪的血量 
    bool ak; // 是否有连弩 
    bool able; // 目前还是否能够出杀 
    bool jump; // 目前是否已经跳身份了 
}pig[20];
void Get_card(int cur)
{
    pig[cur].pai[++pig[cur].cnt] = card[card_top];
    if(card_top < m) card_top ++; // 若牌堆里只剩一张牌了就不必弹出 
}
void Insert(int cur)
{
    like[cur] = true; // 插入集合 
} 
void jie_suan(int cur, int to) // cur干掉了第i只猪 
{
    if(pig[to].who == 'F') 
    {
        bool flag = true;
        for(int i=1;i<=n;i++)
        {
            if(pig[i].who == 'F' && pig[i].xie > 0) // 若有一个反猪还活着
            {
                flag = false; // 说明游戏未结束 
                break;
            } 
        }
        if(flag) over = true; // 无反猪了,游戏结束 
        if(over) return; // 游戏结束了,不用摸牌了 
        Get_card(cur); Get_card(cur); Get_card(cur); // 立即摸三张牌 
    }
    else if(pig[to].who == 'Z')
    {
        if(pig[cur].who == 'M') // 主猪把忠猪干掉了
        {
            for(int i=1;i<=pig[cur].cnt;i++) pig[cur].pai[i] = 'T'; // 清空手牌
            pig[cur].ak = false; // 扔掉装备 
        } 
    }
    if(to == 1) over =  true; // 若主猪被干掉了,游戏直接结束 
    else
    {
        bool flag = true;
        for(int i=1;i<=n;i++)
        {
            if(pig[i].who == 'F' && pig[i].xie > 0) // 若有一个反猪还活着
            {
                flag = false; // 说明游戏未结束 
                break;
            } 
        }
        if(flag) over = true; // 无反猪了,游戏结束 
    }
}
char another(char c)
{
    if(c == 'Z' || c == 'M') return 'F';
    else return 'Z';
}
bool same(char A, char B) // 判断两只猪势力是否相同 
{
    if(A == 'F' && B == 'F') return true;
    if(A == 'Z' && B == 'Z') return true;
    if(A == 'Z' && B == 'M') return true;
    if(A == 'M' && B == 'Z') return true;
    if(A == 'M' && B == 'M') return true;
    return false;
}
bool ask_wu_xie(int start, char now)
{
    int i = start;
    while(1) // 不停的循环询问无懈 
    { 
        if(pig[i].xie == 0) // 猪挂了不用管他 
        {
            i = i % n + 1;
            if(i == start) return false;
            continue;
        }
        int t = -1; // 存储无懈的位置 
        for(int j=1;j<=pig[i].cnt;j++)
        {
            if(pig[i].pai[j] == 'J')
            {
                t = j;
                break; 
            } 
        }
        if(t == -1) // 说明这只猪没有无懈,不用管它了
        {
            i = i % n + 1;
            if(i == start) return false;
            continue; 
        }
        if(same(pig[i].who, now)) // 若此时势力相同
        {
            pig[i].pai[t] = 'T'; // 打出无懈
            pig[i].jump = true; // 打出无懈肯定跳了身份 
            like[i] = false; // 若其是忠猪,则从类反猪名单上划掉 
            now = another(now); // 仔细想想 
            if(!ask_wu_xie(i, now)) return true;
            else return false;
        } 
        i = i % n + 1; // 继续逆时针转 
        if(i == start) return false;
    } 
}
void bin_si(int from, int to)
{
    pig[to].xie --;
    if(pig[to].xie == 0) // 若此时这只猪处于濒死状态
    {
        bool alive = false; 
        for(int j=1;j<=pig[to].cnt;j++)
        {
            if(pig[to].pai[j] == 'P') // 如果有桃赶紧吃掉(不然就挂掉了)
            {
                pig[to].xie ++; // 回一滴血 
                pig[to].pai[j] = 'T'; // 用过这张牌了
                alive = true; break;
            } 
        }
        if(!alive) // 说明这只猪挂掉了
        {
            jie_suan(from, to); // 结算结果(摸三张牌、弃牌、游戏结束之类的) 
        } 
    }
}
bool Kill(int cur, int i)
{
    if(!pig[cur].able) return false; // 若此时都不能出杀了肯定false
    int tt = -1; 
    for(int j=cur%n+1;j!=cur;j=j%n+1) 
    {
        if(pig[j].xie) // 找到第一只活着的猪 
        {
            tt = j;
            break;
        }
    }  
    if((cur == 1 && like[tt]) || (pig[tt].jump && !same(pig[cur].who, pig[tt].who))) // 如果2号位是类反猪或已跳反
    {
        if(!pig[cur].ak) pig[cur].able = false;
        pig[cur].pai[i] = 'T'; // 用掉这张杀
        pig[cur].jump = true; // 跳身份了
        like[cur] = false;
        int t = -1;
        for(int j=1;j<=pig[tt].cnt;j++)
        {
            if(pig[tt].pai[j] == 'D')
            {
                t = j;
                break;
            }
        } 
        if(t != -1) // 说明有闪
        {
            pig[tt].pai[t] = 'T'; // 出闪 
        } 
        else // 否则要掉血 
        {
            bin_si(cur, tt);
        } 
        return true;
    }  
    return false;
}
void action(int from, int to)
{
    if(pig[to].jump) if(ask_wu_xie(from, pig[to].who)) return; // 若询问无懈成功,直接return
    if(from == 1 && pig[to].who == 'Z') // 若发起决斗者是主猪,且被决斗者是忠猪
    {
        bin_si(1, to); // 忠猪直接掉血
    } 
    else 
    {
        int tmp1 = 0, tmp2 = 0;
        for(int i=1;i<=pig[from].cnt;i++) if(pig[from].pai[i] == 'K') tmp1 ++;
        for(int i=1;i<=pig[to].cnt;i++) if(pig[to].pai[i] == 'K') tmp2 ++;
        if(tmp2 > tmp1)
        {
            for(int i=1;i<=pig[from].cnt;i++) if(pig[from].pai[i] == 'K') pig[from].pai[i] = 'T';
            int now = 0;
            for(int i=1;i<=pig[to].cnt;i++) 
            {
                if(pig[to].pai[i] == 'K') 
                {
                    now ++; pig[to].pai[i] = 'T';
                    if(now == tmp1 + 1) break;
                }
            }
            bin_si(to, from);
        }
        else 
        {
            for(int i=1;i<=pig[to].cnt;i++) if(pig[to].pai[i] == 'K') pig[to].pai[i] = 'T';
            int now = 0;
            for(int i=1;i<=pig[from].cnt;i++) 
            {
                if(now == tmp2) break;
                if(pig[from].pai[i] == 'K')
                {
                    now ++; pig[from].pai[i] = 'T';
                }
            }
            bin_si(from, to); 
        }
    }
} 
bool jue_dou(int cur, int i)
{
    int t = -1;
    if(pig[cur].who == 'Z' || pig[cur].who == 'M')
    {
        for(int j=cur%n+1;j!=cur;j=j%n+1)
        {
            if(pig[j].xie == 0) continue;
            if((cur == 1 && like[j]) || (pig[j].jump && !same(pig[cur].who, pig[j].who))) // 找到第一只能决斗的目标 
            {
                t = j;
                break;
            }
        }
    }
    else if(pig[cur].who == 'F')
    {
        t = 1;
    }
    if(t == -1) return false; // 没有找到目标 
    else
    {
        pig[cur].jump = true; // 既然决斗了肯定跳了身份 
        like[cur] = false;
        pig[cur].pai[i] = 'T';
        action(cur, t); // 开始决斗 
        return true;
    }
}
void AOE(int cur, bool which) // 第cur只猪使用了南蛮入侵 / 万箭齐发 
{
    for(int i=cur%n+1;i!=cur;i=i%n+1) // 开始逆时针结算 
    { 
        if(pig[i].xie == 0) continue; // 若这只猪已经挂了直接continue 
        bool flag = false;
        if(pig[i].jump) // 如果跳身份了别人才肯给他出无懈 
        {
            if(ask_wu_xie(cur, pig[i].who)) continue; // 若询问无懈成功直接continue 
        }

        for(int j=1;j<=pig[i].cnt;j++) // 枚举这只猪的牌 
        {
            if(which == 0) // 说明是南蛮入侵 
            {
                if(pig[i].pai[j] == 'K') // 若这张牌是杀 
                {
                    pig[i].pai[j] = 'T'; 
                    flag = true; break;
                }
            }
            else // 说明是万箭齐发 
            {
                if(pig[i].pai[j] == 'D') // 若这张牌是闪 
                {
                    pig[i].pai[j] = 'T'; 
                    flag = true; break;
                }
            }
        }
        if(!flag) // 若这只猪没有杀,说明要掉血 
        {
            bin_si(cur, i); 
            if(over) return; // 游戏结束就不必再往下 
            // 运行到此说明没挂或者用桃子救过来了
            if(i == 1 && !pig[cur].jump) // 若这只猪是主猪且造成伤害的猪还未跳身份 
                Insert(cur); // 将第cur只猪插入到类反猪集合中 
        }
    }
} 
bool can_use(int cur, char tmp, int i) // 表示第cur只猪,用了tmp这种牌 
{
    if(tmp == 'T') return false; // 若这张牌是空的直接false 
    if(tmp == 'D') return false; // 若这张牌是闪,也不可能在出牌阶段出 
    if(tmp == 'J') return false; // 若这张牌是无懈,也不可能在这时候出 
    if(tmp == 'Z') 
    {
        pig[cur].ak = true; // 有连弩了
        pig[cur].able = true; 
        pig[cur].pai[i] = 'T'; // 这张牌用了
        return true; 
    }
    if(tmp == 'P') // 若这张牌是桃子 
    {
        if(pig[cur].xie < 4) //不满血 
        {
            pig[cur].xie ++; // 加血 
            pig[cur].pai[i] = 'T'; // 用了这张牌
            return true; 
        }
        else return false; 
    } 
    if(tmp == 'N') // 如果这张牌是南蛮入侵 
    {
        AOE(cur, 0); // 使用南蛮入侵
        pig[cur].pai[i] = 'T'; // 用了这张牌
        return true; 
    }
    if(tmp == 'W') // 如果这张牌是万箭齐发
    {
        AOE(cur, 1); // 使用万箭齐发 
        pig[cur].pai[i] = 'T'; // 用了这张牌
        return true;
    } 
    if(tmp == 'K')
    {
        if(Kill(cur, i)) // 若可以杀 
        {
            return true;
        }
        else return false;
    } 
    if(tmp == 'F')
    {
        if(jue_dou(cur, i)) // 若可以决斗 
        {
            return true;
        }
        else return false;
    }
    return false;
} 
void Use_card(int cur)
{
    while(1)
    {
        if(pig[cur].xie == 0) break;
        bool fail = false;
        for(int i=1;i<=pig[cur].cnt;i++)
        {
            if(can_use(cur, pig[cur].pai[i], i))
            {  
                if(over) return;
                fail = true; break; // 若找到一张能出的牌,就出然后break 
            }
        }
        if(!fail) break; // 没有一张能出的break就OK了 
    }
}
int main()
{
    scanf("%d%d", &n, &m); // 猪的数量和初始时牌堆中牌的数量
    char str[20];
    pig[1].jump = true; // 主猪的身份是明的 
    for(int i=1;i<=n;i++)
    {
        scanf("%s", str); pig[i].who = str[0]; // 身份:M、Z,F 
        for(int j=1;j<=2005;j++) pig[i].pai[j] = 'T'; //T就是已经用过的牌,这里初始化 
        for(int j=1;j<=4;j++) 
        {
            scanf("%s", str); pig[i].pai[j] = str[0];
        } 
        pig[i].cnt = 4; pig[i].xie = 4; pig[i].ak = false; if(i != 1) pig[i].jump = false; 
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%s", str); card[i] = str[0];
    }
    for(int i=1;;i=i%n+1) // 逆时针轮流出牌 
    {
        if(over) break; 
        if(pig[i].xie == 0) continue; // 如果挂了直接跳过
        pig[i].able = true; // 目前可以使用杀 
        Get_card(i); Get_card(i); //从牌堆里摸两张牌
        Use_card(i);
    }
    if(pig[1].xie == 0)
    {
        puts("FP");
    }   
    else puts("MP");
    for(int i=1;i<=n;i++)
    {
        if(pig[i].xie == 0) 
        {
            puts("DEAD");
            continue;
        }
        for(int j=1;j<=pig[i].cnt;j++)
        {
            if(pig[i].pai[j] != 'T') cout << pig[i].pai[j] << " "; 
        }
        puts("");
    }
}


活动打卡代码 AcWing 380. 舞动的夜晚

ytczy666
2个月前
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define INF 1000000000
const int N = 20010, M = 100010;
int n, m, k, S, T, dep[N], res;
int head[N], tot = 1, idcnt, idx;
int dfn[N], low[N], scc, stk[N], top, inq[N], bl[N], st[M << 2];
struct Node
{
    int from, to, nxt, val, id;
}E[M << 2];
void add(int u, int v, int w)
{
    ++idcnt; 
    E[++tot].to = v; E[tot].from = u; E[tot].nxt = head[u]; E[tot].val = w; head[u] = tot; E[tot].id = idcnt;
    E[++tot].to = u; E[tot].from = v; E[tot].nxt = head[v]; E[tot].val = 0; head[v] = tot;
}
bool bfs()
{
    memset(dep, 0, sizeof(dep));
    std::queue<int> q;
    q.push(S); dep[S] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int i=head[u];i;i=E[i].nxt)
        {
            int v = E[i].to;
            if(!dep[v] && E[i].val > 0)
            {
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
    }
    if(dep[T]) return true;
    return false;
}
int dinic(int u, int flow)
{
    if(u == T) return flow;
    int outf = 0;
    for(int i=head[u];i&&flow;i=E[i].nxt)
    {
        int v = E[i].to;
        if(dep[v] == dep[u] + 1 && E[i].val > 0)
        {
            int tmp = std::min(flow, E[i].val);
            int now = dinic(v, tmp);
            E[i].val -= now; E[i ^ 1].val += now; outf += now; flow -= now;
        }
    }
    if(!outf) dep[u] = 0;
    return outf;
}
void Tarjan(int u)
{
    dfn[u] = ++idx; low[u] = dfn[u];
    stk[++top] = u; inq[u] = 1;
    for(int i=head[u];i;i=E[i].nxt)
    {
        int v = E[i].to;
        if(!E[i].val) continue;
        if(!dfn[v])
        {
            Tarjan(v); 
            low[u] = std::min(low[u], low[v]);
        }
        else if(inq[v])
        {
            low[u] = std::min(low[u], dfn[v]);
        } 
    }
    if(dfn[u] == low[u])
    {
        ++ scc;
        int now = -1;
        while(now != u)
        {
            now = stk[top --];
            bl[now] = scc; inq[now] = 0; 
        }
    }
}
bool check(int cur)
{
    int u = E[cur].from, v = E[cur].to;
    if(!E[cur].val || bl[u] == bl[v] || u == S || v == T || !E[cur].id) return true;
    return false;
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    T = n + m + 1; 
    for(int i=1;i<=k;i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v + n, 1);
    }
    for(int i=1;i<=n;i++) add(S, i, 1); // 从源点到左边都连1的边
    for(int i=n+1;i<=n+m;i++) add(i, T, 1);
    while(bfs()) dinic(S, INF);
    for(int i=1;i<=T;i++) if(!dfn[i]) Tarjan(i); 
    for(int i=2;i<=tot;i++)
    {
        int u = E[i].from, v = E[i].to;
        if(check(i)) continue;
        res ++; st[i] = 1;
    }
    printf("%d\n", res);
    for(int i=2;i<=tot;i++) 
    {
        if(st[i]) printf("%d ", E[i].id);
    }
    if(!res) puts("");
    return 0;   
}