头像

anss

$Note$ $of$ $anss$




离线:3天前


最近来访(73)
用户头像
奔向未来
用户头像
Forms
用户头像
Data_Rookie
用户头像
TEN.X
用户头像
半夏听雨
用户头像
Sings
用户头像
Cabin-65--
用户头像
海问香
用户头像
云衣醉梦
用户头像
Marius
用户头像
姜紫瑶
用户头像
jerotsy
用户头像
coolcoder
用户头像
人间小苦瓜_2
用户头像
OI
用户头像
500分的idiot
用户头像
乘风破浪_93
用户头像
yxc
用户头像
-W-
用户头像
solo起来


anss
3天前

$Pre$

在一些枚举方案的问题中,会存在”后效性”的问题,这种时候就不能用局部最优来形成全局最优解

一、$Leetcode.698$划分为$K$个相等的子集

本题分析完毕后就是要凑齐$K$个值为$val$的集合,那么直观的思路是判断是否可以凑出$K$次$val$,同时每次将选了的数标记已访问,代码如下:

class Solution {
public:
    bool dfs(int u, int sum, vector<int> &nums, int n)
    {
        if (!sum) return true;
        if (u == n) return false;
        // 不选当前数
        if (dfs(u + 1, sum, nums, n)) return true;  
        // 只有当当前结点没有被选的时候才可以选当前数
        if (!st[u])
        {
            st[u] = true;
            if (dfs(u + 1, sum - nums[u], nums, n)) return true;
            st[u] = false;
        }
        return false;
    }
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = 0, n = nums.size();
        sort(nums.begin(), nums.end());
        for (auto t : nums) sum += t;
        if (sum % k) return false;
        if (nums[n - 1] > sum / k) return false;

        int val = sum / k;
        for (int i = 0; i < k; i ++)  // 凑k个val
            if (!dfs(0, val, nums, n)) return false;
        return true;
    }
private:
    static const int N = 20;
    bool st[N];
};

可以发现这种选法的每一次选数,其实都是具有后效性的,因为$k$此选数之间是相互影响的,比如我们已有$4,3,3,2,2,1$,要凑出$3$个$5$,那么明显是可以的,但是如果我们先将$2,2,1$选了,那么在这种策略下我们后面两次就无法进行,但是实际上是可以凑出$3$个$5$的
因此我们应该同时进行$K$次的选数,保证各次之间互不影响

class Solution {
public:
    // last每次凑val时nums上次遍历到的位置
    bool dfs(int last, int sum, int k, vector<int> &nums, int n)
    {
        if (k == 0) return true;
        if (sum < 0) return false;
        if (sum == val) return dfs(0, 0, k - 1, nums, n);
        for (int i = last; i < n; i ++)
            if (!st[i] && val - sum >= nums[i])
            {
                st[i] = true;
                if (dfs(i + 1, sum + nums[i], k, nums, n)) return true;
                st[i] = false;
                if (sum == 0) return false;
            }
        return false;
    }

    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = 0, n = nums.size();
        sort(nums.begin(), nums.end(), greater<int>());
        for (auto t : nums) sum += t;
        if (sum % k) return false;
        if (nums[n - 1] > sum / k) return false;
        val = sum / k;
        if (dfs(0, 0, k, nums, n)) return true;
        return false;
    }
private:
    int val;
    static const int N = 20;
    bool st[N];
};

二、$Acwing.1027$方格取数




anss
22天前

明天$PAT$没时间整理了,先记录一下代码......
最早发生时间即起点到该结点的最长路
这里的最早是指当前结点在能到它的结点都完成后能开始工作的最早时间,因为每个结点必须所有前驱结点全部到达当前结点后当前结点才能进行,因此是求最长路

最晚发生时间是当前点最晚能拖到什么时候且不影响下一个点的最晚发生时间
1.png
如下图中$v_5$最晚的发生时间是7,因此$v_3$可以拖到时间6再执行,只要不影响$v_5$在时间7可以正常进行即可

为什么是取最小值?
比如下面点$u$有三个后继结点,那么在$u$就是取$min\{($vl[a$\~$c]-w[a$\~$c]$)\}$,因为即使$u$提前完成,然后去完成$b$、$c$,整个工程的时间还是会被$a$限制(假设$a$、$b$、$c$三个任务的$vl[]$相同)
1.jpg
参考分享

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;

int top[N], cnt = 1;
int ind[N], ve[N], vl[N], n, m;
int ht[N], hs[N], e[N], ne[N], w[N], idx;

void add(int h[], int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void topsort()  // 求出拓扑访问序列
{
    queue<int> q; q.push(1);
    while (q.size())
    {
        int t = q.front(); q.pop();
        top[cnt ++] = t;
        for (int i = ht[t]; ~i; i = ne[i])
        {
            int j = e[i];
            ind[j] --;
            if (!ind[j]) q.push(j);
        }
    }
}

void get_path()
{
    // 求解事件允许的最早发生时间
    ve[1] = 0;
    for (int i = 1; i <= n; i ++)  // 按照拓扑访问序列,求出每个点的最长路
    {
        int cur = top[i];
        for (int j = ht[cur]; ~j; j = ne[j])
        {
            int k = e[j];
            ve[k] = max(ve[k], ve[cur] + w[j]); 
        }
    }

    memset(vl, 0x3f, sizeof vl);  // 最早时间要初始化0X3f
    vl[n] = ve[n];  // 求解其他时间最晚发生的时间是在终点能在最早时间完成的前提上进行的
    for (int i = n; i >= 1; i --)
    {
        int cur = top[i];
        for (int j = hs[cur]; ~j; j = ne[j])
        {
            int k = e[j];
            vl[k] = min(vl[k], vl[cur] - w[j]);
        }
    }
}

vector<int> path;
void dfs(int u)  // dfs一遍,最早发生时间等于最晚发生时间的就是关键顶点
{
    if (u == n)
    {
        for (auto t : path) cout << t << ' ';
        puts("");
        path.pop_back();
        return;
    }
    for (int i = ht[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (ve[j] == vl[j])
        {
            path.push_back(j);
            dfs(j);
            path.pop_back();
        }
    }
}

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin >> n >> m;
    memset(ht, -1, sizeof ht);
    memset(hs, -1, sizeof hs);  
    while (m --)
    {
        int a, b, c; cin >> a >> b >> c;
        ind[b] ++;
        add(ht, a, b, c), add(hs, b, a, c);
    }
    topsort();
    get_path();
    for (int i = 1; i <= n; i ++)
        cout << ve[i] << ' ' << vl[i] << endl;
    path.push_back(1);
    dfs(1);
    return 0;
}



anss
1个月前

最低公共祖先

第一次记录一个大坑
本题用向上标记法其实就已经够了,但是本$sb$非得奔着复习倍增法的想法,我写了倍增,然后$debug$了一整天
由于倍增法中将$0$记为哨兵,任何跳到0的操作都是不能被执行的,所以对树中结点编号一定不能有0!!!
本题中结点含有负数,因此要先离散化,离散化的时候要从1开始!!!

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10, M = N * 2;
int n, m;
int pre[N], in[N];
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][16], q[M], book[N];
unordered_map<int, int> pos;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void bfs(int root)
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    int hh = 0, tt = 0; q[0] = root;
    while (hh <= tt)
    {
        int t = q[hh ++];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                fa[j][0] = t;
                q[++ tt] = j;
                for (int k = 1; k <= 15; k ++)
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}
int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 15; k >= 0; k --)
        if (depth[fa[a][k]] >= depth[b]) a = fa[a][k];
    if (a == b) return a;
    for (int k = 15; k >= 0; k --)
        if (fa[a][k] != fa[b][k]) 
            a = fa[a][k], b =fa[b][k];
    return fa[a][0];
}

int build(int pl, int pr, int il, int ir)
{
    int root = pre[pl], k = root - il, l, r;
    if (il < root) 
    {
        l = build(pl + 1, pl + k, il, il + k - 1);
        add(root, l);
    }
    if (ir > root)
    {
        r = build(pl + k + 1, pr, il + k + 1, ir);
        add(root, r);
    }
    return root;
}

int main()
{
    cin >> m >> n;
    for (int i = 1; i <= n; i ++) 
    {
        cin >> pre[i];
        book[i] = pre[i];
    }
    sort(book + 1, book + n + 1);  // 将中序排序
    for (int i = 1; i <= n; i ++) 
    {
        pos[book[i]] = i;  // 建立映射
        in[i] = i;  // 建立离散化后的中序映射
    }
    for (int i = 1; i <= n; i ++) pre[i] = pos[pre[i]];  // 建立离散化后的前序序列

    memset(h, -1, sizeof h);
    int root = build(1, n, 1, n);

    bfs(root);
    while (m --)
    {
        int a, b; cin >> a >> b;
        bool has_a = false, has_b = false;
        if (pos.count(a))
        {
            a = pos[a]; has_a = true;
        }
        if (pos.count(b)) 
        {
            b = pos[b]; has_b = true;
        }
        if (has_a && has_b) 
        {
            int p = lca(a, b);
            if (p == a) printf("%d is an ancestor of %d.\n", book[a], book[b]);
            else if (p == b) printf("%d is an ancestor of %d.\n", book[b], book[a]);
            else printf("LCA of %d and %d is %d.\n", book[a], book[b], book[p]);
        }
        else if (has_a) printf("ERROR: %d is not found.\n", b);
        else if (has_b) printf("ERROR: %d is not found.\n", a);
        else printf("ERROR: %d and %d are not found.\n", a, b);
    }
    return 0;
}



anss
1个月前

微信图片_20220818094615.jpg

一、判断要素

① 根节点是黑色的
② 每个红色的点的两个子节点是黑色的
③ 每个点到所有叶结点的路径上黑色结点的数目相同

二、分析

单看前两点,我们只需模拟建树的过程(并不需要将树建出来),每次建树递归结束返回根节点用于判断红色点的两个儿子是否都是黑的,并在最顶层递归判断根节点是黑的即可
然后考虑第三点,我们要知道根结点到叶结点是否满足该条件,而根节点有两个儿子,如果两个儿子满足,那么根节点肯定满足,可以发现这也是具有递归性质的,那么对于每个结点,我们就只需要记录它的左右儿子的到叶结点的路径是否相同即可,一般用返回值即可实现,但是返回值用于记录根节点了,因此这里采用在递归中引用来记录子节点的黑色结点数量

$Summary$

这里的第三个性质检查时实际每个结点都有很多条路径要检查,但是通过递归性,我们对于每个点都只用考虑两个子节点,可以化繁为简,便于实现

三、题中细节

1. 题中已经说明给出的是二叉搜索树,但是数据中存在不是合法二叉搜索树的情况,要记得合法性判断

2. 题中用负值来表示红色结点,但是我们建树或者递归访问不能带着负号,因为我们要通过从小到大排序来获取二叉搜索树的先序序列,而如果带着负号会影响排序,所以对于中序我们要取绝对值,而先序保留负号,在获取先序在中序中的位置的时候取绝对值再获取

四、$Code$

注意引用维护返回值的操作方式

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 40;

int pre[N], in[N];
unordered_map<int, int> pos;
bool ans;

int build(int il, int ir, int pl, int pr, int& sum)
{
    if (il > ir) return 0;  // 非负数都是黑色的结点,叶子结点默认有两个黑色的子节点
    int root = pre[pl];
    int k = pos[abs(root)];  // 建树的非法判断(划分失败)

    if (k < il || k > ir)
    {
        ans = false;
        return 0;
    }

    int left = 0, right = 0, ls = 0, rs = 0;
    left = build(il, k - 1, pl + 1, pl + 1 + k - 1 - il, ls);
    right = build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr, rs);

    if (ls != rs) ans = false;
    sum = ls;
    if (root < 0)  // 如果当前结点是红色的,两个子节点必须都是黑色的
    {
        if (left < 0 || right < 0) ans = false;
    }
    else sum ++ ;  // 如果当前结点是黑色的,当前路径上的sum就要++

    return root;
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        int n;
        cin >> n;
        for (int i = 0; i < n; i ++ )
        {
            cin >> pre[i];
            in[i] = abs(pre[i]);
        }

        sort(in, in + n);

        pos.clear();
        for (int i = 0; i < n; i ++ ) pos[in[i]] = i;

        ans = true;
        int sum;
        int root = build(0, n - 1, 0, n - 1, sum);

        if (root < 0) ans = false;
        if (ans) puts("Yes");
        else puts("No");
    }
    return 0;
}



anss
1个月前

微信图片_20220822173935.jpg

一、简介

$AVL$树是一种自平衡树,在$AVL$树中,任何结点的两个子树的高度最多相差$1$
如果某个时间某结点的两个子树之间的高度差超过$1$,则通过将树旋转进行重新平衡直至恢复子树高度差最多$1$
即$AVL$树是特殊的二叉搜索树

二、旋转操作

1.png

1. 左旋

形象的理解为:一开始$A$为老大,现在$B$颠覆了$A$的霸权,那么我们先将$E$分配给$A$当左小弟(瘦死的骆驼比马大)安抚一下他的情绪,再将$B$右边小弟$E$的位置给$A$,最后$B$便可上位$A$的老大位置了
注意因为$B$一开始为$A$的左小弟,因此$A$只能被安排到$B$的右边
换完后先更新$B$的高度,再更新$A$的距离($A$的高度要取决于更新后的$B$)

int L(int &u)
{
    int p = r[u];
    r[u] = l[p];
    l[p] = u;
    u = p;
    update(l[u]), update(u);  // 换完点后要先后更新子节点(原来的老大)和u(新的老大)的高度
}

2. 右旋

同理右旋时只能安排到左边
换完后先更新$A$的高度,再更新$B$的距离($B$的高度要取决于更新后的$A$)

int R(int &u)
{
    int p = l[u];
    l[u] = r[p];
    r[p] = u;
    u = p;
    update(r[u]), update(u);  // 换完点后要先后更新子节点(原来的老大)和u(新的老大)的高度
}

三、$AVL$树失衡的解决方法

1.PNG

1. 左子树比右子树高(深)2

① 左子树的左子树比左子树的右子树高1

2.PNG

② 左子树的右子树比左子树的左子树高1

3.PNG

2. 右子树比左子树高(深)2

① 右子树的左子树比右子树的右子树高1

4.PNG

② 右子树的右子树比右子树的左子树高1

5.PNG

四、$Code$

用数组存储相关信息,$l[$ $]$、$r[$ $]$中存的只是标号,旋转的时候边的也只是标号,结点值存在$v[idx]$中
判断$u$是否平衡的方法是检查它的左子树高度与右子树高度的差值,由$get$_$balance$返回,在$AVL$树的建立过程中只会出现1、2、-1、-2两种差值
每次$insert$回来后都要检查当前$u$是否需要调整,这样递归的从底层往顶层调整一遍就能保证整个树是平衡的了

#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int l[N], r[N], v[N], h[N], idx;
int update(int u)  // 类似线段树的pushup函数,用两个子树的高度更新当前根的高度
{
    h[u] = max(h[l[u]], h[r[u]]) + 1;
}
int R(int &u)
{
    int p = l[u];
    l[u] = r[p];
    r[p] = u;
    u = p;
    update(r[u]), update(u);  // 换完点后要先后更新子节点(原来的老大)和u(新的老大)的高度
}
int L(int &u)
{
    int p = r[u];
    r[u] = l[p];
    l[p] = u;
    u = p;
    update(l[u]), update(u);  // 换完点后要先后更新子节点(原来的老大)和u(新的老大)的高度
}
int get_balance(int u)
{
    return h[l[u]] - h[r[u]];
}
void insert(int &u, int x)
{
    if (!u) u = ++ idx, v[u] = x;  // u与l[]、r[]中存的只是idx,值存在v[]中
    else if (x < v[u])
    {
        insert(l[u], x);  // 递归的继续插入
        if (get_balance(u) == 2)  // 回来之后要判断u是否需要调整
        {
            if (get_balance(l[u]) == 1) R(u);  // 情况一
            else L(l[u]), R(u);  // 情况二
        }
    }
    else 
    {
        insert(r[u], x);  // 递归的继续插入
        if (get_balance(u) == -2)  // 回来之后要判断u是否需要调整
        {
            if (get_balance(r[u]) == -1) L(u);  // 情况三
            else R(r[u]), L(u);  // 情况四
        }
    }
    update(u);  // 每个点插到该插的位置后都要递归的从底层到顶层updata一遍高度
}
int main()
{
    int n, root = 0; cin >> n;
    while (n --)
    {
        int x; cin >> x;
        insert(root, x);
    }
    cout << v[root];
    return 0;
}



anss
1个月前

图片转:题解

一、二叉堆简介1.jpg

1. 向堆中插入一个元素

2.jpg

2. 删除堆顶元素

3.jpg

二、堆排序

堆排序是一种原地排序法,即在原数组上进行操作,我们在每次$down$的时候要从$\frac{n}{2}$的位置开始往前遍历来$down$,因为$\frac{n}{2}$的左右儿子都是满足堆的性质的(都是叶结点),从$\frac{n}{2}$往前遍历来$down$又可以保证每个前面的结点的子节点都满足堆的性质,正确性得以保证
关于$\frac{n}{2}$: 题解

三、理解

堆的堆顶具有是整个堆中最大/最小元素的性质,同时每个子节点也是其所在的子堆中最大的一个,但是各个子节点之间并没有直接的大小关系,因此要想得到整个堆的大小关系,必须不断利用堆顶元素是最大/最小的性质,将堆顶元素不断提取出来,同时继续维护只改变了堆顶元素剩余的堆,这样就能得到整个堆的大小关系

1. 小根堆$建堆code$

注意这只是建堆,可以通过建好的堆每次与末尾元素交换以输出序列,但这并不是严格的堆排序,堆排序需要将原序列变成有序

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int h[N], n, k;
void down(int u)
{
    int t = u;
    if (2 * u <= n && h[t] > h[2 * u]) t = 2 * u;
    if (2 * u + 1 <= n && h[t] > h[2 *u + 1]) t = 2 * u + 1;
    if (t != u)
    {
        swap(h[u], h[t]);
        down(t);
    }
}
int main()
{
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i ++) scanf("%d", &h[i]);
    for (int u = n / 2; u >= 1; u --) down(u);
    int m = n;
    while (m --)  // 输出m个
    {
        cout << h[1] << ' ';
        // 将堆顶元素和最后一个元素交换以达到删除的现存堆顶的目的
        // 删除现存堆顶后新的堆顶即下一个更小的元素
        h[1] = h[n --]; 
        down(1);
    }
    return 0;
}

2. 堆排序(大根堆实现升序排列)

1.PNG
要实现升序排列,既可以用大根堆也可以用小根堆
① 如果用大根堆,堆顶元素是堆中最大的元素,每次将堆顶元素与序列最后一个元素交换,然后将堆有效末尾–,然后继续维护前面序列的堆的性质,继续将堆顶元素放到新的末尾,这样一直进行下去,最后整个序列就为升序
② 如果用小根堆,堆顶元素就是堆中最小元素,每次将堆顶元素与序列第一个元素交换,然后将序列开头后移,继续维护堆的性质,同理进行下去也可以得到升序序列

下面是用大根堆(堆顶元素为堆中最大元素)来实现升序排列的代码

#include<bits/stdc++.h>
#define x first
#define y second
#define PII pair<int, int>
using namespace std;
typedef long long LL;
const int N = 110;
const int INF_1 = 0x3f3f3f3f;
const LL INF_2 = 2e18;
bool st[N];
int h[N], c[N], n;
void down(int u, int len)
{
    int t = u;
    if (u * 2 <= len && h[t] < h[2 * u]) t = 2 * u;
    if (u * 2 + 1 <= len && h[t] < h[2 * u + 1]) t = 2 * u + 1;
    if (t != u)
    {
        swap(h[t], h[u]);
        down(t, len);
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> h[i];
    for (int i = 1; i <= n; i ++) cin >> c[i];
    int flag = 2;
    for (int u = n / 2; u >= 1; u --) down(u, n);  // 建立堆
    for (int i = n; i >= 2; i --)
    {
        swap(h[1], h[i]);
        down(1, i - 1);
    }
    for (int i = 1; i <= n; i ++) cout << h[i] << ' ';
    return 0;
}

微信图片_20220818094757.jpg

四、例题

堆排序
插入还是堆排序




anss
1个月前

一、股票买卖$I$

只能买一只股票,然后在未来某一天卖出
直接维护每个$p[i]$前面的最小值即可

class Solution {
public:
    int maxProfit(vector<int>& p) {
        int n = p.size(), pre = 1e9, ans = 0;
        for (int i = 0; i < n; i ++) ans = max(ans, p[i] - pre), pre = min(p[i], pre);
        return ans;
    }
};

二、股票买卖$II$

最多只能持有1股,但是可以进行无数次交易

①状态机

class Solution {
public:
    int maxProfit(vector<int>& p) {
        int n = p.size();
        f[0][0] = 0, f[0][1] = -p[0];
        for (int i = 1; i < n; i ++)
        {
            f[i][0] = max(f[i - 1][0], f[i - 1][1] + p[i]);
            f[i][1] = max(f[i - 1][0] - p[i], f[i - 1][1]);
        }
        return max(f[n - 1][0], f[n - 1][1]);
    }
private:
    static const int N = 3e4+10;
    int f[N][2];
};

② 直接分析
1.png

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        for (int i = 0; i + 1 < prices.size(); i ++ )
            res += max(0, prices[i + 1] - prices[i]);
        return res;
    }
};

三、股票买卖$III$

① 前后缀分离

因为只有两次操作,因此可以讨论这两次操作的分界点在哪里,那么就可以预处理出一段,然后枚举另一段
下面的代码中就是枚举第$i$次作为操作分界点来进行处理

class Solution {
public:
    int maxProfit(vector<int>& p) {
        int n = p.size(), minp = p[0];
        for (int i = 1; i < n; i ++)
        {
            f[i] = max(f[i - 1], p[i] - minp);
            minp = min(minp, p[i]);
        }
        for (int i = n - 1; i >= 0; i --) g[i] = max(g[i + 1], p[i]);
        int res = max(0, g[0] - p[0]);  // 因为0前面不能完成一次完成操作,因此要初始化
        for (int i = 1; i < n; i ++) res = max(res, f[i - 1] + g[i] - p[i]);
        return res;
    }
private:
    int f[100010], g[100010];
};

② 状态机

注意将第$0$天的非法状态初始化成$-INF$非法
1.png

class Solution {
public:
    int maxProfit(vector<int>& p) {
        int n = p.size();
        f[0][1] = -p[0], f[0][2] = -INF, f[0][3] = -INF, f[0][4] = -INF;
        for (int i = 1; i < n; i ++)
        {
            f[i][1] = max(f[i - 1][1], f[i - 1][0] - p[i]);
            f[i][2] = max(f[i - 1][2], f[i - 1][1] + p[i]);
            f[i][3] = max(f[i - 1][3], f[i - 1][2] - p[i]);
            f[i][4] = max(f[i - 1][4], f[i - 1][3] + p[i]);
        }
        int res = max(f[n - 1][2], f[n - 1][4]);
        return max(res, 0);
    }
private:
    static const int N = 1e5+10, INF = 1E9;
    int f[N][5];
};

2.jpg

四、股票买卖$IV$

因为$n$天最多进行$n/2$次交易,因此当$k$大于$n/2$的时候就可以直接当做可以进行无数次交易来处理
其他次数的$k$用状态机来处理
$f[j][0]$: 当前已经进行了j笔交易(买+卖)且手中无股票
$f[j][0]$: 当前已经进行了j笔交易(买+卖)且手中有股票
$$f[j][0] = max(f[j][0], f[j - 1][1] + p[i])$$
$$f[j][1] = max(f[j][1], f[j - 1][0] - p[i])$$
2.png

int f[10001][2];
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int INF = 1e8;
        int n = prices.size();
        if (k >= n / 2) {
            int res = 0;
            for (int i = 1; i < n; i ++ )
                if (prices[i] > prices[i - 1])
                    res += prices[i] - prices[i - 1];
            return res;
        }
        memset(f, -0x3f, sizeof f);
        f[0][0] = 0;
        int res = 0;
        for (int i = 1; i <= n; i ++ )
            for (int j = 0; j <= k; j ++ ) {
                f[j][1] = max(f[j][1], f[j][0] - prices[i - 1]);
                if (j) f[j][0] = max(f[j][0], f[j - 1][1] + prices[i - 1]);
            }
        for (int i = 1; i <= k; i ++ ) res = max(res, f[i][0]);
        return res;
    }
};

$Summary$

其实状态机维护的是当前交易的状态(当前已经进行了$j$笔,手中是否有股票),每天的股票价格只是维护最大收益,与状态转换并无关系




anss
1个月前

基环树

概念:就是在树上再加一条边使之存在环,就称为基环树

内向基环树:

有向图,类似基环树的结构,但每个点有且仅有一条出边,即$k$个点有$k$条边,那么必然是存在环的(且只有一个),其它点均指向这个环,如下:
1.png
注意基环也可能仅包含两个点,在某些题中这个性质会让题目有很大改变
通用的拓扑解题方法

$Eg1:$ $leetcode.6135$

一、拓扑排序后维护最大值$O(n)$

本题要求的是图中最长环,由每个结点最多只有一个出边可知这是一个内向基环树森林(存在多个含环有向图连通块),那么我们就可以先拓扑排序将所有环分离出来,然后再枚举所有环维护最大值

// 注意每次取edges的时候都要判断非-1
class Solution {
public:
    int longestCycle(vector<int>& edges) {
        int n = edges.size();
        vector<int> d(n);
        for (int i = 0; i < n; i ++){
            if (edges[i] == -1) continue;
            d[edges[i]] ++;  // 统计每个点的入度
        }
        queue<int> q;
        for (int i = 0; i < n; i ++)  // 将叶结点初始化进q
            if (!d[i]) q.emplace(i);
        while (q.size())  // 用叶结点做拓扑排序,将挂在基树环上的点都标记入度为0
        {
            auto t = q.front();
            q.pop();
            int w = edges[t];
            if (w != -1 && -- d[w] == 0) q.emplace(w);
        } 
        int ans = -1;
        for (int i = 0; i < n; i ++)
        {
            if (d[i] <= 0) continue;
            int ring_size = 1;
            for (int j = edges[i]; j != i && j != -1; j = edges[j]) 
            {
                d[j] = -1;
                ring_size ++;
            }
            ans = max(ans, ring_size);
        }
        return ans;
    }
};

二、枚举所有点,如果这个点还没有被访问,就判断它是否能形成环$O(n)$

每次从没有访问过的点找环的时候要记录开始时间戳,为了避免将下面的情况识别为环:
1.png

class Solution {
public:
    int longestCycle(vector<int>& edges) {
        int n = edges.size(), time[n], ans = -1;
        memset(time, 0, sizeof time);
        for (int i = 0, timedelta = 1; i < n; i ++)
        {
            if (time[i]) continue;  // 如果这个点已经被访问过
            for (int t = i, start_time = timedelta; t != -1; t = edges[t])  // 判断当前点是否能形成环
            {
                if (time[t])
                {
                    if (time[t] >= start_time) ans = max(ans, timedelta - time[t]);
                    break;
                }
                time[t] = timedelta ++;
            }
        }
        return ans;
    }
};

$Eg1:$ $leetcode.6135$

要求最多能安排到一张桌子上的人员个数,这里就要分别讨论长度为2的基环和长度大于2的基环了

①如果基环长度大于2

那么就不能再将链安排进圆桌,因为会破坏链上原有的友好关系
14.png

②如果基环长度为2

那么可以将两个点相连的链都挂上,且不破坏原有的友好关系,并且还可以安排多个这种形式的友好关系到一张桌子
13.png

class Solution {
public:
    int maximumInvitations(vector<int>& g) {
        int n = g.size();
        int d[n]; memset(d, 0, sizeof d);
        for (auto t : g) d[t] ++;
        int max_depth[n]; memset(max_depth, 0, sizeof max_depth);
        queue<int> q;
        for (int i = 0; i < n; i ++)
            if (!d[i]) q.emplace(i);
        while (q.size())  // 拓扑去链留环
        {
            auto t = q.front();
            q.pop();
            int ne = g[t];
            if (ne == -1) continue;
            max_depth[ne] = max(max_depth[ne], max_depth[t] + 1);
            if (-- d[ne] == 0) q.emplace(ne);
        }
        int max_type1 = -1, max_type2 = 0;
        for (int i = 0; i < n; i ++)
        {
            if (d[i] == 0) continue;
            int ring_len = 1;
            for (int j = g[i]; j != i; j = g[j])
            {
                d[j] = 0;
                ring_len ++;
            }
            // 因为可以安排多个奇数环长度为2的到一张桌子,因此max_type2是累加
            if (ring_len == 2) max_type2 += 2 + max_depth[i] + max_depth[g[i]]; 
            else max_type1 = max(max_type1, ring_len);
        }
        return max(max_type1, max_type2);
    }
};



anss
1个月前

一、单点修改,区间查询

线段树 $or$ 树状数组 直接维护即可

二、区间修改,单点查询

线段树 $or$ 树状数组 维护原数组的差分数组,区间修改就只需改一个点,然后进行单点查询

三、区间修改,区间查询

1. 推公式转化为单点修改区间查询

$$s_t=\sum_{i=1}^{i=t}d_i×(t+1)-\sum_{i=1}^{i=t}(i×d_i)$$
1.png
图片出自

2. 线段树懒标记直接区间修改区间查询

线段树懒标记
2.png




anss
2个月前

一、记忆化搜索$\ $ $VS$ $\ $递推$dp$

记忆化搜索的目的和递推$dp$是一样的,都是避免过程中对$f[i][j]$的重复计算
递推是通过设置明确的访问顺序来避免重复计算,记忆化搜索通过判断$f[i][j]$是否已经被计算好来避免重复计算,效果是一样的
记忆化搜索代码逻辑比递推写法简单且便于处理边界情况,但不能像递推一样用滚动数组优化空间,且由于存在递归,运行效率会低于递推,因此应视具体题目选择合适的方法

二、对于不便递推的题目选用记忆化搜索

$eg:$$Acwing691$

题目分析

$f[i][j]$取决于$f[i-1][j]$、$f[i][j-1]$、$f[i][j+1]$、$f[i+1][j]$,这几个前置状态间也存在相互依赖的关系,那么会不会存在环呢?(存在环就不满足拓扑序,就不能用$dp$求解)
假设存在环形状依赖:
那么就会存在矛盾,所以整个依赖关系的拓扑图中是不存在环的,可以从最中心按照顺指针方向从里向外更新$f[i][j]$,但是这样太过麻烦,不存在环可以直接进行记忆化搜索
1.PNG

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
using PII = pair<int, int>;
typedef long long LL;
const int N = 1e3+10;
int f[N][N], g[N][N], n;
bool st[N];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1}; 
int dp(int sx, int sy)
{
    int &v = f[sx][sy];
    if (~v) return v;
    v = 1;
    for (int i = 0; i < 4; i ++)
    {
        int nx = sx + dx[i], ny = sy + dy[i];
        if (nx < 1 || nx > n || ny < 1 || ny > n || g[sx][sy] + 1 != g[nx][ny]) continue;
        v = max(v, dp(nx, ny) + 1);
    }
    return v;
}
int main()
{
    int T;
    scanf("%d", &T);
    for (int cases = 1; cases <= T; cases ++)
    {
        memset(f, -1, sizeof f);
        int id, cnt = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
                cin >> g[i][j];
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
            {
                int t = dp(i, j);
                if (t > cnt || (t == cnt && g[i][j] < id)) id = g[i][j], cnt = t;
            }
        printf("Case #%d: %d %d\n", cases, id, cnt);
    }
    return 0;
}