2022牛客暑期多校训练营3（ACFGJ）

题集链接；

视频题解；

A Ancestor

LCA，线段树

思路

给定两棵节点数相同的树、每个节点的点权、k个指定节点的编号，求k个节点中，除某一个节点外的其他节点在两棵树上的LCA对应点权满足A树LCA点权大于B树LCA点权的情况数；

我们发现需要对两棵树多次求LCA，考虑线段树维护LCA，即线段树节点的值为线段树节点在指定节点数组所覆盖区间内的节点在某树上的LCA值；

代码

#include <iostream>
#include <vector>

using namespace std;

const int N = 2e5 + 10;
const int D = 1e5 + 5;
int fa[N][20];
int dep[N];

vector<int> E[N];

void dfs(int u, int f = -1) {
    
   for (int i = 1; i < 20; i++) {
    
      fa[u][i] = fa[fa[u][i - 1]][i - 1];
   }
   for (auto v : E[u]) {
    
      if (v == f) continue;
      dep[v] = dep[u] + 1;
      fa[v][0] = u;
      dfs(v, u);
   }
}

int lca(int x, int y) {
    
   if(x == -1) return y;
   if(y == -1) return x;
   if (dep[x] < dep[y]) swap(x, y);
   for (int i = 19; i >= 0; i--) {
    
      if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
   }
   if (x == y) return x;
   for (int i = 19; i >= 0; i--) {
    
      if (fa[x][i] != fa[y][i]) {
    
         x = fa[x][i];
         y = fa[y][i];
      }
   }
   return fa[x][0];
}

int ks[N], wt[N];

struct SEG_tree {
    
   vector<int> lc;
   vector<pair<int,int>> Range;
   int D;

   SEG_tree(int n, int d) : D(d) {
    
      int sz = 1;
      while (sz < n) sz <<= 1;
      lc.resize(sz * 2);
      Range.resize(sz * 2);
      dfs(1 + D);
      build(1, n);
   }

   int Lson(int p) {
     return p * 2 + 1; }
   int Rson(int p) {
     return p * 2 + 2; }

   void push_up(int p) {
    
      lc[p] = lca(lc[Lson(p)], lc[Rson(p)]);
   }

   void build(int l, int r, int p = 0) {
     Range[p] = {
    l, r}; 
      if(l == r) {
    
         lc[p] = ks[l] + D;
         return;
      }
      int mid = (l + r) >> 1;
      build(l, mid, Lson(p));
      build(mid + 1, r, Rson(p));
      push_up(p);
   }

   int querry(int x ,int p = 0) {
    
      auto [l , r] = Range[p];
      if(l <= x && x <= r) {
    
         if(l == r) return -1;
         int mid = (l + r) >> 1;
         auto res = lca(querry(x, Lson(p)), querry(x, Rson(p)));
         return res;
      }
      return lc[p];
   }
};

int main() {
    
   int n, k;
   cin >> n >> k;
   for (int i = 1; i <= k; i++) {
    
      scanf("%d", &ks[i]);
   }
   for (int i = 1; i <= n; i++) {
    
      scanf("%d", &wt[i]);
   }
   for (int i = 2; i <= n; i++) {
    
      int tmp;
      scanf("%d", &tmp);
      E[tmp].push_back(i);
   }
   for (int i = 1; i <= n; i++) {
    
      scanf("%d", &wt[i + D]);
   }
   for (int i = 2; i <= n; i++) {
    
      int tmp;
      scanf("%d", &tmp);
      E[tmp+D].push_back(i+D);
   }
   SEG_tree a(k,0),b(k,D);
   // printf("*%d %d",lca(3,4),lca(3+D,4+D));
   //处理线段树
   int ans=0;
   for(int i=1;i<=k;i++)
   {
    
      // printf("%d\n",a.querry(i));
      if( wt[a.querry(i)]> wt[b.querry(i)])ans++;
   }
   cout<<ans;
}

C Concatenation

字典树，sort

思路

我们首先确定了sort排序所用的cmp函数；
正解是使用字典树来加速这个过程，只有对于两个串存在公共前缀是才进行cmp（也许吧）；
实际上并没有快多少；

代码

暴力nlogn来碾

#include <iostream>
#include <vector> 
#include <algorithm>
#include <string>

using namespace std;
int main() {
    
   int n;
   cin >> n;
   vector<string> str(n);

   for (int i = 0; i < n; i++) cin >> str[i];

   sort(str.begin(), str.end(),
        [](string& a, string& b) {
     return a + b < b + a; });

   for (int i = 0; i < n; i ++ ) cout << str[i];
   return 0;
}

F Fief

点双

思路

我们首先可以认为点双内部的点是可以随意分割的，即在一个点双内，可以使一方的点数为从零到满的任意值；

我们在此题中暂且认为割点不属于任何点双，考虑割点对点双的影响：
如果存在某割点可以将某点双割离两个问询点，则被割离的点双内部所有点一定同属于一方（割点处无法保证两方均与该点双内部连通）；

即图内不存在将某个点双从问询点所在点双割离的割点；

接下来考虑点双之间的关系：
当组成图的若干点双组成一条链时（O-O-O-O-…-O，O代表点双），并且被问询两点位于这条链的两个端点，为YES；

特殊情况包括但不限于：图不连通（n=2时不连通也为YES）、询问点为割点、出现三叉（多岔）链、全图是且仅是一个点双；

也许遇到一些问题

补题时候想到此样例问了半天，最后发现是自己题读假了

对于样例

11 16
1 2
2 3
1 3
3 4
2 4
5 4
4 6
6 7
5 6
8 6
5 8
8 9
9 11
8 10
10 11
9 10
1
1 11

即

也许会认为对于1，11是YES，因为对于五个点有1,2,3,4,5，对于六个点有1,2,3,6,7；
实际不然，题目中要求有：could he always find a list such that Antileaf and Fstqwq's fief would be always connected regardless of the result of the lottery，即要求列表是对于任意分割数量的都可行，上面的分配方式实际上改变了列表的内容；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using namespace std;
const int N = 100005;
/* 下文认为割点不在任何点双中 中心思想：图内不存在将某个点双从问询点所在点双割离的割点 显然0：若整个图不联通，（除n==2&&m==0外），或问询点为割点时，一定为NO； 显然1：当组成图的若干点双组成一条链时（O-O-O-O-...-O），并且被问询两点位于这条链的两个端点，为YES； 显然2：当组成图的仅有一个点双时（O），并且被问询两点都在此点双（废话），为YES； */
stack<int> s;       // dfs栈
vector<int> rod[N]; // 存路
int dfn[N], dc = 1; // dfs存储dfs入序，dc用于分配dfs序
int low[N];         // low存储节点下子树通过返祖边所连接的最小dfs序
vector<int> scc[N];
int inscc[N]; // 标记每个点双的入度，用来判链头
int sc = 1;   // scc存储每个双连通分量内的元素，sc分配双连通分量编号
int mk[N];    // 标记点所在点双编号
int cut[N]; // cut存储该点删去后，该点所在的连通块会变成几块，cut[i]>1的为割点

void dfs(int u, int r)
{
    
    s.push(u);
    cut[u] = (u == r) ? 0 : 1;
    low[u] = dfn[u] = dc++;
    if (u == r && rod[u].empty())
    {
    
        int now = s.top();
        s.pop();
        scc[sc].push_back(now);
        sc++;
    }
    for (int j = 0; j < rod[u].size(); j++)
    {
    
        int to = rod[u][j];
        if (!dfn[to])
        {
    
            dfs(to, r);
            low[u] = min(low[u], low[to]);
            if (low[to] >= dfn[u])
            {
    
                int now;
                do
                {
    
                    now = s.top();
                    s.pop();
                    scc[sc].push_back(now);
                } while (now != to);
                scc[sc].push_back(u);
                sc++;
                cut[u]++;
            }
        }
        else
        {
    
            low[u] = min(low[u], dfn[to]);
        }
    }
}

int main()
{
    
    int n, m, q, u, v;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
    
        scanf("%d%d", &u, &v);
        rod[u].push_back(v), rod[v].push_back(u);
    }
    int f = 1;
    dfs(1,1);
    int ysc = 0;
    for (int i = 1; i < sc; i++)
    {
    
        int ff = 1;
        for (auto x : scc[i])
        {
    
            if (cut[x] <= 1)
                mk[x] = i, ff = 0;
        }
        if (!ff)
            ysc++;
    }
    for (int i = 1; i <= n&&f; i++)
    {
    
        if(!dfn[i])f=0;
        if (cut[i] >= 2)
        {
    
            unordered_map<int, bool> mp;
            for (auto u : rod[i])
            {
    
                if (cut[u] <= 1 && !mp[mk[u]])
                {
    
                    inscc[mk[u]]++;
                    mp[mk[u]] = 1;
                }
            }
        }
    }
    int chainedge = 0;
    for (int i = 1; i < sc; i++)
    {
    
        if (inscc[i] == 1)
            chainedge++;
    }
    // for (int i = 1; i <= n; i++)
    // printf("%d ", mk[i]);
    // printf("\n%d \n", mxcut);
    // for (int i = 1; i <= n; i++)
    // printf("%d ", inscc[i]);
    // printf("\n");
    // for (int i = 1; i <= n; i++)
    // printf("%d ", cut[i]);
    // printf("\n");
    cin >> q;
    while (q--)
    {
    
        scanf("%d%d", &u, &v);
        if ((f && chainedge == ((ysc == 1) ? 0 : 2) && //有一个连通块，不存在三叉链（或更多）
             ((inscc[mk[u]] == ((ysc == 1) ? 0 : 1)) &&
              (inscc[mk[v]] == ((ysc == 1) ? 0 : 1)) && //问询两点都在链头
              ((ysc == 1) ? 1 : (mk[u] != mk[v]))) &&   //问询两点不共块
             cut[u] == 1 &&
             cut[v] == 1) ||    //问询两点不为割点
            (n == 2 && m == 0)) //特判
        {
    
            printf("YES\n");
        }
        else
            printf("NO\n");
    }
    return 0;
}

G Geometry

闵可夫斯基和

思路

给定两个凸包和各自的速度矢量，问其能否发生碰撞和发生碰撞所需的时间；

问题可以转化为求解 t 使得 $t\overrightarrow{v_1}+\vec{a}=t\overrightarrow{v_2}+\vec{b}$ ，其中 $\vec{a}\in A,\vec{b}\in B$；
变形为 $\vec{a}-\vec{b}=t(\overrightarrow{v_2}-\overrightarrow{v_1})$；

于是问题就变成了求过原点，方向与 $\overrightarrow{v_2}-\overrightarrow{v_1}$ 相同的射线 和 A与-B两凸包的闵可夫斯基和凸包的交点；

求交点时注意判断交点是否在射线方向（避免反向）

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define double long double
const double eps = 1e-8;
const double PI = acos(-1.0);
int sign(double x) // 符号函数
{
    
    if (fabs(x) < eps)
        return 0;
    if (x < 0)
        return -1;
    return 1;
}
struct Point
{
    
    double x, y;
    Point(double a = 0, double b = 0) {
     x = a, y = b; }
    Point operator+(const Point &a) const {
     return Point(x + a.x, y + a.y); }
    Point operator-(const Point &a) const {
     return Point(x - a.x, y - a.y); }
    Point operator*(const double &a) const {
     return Point(x * a, y * a); }
    Point operator/(const double &a) const {
     return Point(x / a, y / a); }
    bool operator==(const Point &a) const {
     return !sign(x - a.x) && !sign(y - a.y); }
    bool operator<(const Point &a) const {
     return (fabs(x - a.x) < eps) ? (y < a.y) : (x < a.x); }
};
struct Line
{
    
    Point a, v;
    Line(Point x = Point(), Point y = Point()) {
     a = x, v = y; }
};
struct Segm
{
    
    Point a, b;
    Segm(Point x = Point(), Point y = Point()) {
     a = x, b = y; }
};
const int dots_num = 1e5 + 5;
struct Poly
{
    
    int num;
    Point dots[dots_num];
    Poly(int x = 0) {
     num = x; }
};
double dot(Point a, Point b) {
     return a.x * b.x + a.y * b.y; }
double cross(Point a, Point b) {
     return a.x * b.y - b.x * a.y; }
double get_length(Point a) {
     return sqrt(dot(a, a)); }
Point get_line_intersection(Line m, Line n)
{
    
    Point u = m.a - n.a;
    if (sign(cross(m.v, n.v)) == 0)
        return Point(0, 0);
    double t = cross(n.v, u) / cross(m.v, n.v);
    return m.a + m.v * t;
}
Point p[100005], stk[200005];
int tk = 0;
Poly Andrew(int n)
{
    
    tk = 0;
    sort(p, p + n);
    for (int i = 0; i < n; i++)
    {
    
        if (i && p[i] == p[i - 1])
            continue;
        while (tk >= 2 && sign(cross(stk[tk - 1] - stk[tk - 2], p[i] - stk[tk - 2]) >= 0))
        {
    
            tk--;
        }
        stk[tk++] = p[i];
    }
    int hlf = tk;
    for (int i = n - 2; i >= 0; i--)
    {
    
        if (p[i] == p[i + 1])
            continue;
        while (tk >= hlf + 1 && sign(cross(stk[tk - 1] - stk[tk - 2], p[i] - stk[tk - 2]) >= 0))
        {
    
            tk--;
        }
        stk[tk++] = p[i];
    }
    Poly ans = Poly();
    for (int i = tk - 1; i; i--)
        ans.dots[ans.num++] = stk[i];
    return ans;
}

Poly Minkowski_sum(Poly &a, Poly &b)
{
    
    Poly ans = Poly();
    ans.dots[ans.num++] = a.dots[0] + b.dots[0];
    int i = 0, j = 0;
    while (i < a.num && j < b.num && ans.num < a.num + b.num)
    {
    
        if (sign(cross(a.dots[(i + 1) % a.num] - a.dots[i], b.dots[(j + 1) % b.num] - b.dots[j])) >=
            0)
        {
    
            ans.dots[ans.num] = ans.dots[ans.num - 1] + a.dots[(i + 1) % a.num] - a.dots[i];
            i++;
        }
        else
        {
    
            ans.dots[ans.num] = ans.dots[ans.num - 1] + b.dots[(j + 1) % b.num] - b.dots[j];
            j++;
        }
        ans.num++;
    }
    while (i < a.num && ans.num < a.num + b.num)
    {
    
        ans.dots[ans.num] = ans.dots[ans.num - 1] + a.dots[(i + 1) % a.num] - a.dots[i];
        i++;
        ans.num++;
    }
    while (j < b.num && ans.num < a.num + b.num)
    {
    
        ans.dots[ans.num] = ans.dots[ans.num - 1] + b.dots[(j + 1) % b.num] - b.dots[j];
        j++;
        ans.num++;
    }
    return ans;
}

bool on_segment(Point p, Segm m)
{
    
    Point u = m.a - p, v = m.b - p;
    return sign(cross(u, v)) == 0 && sign(dot(u, v)) <= 0;
}
bool point_in_polygon(Point p, Poly &m)
{
    
    if (m.num == 2)
    {
    
        return on_segment(p, Segm(m.dots[0], m.dots[1]));
    }
    for (int i = 0; i < m.num; i++)
    {
    
        if (on_segment(p, Segm(m.dots[(i + 1) % m.num], m.dots[i])))
            return 1;
        if (sign(cross(p - m.dots[i], m.dots[(i + 1) % m.num] - m.dots[i])) > 0)
            return 0;
    }
    return 1;
}
inline int read()
{
    
    int x = 0;
    bool op = 0;
    char c = getchar();
    while (!isdigit(c))
        op |= (c == '-'), c = getchar();
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return op ? -x : x;
}
int main()
{
    
    Poly a, b;
    Point v1, v2;
    int n, u, v;
    n = read();
    for (int i = 0; i < n; i++)
    {
    
        u = read(), v = read();
        p[i] = Point(u, v);
    }
    a = Andrew(n);
    n = read();
    for (int i = 0; i < n; i++)
    {
    
        u = read(), v = read();
        p[i] = Point(-u, -v);
    }
    b = Andrew(n);
    Poly ans = Minkowski_sum(a, b);
    for (int i = 0; i < ans.num; i++)
        p[i] = ans.dots[i];
    ans = Andrew(ans.num);
    scanf("%Lf%Lf%Lf%Lf", &v1.x, &v1.y, &v2.x, &v2.y);
    Line bas = Line(Point(), v2 - v1);
    double mindis = 1e22;
    if (point_in_polygon(Point(), ans))
        printf("0");
    else if (sign(get_length(bas.v)) == 0)
        printf("-1");
    else
    {
    
        for (int i = 0; i < ans.num; i++)
        {
    
            Segm tmp = Segm(ans.dots[i], ans.dots[(i + 1) % ans.num]);
            if (sign(cross(tmp.a, bas.v)) != sign(cross(tmp.b, bas.v)))
            {
    
                Point gli = get_line_intersection(bas, Line(tmp.a, tmp.b - tmp.a));
                if (sign(dot(gli, bas.v)) >= 0)
                    mindis = min(mindis, get_length(gli));
            }
            else if (!sign(cross(tmp.a, bas.v)))
            {
    
                if (sign(dot(tmp.a, bas.v)) >= 0)
                    mindis = min(mindis, get_length(tmp.a));
                if (sign(dot(tmp.b, bas.v)) >= 0)
                    mindis = min(mindis, get_length(tmp.b));
            }
        }
        if (mindis < 1e20)
            printf("%.16Lf", mindis / get_length(bas.v));
        else
            printf("-1");
    }
    return 0;
}

J Journey

迪杰斯特拉

思路

考虑将路口视为边，有向道路视为点，这样便很方便地处理了右转的判定问题；

接下来的事情就很简单了，注意建图时使用map可能导致超时；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using namespace std;
const int N = 5e5+10;

unordered_map<long long ,int > mp;

int ctmp=1;
vector<pair<int,int>>rod[N*8];

inline int gm(int a,int b)
{
    
    auto p = 1ll * a * N + b;
    if(mp[p])return mp[p];
    else return (mp[p]=ctmp++);
}


int dis[N*8];
bool vis[N*8];
void dijk(int s)
{
    
	typedef pair<int,int> pii;
	priority_queue<pii,vector<pii>,greater<pii> >que;
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	dis[s]=0;
	que.push({
    0,s});//先将s入队，不标记被访问，下面循环中再加入相邻边；
	while(!que.empty())
	{
    
		int now=que.top().second;
		que.pop();//堆顶元素在加入时已经被预更新距离了，所以.first不需要再使用
		if(vis[now])continue;
		vis[s]=1;
		for(int i=0;i<rod[now].size();i++)
		{
    
			if(dis[rod[now][i].first]>rod[now][i].second+dis[now])
			{
    //可被更新的点一定是未访问点，否则存在负权边
				dis[rod[now][i].first]=rod[now][i].second+dis[now];
				que.push({
    dis[rod[now][i].first],rod[now][i].first});
			}
		}
	}
}
int main()
{
    
    int n,c[4];
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    
        for(int j=0;j<4;j++)scanf("%d",&c[j]);
        for(int j=0;j<4;j++)
        {
    
            if(c[j]==0)continue;
            for(int k=0;k<4;k++)
            {
    
                if(c[k]==0)continue;
                if(k==(j+1)%4)rod[gm(c[j],i)].push_back({
    gm(i,c[k]),0});
                else rod[gm(c[j],i)].push_back({
    gm(i,c[k]),1});
            }
        }
    }
    pair<int,int>s,t;
    scanf("%d%d%d%d",&s.first,&s.second,&t.first,&t.second);
    dijk(gm(s.first,s.second));
    if(dis[gm(t.first,t.second)]==dis[0])printf("-1");
    else printf("%d",dis[gm(t.first,t.second)]);
    return 0;
}