首页 > 其他分享 >杂题小记（2023.02.22）

杂题小记（2023.02.22）

时间：2023-03-05 12:57:29浏览次数：57  
标签：return 22 int 2023.02 SON uf 杂题 void define

杂题小记（2023.02.22）

目录

更好的阅读体验戳此进入

好吧这一天刷了好几道大水题，大概就是写某道题的时候延申延申又延申出来一大堆奇怪的没怎么写过的小知识点，就丢到杂题里了。

HDU-3038 How Many Answers Are Wrong

题面

存在 $ n $ 个数，给定 $ m $ 个区间限制：给定 $ l, r, s $ 表示 $ \sum_{i = l}^r = s $，你需要判断有多少限制与其之前的限制矛盾。

Solution

由题意不难想到带权并查集实现，首先将闭区间转换为左闭右开区间，然后维护带权并查集的 $ dis $，每次判断是否合法即可。

然后 HDU 默认多测题面里不写，我还以为代码写错了找了半天。。。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template < typename T = int >
inline T read(void);

int N, M;
int ans(0);

class UnionFind{
private:
    int fa[210000];
    ll dis[210000];
public:
    UnionFind(void){for(int i = 1; i <= 201000; ++i)fa[i] = i, dis[i] = 0;}
    void Clear(void){for(int i = 1; i <= 201000; ++i)fa[i] = i, dis[i] = 0;}
    int Find(int x){
        if(x == fa[x])return x;
        int cfa = fa[x];
        fa[x] = Find(fa[x]);
        dis[x] += dis[cfa];
        return fa[x];
    }
    void Union(int s, int t, ll d){
        int fs = Find(s), ft = Find(t);
        if(fs == ft)return;
        fa[fs] = ft;
        dis[fs] = d + dis[t] - dis[s];
    }
    bool CheckDis(int s, int t, ll d){
        return dis[s] != d + dis[t];
    }
}uf;

int main(){
    while(true){
        ans = 0, uf.Clear();
        N = read(), M = read();
        while(M--){
            int s = read(), t = read() + 1, d = read();
            if(uf.Find(s) != uf.Find(t))uf.Union(s, t, d);
            else ans += uf.CheckDis(s, t, d);
        }printf("%d\n", ans);
    }
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    int c = getchar();
    if(!~c)exit(0);
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P1525 [NOIP2010 提高组] 关押罪犯

题面

存在 $ n $ 个人和 $ m $ 条限制，每条限制为 $ s, t, w $ 表示若 $ s $ 和 $ t $ 在同一监狱内将会贡献 $ w $，你需要将 $ n $ 个人分到两个监狱中，以最小化最大贡献，输出最小值，若不存在贡献则输出 0。

Solution

扩展域并查集。与其说扩展域并查集，也可以认为其就是利用了 2-SAT 的思想，每个点拆成两个，然后贪心地优先取更大的限制，尽量去安排即可。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template < typename T = int >
inline T read(void);

int N, M;
struct Node{int s, t, w;};
basic_string < Node > rels;

class UnionFind{
private:
    int fa[410000];
public:
    UnionFind(void){for(int i = 1; i <= 401000; ++i)fa[i] = i;}
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
    void Union(int s, int t){
        int fs = Find(s), ft = Find(t);
        if(fs == ft)return;
        fa[fs] = ft;
    }
}uf;

int main(){
    N = read(), M = read();
    for(int i = 1; i <= M; ++i){
        int s = read(), t = read(), w = read();
        rels += Node{s, t, w};
    }sort(rels.begin(), rels.end(), [](const Node &a, const Node &b)->bool{return a.w > b.w;});
    for(auto rel : rels){
        if(uf.Find(rel.s << 1) != uf.Find(rel.t << 1))uf.Union(rel.s << 1, (rel.t << 1) | 1), uf.Union((rel.s << 1) | 1, rel.t << 1);
        else printf("%d\n", rel.w), exit(0);
    }printf("0\n");
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P2024 [NOI2001] 食物链

题面

存在 $ A \to B \to C $ 的食物链关系，存在 $ n $ 个动物，$ m $ 条限制，每条限制为 $ s, t $ 为同类或 $ s \to t $，求有多少条与之前矛盾（包括本身不合法）。

Solution

考虑扩展域并查集，将 $ P_i $ 分解成 $ P_{i, A}, P_{i, B}, P_{i, C} $ 然后从意义上处理即可，同样类似于 2-SAT 的思想。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
// #define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define SON(i, x) (i + N * x)

template < typename T = int >
inline T read(void);

int N, M;
int ans(0);

class UnionFind{
private:
    int fa[210000];
public:
    UnionFind(void){for(int i = 1; i <= 201000; ++i)fa[i] = i;}
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
    void Union(int s, int t){
        int fs = Find(s), ft = Find(t);
        if(fs == ft)return;
        fa[fs] = ft;
    }
}uf;

int main(){
    N = read(), M = read();
    while(M--){
        int opt = read(), s = read(), t = read();
        if(s > N || t > N){++ans; continue;}
        if(opt == 1){
            if(
                uf.Find(SON(s, 0)) == uf.Find(SON(t, 1)) ||
                uf.Find(SON(s, 0)) == uf.Find(SON(t, 2)) ||
                uf.Find(SON(s, 1)) == uf.Find(SON(t, 0)) ||
                uf.Find(SON(s, 1)) == uf.Find(SON(t, 2)) ||
                uf.Find(SON(s, 2)) == uf.Find(SON(t, 0)) ||
                uf.Find(SON(s, 2)) == uf.Find(SON(t, 1))
            )++ans;
            else uf.Union(SON(s, 0), SON(t, 0)), uf.Union(SON(s, 1), SON(t, 1)), uf.Union(SON(s, 2), SON(t, 2));
        }else{
            if(s == t){++ans; continue;}
            if(
                uf.Find(SON(s, 0)) == uf.Find(SON(t, 0)) ||
                uf.Find(SON(s, 0)) == uf.Find(SON(t, 2)) ||
                uf.Find(SON(s, 1)) == uf.Find(SON(t, 1)) ||
                uf.Find(SON(s, 1)) == uf.Find(SON(t, 0)) ||
                uf.Find(SON(s, 2)) == uf.Find(SON(t, 2)) ||
                uf.Find(SON(s, 2)) == uf.Find(SON(t, 1))
            )++ans;
            else uf.Union(SON(s, 0), SON(t, 1)), uf.Union(SON(s, 1), SON(t, 2)), uf.Union(SON(s, 2), SON(t, 0));
        }
    }printf("%d\n", ans);

    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P5787 二分图 /【模板】线段树分治

题面

在共 $ k $ 时间中，有 $ m $ 条边每条边都有其对应时效，求对于每一段时间中该 $ n $ 个点的图是否为二分图。

Solution

首先二分图可以通过扩展与并查集判断，同时并查集需要支持可撤销并进行按秩合并，对于询问进行线段树分治即可。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template < typename T = int >
inline T read(void);

int N, M, K;

class UnionFind{
private:
    int fa[410000], siz[410000];
    struct Mdf{int s; int fs; int t; int sizt;};
    stack < Mdf > mdfs;
public:
    UnionFind(void){for(int i = 0; i <= 401000; ++i)fa[i] = i, siz[i] = 1;}
    auto GetTop(void){return mdfs.empty() ? Mdf() : mdfs.top();}
    int Find(int x){return x == fa[x] ? x : Find(fa[x]);}
    void Union(int s, int t){
        int fs = Find(s), ft = Find(t);
        if(siz[fs] > siz[ft])swap(fs, ft);
        if(fs == ft)return;
        mdfs.push(Mdf{fs, fa[fs], ft, siz[ft]});
        siz[ft] += siz[fs];
        fa[fs] = ft;
    }
    void Repeal(Mdf endp){
        while(!mdfs.empty() && (mdfs.top().s != endp.s || mdfs.top().t != endp.t))
            fa[mdfs.top().s] =mdfs.top().fs, siz[mdfs.top().t] = mdfs.top().sizt, mdfs.pop();
    }
}uf;

class SegTree{
private:
    struct Line{int s, t;};
    basic_string < Line > tr[110000 << 2];
    #define LS (p << 1)
    #define RS (LS | 1)
    #define MID ((gl + gr) >> 1)
public:
    void Insert(int l, int r, int s, int t, int p = 1, int gl = 0, int gr = K - 1){
        if(l <= gl && gr <= r)return tr[p] += Line{s, t}, void();
        if(l <= MID)Insert(l, r, s, t, LS, gl, MID);
        if(r >= MID + 1)Insert(l, r, s, t, RS, MID + 1, gr);
    }
    void dfs(int p = 1, int gl = 0, int gr = K - 1){
        bool legal(true);
        auto lst = uf.GetTop();
        for(auto line : tr[p]){
            int fs = uf.Find(line.s << 1), ft = uf.Find(line.t << 1);
            if(fs == ft){
                legal = false;
                for(int i = gl; i <= gr; ++i)printf("No\n");
                break;
            }uf.Union(line.s << 1, (line.t << 1) | 1), uf.Union((line.s << 1) | 1, line.t << 1);
        }
        if(legal){
            if(gl != gr)dfs(LS, gl, MID), dfs(RS, MID + 1, gr);
            else printf("Yes\n");
        }uf.Repeal(lst);
    }
}st;

int main(){
    N = read(), M = read(), K = read();
    while(M--){
        int s = read(), t = read(), l = read(), r = read() - 1;
        st.Insert(l, r, s, t);
    }st.dfs();
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P2627 [USACO11OPEN]Mowing the Lawn G

题面

给定序列 $ A_n $，你要在其中选择数个数删除，使得最大的连续的保留的数不超过 $ k $ 个。

Solution

考虑 DP，令 $ dp(i) $ 表示考虑前 $ i $ 个数的最大值，有转移：

\[dp(i) = \max\{ dp(j - 1) + \sum_{k = j + 1}^i E_k, j \in [i - k, i] \} \]

预处理前缀和后有：

\[dp(i) = \max\{ dp(j - 1) + sum_i - sum_{j} \} \]

将 $ sum_i $ 提出：

\[dp(i) = sum_i + \max\{ dp(j - 1) - sum_{j} \} \]

于是维护长度为 $ k $ 的区间最大 $ dp(i - 1) - sum_i $ 即可。

Tips：一个我调了半天的问题就是需要注意初始时应该考虑到 $ j = 0 : dp(0) - sum_0 $ 的情况。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template < typename T = int >
inline T read(void);

int N, K;
ll A[110000];
ll sum[110000];
ll dp[110000];
deque < pair < int, ll > > cur;

int main(){
    N = read(), K = read();
    for(int i = 1; i <= N; ++i)sum[i] = sum[i - 1] + (A[i] = read());
    cur.push_back({0, 0});
    for(int i = 1; i <= N; ++i){
        while(!cur.empty() && cur.front().first < i - K)cur.pop_front();
        while(!cur.empty() && cur.back().second < dp[i - 1] - sum[i])cur.pop_back();
        cur.push_back({i, dp[i - 1] - sum[i]});
        dp[i] = sum[i] + (cur.empty() ? 0 : cur.front().second);
    }printf("%lld\n", dp[N]);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P4954 [USACO09OPEN]Tower of Hay G

题面

存在 $ n $ 个砖块，每个有宽度 $ w_i $，按序给定每个砖块，你需要按序将其搭高，必须满足上层的宽度不小于下层，且所有砖块都必须被使用。

Solution

由于均使用的限制存在，不难想到所有方案中最优方案一定满足最底层最小。同时我们一定也需要满足尽量使高层更小，并且不难发现一般的 DP 的维度难以降低主要都是在讨论最后一层的高度等，而我们此时可以考虑将砖块逆序翻转，然后做前缀和，令其为 $ s_i $，然后令 $ f(i) $ 表示前 $ i $ 个最高能搭建多少层，$ g(i) $ 表示当用到第 $ i $ 块时最优方案中 $ w_i $ 所在层的宽度，转移显然为当我们找到最大的一个 $ j $ 满足 $ s_i - s_{j} \ge g(j) $，则 $ f(i) = f(j) + 1, g(i) = s_i - s_j $。移项得到 $ s_i \ge s_j + g(j) $，而我们需要的是 $ j $ 最大的，如果存在 $ k \lt j $ 且 $ s_k + g(k) \ge s_j + g(j) $ 那么 $ k $ 一定不优，可以直接忽略，以此维护递增的单调队列并转移即可。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template < typename T = int >
inline T read(void);

int N;
int w[110000];
ll s[110000];
ll F[110000], G[110000];
deque < pair < int, ll > > cur;

int main(){
    N = read();
    for(int i = 1; i <= N; ++i)w[i] = read();
    reverse(w + 1, w + N + 1);
    for(int i = 1; i <= N; ++i)s[i] = s[i - 1] + w[i];
    cur.push_back({0, 0});
    for(int i = 1; i <= N; ++i){
        pair < int, ll > lst = {-1, -1ll};
        while(!cur.empty() && cur.front().second <= s[i])lst = cur.front(), cur.pop_front();
        if(~lst.first)cur.push_front(lst);
        F[i] = F[cur.empty() ? 0 : cur.front().first] + 1;
        G[i] = s[i] - s[cur.empty() ? 0 : cur.front().first];
        while(!cur.empty() && cur.back().second > s[i] + G[i])cur.pop_back();
        cur.push_back({i, s[i] + G[i]});
    }printf("%lld\n", F[N]);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2023_02_22 初稿

标签：return,22,int,2023.02,SON,uf,杂题,void,define
From： https://www.cnblogs.com/tsawke/p/17180241.html

相关文章

  • 杂题小记（2023.02.24）
    杂题小记（2023.02.24）目录杂题小记（2023.02.24）更好的阅读体验戳此进入LG-P5251[LnOI2019]第二代图灵机题面SolutionCodeLG-P3765总统选举题面SolutionCodeUPD更好的阅读体......
  • 杂题小记（2023.02.27）
    杂题小记（2023.02.27）目录杂题小记（2023.02.27）更好的阅读体验戳此进入LG-P3865【模板】ST表LG-P3293[SCOI2016]美味题面SolutionCodeLG-P5490【模板】扫描线题面Solution......
  • 杂题小记（2023.03.01）
    杂题小记（2023.03.01）目录杂题小记（2023.03.01）更好的阅读体验戳此进入[ARC084D]SmallMultiple题面SolutionCodeLG-P2371[国家集训队]墨墨的等式题面SolutionCodeLG-P2158......
  • 杂题小记（2023.02.28）
    杂题小记（2023.02.28）目录杂题小记（2023.02.28）更好的阅读体验戳此进入SP2713GSS4-CanyouanswerthesequeriesIV题面SolutionCodeLG-P4391[BOI2009]RadioTransmissio......
  • IDEA2022配置maven步骤
    IDEA2022配置mavenPS:默认你已经下载maven并解压配置好了步骤打开IDEA点击File中的Settings2.打开BuildExecution-->BuildTools-->Maven现在就配置完成了，让我们......
  • MacOS Ventura 13.2.1 (22D68) 下载
    基于官方镜像制作.支持制作U盘启动和VMWare加载. 下载地址:XEngine--XEngine网络开发框架XEngine网络通信引擎XEngine网络中间件(xyry.org)......
  • ubuntu 22.04 配置 samba 服务
     通过在ubuntu系统中安装samba，使得windows10 能访问安装在vmware中的ubuntu文件。sudoaptinstallsamba#编辑samba配置文件：sudovim/etc/samba/smb......
  • CCPC2022 Guangzhou Site
    大概按题目难度顺序排序。这篇题解可能没那么口胡。被dead_X称为全是签到题。GYM104053EElevator相当于每个电梯在\(-x_i\)，每次可以把最大的，编号最小的值减一，要求......
  • QD2022Q4
    /*************************************************************题目描述*[最多等和不相交连续子序列Q]*给一个二维数组nums，对于每一个元......
  • 代码随想录算法Day32 | 122.买卖股票的最佳时机II ，55. 跳跃游戏 ，45.跳跃游戏II
    把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！122.买卖股票的最佳时机II题目链接：122.买卖股票的最佳时机II-力扣（LeetCode）思路   这道题使用贪心......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99