2022牛客多校三_F G

2022牛客多校三

传送门

为什么题越补越多了a

F- Fief

prob. : 给n个点m边，两个标记点，问是否存在一个排列使得两个标记点（x，y）在两端，且在该排列中任意划分，分出的两部分仍连通。

ideas:

如果x或y为割点，则不可行（可以画一下图理解一下）

如果有一个环，环内点两两可达，这些点等价

点双缩点后的图，如果是一条链，且xy在链的两端则可行；如果是树则不可行（在任意一个度数>2的节点都会出现决策问题）

---

点双边双参考：https://blog.csdn.net/a_forever_dream/article/details/103019013

点双连通： 对于一个无向图，不包含割点

除了比较特殊的一个点双，其他都满足，任意两点之间存在至少两条点不重复的路径

边双连通: 对于一个无向图，不包含割边

对于一个边双中的任意两个点，它们之间都有至少两条边不重复的路径。

• 点双连通：删掉一个点之后，图仍联通
• 边双连通：删掉一条边之后，图仍联通

点双形象化的理解：

https://www.cnblogs.com/cutemush/p/12686604.html

会以割点为界分割连通块，对于每个连通块标号当做一个新的点；对于割点再单独拎出来当做一个新的点

点双缩点板子：https://blog.csdn.net/qq_41661919/article/details/85482289

但是前向星（

---

真的借这个题学了下点双，板子其实还好，刚开始没理解就上就有点难改了（

注意点开两倍，点双缩点会越缩越多来着（

code:

#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int N = 2e5 + 10;
const int M = N << 2;
int head[N];
int ver[M];
int Next[M];
int tot, n, m;

void add(int x, int y) {
    
    ver[++tot] = y;
    Next[tot] = head[x];
    head[x] = tot;
}

int root;
vector<int> dcc[N];
int stackk[N];
int dfn[N], low[N];
int num = 0;//时间戳
int top;//stackk
int cnt = 0;//联通块数目
bool cut[N];//割点判断
void tarjan(int x) {
    
    dfn[x] = low[x] = ++num;
    stackk[++top] = x;
    if (x == root && head[x] == 0) {
    
        dcc[++cnt].push_back(x);//cnt联通块标号
        return;
    }
    int flag = 0;
    for (int i = head[x]; i; i = Next[i]) {
    
        int y = ver[i];
        if (!dfn[y]) {
    
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x]) {
    
                flag++;
                if (x != root || flag > 1)cut[x] = true;
                cnt++;
                int z;
                do//弹出的元素与x一起构成一个联通块(或者说割点的子树中的节点+割点?)
                {
    
                    z = stackk[top--];
                    dcc[cnt].push_back(z);
                } while (z != y);
                dcc[cnt].push_back(x);
            }
        } else low[x] = min(low[x], dfn[y]);
    }
}

int tot2 = 1;
int new_id[N];

int hc[N];
int vc[M];
int nc[M];

int du[N];

void add_c(int x, int y) {
    
    vc[++tot2] = y;
    nc[tot2] = hc[x];
    hc[x] = tot2;
}

bool vis[N];

void dfs(int x, int p) {
    
    vis[x] = 1;
    for (int i = hc[x]; i; i = nc[i]) {
    
        int to = vc[i];
        if (to == p) continue;
        if (!vis[to]) {
    
            dfs(to, x);
        }
    }
}

int main() {
    

    scanf("%d%d", &n, &m);
    tot = 1;//方便用^运算访问各边的终点
    for (int i = 1; i <= m; ++i) {
    
        int x, y;
        scanf("%d%d", &x, &y);
        if (x == y)continue;
        add(x, y);
        add(y, x);
    }
    for (int i = 1; i <= n; ++i) {
    
        if (!dfn[i])root = i, tarjan(i);
    }
    //输出割点
    /*for(int i=1;i<=n;++i) if(cut[i])printf("%d ",i);*/
    //上面求割点同时求V-DCC
    //下面输出每个联通块中的点
// for (int i = 1; i <= cnt; ++i) {
    
// for (int j = 0; j < dcc[i].size(); ++j)
// cout << i << " " << dcc[i][j] << endl;
// }

    //缩点
    tot2 = 1;
    int num2 = cnt;
    for (int i = 1; i <= n; ++i) {
    
        if (cut[i])new_id[i] = ++num2;//缩点后割点的新编号,相当于每个割点单独作为一个联通块
    }
    for (int i = 1; i <= cnt; ++i) {
    
        for (int j = 0; j < dcc[i].size(); ++j) {
    
            int x = dcc[i][j];
            if (cut[x])//一个联通块中有且只有一个割点，通过割点们把这些联通块连接起来;
            {
    
                add_c(i, new_id[x]);
                add_c(new_id[x], i);
            } else new_id[x] = i;//其余点均只属于一个联通块
        }
    }

    //输出缩点后的图中各点之间的邻接关系，再次注意^符号的使用，i从2开始，每次加2，<tot2而非<=；
    //tot2是边数
// for (int i = 2; i < tot2; i += 2) {
    
// cout << vc[i ^ 1] << " " << vc[i] << endl;
// }

    bool flag = 1;
    dfs(1, -1);
    for (int i = 1; i <= num2; ++i) {
    
        if (!vis[i]) flag = 0;
    }

    // 链的两端
    for (int i = 1; i <= num2; ++i) {
    
        for (int u = hc[i]; u; u = nc[u]) {
    
            du[i]++;
        }
    }

    // 判他是不是树
    for (int i = 2; i <= num2; ++i) {
    
        if (du[i] > 2) flag = 0;
    }

    int q;
    scanf("%d", &q);

    while (q--) {
    
        int x, y;
        scanf("%d%d", &x, &y);
        if (n == 2) {
    
            puts("YES");
            continue;
        }
        if (!flag || cut[x] || cut[y]) {
    
            puts("NO");
            continue;
        }
        if ((du[new_id[x]] == 1 && du[new_id[y]] == 1 && new_id[x] != new_id[y]) || (cnt == 1)) {
    
            puts("YES");
        } else {
    
            puts("NO");
        }
    }

    return 0;
}

G - Geometry

prob. ： 给两个凸包以及凸包的速度，问多久相撞

ideas：

闵可夫斯基和：两个欧几里得空间的点集的和

多用于探究两个或多个凸包的关系，把凸包的关系转化为向量的加减法

算法思路是将两个凸包的边极角排序（将两个有序的凸包的边极角排序，注意起点位置以及可能存在三点共线的情况，在一些题的情况下需要对闵和后的凸包再求一次凸包)

用闵和可以判断凸包是否相交：将一个凸包B按原点对称，之后与凸包A作闵和，得到的新的凸包，判断原点是否在该凸包内

---

该题可以转化为求是否存在$\vec{a}+k\vec{x}=\vec{b}+k\vec{y}$

即求$\vec{a}-\vec{b}=k(\vec{y}-\vec{x})$

$\vec{a}+(-\vec{b})=k(\vec{y}-\vec{x})$

将凸包B按原点对称之后与A作闵和，对于新的凸包枚举每条边与直线的交点算tmpk然后比较得答案

---

这样做没有什么精度问题，本来队友在写二分+二分会被边界数据卡死

卡精度的题最好不要旋转

“0会变成1e-7 然后跳1e9倍就有值了（？”