首页 > 其他分享 >2024.1.7做题纪要

2024.1.7做题纪要

时间：2024-01-13 09:56:07浏览次数：30  
标签：std 2024.1 int max ll 做题 now root 纪要

P4093 [HEOI2016/TJOI2016] 序列

不会写，褐的题解。

设 \(dp_i\) 表示以 \(i\) 结尾的最长子序列，维护就行了。

教员 
#include <bits/stdc++.h>

int N, M;
int number[110000], min[110000], max[110000];

class Binary_Indexed_Tree {
    #define lowbit(x) (x & (-x))

public:
    int num[110000];

    Binary_Indexed_Tree() {
        for (int i = 1; i <= 100000; ++ i)
            num[i] = -1e9;
    }

    void Add(int position, int val) {
        while (position <= 1e5) {
            num[position] = std::max(num[position], val);
            position += lowbit(position);
        }
    }

    int Query(int position) {
        int result = -1e9;

        while (position) {
            result = std::max(result, num[position]);
            position -= lowbit(position);
        }
        return result;
    }

    void clear(int position) {
        while (position <= 1e5) {
            num[position] = -1e9;
            position += lowbit(position);
        }
    }
}tree;

int dp[110000], p[110000];

bool cmp1(int &i, int &j) {
    return max[i] < max[j];
}

bool cmp2(int &i, int &j) {
    return number[i] < number[j];
}

void CDQ(int l, int r) {
    if (l == r) {
        dp[l] = std::max(dp[l], 1);
        return;
    }
    int mid = (l + r) >> 1;
    CDQ(l, mid);
    for (int i = l; i <= r; ++ i)
        p[i] = i;
    std::sort(p + l, p + mid + 1, cmp1);
    std::sort(p + mid + 1, p + r + 1, cmp2);

	for (int i = l, j = mid + 1; j <= r; ++j) {
		while (i <= mid && max[p[i]] <= number[p[j]]) {
			tree.Add(number[p[i]], dp[p[i]]);
			++i;
		}
		dp[p[j]] = std::max(dp[p[j]], tree.Query(min[p[j]]) + 1);
	}
    for (int i = l; i <= mid; ++ i)
        tree.clear(number[i]);
    CDQ(mid + 1, r);
}

int answer;

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

    std::cin >> N >> M;
    for (int i = 1; i <= N; ++ i) {
        std::cin >> number[i];
        max[i] = min[i] = number[i];
    }
    for (int i = 1, x, y; i <= M; ++ i) {
        std::cin >> x >> y;
        min[x] = std::min(min[x], y);
        max[x] = std::max(max[x], y);
    }

    CDQ(1, N);

    for (int i = 1; i <= N; ++ i)
        answer = std::max(answer, dp[i]);
    std::cout << answer << '\n';

    return 0;
}
/*

*/

P3345 [ZJOI2015] 幻想乡战略游戏

毒瘤题。

看见度数小于 \(20\)，直接跑就行了，每次跑分治重心就行。

小胡子 
#include <bits/stdc++.h>

typedef long long ll;

ll N, Q;
bool visit[210000];
ll cnt = 1, head[210000], next[210000], to[210000], value[210000];
ll size[210000], root, max[210000], S;

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

ll fa[110000];
ll len[110000];

void GetRoot(ll now, ll fat) {
    size[now] = 1;
    max[now] = 0;

    for (ll i = head[now]; i; i = next[i]) {
        if (visit[to[i]] || fat == to[i])
            continue;
        GetRoot(to[i], now);
        size[now] += size[to[i]];
        max[now] = std::max(max[now], size[to[i]]);
    }
    max[now] = std::max(max[now], S - size[now]);
    if (max[now] < max[root])
        root = now;
}

std::unordered_map<ll, ll> part[110000];

ll min[510000][20];
ll dfn[510000], fat[510000], tot, deep[510000];
ll lg[510000];

void Dfs(ll now, ll f) {
	deep[now] = deep[f] + 1;
	fat[now] = f;
	dfn[now] = ++ tot;
	min[tot][0] = now;
	for (ll i = head[now]; i != 0; i = next[i]) {
		if (to[i] == f)
			continue;
        len[to[i]] = len[now] + value[i];
		Dfs(to[i], now);
	}
	return;
}

ll Min(ll l, ll r) {
	if (deep[l] < deep[r])
		return l;
	return r;
}

void Pretreatment() {
	Dfs(1, 1);
	lg[1] = 0;
    for (ll i = 2; i <= N; ++ i)
		lg[i] = lg[i >> 1] + 1;
	for (ll i = N; i >= 1; -- i) {
		for (ll j = 1; i + (1 << j) - 1 <= N; ++ j) {
			min[i][j] = Min(min[i][j - 1], min[i + (1 << (j - 1))][j - 1]);
		}
	}
}

ll GetLca(ll u, ll v) {
    if (u == v)
        return u;
    
    u = dfn[u], v = dfn[v];
    if (u > v) 
        std::swap(u, v);
    u ++;
    
    ll len = lg[v - u + 1];
    ll answer = Min(min[u][len], min[v - (1 << len) + 1][len]);
    return fat[answer];  
}

ll GetDis(ll x, ll y) {
    if (x == 0 || y == 0)
        return 0;
    ll lca = GetLca(x, y);
    return len[x] + len[y] - 2 * len[lca];
}

ll sum[110000];
ll ans[110000], fuck[110000];

ll GetSum(ll now) {
    ll result = ans[now];
    for (ll i = now; fa[i]; i = fa[i]) {
        result += ans[fa[i]] - fuck[i] + GetDis(now, fa[i]) * (sum[fa[i]] - sum[i]);
    }
    return result;
}

ll Root;

ll GetAnswer() {
    ll now = Root, last = Root;
    ll has;
    bool flag = false;
    while (flag == false) {
        flag = true;
        has = GetSum(now);
        for (ll i = head[now]; i; i = next[i]) {
            ll temp = GetSum(to[i]);
            if (has > temp) {
                flag = false;
                has = temp;
                now = to[i];
            }
        }
        now = part[last][now];
        last = now;
    }
    return has;
}

void Solve(ll now) {
    visit[now] = true;
    part[now][now] = now;
    for (ll i = head[now]; i; i = next[i]) {
        if (visit[to[i]])
            continue;
        S = size[to[i]];
        root = 0;
        GetRoot(to[i], now);
        part[now][to[i]] = root;
        fa[root] = now;
        Solve(root);
    }
}

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

    std::cin >> N >> Q;
    for (ll i = 1, u, v, c; i <= N - 1; ++ i) {
        std::cin >> u >> v >> c;
        AddEdge(u, v, c);
        AddEdge(v, u, c);
    }
    Pretreatment();
    root = 0;
    max[0] = N + 1;
    S = N;
    GetRoot(1, 0);
    Root = root;
    Solve(root);
    for (ll i = 1, u, e; i <= Q; ++ i) {
        std::cin >> u >> e;
        for (ll now = u; now; now = fa[now]) {
            sum[now] += e;
            ans[now] += GetDis(u, now) * e;
            if (fa[now])
                fuck[now] += GetDis(u, fa[now]) * e;
        }
        std::cout << GetAnswer() << '\n';
    }
}

P7409 SvT

不会虚树，那么直接写 \(SA\) 就好了。

\(SA\) 的版本是很好写的。

大胡子 


#include <bits/stdc++.h>

const int MAXN = 5e5 + 1000;

int N, M;
int num[3100000];
char ch[MAXN];

class Suffix_Array {
public:
    int barrel[MAXN], temp[MAXN];
    int SA[MAXN], rank[MAXN], height[MAXN];

    void SuffixArray() {
        int m = 26, n = N;
        for (int i = 1; i <= m; ++ i)
            barrel[i] = 0;
        for (int i = 1; i <= n; ++ i)
            barrel[rank[i] = ch[i] - 'a' + 1] ++;
        for (int i = 2; i <= m; ++ i)
            barrel[i] += barrel[i - 1];
        for (int i = n; i >= 1; -- i)
            SA[barrel[rank[i]] --] = i;

        for (int w = 1, tot = 0; w <= n; m = tot, tot = 0, w <<= 1) {
            for (int i = 1; i <= n; ++ i)
                if (i + w > n)
                    temp[++ tot] = i;
            for (int i = 1; i <= n; ++ i)
                if (SA[i] > w)
                    temp[++ tot] = SA[i] - w;

            for (int i = 1; i <= m; ++ i)
                barrel[i] = 0;
            for (int i = 1; i <= n; ++ i)
                barrel[rank[temp[i]]] ++;
            for (int i = 2; i <= m; ++ i)
                barrel[i] += barrel[i - 1];
            for (int i = n; i >= 1; -- i)
                SA[barrel[rank[temp[i]]] --] = temp[i];

            tot = 0;
            std::swap(temp, rank);
            for (int i = 1; i <= n; ++ i)
                rank[SA[i]] = (temp[SA[i]] == temp[SA[i - 1]] && temp[SA[i] + w] == temp[SA[i - 1] + w]) ? tot : ++ tot;
            if (tot == n)
                return;
        }
    }

    void GetHeight() {
        int n = N;
        for (int i = 1, k = 0; i <= n; ++ i) {
            if (rank[i] == 1)
                continue;
            if (k)
                k --;
            while (ch[i + k] == ch[SA[rank[i] - 1] + k])
                k ++;
            height[rank[i]] = k;
        }
    }
}SA;

namespace ST {
    int lg[MAXN];
    int ST[MAXN][20];

    void Pretreatment() {
        lg[1] = 0;
        for (int i = 1; i <= N; ++ i) {
            if (i >= 2)
                lg[i] = lg[i >> 1] + 1;
            ST[i][0] = SA.height[i];
        }
        for (int i = N; i >= 1; -- i) {
            for (int j = 1; i + (1 << j) - 1 <= N; ++ j) {
                ST[i][j] = std::min(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    int GetAnswer(int l, int r) {
        if (l > r)
            return 0;
        int len = lg[r - l + 1];
        return std::min(ST[l][len], ST[r - (1 << len) + 1][len]);
    }
}

long long answer;

class Disjoint {
public:
    int fat[3100000];
    int size[3100000];

    void Pretreatment(int n) {
        for (int i = 1; i <= n; ++ i) {
            fat[i] = i;
            size[i] = 1;
        }
    }

    int Find(int x) {
        if (fat[x] != x)
            x = Find(fat[x]);
        return fat[x];
    }

    void Union(int x, int y, int val) {
        if (x == y)
            return;
        x = Find(x);
        y = Find(y);
        if (x != y) {
            fat[x] = y;
            answer += 1ll * size[x] * size[y] * val;
            size[y] += size[x];
        }
    }
}set;

class Sort {
public:
    int x, y, val;
}ask[MAXN * 6];

bool cmp1(const int &a, const int &b) {
    return SA.rank[a] < SA.rank[b];
}

bool cmp2(const Sort &a, const Sort &b) {
    return a.val > b.val;
}

std::map<int, int> map;

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

    std::cin >> N >> M;
    std::cin >> (ch + 1);
    N = strlen(ch + 1);
    SA.SuffixArray();
    SA.GetHeight();
    ST::Pretreatment();
    for (int i = 1, n; i <= M; ++ i) {
        std::cin >> n;
        set.Pretreatment(n);
        int cnt = 0;
        map.clear();
        for (int j = 1, x; j <= n; ++ j)  {
            std::cin >> x;
            if (!map[x])
                num[++ cnt] = x;
            map[x] ++;
        }
        std::sort(num + 1, num + 1 + cnt, cmp1);
        for (int j = 1; j <= cnt - 1; ++ j) {
            int left = num[j];
            int right = num[j + 1];
            ask[j] = {j, j + 1, ST::GetAnswer(SA.rank[left] + 1, SA.rank[right])};
        }
        std::sort(ask + 1, ask + 1 + cnt - 1, cmp2);
        answer = 0;
        for (int j = 1; j <= cnt - 1; ++ j) {
            set.Union(ask[j].x, ask[j].y, ask[j].val);
        }
        std::cout << answer << '\n';
    }
    return 0;
}

标签：std,2024.1,int,max,ll,做题,now,root,纪要
From： https://www.cnblogs.com/jueqingfeng/p/17950105

相关文章

  • 2024.1 做题记录
    P2423[HEOI2012]朋友圈考虑\(a\oplusb\bmod2=1\)的限制实际上转化为不同左侧点最多选择两个，因为奇偶性需要不同。暴力枚举左侧的点集，考虑B侧的点，首先需要跟左侧点集任意有边，之后内部还需要是完全图。B侧选定点的最大团这个东西是不好做的，但是我们可以借助边的性质......
  • 2024.1.12 闲话
    第一次写闲话，写得不好请见谅。最近总算是从一个深渊中脱离出来了。我意识到，现在自己无论是喜欢些什么，还是想要些什么，一些并不是现在所必需，也并不是现在该去关注的东西本就不应该占据我太多的时间。有句话说，其实一个人需要的东西很少，但是想要的东西很多。我觉得这话能够解释许许......
  • 2024.1.12做题纪要
    2-SAT考场的时候直接不考试去学了，板子还挺简单的。SOV#include<bits/stdc++.h>intN,M;intcnt,head[2100000],next[4100000],to[4100000];voidAddEdge(intu,intv){++cnt;next[cnt]=head[u];head[u]=cnt;to[cnt]=v;}boolvisi......
  • 2024.1.12-学习进度笔记
    今天，我尝试安装了git并尝试安装了PaddleOCR。 参考：https://blog.csdn.net/mukes/article/details/115693833参考：https://gitee.com/paddlepaddle/PaddleOCR/blob/release/2.6/doc/doc_ch/quickstart.md参考：https://gitee.com/paddlepaddle/PaddleOCR/blob/release/2.6/doc/do......
  • 南外集训 2024.1.8 T3
    题意给定一个序列\(a\)，将之划分为两个子序列，使得两个序列前缀最大值的和之和最小。\(1\len\le5\times10^5,1\lea_i\le10^9\)做法首先DP很容易做到平方：考虑前\(i\)个数，其中一个子序列当前的最大值当然是前\(i\)个数的最大值，记另一个序列的最大值是\(j\)，此时的最......
  • 2024.1.6做题纪要
    P4390[BalkanOI2007]Mokia摩基亚/（离线）简单题第一眼看题，emmm，跟分治有半毛钱关系啊！！！！这每次分治一次不直接复杂度爆炸？？冷静下来后，我们发现对于一个点，对于区间产生贡献充要条件是他的\(x\)轴要在区间内。所以。。。我们是不是可以离线下来对于\(x\)轴排一遍序，我们只有左半部......
  • 2024.1.6做题总结
    luogu2258[NOIP2014普及组]子矩阵本题乍一看数据范围很小，但是如果暴力的话时间复杂度为\(O(C^r_nC^c_m)\)，在最坏情况（\(r=\frac{1}{2}n,c=\frac{1}{2}m\)）下过不了。本题满足最优化，但是没得贪，二维好像不好跑dp啊。可以枚举哪些行，然后跑一维的dp。我们用一个dfs固定一下......
  • Solution Set【2024.1.5】
    明天再补。[POI2011]LightningConductor设\(f_i\)表示只考虑\(\left[1,i\right]\)的情况下\(i\)的答案，那么有：\[f_i=\max\limits_{j\lei}a_j-a_i+\sqrt{\left\lverti-j\right\rvert}\]发现其满足四边形不等式，于是使用分治优化即可。时间复杂度\(O(n\log......
  • 2024.1.5——每日总结
    学习所花时间（包括上课）：9h代码量（行）：0行博客量（篇）：1篇今天，上午学习，下午学习；我了解到的知识点：1.ERP明日计划：学习......
  • 南外集训 2024.1.5 T3
    非常简单的一道题。要好好反思为什么没有做出来。题意给定一棵点带权的树，强制在线询问一条链上取恰好\(m\)个数按位与的最大值。\(1\len\le10^6,1\leq\le10^5,1\lem\le10,0\leV<2^{62}\)。解法考虑一个暴力：取出树链上所有点权，二分答案\(x\)，则需要检查是否存在至......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99