「杂题集」- 2019年10月16日

挑战

最后发现就是分块大暴力,要是有更有意思的解法就好了(不过这个信息本来就没有优秀的合并方式,或者用一种二位在线偏序结构倒是可以解决这个问题)。

// challenge.cpp
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 1e5 + 200;
const unsigned MAGIC_NUM = 4294967295u;

ll ai[MAX_N], wi[MAX_N], n, q, block_siz, block_tot, lft[MAX_N];
pair<ll, int> tmp[MAX_N];
ll pre[MAX_N], tree[MAX_N];

int lowbit(int x) { return x & (-x); }

void update(int x, ll d)
{
    for (; x <= n; x += lowbit(x))
        tree[x] += d;
}

ll query(int x)
{
    ll ans = 0;
    for (; x; x -= lowbit(x))
        ans += tree[x];
    return ans;
}

unsigned xnor(unsigned a, unsigned b) { return ~((a & MAGIC_NUM) ^ (b & MAGIC_NUM)); }

void rebuild(int id)
{
    for (int i = lft[id]; i <= lft[id + 1] - 1; i++)
        tmp[i] = make_pair(wi[i], i);
    sort(tmp + lft[id], tmp + lft[id + 1]);
    pre[lft[id]] = wi[tmp[lft[id]].second] * ai[tmp[lft[id]].second];
    for (int i = lft[id] + 1; i <= lft[id + 1] - 1; i++)
        pre[i] = pre[i - 1] + wi[tmp[i].second] * ai[tmp[i].second];
}

int main()
{
    scanf("%lld%lld", &n, &q);
    block_siz = sqrt(n), block_tot = (n + block_siz - 1) / block_siz;
    lft[1] = 1, lft[block_tot + 1] = n + 1;
    for (int i = 2; i <= block_tot; i++)
        lft[i] = lft[i - 1] + block_siz;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &ai[i]), update(i, ai[i]);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &wi[i]);
    for (int i = 1; i <= block_tot; i++)
        rebuild(i);
    while (q--)
    {
        ll op, x, y, z;
        scanf("%lld%lld%lld", &op, &x, &y);
        if (op == 1)
        {
            scanf("%lld", &z);
            unsigned ans = 0, pans = query(y) - query(x - 1);
            int xid = (x + block_siz - 1) / block_siz, yid = (y + block_siz - 1) / block_siz;
            if (xid != yid)
            {
                for (int i = xid + 1; i <= yid - 1; i++)
                {
                    int pos = lower_bound(tmp + lft[i], tmp + lft[i + 1], make_pair(z + 1, 0)) - tmp - 1;
                    ans += pos >= lft[i] ? pre[pos] : 0;
                }
                for (int i = x; i <= lft[xid + 1] - 1; i++)
                    if (wi[i] <= z)
                        ans += wi[i] * ai[i];
                for (int i = lft[yid]; i <= y; i++)
                    if (wi[i] <= z)
                        ans += wi[i] * ai[i];
            }
            else
                for (int i = x; i <= y; i++)
                    if (wi[i] <= z)
                        ans += wi[i] * ai[i];
            printf("%u\n", xnor(ans, pans));
        }
        else if (op == 2)
        {
            update(x, -ai[x]), ai[x] = y;
            rebuild((x + block_siz - 1) / block_siz);
            update(x, ai[x]);
        }
        else
        {
            wi[x] = y;
            rebuild((x + block_siz - 1) / block_siz);
        }
    }
    return 0;
}

CF9E

真的暴力,本来以为是\(O(n^2 \log n)\)的大暴力,忘记了 BFS 可以做到更优(因为队列中的距离单调)。

@@ -0,0 +1,82 @@
// CF59E.cpp
#include <bits/stdc++.h>
#define pr pair<int, int>

using namespace std;

const int MAX_N = 3010, MAX_M = 20202;

int head[MAX_N], current, n, m, k;
int upward[MAX_N][MAX_N], dist[MAX_N][MAX_N], tmp[MAX_N];
vector<int> vecs[MAX_N][MAX_N];

struct edge
{
    int to, nxt;
} edges[MAX_M << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

bool check(int a, int b, int c)
{
    for (int i = 0, siz = vecs[a][b].size(); i < siz; i++)
        if (vecs[a][b][i] == c)
            return false;
    return true;
}

void writeAns(int pre)
{
    printf("%d\n1 ", dist[pre][n]);
    int pt = n, tot = 0;
    int fat = n;
    /*
    while (pt != 1)
    {
        tmp[++tot] = pt;
        int tp = pre, pre = upward[pre][pt], pt = tp;
    }
    */
    while (fat != 1)
    {
        tmp[++tot] = fat;
        int tp = pre;
        pre = upward[pre][fat];
        fat = tp;
    }
    for (int i = tot; i >= 1; i--)
        printf("%d ", tmp[i]);
}

void bfs()
{
    queue<pr> q;
    q.push(make_pair(0, 1));
    while (!q.empty())
    {
        int pre = q.front().first, u = q.front().second;
        q.pop();
        if (u == n)
            writeAns(pre), exit(0);
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (!dist[u][edges[i].to] && check(pre, u, edges[i].to))
                upward[u][edges[i].to] = pre, dist[u][edges[i].to] = dist[pre][u] + 1, q.push(make_pair(u, edges[i].to));
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1, u, v; i <= m; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    for (int i = 1, x, y, z; i <= k; i++)
        scanf("%d%d%d", &x, &y, &z), vecs[x][y].push_back(z);
    bfs();
    puts("-1");
    return 0;
}

CF1244D

刚开始觉得挺复杂,后面发现多数情况都可以被判作无解:除了一条链的情况,其他都可以被认为是无解的,这个很容易证明。所以,搞 6 次就可以拿到解。

// CF1244D.cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAX_N = 1e5 + 200;

int head[MAX_N], current, n, color[4][MAX_N], dp[MAX_N], deg[MAX_N], answer[MAX_N];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void dfs(int u, int fa, int A, int B)
{
    dp[u] = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
        {
            dfs(edges[i].to, u, B, A ^ B);
            dp[u] += dp[edges[i].to];
        }
    dp[u] += color[A ^ B][u];
}

void getAns(int u, int fa, int A, int B)
{
    answer[u] = A ^ B;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            getAns(edges[i].to, u, B, A ^ B);
}

signed main()
{
    memset(head, -1, sizeof(head));
    scanf("%lld", &n);
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= n; j++)
            scanf("%lld", &color[i][j]);
    for (int i = 1, u, v; i < n; i++)
        scanf("%lld%lld", &u, &v), deg[u]++, deg[v]++, addpath(u, v), addpath(v, u);
    int pt = 0;
    bool flag = false;
    for (int i = 1; i <= n; i++)
        flag |= deg[i] > 2, pt = (deg[i] == 1 ? i : pt);
    if (flag)
        puts("-1"), exit(0);
    int ans = 1e18, oA, oB;
    for (int A = 1; A <= 3; A++)
        for (int B = 1; B <= 3; B++)
            if (A != B)
            {
                dfs(pt, 0, A, B);
                if (dp[pt] < ans)
                    oA = A, oB = B, ans = dp[pt];
            }
    getAns(pt, 0, oA, oB);
    printf("%lld\n", ans);
    for (int i = 1; i <= n; i++)
        printf("%lld ", answer[i]);
    return 0;
}

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注