头像

HYL_7

广东科技学院




离线:2小时前


最近来访(83)
用户头像
yxc的小迷妹
用户头像
G.E.M
用户头像
JiuCherish
用户头像
夜语声烦
用户头像
yxc的小迷妹1
用户头像
keahixie
用户头像
wangjw
用户头像
Cretaceous
用户头像
o樱桃小完犊子o
用户头像
周摆摆
用户头像
ZJY_ET
用户头像
Stargazing_9
用户头像
Vebb.
用户头像
加加加油_然君
用户头像
我要偷偷卷
用户头像
闲云雾野
用户头像
TYF
用户头像
Seven_Study
用户头像
Tsuki
用户头像
yxc


HYL_7
8小时前

题目解析

  1. 给我们一列数,每一列数都是 $1~2000$ 的范围内
  2. 选取一个$F$,$F$是至少挑出多少个次数的值,即$F = 5$,则可以挑选$≥5$次
  3. 样例分析: 6 4 2 10 3 8 5 9 4 1 至少挑6次,平均值 = 6.5
    划分结果为 10 3 8 5 9 4 ,注意最后的数需要下取整,因为如果要四舍五入的话这个数可能太大我们无法取到

数据长度:$1≤N≤100000$

时间复杂度

  1. 初步分析为:$O(logn)$ ~ $O(n)$
  2. 前缀和、二分都是$O(n)$的时间复杂度$O(n * logL)$ $L$是答案的范围

思路:

  1. 如果我们通过取得平均值为 $mid$ 的情况下,是否为一种合法方案,也就是问我们在原序列当中存不存在一段连续的子序列,它的平均值能够 $≥mid$
  2. 注意这里有个常用技巧:将所有的数都减去一个 $mid$ 得出新的序列
  3. 这个问题就变成了存不存在一个连续的子段是否都 $≥ 0$ ,这里就变成了最优化转换为判定问题
  4. 可设该子段的最后一个数为 $j$ ,第一个数的前一个数为 $i$ ,该子序列和长度要满足 $≥F$ ,那么这个子序列的和可以用 $sum[j]-sum[i] ≥ 0$ 表示,为满足最大值,那么我们就要让$sum[i]$尽可能达到最小,$sum[j]$尽可能达到最大
  5. $sum[j]-sum[i] ≥ 0$ 可得 $sum[j] ≥ sum[i]$ 。根据这个式子,这个问题也就变成了 $[0,j-F]$ 的序列和sum[i] 是否满足 $sum[j] ≥ sum[i]$

代码


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n,m;
int cows[N];
double sum[N];

bool check(double avg)
{
    for(int i = 1; i <= n ; i ++) sum[i] = sum[i - 1] + cows[i] - avg;//每个数变成它本身减去平均数
    double minv = 0; //定义一个最小值
    for(int i = 0,j = m; j <= n;j ++ ,i ++)
    {
        minv = min(minv,sum[i]);
        if(sum[j] >= minv) return true;
    }
    return false;
}

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

    for(int i = 1; i <= n ; i ++) cin >> cows[i];
    double l = 0,r = 2000;
    while(r - l > 1e-5)
    {
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }

    printf("%d\n",int(r * 1000));

    return 0;
}


活动打卡代码 AcWing 102. 最佳牛围栏

HYL_7
8小时前

题目解析

  1. 给我们一列数,每一列数都是 $1~2000$ 的范围内
  2. 选取一个$F$,$F$是至少挑出多少个次数的值,即$F = 5$,则可以挑选$≥5$次
  3. 样例分析: 6 4 2 10 3 8 5 9 4 1 至少挑6次,平均值 = 6.5
    划分结果为 10 3 8 5 9 4 ,注意最后的数需要下取整,因为如果要四舍五入的话这个数可能太大我们无法取到

数据长度:$1≤N≤100000$

时间复杂度

  1. 初步分析为:$O(logn)$ ~ $O(n)$
  2. 前缀和、二分都是$O(n)$的时间复杂度$O(n * logL)$ $L$是答案的范围

思路:

  1. 如果我们通过取得平均值为 $mid$ 的情况下,是否为一种合法方案,也就是问我们在原序列当中存不存在一段连续的子序列,它的平均值能够 $≥mid$
  2. 注意这里有个常用技巧:将所有的数都减去一个 $mid$ 得出新的序列
  3. 这个问题就变成了存不存在一个连续的子段是否都 $≥ 0$ ,这里就变成了最优化转换为判定问题
  4. 可设该子段的最后一个数为 $j$ ,第一个数的前一个数为 $i$ ,该子序列和长度要满足 $≥F$ ,那么这个子序列的和可以用 $sum[j]-sum[i] ≥ 0$ 表示,为满足最大值,那么我们就要让$sum[i]$尽可能达到最小,$sum[j]$尽可能达到最大
  5. $sum[j]-sum[i] ≥ 0$ 可得 $sum[j] ≥ sum[i]$ 。根据这个式子,这个问题也就变成了 $[0,j-F]$ 的序列和sum[i] 是否满足 $sum[j] ≥ sum[i]$

代码


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n,m;
int cows[N];
double sum[N];

bool check(double avg)
{
    for(int i = 1; i <= n ; i ++) sum[i] = sum[i - 1] + cows[i] - avg;//每个数变成它本身减去平均数
    double minv = 0; //定义一个最小值
    for(int i = 0,j = m; j <= n;j ++ ,i ++)
    {
        minv = min(minv,sum[i]);
        if(sum[j] >= minv) return true;
    }
    return false;
}

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

    for(int i = 1; i <= n ; i ++) cin >> cows[i];
    double l = 0,r = 2000;
    while(r - l > 1e-5)
    {
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }

    printf("%d\n",int(r * 1000));

    return 0;
}


活动打卡代码 AcWing 113. 特殊排序

HYL_7
9小时前

题目

https://www.acwing.com/problem/content/115/

对题目的理解

  1. 不具有传递性:$a < b, b < c$ 不能推出 $a < c$
  2. 具有反对称性:$a > b$ 可以推出 $b < a$
  3. $a_1,a_2,…,a_n$
    使得每一个数都满足以下性质:$a_i$ < $a_i+1$
    4.最多只能询问10000次,那么说明时间复杂度为 $O(log n)$

思路

  1. 基于插入排序的框架:先写一段循环使其形成一个特殊的单调排序,这个排序只满足$a_i$ < $a_{i+1}$,并不能保证是一个严格单调递增的序列
  2. 接下来要解决的问题在于如果给定一个$i$,如何快速将其插入这个序列当中
    将这个序列的左边界和右边界分别设为$-∞$和$+∞$
    设这个序列的中点设为 $m$
  3. 如果$a_{m} > i$, $a_{m-1} < i$ ,那么$i$在这两者之间,相应的如果$a_{m-2} < i$, 那么 $i$在$a_{m-2}$和$a_{m}$之间,所以从后往前查找,第一个小于$i$的数,则将其插入这个区间
  4. 同理 $a_{m} < i$ ,此时 $a_{m}$ 必然是第一个小于$i$的数,则$a_{m-1} > i$,$i$ 应该放在$a_{m}$与$a_{m-1}$之间

代码

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res;
        res.push_back(1);//先插入1,后面的元素就能和1比较
        for(int i = 2; i <= N; i ++)
        {
            int l = 0,r = res.size() - 1;
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(compare(res[mid],i)) l = mid;
                else r = mid - 1;
            }
            res.push_back(i);
            for(int j = res.size() - 2; j > r; j --) swap(res[j],res[j + 1]);
            //r返回的是小于待插入元素x的最大元素的位置,r + 1位置的元素是大于x的,目标就是将x放在r位置的后面
            //从后往前不断交换相邻的两个数直到待插入的元素到达指定位置
            if(compare(i,res[r])) swap(res[r],res[r + 1]);
            //如果说i比res[r]还要小,那么只能交换i与res[r]的位置,以达到最小的状态
        }
        return res;
    }
};


活动打卡代码 AcWing 1636. 最低公共祖先

HYL_7
8天前
/*
    前:6 3 1 2 5 4 8 7 
    中:1 2 3 4 5 6 7 8 

         6     -------0
      3     8  -------1
    1   5 7    -------2
     2 4       -------3

    找公共祖先LCA:
        比如找2和7的公共祖先
            每次将比较低的那个点往上移动一格,
                然后判断移动后的那个点所在的层次是否相遇另外一个点
                    如果两个点在同个层次的话,那么两个点同时往上走对应一格
                        直到两个点走到了相同的一个值,则该值为它们的公共祖先

    这里有两个存储问题:
        每一个点的深度是多少,每一个点的父节点是多少
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 10010;

int n,m;
int in[N],pre[N],seq[N]; // 中序遍历,前序遍历,整个的序列
                         // in和pre是离散化后的值,seq存的是原来的数值
unordered_map<int,int> pos; //主要起到离散化的作用
int p[N],depth[N];

int build(int il,int ir,int pl,int pr,int d)
{
    int root = pre[pl];
    int k = root;

    depth[root] = d;

    if(il < k) p[build(il,k - 1,pl + 1,pl + 1 + (k - 1 - il),d + 1)] = root;
    if(k < ir) p[build(k + 1,ir,pl + 1 + (k  - 1 - il) + 1,pr,d + 1)] = root;

    return root;
}

int main()
{
    cin >> m >> n;
    for(int i = 0 ; i < n ; i ++)//读入前序遍历的结果
    {
        cin >> pre[i];
        seq[i] = pre[i];
    }

    sort(seq,seq + n);
    //先把映射的值得出中序遍历
    for(int i = 0 ; i < n ; i ++)
    {
        pos[seq[i]] = i;
        in[i] = i;
    }

    //再将之前的前序遍历转为中序遍历
    for(int i = 0 ; i < n ; i ++) pre[i] = pos[pre[i]];

    //重建二叉树
    build(0,n - 1,0,n - 1,0);

    while (m -- )
    {
        int a,b;
        cin >> a >> b;

        if(pos.count(a) && pos.count(b))//a和b同时存在的时候
        {
            a = pos[a],b = pos[b];//先将a和b变成离散化后的值
            int x = a,y = b;//先进行缓存一下a和b,方便下次进行替换

            while(a != b)
                if(depth[a] < depth[b]) b = p[b];
                else a = p[a];

            if(a != x && a != y) printf("LCA of %d and %d is %d.\n",seq[x],seq[y],seq[a]);
            else if(a == x) printf("%d is an ancestor of %d.\n",seq[x],seq[y]);
            else printf("%d is an ancestor of %d.\n",seq[y],seq[x]);
        }
        else if(pos.count(a) == 0 && pos.count(b) == 0)
        {
            printf("ERROR: %d and %d are not found.\n",a,b);
        }
        else if(pos.count(a) == 0) printf("ERROR: %d is not found.\n",a);
        else if(pos.count(b) == 0) printf("ERROR: %d is not found.\n",b);
    }



    return 0;
}


活动打卡代码 AcWing 1623. 中缀表达式

HYL_7
8天前
/*
    中序遍历

    这道题不用考虑优先级的问题,但如果要考虑优先级的话
        如果说当前节点的优先级比左右儿子要高,那么左右儿子一定要加括号
        如果说当前节点的优先级比左右儿子要低,那么左右儿子不用加括号


*/

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 25;

int n;
int l[N],r[N];
string w[N];
bool st[N],is_leaf[N]; // 判断一下每个节点是否为叶节点

string dfs(int u)
{
    string left,right;
    if(l[u] != -1)
    {
        left = dfs(l[u]);
        if(!is_leaf[l[u]]) left = "(" + left + ")";
    }
    if(r[u] != -1)
    {
        right = dfs(r[u]);
        if(!is_leaf[r[u]]) right = "(" + right + ")";
    }
    return left + w[u] + right;
}

int main()
{
    cin >> n ;
    for(int i = 1; i <= n ;i ++)
    {
        cin >> w[i] >> l[i] >> r[i];
        if(l[i]) st[l[i]] = true;
        if(r[i]) st[r[i]] = true;

        if(l[i] == -1 && r[i] == -1) is_leaf[i] = true;
    }

    int root = 1;
    while(st[root]) root ++;

    cout << dfs(root) << endl;

    return 0;
}


活动打卡代码 AcWing 1649. 堆路径

HYL_7
8天前
/*
            98
        72      86
     60    65 12   23
  50     
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1010;

int n;
int h[N];
bool gt,lt;
vector<int>path;

void dfs(int u)
{
    path.push_back(h[u]);
    if(u * 2 > n) // 叶节点
    {
        cout << path[0];
        for(int i = 1; i < path.size(); i ++)
        {
            cout << ' ' << path[i];
            if(path[i] > path[i - 1]) gt = true;
            else if(path[i] < path[i - 1]) lt = true;
        }
        cout << endl;
    }
    if(u * 2 + 1 <= n) dfs(u * 2 + 1);
    if(u * 2 <= n) dfs(u * 2);


    path.pop_back();
}

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

    dfs(1);

    if(gt && lt) puts("Not Heap");
    else if(gt) puts("Min Heap");
    else puts("Max Heap");

    return 0;
}



HYL_7
8天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 1e5 + 10;

int n;
double P,R;
int p[N],f[N];//p是所有节点的父节点
bool is_leaf[N];

int dfs(int u)
{
    if(f[u] != -1) return f[u];
    if(p[u] == -1) return f[u] = 0;
    return f[u] = dfs(p[u]) + 1;
}

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

    memset(p,-1,sizeof p);

    for(int i = 0; i < n ; i ++)
    {
        int k;
        cin >> k;
        for(int j = 0 ;j < k ; j ++)
        {
            int son;
            cin >> son;
            p[son] = i;
        } 
        if(!k) is_leaf[i] = true;
    }

    memset(f,-1,sizeof f);

    int res = N ,cnt = 0;
    for(int i = 0 ; i < n ;i ++)
        if(is_leaf[i])
        {
            if(res > dfs(i)) res = dfs(i),cnt = 1;
            else if(res == dfs(i)) cnt ++;
        }

    printf("%.4lf %d\n",P * pow(1 + R / 100,res),cnt);

    return 0;
}



HYL_7
8天前
/*
    f[i]表示i到根的距离

*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 100010;

int n;
double P,R;
int p[N],f[N];

int dfs(int u)
{
    if(f[u] != -1) return f[u];
    if(p[u] == -1) return f[u] = 0;
    return f[u] = dfs(p[u]) + 1;
}


int main()
{
    cin >> n >> P >> R;
    for(int i = 0 ; i < n;i ++) cin >> p[i];

    memset(f,-1,sizeof f);

    int res = 0,cnt = 0;
    for(int i = 0 ; i < n ; i ++)
        if(dfs(i) > res)
        {
            res = dfs(i);
            cnt = 1;
        }
        else if(dfs(i) == res) cnt ++;

    printf("%.2lf %d\n",P * pow(1 + R / 100 ,res),cnt);

    return 0;
}



HYL_7
8天前
/*
    假设为三层,每一层都是相乘(1 + r)
        根节点都是供应商 p
        中间节点都是经销商 p*(1 + r)
        叶节点都是零售商 p*(1 + r)^2

    f[i] 表示i到根节点的距离

    dfs(u) ->记忆化搜索
    {
        if(f[u]已存在) return;
        if(u是root) return 0;
        return f[u] = dfs(p[u]) + 1;
    }
    用一个数组存储每个点的父节点即可
*/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 100010;

int n;
double P,R;
int p[N],f[N],c[N];

int dfs(int u)
{
    if(f[u] != -1) return f[u];

    if(p[u] == -1) return f[u] = 0;
    return f[u] = dfs(p[u]) + 1;
}

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

    memset(p,-1,sizeof p);
    for(int i = 0 ; i < n; i ++)
    {
        int k;
        cin >> k;
        for(int j = 0;j < k ; j ++)
        {
            int son;
            cin >> son;
            p[son] = i;
        }
        if(!k) cin >> c[i];
    }

    memset(f,-1,sizeof f);

    double res = 0;
    for(int i = 0; i < n ; i ++)
        if(c[i]) //记录一下所有相邻的点
            res += c[i] * P * pow(1 + R / 100,dfs(i));//pow函数返回p的幂次方,dfs返回i到根节点的距离

    printf("%.1lf\n",res);

    return 0;
}


活动打卡代码 AcWing 1608. 森林里的鸟

HYL_7
8天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;

int n;
int p[N];
int birds[10];//每张照片最多十只鸟
bool st[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d", &n);

    for(int i = 0; i < N ; i ++) p[i] = i;

    int cnt = 0;
    for(int i = 0;i < n ; i ++)
    {
        int k;
        scanf("%d", &k);

        for(int j = 0 ; j < k; j ++)//先将当前鸟的全部读出来
        {
            scanf("%d",&birds[j]);
            st[birds[j]] = true;

        }
        for(int j = 1;j < k ; j ++)//每次合并相邻两个,即该鸟合并前一个鸟,这里需要求一下合并多少次
        {
            int a = birds[j - 1],b = birds[j];
            a = find(a),b = find(b);
            if(a != b)
            {
                p[a] = b;
                cnt ++;
            }
        }
    }

    int tot = 0;
    for(int i = 0 ; i < N ; i ++) tot += st[i];

    printf("%d %d\n",tot - cnt,tot);

    int q;
    scanf("%d", &q);
    while(q --)
    {
        int a,b;
        scanf("%d%d", &a, &b);
        if(find(a) == find(b)) puts("Yes");
        else puts("No");
    }

    return 0;
}