526互联

2024.1.12做题纪要

发布时间 2024-01-12 21:29:14作者: 觉清风

2-SAT

考场的时候直接不考试去学了，板子还挺简单的。

SOV 
#include <bits/stdc++.h>

int N, M;
int cnt, head[2100000], next[4100000], to[4100000];

void AddEdge(int u, int v) {
    ++ cnt;
    next[cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
}

bool visit[2100000];
int dfn[2100000], low[2100000], total;
std::stack<int> stack;
int color[2100000], colSum;

void tarjan(int now) {
    dfn[now] = low[now] = ++ total;
    stack.emplace(now);
    visit[now] = true;
    for (int i = head[now]; i; i = next[i]) {
        if (!dfn[to[i]]) {
            tarjan(to[i]);
            low[now] = std::min(low[now], low[to[i]]);
        }
        else {
            if (visit[to[i]]) {
                low[now] = std::min(low[now], dfn[to[i]]);
            }
        }
    }
    if (low[now] == dfn[now]) {
        ++ colSum;
        int temp = stack.top();
        while (low[temp] != dfn[temp]) {
            stack.pop();
            color[temp] = colSum;
            visit[temp] = false;
            temp = stack.top();
        }
        color[temp] = colSum;
        visit[temp] = false;
        stack.pop();
    }
}

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

    std::cin >> N >> M;
    for (int i = 1, a, va, b, vb; i <= M; ++ i) {
        std::cin >> a >> va >> b >> vb;
        if (va && vb) {
            AddEdge(a + N, b);
            AddEdge(b + N, a);
        }
        if (!va && vb) {
            AddEdge(a, b);
            AddEdge(b + N, a + N);
        }
        if (va && !vb) {
            AddEdge(a + N, b + N);
            AddEdge(b, a);
        }
        if (!va && !vb) {
            AddEdge(a, b + N);
            AddEdge(b, a + N);
        }
    }
    for (int i = 1; i <= N * 2; ++ i)
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= N; ++ i) {
        if (color[i] == color[i + N]) {
            std::cout << "IMPOSSIBLE\n";
            return 0;
        }
    }
    std::cout << "POSSIBLE\n";
    for (int i = 1; i <= N; ++ i)
        std::cout << (color[i] < color[i + N]) << ' ';
    std::cout << '\n';
    return 0;
}

小幸运

题目背景好评

原来你是我最想留住的幸运，原来我们和爱情曾经靠得那么近
那为我对抗世界的决定，那陪我淋的雨
一幕幕都是你 一尘不染的真心，与你相遇 好幸运
可我已失去为你泪流满面的权利，但愿在我看不到的天际
你张开了双翼，遇见你的注定 她会有多幸运

题目。。。一言难尽。虽然是原题，但是挺逆天。

用 \(2-SAT\) 还有叉积判断直线相交。

首先对于每个点我们可以分成左上，右上，左下，右下，四个部分。对于每个部分都开一个 \(true\) 和 \(false\) 点。由于我们必须选对角线的一个，也就是说在左上和右下中必须选一个，右上和左下中必须选一个，所以将每个部分的 \(true\) 和对角线的 \(false\) 连接。

具体来说二分我们的长度，然后 \(O(N^2)\) 判断每两个点间的四个部分那些部分冲突（有交），将其连边。值得注意的是判断每个部分是否在范围内，若不在范围内就将该部分的 \(true\) 连向 \(false\) 就行。具体为什么我太菜了不知道，蒙出来的。

TG 
#include <bits/stdc++.h>

typedef long long ll;

int N, W, H;
int cnt, head[1000000], next[1000000], to[1000000];

void AddEdge(int u, int v) {
    ++ cnt;
    next[cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
}

void clear() {
    cnt = 0;
    for (int i = 1; i <= N * 8 + 100; ++ i)
        head[i] = 0;
}

bool visit[1000000], ttt;
int dfn[1000000], low[1000000], total;
std::stack<int> stack;
int color[1000000], colSum;

void tarjan(int now) {
    dfn[now] = low[now] = ++ total;
    stack.emplace(now);
    visit[now] = true;
    for (int i = head[now]; i; i = next[i]) {
        if (!dfn[to[i]]) {
            tarjan(to[i]);
            low[now] = std::min(low[now], low[to[i]]);
        }
        else {
            if (visit[to[i]]) {
                ttt = true;
                low[now] = std::min(low[now], dfn[to[i]]);
            }
        }
    }
    if (low[now] == dfn[now]) {
        ++ colSum;
        int temp = stack.top();
        while (low[temp] != dfn[temp]) {
            stack.pop();
            color[temp] = colSum;
            visit[temp] = false;
            temp = stack.top();
        }
        color[temp] = colSum;
        visit[temp] = false;
        stack.pop();
    }
}

class Point {
public:
    double x, y;
}pos[70];

class Triangle {
public:
    Point point[4];
};

int x[5], y[5];
int id[70][5][2];

int tot;

Triangle Transfer(Point vertex, int direction, double len) {
    Triangle result;
    result.point[1] = vertex;
    result.point[2] = {vertex.x + x[direction] * len, vertex.y};
    result.point[3] = {vertex.x, vertex.y + y[direction] * len};
    return result;
}

double CrossProduct(const Point &vector1, const Point &vector2) {
    return (vector1.x * vector2.y - vector1.y * vector2.x);
}

bool tyui = false;

bool cross(const Point &x1, const Point &y1, const Point &x2, const Point &y2) {
    double temp1, temp2;
    Point vector = {y2.x - x2.x, y2.y - x2.y}, temp;

    temp = {x1.x - x2.x, x1.y - x2.y};
    temp1 = CrossProduct(vector, temp);
    temp = {y1.x - x2.x, y1.y - x2.y};
    temp2 = CrossProduct(vector, temp);

    if (temp1 <= 0 && temp2 <= 0)
        return false;
    if (temp1 >= 0 && temp2 >= 0)
        return false;
    
    vector = {y1.x - x1.x, y1.y - x1.y};
    temp = {x2.x - x1.x, x2.y - x1.y};
    temp1 = CrossProduct(vector, temp);
    temp = {y2.x - x1.x, y2.y - x1.y};
    temp2 = CrossProduct(vector, temp);
    
    if (temp1 <= 0 && temp2 <= 0)
        return false;
    if (temp1 >= 0 && temp2 >= 0)
        return false;
    return true;
}

bool Overlap(const Triangle &a, const Triangle &b) {
    for (int i1 = 1; i1 <= 3; ++ i1) {
        for (int i2 = i1 + 1; i2 <= 3; ++ i2) {

            for (int j1 = 1; j1 <= 3; ++ j1) {
                for (int j2 = j1 + 1; j2 <= 3; ++ j2) {
                    if (cross(a.point[i1], a.point[i2], b.point[j1], b.point[j2])) {
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

bool checkRange(Point a) {
    if (a.x < 0 || a.x > W || a.y < 0 || a.y > H)
        return false;
    return true;
}

bool check(double len) {
    len /= 1e7;
    ttt = false;
    clear();
    for (int i = 1; i <= tot; ++ i)
        dfn[i] = low[i] = color[i] = visit[i] = 0;
    for (int i = 1; i <= N; ++ i) {
        for (int j = 1; j <= 2; ++ j) {
            AddEdge(id[i][j][false], id[i][j + 2][true]);
            AddEdge(id[i][j + 2][false], id[i][j][true]);
        }
        for (int k1 = 1; k1 <= 4; ++ k1) {
            Triangle now = Transfer(pos[i], k1, len);

            bool flag1 = false;
            for (int o = 1; o <= 3; ++ o)
                if (!checkRange(now.point[o]))
                    flag1 = true;
            if (flag1) {
                AddEdge(id[i][k1][true], id[i][k1][false]);
            }

            for (int j = i + 1; j <= N; ++ j) {
                for (int k2 = 1; k2 <= 4; ++ k2) {
                    Triangle temp = Transfer(pos[j], k2, len);

                    if (Overlap(now, temp)) {
                        AddEdge(id[i][k1][true], id[j][k2][false]);
                        AddEdge(id[j][k2][true], id[i][k1][false]);
                    }
                }
            }
        }
    }

    for (int i = 1; i <= tot; ++ i)
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= N; ++ i) {
        for (int j = 1; j <= 4; ++ j) {
            if (color[id[i][j][false]] == color[id[i][j][true]])
                return false;
        }
    }
    return true;
}

int main() {
    freopen("lucky.in", "r", stdin);
    freopen("lucky.out", "w", stdout);

    x[1] = x[4] = -1;
    x[2] = x[3] = 1;
    y[1] = y[2] = 1;
    y[3] = y[4] = -1;
    std::cin >> N >> W >> H;
    for (int i = 1; i <= N; ++ i)
        std::cin >> pos[i].x;
    for (int i = 1; i <= N; ++ i)
        std::cin >> pos[i].y;
    for (int i = 1; i <= N; ++ i) {
        for (int j = 1; j <= 4; ++ j) {
            id[i][j][false] = ++ tot;
            id[i][j][true] = ++ tot;
        }
    }
    ll l = 1, r = 1e9 * 1e7, mid, answer = 0;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (check(mid)) {
            answer = mid;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
    printf("%.0lf", 1.0 * answer / 1e7 * 2);
    return 0;
}
/*
4 100 100
5 5 10 10
0 10 5 5
*/

P4735 最大异或和

可持久化 \(trie\) 板子题。

我们每次加入的时候加前缀和，每次查询在范围内的与 \(pre_N \bigotimes x\) 贪心的在 \(trie\) 树上跑就行了。

注意范围是 \(l-1\) 到 \(r-1\)，因为是前缀和，注意若 \(l-1=0\) 则答案于 \(pre_N \bigotimes x\) 取个 \(max\)。

GER 
#include <bits/stdc++.h>
#define mian main

int N, M;
char opt;
int pre[610000], sum;

class Trie {
public:
    int root[610000], tot;
    int child[610000 * 40][2], max[610000 * 40];
    void Insert(int rank, int num) {
        root[rank] = ++ tot;
        int now = root[rank];
        max[now] = rank;
        int last = root[rank - 1];
        
        for (int i = 30; i >= 0; -- i) {
            child[now][0] = child[last][0];
            child[now][1] = child[last][1];
            int ch = ((num >> i) & 1);
            child[now][ch] = ++ tot;
            now = child[now][ch];
            last = child[last][ch];
            max[now] = rank;
        }
    }

    int Ask(int l, int r, int num) {
        int result = 0;
        int now = root[r];
        for (int i = 30; i >= 0; -- i) {
            int ch = ((num >> i) & 1);
            int to = child[now][ch ^ 1];
            if (to && max[to] >= l) {
                result += ((1 & (ch ^ 1)) << i);
                now = to;
            }
            else {
                result += ((1 & ch) << i);
                now = child[now][ch];
            }
        }
        return result;
    }
}trie;

int mian() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> N >> M;
    for (int i = 1, x; i <= N; ++ i) {
        std::cin >> x;
        ++ sum;
        pre[sum] = pre[sum - 1] ^ x;
        trie.Insert(sum, pre[sum]);
    }
    for (int i = 1, l, r, x; i <= M; ++ i) {
        std::cin >> opt;
        while (opt != 'A' && opt != 'Q')
            std::cin >> opt;
        if (opt == 'A') {
            std::cin >> x;
            sum ++;
            pre[sum] = pre[sum - 1] ^ x;
            trie.Insert(sum, pre[sum]);
        }   
        else {
            std::cin >> l >> r >> x;
            int answer = trie.Ask(l - 1, r - 1, pre[sum] ^ x) ^ pre[sum] ^ x;
            if (l == 1)
                answer = std::max(answer, pre[sum] ^ x);
            std::cout << answer << '\n';
        }
    }
    return 0;
}