首页 > 其他分享 >周赛

周赛

时间:2024-12-02 09:57:12浏览次数:4  
标签:周赛 cnt int sum vector ans 节点

Leetcode 周赛复盘

第426场周赛

100501. 仅含置位位的最小整数

Easy. 只需要不断将1向左移,直到大于该数即可,返回此时的数-1。

class Solution {
public:
    int smallestNumber(int n) {
        int i=1;
        while(i <= n)
            i <<= 1;
        return i-1;
            
    }
};

100444. 识别数组中的最大异常值

Medium.
不要慌,首先思考一下,寻找到异常值后,会出现剩下的元素之和等于其中一个元素。这样我们的和肯定是偶数。那么,只需要在累加的时候统计一下数字出现的情况,然后:

  1. 判断和是否为偶数。
  2. 一个个挑选出异常值,然后判断和的一半是否存在。存在的情况包括:(1)和的一半与异常值相同且异常值出现了不止一次。(2)和的一半与异常值不同且出现了一次。
  3. 直到最后找到最大的异常值即可。
class Solution {
public:
    int getLargestOutlier(vector<int>& nums) {
        int sum = 0;
        vector<int> cal(2005,0);
        for(auto i:nums)
            {
                cal[i+1000] ++;
                sum += i;
            }
        int ans = -2005;
        for(auto i:nums)
            {
                sum -= i;
                if(sum % 2 != 0) 
                {
                    sum+=i;
                    continue;
                }
                int temp = sum / 2;
                if(temp+1000 >= 0 && temp+1000 <= 2000 && cal[temp+1000])
                {
                    if(temp == i && cal[temp+1000] > 1 || temp != i)
                        ans = (ans > i) ? ans : i;
                }
                sum += i;
            }
        return ans;
    }
};

100475. 连接两棵树后最大目标节点数目

参考:灵神的题解,膜拜大佬orz

首先很明显,要加边的端点在第一棵树上必然是端点i。
接下来需要考虑第二棵树上应该添加到哪个节点。暴力枚举第二个节点。DFS计算距离\(j\)不超过\(k-1\)的节点个数\(cnt_j\)。要注意新添加的边,所以是\(k-1\)。\(cnt_j\)取得最大值,记为\(max_2\)。新添加的边连接到其对应的节点上。

暴力枚举第一棵树节点i,DFS计算距离i不超过k的节点个数。则有\(cnt_i+cnt_j\)为答案。

class Solution {
public:
    vector<vector<int> > buildGraph(vector<vector<int> > & edges)
    {
        // 建立无向图邻接链表。
        vector<vector<int> > g(edges.size() + 1); // 边数
        for (auto &e: edges)
        {
            int v1 = e[0];
            int v2 = e[1];
            g[v1].push_back(v2);
            g[v2].push_back(v1);
        }
        return g;
    }
    int dfs(int cur, int pa, int dist, vector<vector<int> >&g, int k)
    {
        // dfs 终点。
        if(dist > k)
            return 0;
        // 计数:当前状态为1.
        int cnt = 1;
        for(int next:g[cur])
        {
            // 无向图:下一个节点和上一个节点不形成环。递归累加。
            if(next != pa)
                cnt += dfs(next, cur, dist+1, g, k);
        }
        return cnt;
    }
    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {
        int max2 = 0;
        if(k > 0)
        {
            vector<vector<int> > graph2 = buildGraph(edges2);
            for(int i = 0; i < edges2.size()+1; i++)
                max2 = max(max2, dfs(i, -1, 0, graph2, k-1));
        }
        vector<vector<int> > graph1 = buildGraph(edges1);
        vector<int> ans(edges1.size() + 1);
        for(int i = 0; i < ans.size(); i++)
            ans[i] = dfs(i,-1,0,graph1,k) + max2;
        return ans;
    }
};

标签:周赛,cnt,int,sum,vector,ans,节点
From: https://www.cnblogs.com/mumujun12345/p/18581046

相关文章

  • 牛客周赛 Round 70(A~F)
    比赛链接:是的,这次我还是没有AK,F题写了快一小时20多分钟,E题快写了20多分钟,没时间做G了A.小苯晨跑题面:现在正在晨跑的小苯面前有四个数据,他想知道这些数据是否乱飞了,请你帮他确定吧。(如果所有数据都相等,则认为数据没有乱飞,反之则乱飞了。)输入:本题含有多组测试数据。第一行......
  • 425 周赛第2题 3365. 重排子字符串以形成目标字符串
     给你两个字符串 s 和 t(它们互为字母异位词),以及一个整数 k。你的任务是判断是否可以将字符串 s 分割成 k 个等长的子字符串,然后重新排列这些子字符串,并以任意顺序连接它们,使得最终得到的新字符串与给定的字符串 t 相匹配。如果可以做到,返回 true;否则,返回 false。......
  • 牛客周赛 Round 69
    构造C的歪思路取\(|a-b|+\max(a,b)\)即可构造第三项。代码#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);inta,b;cin>>a>>b;intd=abs(......
  • 牛客周赛 Round 69(A~E)
    文章目录A构造C的歪思路codeB不要三句号的歪思路codeC仰望水面的歪思路codeD小心火烛的歪思路codeE喜欢切数组的红思路code牛客周赛Round69A构造C的歪思路签到题,求出公差d,让最大的数加上公差d即可code inta,b; cin>>a>>b; intk=max(a,b)-mi......
  • 河南工大2024新生周赛(5)——命题人:刘庭铄
    本次比赛题目难度:easy:I,Dmedium-easy:H,L,Emedium:B,Jmediumhard:A,Ghard:C, F题为算法板子题,不计入难度表  A.阿拉德的冒险者遍历的路线已经确定(1~n),只需要从1到n遍历一遍,将各自需要消耗的生命力排序后放入另一数组中,由于数据较小,每次重新......
  • 牛客周赛 Round 69
    题解赛时做题A入门题等差数列,找公差,构造第三个即可B题意简单,考察字符串转化成数字C几何题,大概初中难度,用全等或者向量都可以(初做时废了半天劲,果然上了大学就废了赛后补题D纯暴力,但是可以收获的有两点将二维转化成一维处理bitset的使用和二进制操作__builtin_popco......
  • 【牛客训练记录】牛客周赛 Round 69
    训练情况赛后反思好吧,D题没想到二进制枚举,以为\(O(2^knm)\)不可做。。。A题要求要等差数列,我们先求公差,为两元素的最大值-最小值,再在最大值的基础上加上公差即可。#include<bits/stdc++.h>//#defineintlonglong#defineendl'\n'usingnamespacestd;voidsol......
  • 牛客周赛 Round 69(A~E)
    https://ac.nowcoder.com/acm/contest/96115#question真难过,一个小时竟然做不出F。没想到F是线段树的变式,我还想开7,8个树状数组进行维护,直接秀逗了。要做大物作业,先丢个题解吧A.构造C的歪#include<iostream>#include<queue>#include<map>#include<set>#include<vector>#in......
  • 425 周赛第一题 3364. 最小正和子数组
       给你一个整数数组 nums 和 两个 整数 l 和 r。你的任务是找到一个长度在 l 和 r 之间(包含)且和大于0的 子数组 的 最小 和。返回满足条件的子数组的 最小 和。如果不存在这样的子数组,则返回-1。子数组 是数组中的一个连续 非空 元素序列。 示......
  • 牛客周赛63(C++实现)
    ......