首页 > 其他分享 >08-09 题解

08-09 题解

时间：2024-08-10 10:16:39浏览次数：10  
标签：mini int 题解 08 09 maxi INF id lstps

08-09 题解

A

小水题

思路

假设我们选定了当前子序列的绝对众数 \(x\)， 那么该序列里最多再放 \(num_x - 1\) 个其他数字

为了分出最少的子序列， 肯定要让每个子序列在拥有绝对众数的同时能消化尽量多的其他数字

由此， 可以得到一个贪心策略： 每次取出出现次数最多的一个数字， 消掉出现次数最少的那些数字

这个可以排序后双指针实现， 但是我选择细节更简单的线段树哈哈哈

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, INF = 1e18;

int n;
int a[N], maxi, cnt[N];
bool vis[N];

struct Seg_Tree{
    struct Node{
        int l, r;
        int maxi, maxps;
        int mini, minps;
    }t[2 * N];

    void Push_up(int id){
        int l = id * 2, r = id * 2 + 1;
        if(t[l].maxi > t[r].maxi){
            t[id].maxi = t[l].maxi;
            t[id].maxps = t[l].maxps;
        }else{
            t[id].maxi = t[r].maxi;
            t[id].maxps = t[r].maxps;
        }

        if(t[l].mini < t[r].mini){
            t[id].mini = t[l].mini;
            t[id].minps = t[l].minps;
        }else{
            t[id].mini = t[r].mini;
            t[id].minps = t[r].minps;
        }        
    }

    void Build(int id, int l, int r){
        t[id].l = l, t[id].r = r;
        if(l == r){
            if(!cnt[l]){
                t[id].maxi = -INF, t[id].maxps = l;
                t[id].mini = INF, t[id].minps = l;
            }else{
                t[id].maxi = cnt[l], t[id].maxps = l;
                t[id].mini = cnt[l], t[id].minps = l;
            }
            return;
        }
        int mid = (l + r) / 2;
        Build(id * 2, l, mid);
        Build(id * 2 + 1, mid + 1, r);
        Push_up(id);
    }

    void Modify(int id, int l, int r, int v){
        if(r < t[id].l || t[id].r < l){
            return;
        }
        if(l <= t[id].l && t[id].r <= r){
            t[id].maxi += v;
            t[id].mini += v;
            if(!t[id].maxi){
                t[id].maxi = -INF;
                t[id].mini = INF;
            }
            return;
        }
        Modify(id * 2, l, r, v);
        Modify(id * 2 + 1, l, r, v);
        Push_up(id);
    }
}tr;

signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        ++cnt[a[i]];
        maxi = a[i] > maxi ? a[i] : maxi;
    }

    tr.Build(1, 1, maxi);

    int cnt = 0;
    while(true){
        int mxi = tr.t[1].maxi;
        int mxps = tr.t[1].maxps;
        if(mxi == -INF) break;
        ++cnt;
        
        tr.Modify(1, mxps, mxps, -mxi);
        int sum = 0, lim = mxi - 1;
        while(true){
            int mni = tr.t[1].mini;
            int mnps = tr.t[1].minps;
            if(mni == INF) break;
            if(sum + mni <= lim){
                sum += mni;
                tr.Modify(1, mnps, mnps, -mni);
            }else{
                int delta = lim - sum;
                tr.Modify(1, mnps, mnps, -delta);
                break;
            }
        }
    }
    cout << cnt << "\n";
}

B

非常巧妙的转化

思路

每个中心点在 上/下、 左/右 的选择可以视作独立的

意思就是在合法（要选择的点没有被占用）的情况下， 上/下 可以任选一个点， 左/右 同理， 相互之间没有影响

然后设计一种建边方式， 表示我们在这两个点（上/下， 左/右）中的选择

在 上和下， 左和右 之间连一条边（如果一方不合法， 那就往自己连边； 如果两方都不合法， 那就无解）， 然后给边定向

设有向边 \((u, v)\) 表示我们在 \((u, v)\) 之中选择了 \(u\)， 对此的限制是 ： 每个点只能有一个出度（只能被选择一次）

分连通块讨论， 设当前连通块点数为 \(n\)， 边数为 \(m\)

  1. \(m > n\) 无解， 因为每条边对应一个出度， 这样每个点不可能只有一个出度
  2. \(m < n\)， 此时因为是连通块， 所以一定有 \(m = n - 1\)， 是一棵树。 以每个点为根都有一种定向方案， 所以方案数为 \(n\)
  3. \(m = n\)， 这时是一颗基环树， 分环和树 考虑。在环上， 有顺时针、 逆时针 \(2\) 种方案（自环只有 \(1\) 种， 特判）， 在树上， 每个根节点的入度已经有了， 所以方案固定。 方案数为 \(2\)

完结

代码

其实本题暴搜分连通块考虑， 加上剪枝是可以过的哈哈哈

剪枝代码不放了， 这里是正解

注意并查集大小是 \(n^2\)， 在网格图问题中一定注意数组是 \(O(n)\) 还是 \(O(n^2)\)， 我因为这个挂了 28 pts

#include<bits/stdc++.h>
#define int long long
#define Pii pair <int, int>
using namespace std;
const int N = 1e3 + 10, MOD = 1e9 + 7;

int n, m;
int e[N][N], id[N][N], cid;
char s[N];

struct Ufs{
    int s[N * N] ,cnte[N * N], si[N * N], tg[N * N];

    void Init(int x){
        for(int i = 1; i <= x; i++){
            s[i] = i;
            cnte[i] = 0;
            si[i] = 1;
        }
    }

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

signed main(){
    cin >> n >> m;

    st.Init(n * m);
    for(int i = 1; i <= n; i++){
        cin >> (s + 1);
        for(int j = 1; j <= m; j++){
            e[i][j] = s[j] - '0';
            id[i][j] = ++cid;
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(e[i][j] == 1){
                int fa = 0, fb = 0;

                if(i != 1 && !e[i - 1][j]){
                    fa = st.Find(id[i - 1][j]);
                    fb = fa;
                }
                if(i != n && !e[i + 1][j]){
                    fb = st.Find(id[i + 1][j]);
                    if(!fa) fa = fb;
                }
                if(fa == fb){
                    ++st.cnte[fa];
                    st.tg[fa] = 1;
                }else{
                    st.si[fa] += st.si[fb];
                    st.cnte[fa] += st.cnte[fb] + 1;
                    st.tg[fa] |= st.tg[fb];
                    st.s[fb] = fa;
                }

                if(!fa && !fb){
                    cout << "0\n";
                    return 0;
                }                

                fa = 0, fb = 0;
                if(j != 1 && !e[i][j - 1]){
                    fa = st.Find(id[i][j - 1]);
                    fb = fa;
                }
                if(j != m && !e[i][j + 1]){
                    fb = st.Find(id[i][j + 1]);
                    if(!fa) fa = fb;
                }

                if(!fa && !fb){
                    cout << "0\n";
                    return 0;
                }

                if(fa == fb){
                    ++st.cnte[fa];
                    st.tg[fa] = 1;
                }else{
                    st.si[fa] += st.si[fb];
                    st.cnte[fa] += st.cnte[fb] + 1;
                    st.tg[fa] |= st.tg[fb];
                    st.s[fb] = fa;
                }                
            }
        }
    }    

    int ans = 1;
    for(int i = 1; i <= cid; i++){
        if(st.Find(i) == i){
            int f = st.Find(i);
            if(st.si[f] < st.cnte[f]){
                cout << "0\n";
                return 0;
            }
            if(st.si[f] == st.cnte[f]){
                if(st.tg[f]){
                    ans *= 1;
                }else{
                    (ans *= 2) %= MOD;
                }
            }else{
                (ans *= st.si[f]) %= MOD;
            }
        }
    }
    cout << ans << "\n";
}

C

正解要 CDQ 处理三维偏序， MnZn 写不出来， 这里只介绍结论证明

思路

有一个 一眼看上去就不对 的结论： 如果一个区间 \([l, r]\) 有 \(ka\) 个 \(0\) 和 \(kb\) 个 \(1\)， 那么他是可以被删掉的， 贡献的次数为 \(k\)

证明：

要证 「若\(len_{l, r} = ka + kb\) 就能删完」， 只需证 「该区间至少能进行一次删除」， 然后转化为 \(len_{l, r} = (k - 1)a + (k - 1)b\) 的子问题

把 \(l, r\) 分成 \(k\) 段长为 \(a + b\) 的段

若有一段内满足 \(a' = a, b' = b\) 那就直接完事了

否则一定有相邻的两段， 一段 \(a' > a\) ， 另一端 \(a' < a\)， 那一个长度为 \(a + b\) 的滑动窗口放在上面

因为每次 \(a'\) 的变化量为 \(0\) 或 \(1\)， 所以 \(a'\) 的变化函数一定是连续的

根据零点存在性定理（好像是必修一的）， 由 \(a' > a\) 到 \(a' < a\)， 一定会经过 \(a' = a\) 的点， 所以该区间一定能删至少一次

然后简单的 \(n^2\) DP 就可以获得 88 pts

咱也不知道 MX 数据咋造的

代码

部分分的

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, INF = 1e18;

int n, a, b;
int sa[N], sb[N], dp[N];
char t[N];

signed main(){
	cin >> a >> b >> (t + 1);
	n = strlen(t + 1);

	for(int i = 1; i <= n; i++){
		sa[i] = sa[i - 1];
		sb[i] = sb[i - 1];
		if(t[i] == '0') ++sa[i];
		if(t[i] == '1') ++sb[i];
	}

	int len = a + b;
	for(int i = 1; i <= n; i++){
		dp[i] = dp[i - 1];
		for(int k = 1; k * len <= i; k++){
			if(sa[i] - sa[i - k * len] <= k * a && sb[i] - sb[i - k * len] <= k * b){
				dp[i] = dp[i - k * len] + k > dp[i] ? dp[i - k * len] + k : dp[i];
			}
		}
	}
	cout << dp[n] << "\n";
}

D - P9514

思路

要往模 \(d\) 的余数上考虑， 这是一定的

还发现我们的矩阵最大就是 \(d * d\) 的， 这样一定可以囊括所有的图案

先观察 I, II 类图案的排列方式

I 的就是从初始点开始， 横坐标每隔 d 有一个， 纵坐标每隔 d 有一个（可能表述不严谨， 可以看题面的样例解释）， 所以我们的 \(d * d\) 矩阵包含且仅能包含一个

II 的就是每隔 d 有一列， 每隔 d 有一行

要我们求一个类似最大子矩阵的问题， 复杂度在 \(n^2\) 左右， 考虑分别枚举 \(x, y\) 方向

先枚举 \(l_x\)， 根据上面的观察， 贪心地来选 \(r_x\) 最小是 \([l, l + d - 1]\) 中最晚出现的 I 类图案的横坐标

然后再考虑 \(y\) 方向， 这里只需考虑 \(mod\ d\) 意义下的， 在 \(y\) 轴上构成一个环状结构（使用滑动窗口， 在 \(y\) 轴上取出任意一段长度为 \(d\) 的都可以）， 最小的长度就是环上断开一条最长的、 上面没有图案的边

对于每一个「不被 I 类图案覆盖、 并且 \(S_j\) 等于他的所有的 II 类图案都已经被第一种方案（\(R_j\) 覆盖完毕了」 的 \(y\) ， 我们可以把他删掉， 否则存到对应的最大的 \(R_j\)中， 因为这个 II 类图案我们还没有满足， 还要用到这个 \(y\)

再考虑扩大 \(r\) ， 使得剩下的 II 类也被满足

从小往大枚举 \(r\)， 每次删掉已经满足条件的 \(y\) ， 取 min 即可

代码

#include<bits/stdc++.h>
#define int long long
#define Pii pair <int, int>
using namespace std;
const int N = 5e3 + 10, M = 5e5 + 10, INF = 1e9;

int n, m, d;
int p[M], q[M], r[M], s[M];
int lstps[N][N * 2];
bool visx[N], visy[N];
vector <int> ps[N * 2];

struct List{
    int pre[N], nxt[N], len, hd, tl;

    void Init(){
        for(int i = 0; i < d; i++){
            pre[i] = i - 1;
            nxt[i] = i + 1;
        }
        hd = 0, tl = d - 1;
        len = INF;
    }

    void Del(int x){
        int l = pre[x], r = nxt[x];
        
        if(l != -1) nxt[l] = r;
        if(r != d) pre[r] = l;

        if(pre[r] == -1) hd = r;
        if(nxt[l] == d) tl = l;

        if(l != -1 && r != d){
            len = min(len, d - (r - l) + 1);
        }
    }
}lst;

signed main(){
    cin >> n >> m >> d;
    for(int i = 1; i <= n; i++){
        cin >> p[i] >> q[i];
        visx[p[i]] = 1;
        visy[q[i]] = 1;
    }
    for(int i = 1; i <= m; i++){
        cin >> r[i] >> s[i];
        lstps[s[i]][r[i]] = r[i];
        lstps[s[i]][r[i] + d] = r[i] + d;
    }

    for(int i = 0; i < d; i++){
        for(int j = 1; j < 2 * d; j++){
            lstps[i][j] = max(lstps[i][j], lstps[i][j - 1]);
        }
    }

    int ans = d * d;
    for(int l = 0; l <= d; l++){
        int r = 0;
        for(int j = l + d - 1; j >= 0; j--){
            if(visx[j % d]){
                r = j;
                break;
            }
        }

        lst.Init();
        for(int y = 0; y < d; y++){
            if(!visy[y]){
                if(lstps[y][l + d - 1] < r){
                    lst.Del(y);
                }else{
                    ps[lstps[y][l + d - 1]].push_back(y);
                }
            }
        }

        for(int j = r; j <= l + d - 1; j++){
            for(auto k : ps[j]){
                lst.Del(k);
            }
            ans = min(ans, (j - l + 1) * min(lst.len, (lst.tl - lst.hd + 1)));
            ps[j].clear();
        }
    }
    cout << ans << "\n";
}

标签：mini,int,题解,08,09,maxi,INF,id,lstps
From： https://www.cnblogs.com/Bubblee/p/18351999

相关文章

  • P1725 琪露诺 题解
    思路动态规划，单调队列动态规划观察题目，发现下标为\(i\)的点只能对\([i+l,i+r]\)区间的点产生贡献。设\(f_i\)为到达点\(i\)时的最大冻结指数。易得状态转移方程式：\(f_k\leftarrow\max(f_k,f_i+a_k),(k\in[i+l,i+r])\)。若直接对该方程进行转移，时间复......
  • AT_abc208_d 题解
    题目传送门做完这道题后感觉对Floyd的理解更深了。根据题面要求，设\(f(k,i,j)\)表示从\(i\)到\(j\)的所有只经过\(1\simk\)的点的所有路径的最短距离。很明显\(k\)那一维是阶段，因为它描述了从\(i\)到\(j\)路径中的不同点，而我们就是根据这一条件来划分集合，这......
  • CF908D New Year and Arbitrary Arrangement 题解
    Description给定\(k,pa,pb\)，有一初始为空的序列。每次有\(\dfrac{pa}{pa+pb}\)的概率往序列后面加一个a。每次有\(\dfrac{pb}{pa+pb}\)的概率往序列后面加一个b。当出现大于等于\(k\)个形如ab的子序列（a和b不一定相邻）时停止。求序列最终的ab子序列期望数。So......
  • 【保奖思路】2024年华为杯研究生数学建模D题解题思路分享（点个关注，后续会更新
    您的点赞收藏是我继续更新的最大动力！一定要点击如下的卡片链接，那是获取资料的入口！点击链接加入群聊【2024华为杯研赛资料汇】：http://qm.qq.com/cgi-bin/qm/qr?_wv=1027&k=MwNruKbEvR9aZns1l7xXBWmQQKYAEh-F&authKey=igaBN79pz6BhNlDQ6TIZ5YFAbn71aDcYL77uANPquLF%2FTVgeSAhE......
  • 【保奖思路】2024年华为杯研究生数学建模D题解题思路分享（点个关注，后续会更新
    您的点赞收藏是我继续更新的最大动力！一定要点击如下的卡片链接，那是获取资料的入口！点击链接加入群聊【2024华为杯研赛资料汇】：http://qm.qq.com/cgi-bin/qm/qr?_wv=1027&k=MwNruKbEvR9aZns1l7xXBWmQQKYAEh-F&authKey=igaBN79pz6BhNlDQ6TIZ5YFAbn71aDcYL77uANPquLF%2FTVgeSAhE......
  • CF1984G Magic Trick II 题解
    前记第一篇黑题题解。难调。好写。码量不大。Description给定一个大小为nnn的排列pp......
  • AGC001 题解
    目录A-BBQEasyB-MysteriousLightC-ShortenDiameterA-BBQEasy先将\(2N\)个数排序，从大到小考虑，最大的数一定不会产生贡献，次大的数可以和最大的数捆绑在一起，并产生贡献，以此类推，这样的贪心正确性还是较为显然的。#include<bits/stdc++.h>#definelllonglongusin......
  • CF1999F.Expected Median 题解
    一.前言这是一道很有趣的数学题目，用到了逆元和组合数学，非常适合新手练手。二.题目大意：给出一个长度为\(n\)的\(01\)数组。找出所有长度为\(k\)的子序列的中位数，求出其和。妥妥的数学题~三.分析首先考虑对答案的贡献。很明显，只有\(1\)作为中位数时才会做出贡献，于是......
  • CF908G New Year and Original Order 题解
    CF908C定义\(S(n)\)为将\(n\)所有数位从小到大排序后得到的数，求\(\sum_{i=1}^{n}S(i)\)\(1\leqn\leq10^{700}\)看到这个题大部分人都会奔着数位\(dp\)的地方想但这个题的难度在于插入一个数后不好算贡献其实也挺好算的\(dp\)维护当前若干数字排完序......
  • CF641E Little Artem and Time Machine 题解
    题目传送门前置知识CDQ分治解法单点修改区间查询，但值域巨大，考虑离散化掉\(x\)。时刻\(t\)仍很大，考虑将其作为CDQ分治的第一维，然后套个CDQ分治即可，注意及时清空桶数组。代码CodeForces275382150#include<bits/stdc++.h>usingnamespacestd;#definelllonglon......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99