2024省选联测10

A. 小幸运

题目描述

给出平面上 \(n\) 个点的坐标，以及整数 \(W，H\)。以每个点为底边中点构造底边长度相等且底边与一坐标轴平行的等腰直角三角形，满足三角形在 \((0,0),(W,0),(W,H),(0,H)\) 四点构成的矩形内部且三角形内部区域互不重叠。求每个三角形底边长度的最大值。

把所有坐标扩大两倍后答案只可能是整数。二分答案。每个点拆成 \(4\) 个小三角形，需要选择两个相邻的三角形。判断这 \(4n\) 个三角形是否相交，做 2-SAT。

如果两个三角形有边相交，那么这两个三角形相交。

#define id(x, y) x + y * n
#define fid(x, y) x + y * n + 4 * n

/*
t(): 是否在边界内。
f(): 是否相交
*/

bool check(int d)
{
    tot = top = cnt = pos = 0;
    for(int i = 1; i <= 8 * n; ++ i) dfn[i] = low[i] = head[i] = 0;

    for(int i = 1; i <= n; ++ i)
    {
        add(id(i, 0), fid(i, 3)); add(fid(i, 0), id(i, 3));
        add(id(i, 3), fid(i, 0)); add(fid(i, 3), id(i, 0));
        add(id(i, 1), fid(i, 2)); add(fid(i, 1), id(i, 2));
        add(id(i, 2), fid(i, 1)); add(fid(i, 2), id(i, 1));
        for(int j = 0; j <= 3; ++ j) if(!t(i, j, d)) add(id(i, j), fid(i, j));
    }

    for(int i = 1; i < n; ++ i)
        for(int a = 0; a <= 3; ++ a)
            for(int j = i + 1; j <= n; ++ j)
                for(int b = 0; b <= 3; ++ b)
                    if(f(i, a, j, b, d)) add(id(i, a), fid(j, b)), add(id(j, b), fid(i, a));
    
    for(int i = 1; i <= n * 8; ++ i) if(!dfn[i]) tarjan(i);
    for(int i = 1; i <= n * 4; ++ i) if(sd[i] == sd[i + n * 4]) return 0;
    return 1;
}

B. 山河入梦来

题目描述

给定一个 \(n\times n\) 的矩阵，第 \(i\) 行的第 \(L_i\) 到 \(R_i\) 列为 \(1\)，其余为 \(0\)。求行列式。\(n\le 10^5\)

求行列式可以转换成上三角矩阵。

对于 \(L_i\) 相同的一些值，我们会保留 \(R_i\) 最小的行。使用可并堆维护。

void work()
{
    scanf("%d", &n); ans = 1;
    for(int i = 1; i <= n; ++ i) rt[i] = 0, p[i] = r[i] = i;

    for(int i = 1, l, r; i <= n; ++ i)
        scanf("%d%d", &l, &r), t[i] = {r, 1, 0, 0}, rt[l] = merge(rt[l], i);

    // p[i] 右端点为 i 的行数
    // r[i] 第 i 行的右端点
    for(int i = 1; i <= n; ++ i)
    {
        if(!rt[i]) {ans = 0; break;}
        
        int x = rt[i], w = t[rt[i]].x, y;
        if(p[x] != i)
            p[y = r[i]] = p[x], r[p[x] = i] = x, r[p[y]] = y, ans *= -1;
        rt[i] = merge(t[rt[i]].ls, t[rt[i]].rs);
        if(rt[i] && t[rt[i]].x == w) {ans = 0; break;}
        rt[w + 1] = merge(rt[w + 1], rt[i]);
    }

    if(ans == 0) printf("tie\n");
    if(ans > 0) printf("pp\n");
    if(ans < 0) printf("xx\n");
}

C. 遇见

放假了，先咕。