头像

Ncik


访客:20157

在线 



Ncik
1天前

算法

(贪心) $O(n\log n)$

对所有的部分按照左端点 $c[i]$ 从小到大排序
依次分配每一部分。
为了演奏 $[c, d]$ 这部分,必须要求演奏者的 $a \leq c$。
维护一个数据结构 $S$,存所有满足 $a \leq c$ 的区间 $[a, b]$
选那一个人来满足要求呢?

选择 S 中 b >= d 的最小的 b 对应的区间

假设有 $[a_1, b_1]$,$[a_2, b_2]$,且 $b_1 > b_2 > d$,$a_1$ 和 $a_2$ 均小于等于 $c$。
因为小于等于 $c$ 的部分已经都分配完了,所以左端点不会对答案产生影响。
但是对于右端点,一定是取 $b_2$ 比 $b_1$ 更好。
如果存在 $[b_2 + 1, b_1]$ 的部分,$[a_1, b_1]$ 还可以派上用场。
因此这样贪心的策略是正确的。

那么我们就用 set 来维护 $a \leq c$ 的 $b$ 即可。
每次在 set 中查找大于等于 $d$ 的第一个数就可以了。

C++ 代码

#include <iostream>
#include <set>
#include <algorithm>
#define x first
#define y second

using namespace std;

const int N = 1e5 + 10;

typedef pair<pair<int, int>, int> PII;
set<pair<int, int> > s;
PII a[N], b[N];
int cnt[N], ans[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    // (<a,b>, id)
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].x.x >> a[i].x.y;
        a[i].y = i;
    }

    int m;
    cin >> m;
    // (<c, d>, id)
    for (int i = 1; i <= m; ++i) {
        cin >> b[i].x.x >> b[i].x.y;
        b[i].y = i;
        cin >> cnt[i];
    }

    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);

    int j = 1; 
    for (int i = 1; i <= n; ++i) {
        while (j <= m && b[j].x.x <= a[i].x.x) {
            s.insert(make_pair(b[j].x.y, b[j].y));
            ++j;
        }
        set<pair<int, int> >::iterator it = s.lower_bound(make_pair(a[i].x.y, 0));
        if (it == s.end()) {
            cout << "NO\n";
            return 0;
        } 
        cnt[it->y]--;
        ans[a[i].y] = it->y;
        if (!cnt[it->y]) s.erase(it);
    }

    cout << "YES\n";
    for (int i = 1; i <= n; ++i) 
        cout << ans[i] << " \n"[i == n];

    return 0;
}


活动打卡代码 AcWing 507. 积木大赛

Ncik
1天前
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int h[N];

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i) cin >> h[i];

    int ans = h[1];
    for (int i = 2; i <= n; ++i) {
        if (h[i] > h[i - 1]) ans += h[i] - h[i - 1];
    } 

    cout << ans << '\n';

    return 0;
}



Ncik
8天前

算法

(树状数组) $O(n\log n)$

考虑枚举中间的 $j$, 这样只需要计算出有多少个对应的 $i$,$k$。
如果一个 $j$ 有$left[j]$ 个对应的 $i$ 和 $right[j]$ 个对应的 $k$,那么它会贡献 $left[j] * right[j]$ 的答案。
考虑计算 $left[j]$
直接树状数组即可。
$right[j]$ 的计算同理,倒过来即可。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

const int N = 3e4 + 10;

ll n;
ll a[N], cnt[N], cntl[N], cntr[N];

void add(ll x) {
    while (x <= n) {
        cnt[x]++;
        x += x & -x;
    }
}

ll sum(ll x) {
    ll s = 0;
    while (x > 0) {
        s += cnt[x];
        x -= x & -x;
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<int> v;
    for (int i = 1; i <= n; ++i) 
         v.push_back(a[i]);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 1; i <= n; ++i) {
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
    }

    for (int i = 1; i <= n; ++i) {
        cntl[i] = sum(a[i] - 1);
        add(a[i]);
    }

    fill(cnt + 1, cnt + n + 1, 0);

    for (int i = n; i >= 1; --i) {
        cntr[i] = sum(n - a[i]);
        add(n - a[i] + 1);
    }

    ll ans = 0;
    for (int i = 1; i <= n; ++i) 
         ans += cntl[i] * cntr[i];

    cout << ans << '\n';

    return 0;
}



Ncik
11天前

树状数组仅支持单点修改+区间查询或者区间修改+单点查询。

前缀和

给定一个长度为$n(n ≤ 10^5 )$的序列 $𝑎$。
有很多次询问,每次询问一个区间和:
$Q \ l \ r$ 询问 $𝑎_{[𝑙\, , 𝑟]}$ 的区间和

动态前缀和

给定一个长度为 $n(n ≤ 10^5 )$ 的序列𝑎(初值全为0)。
有很多次操作,每个操作可能是:
$Q \ l \ r$ 询问$𝑎_{[𝑙\, , \,𝑟]}$ 的区间和
$M \ x \ y$ 将 $𝑎_x$ 的值改为 $𝑎_x + y$
如使用朴素的前缀和算法,每一次修改操作后需要重新扫一遍数组。
能否找出一个能够尽可能地重复利用信息的方法呢?

树状数组

每一个整数都可以表示成 $2$ 的幂次的和的形式,
那么一个序列是否也可以表示成一系列子序列的和呢?

令 $c_{i}=a_{i-2}{ }^{k}+1+a_{i-2}{ }^{k}+2+\cdots+a_{i}$
其中 $k$ 表示 $i$ 的二进制形式中末尾 0 的个数

9.8.JPG

于是 $s_{i}=a_{1}+a_{2}+\cdots+a_{i}=c_{i}+a_{1}+a_{2}+\cdots+a_{i-2^{k}}=c_{i}+s_{i-2^{k}}$
$s_{i - 2^k}$又可以递归地表示下去。
由于$i$表示成二进制只有 $\log \, i$ 位,所以 $s_i$ 能表示
$c$序列中不超过 $\log \, i$ 项的和。

$a_i$ 的改变会影响到 $c_i$ 中的哪些项呢?
例:包含 $a_{11010(2)}$ 的有 $c_{11010(2)}$,$c_{11100(2)}$,$c_{100000(2)}$,$c_{1000000(2)}$
被波及到的不超过 $\log n$ 项.

设函数 $lowbit(x)$ 表示 $x$ 的二进制最低位

例:$28=00011100(2)$,lowbit $(28)=00000100(2)=4$。

lowbit $(x)=x \&(\sim x+1)=x \&-x$

查询:

$s_{i}=a_{1}+a_{2}+\cdots+a_{i}$
$=c_{i}+c_{i-\mathrm{lowbit}(i)}+c_{i- \mathrm{lowbit}(i)-\operatorname{lowbit}(i-\operatorname{lowbit}(i))}+\cdots$

int query(int x) {
    int s = 0;
    for (int i = x; i; i -= i & -i) 
        s += c[i];
    return s;
}

修改:

void modify(int x, int y) {
    for (int i = x; i <= n; i += i & -i)
        c[i] += y;
}

单次修改和查询操作时间复杂度均为 $O(\log n)$
注意:要求元素下标必须从 1 开始,否则会出现死循环。

区间加法单点求值

给定一个长度为 $n(n \leq 10^5 )$ 的序列 $𝑎$ (初值全为0)。
有很多次操作,每个操作可能是:

  • $M \ l \ r \ k$ 将 $𝑎_{[𝑙,𝑟]}$ 每个值加上 $k$
  • $Q \ x $ 询问 $a_x$的值

Sol:

设差分序列 $b$,其中 $b[i]=a[i]-a[i-1]$
于是序列 $a$ 在区间 $[l,r]$ 上的区间加法,就可以转化为序列 $b$ 在 $l-1$ 和
$r$ 两个位置上的单点修改。序列 $a$ 的单点求值就可以转化为序列 $b$ 上的
前缀和。
用树状数组维护序列b的单点修改和求前缀和即可。

树状数组的作用

  • 单点修改复杂度 $O(\log n)$
  • 计算区间和复杂度 $O(\log n$
  • 树状数组适合单个元素经常修改,而且还反复要求部分的区间的和的情况

例题:

题目: 模板】树状数组 1

Code:

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using W = V<V<T>>;

template <class T> struct Fenwick {
    int n;
    V<T> seg;
    Fenwick(int _n = 0) : n(_n), seg(n + 1) {}
    // 在第i个元素上+x
    void add(int i, T x) {
        while (i <= n) {
            seg[i] += x;
            i += i & -i;
        }
    } 
    //  [1,i]的sum
    T sum(int i) {
        T s = 0;
        while (i > 0) {
            s += seg[i];
            i -= i & -i;
        }
        return s;
    } 
    // [a, b]的sum
    T sum(int a, int b) { return sum(b) - sum(a); } 
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    Fenwick<ll> fw(n);

    for (int i = 1; i <= n; ++i) {
        ll a;
        cin >> a;
        fw.add(i, a);
    }

    for (int i = 0; i < q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            int p;
            ll x;
            cin >> p >> x;
            fw.add(p, x);
        }
        else {
            ll l, r;
            cin >> l >> r;
            cout << fw.sum(l - 1, r) << '\n';
        }
    }

    return 0;
}

题目: 【模板】树状数组 2

利用差分把区间查询变成单点修改,把单点查询变成区间查询

Code:

#include <iostream>

using namespace std;
using ll = long long;

const int N = 5e5 + 10;

ll n, m;
ll c[N];

void add(ll x, ll y) {
    while (x <= n) {
        c[x] += y;
        x += x & -x;
    }
}

ll sum(ll x) {
    ll s = 0;
    while (x > 0) {
        s += c[x];
        x -= x & -x;
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    ll pre = 0;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        add(i, x - pre);
        pre = x;
    }

    for (int i = 1; i <= m; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            ll x, y, k;
            cin >> x >> y >> k;
            add(x, k);
            add(y + 1, -k);
        }
        else {
            ll x;
            cin >> x;
            cout << sum(x) << '\n';
        }
    }

    return 0;
}

二维前缀和

给定一个矩阵 $𝑎$ (初值全为0)。有很多次询问,每个询问形如:

  • $Q \ u \ d \ l \ r$ 询问 $a_{[𝑢,𝑑] ×[𝑙,𝑟]}$ 的区间和
  • $M \ x \ y \ z$ 将 $𝑎_{x,𝑦}$ 的值改为 $𝑎_{x,𝑦}+z$

其实,树状数组可以简单地扩展到二维,例如修改函数只需要改成
如下形式。可惜的是,二维树状数组的空间消耗较大,在算法竞赛
中不太常用。

void modify(int x, int y, int z) {
    for (int i = x; i <= n; i += i & -i)
        for (int j = y; j <= m; j += j & -j)
            c[i][j] += z;
}

如果矩阵过大或者稀疏矩阵的话,用树套树或者动态开点的线段树来维护更好。

逆序对

给定一个序列 $𝑎$,称满足 $1 ≤ 𝑗 < 𝑘 ≤ n$, $a_i > 𝑎_j$ 的数对 $(𝑗,𝑘)$ 为序列 $𝑎$ 的
逆序对。
定理:每次交换相邻的两个元素,序列中逆序对个数增加或减少1.
逆序对个数为冒泡排序过程中交换两个元素的次数。
求逆序对个数:归并排序或树状数组。

用树状数组求逆序对,只需要从后向前枚举数列中的数a[i],查询
树状数组中小于a[i]的元素个数,再在树状数组让a[i]的计数增加1。

long long ans = 0;
for (int i = n; i >= 1; --i)
    ans += query(a[i] - 1), modify(a[i]);

离散化

如果想要使用树状数组求逆序对,那么空间消耗与元素的最大取值是
同级别的。当元素取值范围太大时,空间消耗便会无法承受。其实,
我们只需要知道元素之间的大小关系即可,所以可以将元素的具体值
转化为值的排名,从而将空间消耗优化为与元素个数相同。
将取值转化为排名的方法叫做离散化。
离散化有多种实现方式,时间复杂度与排序的时间复杂度相同。

通过 $vector$ 对序列 $a$ 进行离散化:

vector<int> v;
for (int i = 1; i <= n; ++i)
    v.push_back(a[i]);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 1; i <= n; ++i)
    a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;

练习题:

  1. 弱弱的战壕
  2. SuperBrother打鼹鼠
  3. 旅行规划
  4. [USACO19JAN]Sleepy Cow Sorting G
  5. 逆序对
  6. 三元上升子序列
  7. 论如何玩转 Excel 表格



Ncik
11天前

算法

(回溯) $O(2^n)$

对于这个问题,首先用枚举的思想,取一个子序列,每个数有两种状态,‘取’或者‘不取’。我们发现按顺序来枚举的话,有些前缀是相同的,所以这个问题可认为是一个n层的满二叉树上的状态,二叉树上某个节点,其左子树代表取这个数的状态,右子树代表不取这个数的状态。在递归的同时,用一个数组来记录路径上取的数的状态,最终获得所有组合。

C++ 代码

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> combination;
        vector<vector<int>> combinations;
        helper(1, combination, n, k, combinations);
        return combinations;
    }

    // 递归地求解问题
    // pos代表已访问到哪个数,combination代表当前地组合
    void helper(int pos, vector<int>& combination,
                int n, int k, vector<vector<int>>& combinations) {
        // 第一个递归出口,如果满足 k 个,将这种组合加入最终结果中
        if (combination.size() == k) {
            combinations.push_back(combination);
            return;
        }

        // 第二个递归出口,如果已访问完1 ~ n所有数字,退出当前函数
        if (pos == n + 1) {
            return;
        }

        // 可行性剪枝,如果后面的数都放入,个数不足k的话,退出
        if (combination.size() + n - pos + 1 < k) {
            return;
        }

        // 如果将当前数放入组合,将pos加入combination,继续递归
        combination.push_back(pos);
        helper(pos + 1, combination, n, k, combinations);
        // 递归结束后,弹出pos,还原状态
        combination.pop_back();

        // 不将pos加入combination的情况
        helper(pos + 1, combination, n, k, combinations);
    }
};

Java 代码

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        dfs(1, n, k, temp, res);
        return res;
    }

    public void dfs(int cur, int n, int k, List<Integer> temp, List<List<Integer>> res) {
        if (temp.size() == k) {
            res.add(new ArrayList<>(temp));
            return;
        }
        if (cur > n) return;
        temp.add(cur);
        dfs(cur + 1, n, k, temp, res);
        temp.remove(temp.size() - 1);
        dfs(cur + 1, n, k, temp, res);
    }
}



Ncik
11天前
#define dbg(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl
struct UnionFind
{
    std::vector<int> par, cou;
    UnionFind(int N = 0) : par(N), cou(N, 1) {
        iota(par.begin(), par.end(), 0);
    }
    int find(int x) { return (par[x] == x) ? x : (par[x] = find(par[x])); }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (cou[x] < cou[y]) std::swap(x, y);
        par[y] = x, cou[x] += cou[y];
        return true;
    }
    int count(int x) { return cou[find(x)]; }
    bool same(int x, int y) { return find(x) == find(y); }
};
class Solution {
public:
    using pint = pair<int, int>;
    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        vector<pint> va, vb, v0;
        for (auto p : edges)
        {
            if (p[0] == 1) va.emplace_back(p[1] - 1, p[2] - 1);
            if (p[0] == 2) vb.emplace_back(p[1] - 1, p[2] - 1);
            if (p[0] == 3) v0.emplace_back(p[1] - 1, p[2] - 1);
        }
        UnionFind ufa(n), ufb(n);
        int ret = 0;
        for (auto p : v0)
        {
            ret += ufa.unite(p.first, p.second);
            ufb.unite(p.first, p.second);
        }
        for (auto p : va)
        {
            ret += ufa.unite(p.first, p.second);
        }
        for (auto p : vb)
        {
            ret += ufb.unite(p.first, p.second);
        }
        dbg(ufa.count(0));
        dbg(ufb.count(0));
        if (ufa.count(0) < n or ufb.count(0) < n) return -1;
        return edges.size() - ret;
    }
};



Ncik
17天前
const int P=1e9+7;
class Solution {
public:
    int son[1005][2],size[1005],val[1005],C[1005][1005];
    int DFS(int x){
        int ans=C[size[son[x][0]]+size[son[x][1]]][size[son[x][0]]];
        if (son[x][0]) ans=1ll*ans*DFS(son[x][0])%P;
        if (son[x][1]) ans=1ll*ans*DFS(son[x][1])%P;
        return ans;
    }
    int numOfWays(vector<int>& nums) {
        C[0][0]=1;
        for (int i=1;i<=1000;i++){
            C[i][0]=1;
            for (int j=1;j<=i;j++)
                C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
        }
        val[1]=nums[0];
        for (int i=2;i<=nums.size();i++){
            int x=1,y,t;
            while (x){
                size[x]++;
                y=x;
                t=nums[i-1]>val[x];
                x=son[x][t];
            }
            son[y][t]=i;size[i]=1;
            val[i]=nums[i-1];
        }
        return DFS(1)-1;
    }
};



Ncik
17天前
class Solution {
public:
    int vis[35][35],cnt=0,ans=0,n,m,num=0;
    int DFS(int x,int y,vector<vector<int>>& grid){
        if (x<0||x>=n||y<0||y>=m||grid[x][y]!=1) return 0;
        if (vis[x][y]) return 1;
        int nxt = 0;
        vis[x][y]=cnt;
        nxt+=DFS(x-1,y,grid);
        nxt+=DFS(x,y-1,grid);
        nxt+=DFS(x,y+1,grid);
        nxt+=DFS(x+1,y,grid);
        if (nxt<=1) ans=1;
        return 1;
    }
    int ok(vector<vector<int>>& grid){
        for (int i=0;i<n;i++) for (int j=0;j<m;j++) vis[i][j]=0;cnt=0;
        for (int i=0;i<n;i++)
            for (int j=0;j<m;j++)
                if (!vis[i][j]&&grid[i][j]==1){
                    cnt++;
                    DFS(i,j,grid);
                }
        return (cnt>=2||cnt==0);
    }
    int minDays(vector<vector<int>>& grid) {
        n=grid.size(),m=grid[0].size();
        if (ok(grid)) return 0;
        for (int i=0;i<n;i++)
            for (int j=0;j<m;j++)
                if (grid[i][j]==1){
                    grid[i][j]=0;
                    if (ok(grid)) return 1;
                    grid[i][j]=1;
                }
        return 2;
    }
};



Ncik
17天前
class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int ans = 0;
        int pos = 0, neg = 0;
        for (int num: nums) {
            if (num == 0) {
                pos = neg = 0;
            }
            else if (num > 0) {
                ++pos;
                if (neg > 0) {
                    ++neg;
                }
            }
            else {
                int newpos = (neg > 0 ? neg + 1 : 0);
                int newneg = (pos > 0 ? pos + 1 : 1);
                pos = newpos;
                neg = newneg;
            }
            ans = max(ans, pos);
        }
        return ans;
    }
};



Ncik
17天前
class Solution {
public:
    bool containsPattern(vector<int>& arr, int m, int k) {
        int n = arr.size();
        for (int i = 0; i + m * k <= n; ++i) {
            bool check = true;
            for (int j = i + m; j < i + m * k; ++j) {
                if (arr[j] != arr[j - m]) {
                    check = false;
                    break;
                }
            }
            if (check) {
                return true;
            }
        }
        return false;
    }
};