力扣301周赛C~DABC299 D、E、G

第 301 场周赛

C:

 

思路:

经典双指针问题,用i表示字符串start当前枚举到的位置,用j表示字符串target当前枚举到的位置:

  1. i从当前位置向后跑,跑到start串下标i之后的第一个不为'_'的位置

  2. j从当前位置向后跑,跑到target串下标j之后的第一个不为'_'的位置

  3. 判断start[i]与target[j]是否相同,如果不同,指定是无解了。

  4. 如果当前start[i]=='L'时,应该是i>=j,如果是'R'则应该是i<=j,否则无解。

  5. 检查i<n and j<n,如果满足,返回步骤1,重复执行操作,否则进行步骤6

  6. 如果i<n-1,检查start,同理检查target字符串,之后的字符应全是'_'

    代码:

    class Solution:
        def canChange(self, start: str, target: str) -> bool:
            n=len(start)
            i=j=0
            while i<n and j<n:
                while i<n and start[i]=='_':
                    i+=1
                while j<n and target[j]=='_':
                    j+=1
                if i<n and j<n:
                    if start[i]!=target[j]:
                        return False
                    c=start[i]
                    if c=='L' and i<j or c=='R' and i>j:
                        return False
                    i+=1
                    j+=1
            while i<n:
                if start[i]!='_':
                    return False
                i+=1
            while j<n:
                if target[j]!='_':
                    return False
                j+=1
            return True

D:

 

思路:

不会,参考题解

数学 & 递推,附复杂度与 n 无关(klogk)的做法:

2338. 统计理想数组的数目 - 力扣(LeetCode)

代码

class Solution {
    const int MOD=1e9+7;
    const int MAXP=16;
​
public:
​
    int idealArrays(int n, int K) {
        //nlnn求因数
        vector<vector<int>>fac(K+1);
        for(int i=1;i<=K;i++){
            for(int j=i<<1;j<=K;j+=i){
                fac[j].push_back(i);
            }
        }
​
        //计算子问题答案,f[i][j]表示以i为结束元素,长度为j的方案个数,长度为j的序列元素两两不同
        vector<vector<long long>>f;
        f.resize(K+1,vector<long long>(20));
        for(int i=1;i<=K;i++){
            f[i][1]=1;
            for(int j=2;j<=MAXP;j++){
                for(int t:fac[i]){
                    f[i][j]=(f[i][j]+f[t][j-1])%MOD;
                }
            }
        }    
​
        //求组合数
        vector<vector<long long>>C;
        C.resize(n+1,vector<long long>(20));
​
        C[0][0]=C[1][0]=C[1][1]=1;
        for(int i=2;i<=n;i++){
            C[i][0]=1;
            for(int j=1;j<=i&&j<=MAXP;j++){
                C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
            }
        }
​
        //统计最终答案
​
        long long ans=0;
        for(int i=1;i<=K;i++){//终点
            for(int j=1;j<=MAXP;j++){//选几个数
                ans=(ans+C[n-1][j-1]*f[i][j])%MOD;
                //最终元素为i,从n个元素里面选取长度为j的不重复元素,将这j个不重复元素确定好位置,这个长度为n
                //的序列就确定了,那么第一个最小的元素肯定在位置1,那剩下来的n-1个位置,放置j-1个数就行了
                //因为最终元素为i,长度为j的序列中元素两两不同的方案书为f[i][j],选取的位置有C[n-1][j-1]
                //所以乘法原理即可
            }
        }
        return ans;
    }
};

ABC299

D - Find by Query

题目大意:

 

 

思路:

看到最多询问20次,长度为2e5,首先想到的应该是二分,怎么二分呢?

注意到S[1]='0',S[N]='1',那么每次查询中间的位置,如果query(l+r>>1)=='0',那就令l=l+r>>1,否则r=l+r>>1

,这样就能时刻保证S[l]='0',S[r]='1'

代码:

#include <bits/stdc++.h>
​
using namespace std;
​
int main()
{
    int n;
    cin >> n;
    int l = 1, r = n;
    int cnt = 20;
    while (cnt > 0)
    {
        cnt--;
        int mid = l + r >> 1;
        cout << "? " << mid << endl;
        char x;
        cin >> x;
        if (l + 1 == mid && x == '1')
        {
            cout << "! " << l << endl;
            return 0;
        }
        if (mid + 1 == r && x == '0')
        {
            cout << "! " << mid << endl;
            return 0;
        }
        if (x == '0')
        {
            l = mid;
        }
        else
        {
            r = mid;
        }
    }
    return 0;
}

E - Nearest Black Vertex

题目大意:

 

思路:

  1. 首先建图,然后跑最短路,堆优化迪杰斯特拉的时间复杂度为O(M*log(N)),但是这个题边权全为1,就不需要堆优化了,普通队列即可,所以求以每一个点s(1<=s<=n)为起点到其他点的最短路径的时间复杂度为O(NM)

  2. 读入k个限制,u,d,遍历以u为起点,到其他点(下面用v表示)的最短路径,如果

    dist[ u ][ v ] < d

    ,则这个点不可能是黑色点,标记

  3. 全部标记完之后,再次遍历k个限制,遍历每个限制是否有解即可

    即寻找dist[u][v]==d,是否有点满足,并且这个点v没有被标记为不能做为黑色点

    代码:代码写的与思路有一点不一样,我的代码在读入限制的时候就判断他有没有可行点解了,就是

dist[u][v]==d是否存在,如果已经找到一个点不满足就不接着做了,直接输出No即可,现在看来有点鸡肋了,即使这样做,等k个限制跑完之后,仍然需要再次跑k个限制看看是否满足条件,因为假如你
u1,找到某个唯一可以当作黑色点的v1,此时这个v1还没有被标记为不能当作黑点
接下来限制u2 d的时候,把v1标记做了不能当作黑点,只遍历一遍是不行的也就是说如果说只有这两个限制,只跑一边会输出Yes,然后输出可行解,但实际是No,因为u1的唯一可以当作黑点的v1被u2 hcak掉了
#include <bits/stdc++.h>
using namespace std;
​
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define PII pair<int, int>
#define de(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
#define endl "\n"
#define int long long
#define LL long long
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
​
vector<int> edge[N];
int dist[2005][2005];
int n, m;
void dijkstra(int s)
{
    vector<int> vis(n + 1, 0);
    dist[s][s] = 0;
    queue<int> q;
    q.push(s);
    while (q.size())
    {
        int t = q.front();
        q.pop();
        if (vis[t])
            continue;
        vis[t] = true;
        for (auto v : edge[t])
        {
            if (dist[s][v] > dist[s][t] + 1)
            {
                dist[s][v] = dist[s][t] + 1;
                q.push(v);
            }
        }
    }
}
​
void solve()
{
​
    cin >> n >> m;
    for (int i = 0; i <= n + 1; i++)
    {
        for (int j = 0; j <= n + 1; j++)
        {
            dist[i][j] = INT64_MAX;
        }
    }
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
    {
        dijkstra(i);
    }
    int k;
    vector<int> st(n + 1, 1);
    cin >> k;
    vector<PII> query;
    bool ok = true;
    for (int i = 0; i < k; i++)
    {
        int u, d;
        cin >> u >> d;
        query.emplace_back(u, d);
        bool f = 0;
        for (int v = 1; v <= n; v++)
        {
            if (dist[u][v] < d)
            {
                st[v] = 0; // 不能为黑色
            }
            else if (dist[u][v] == d && st[v] == 1) // 找到合法黑色点了
            {
                f = 1;
            }
        }
        if (!f) // 这个点u没有合法点当u
            ok = 0;
    }
​
    for (int i = 0; i < k; i++)
    {
        auto [u, d] = query.back();
        query.pop_back();
        bool f = 0;
        for (int v = 1; v <= n; v++)
        {
            if (dist[u][v] < d)
            {
                st[v] = 0; // 不能为黑色
            }
            else if (dist[u][v] == d && st[v] == 1) // 找到合法黑色点了
            {
                f = 1;
            }
        }
        if (!f) // 这个点u没有合法点当u
            ok = 0;
    }
​
    if (ok)
    {
        cout << "Yes\n";
        for (int i = 1; i <= n; i++)
        {
            cout << st[i];
        }
    }
    else
    {
        cout << "No\n";
    }
}
​
signed main()
{
    FAST;
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
​
    return 0;
}

G - Minimum Permutation

题目:

有一个长度为 N 的序列,保证其中包含1~M,请你找到一个长M的子序列,使得其中每个数字都出现了一次,并使得排列的字典序最小。

思路:

贪心。考虑单调栈(定义s[i]表示栈中第i个元素是什么,tt表示现在的栈顶元素所在的位置),顺序枚举这个长度为N的序列。

假如我们现在处理第i个元素,那么前i-1个元素已经处理好了,对于第i个元素a[i],

  • 如果a[i]在栈里,直接跳过就行了

  • a[i]>s[tt](栈顶),直接加到栈里面就可以了

  • a[i]<s[tt](栈顶),判断当前栈顶所在元素在 [i +1~n]在后面是否出现过,如果出现过,可以放心的把栈顶去掉了,循环次操作,然后将a[i]加入栈顶就可以了。这样一定是正确的,因为我们去掉栈顶的条件是栈顶小于当前元素(保证字典序更小),后面出现过当前栈顶(保证后面可以把这个删去的栈顶加进来)

    #include <bits/stdc++.h>
    using namespace std;
    ​
    #define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
    #define PII pair<int, int>
    #define de(a) cout << #a << " = " << a << "\n";
    #define deg(a) cout << #a << " = " << a << " ";
    #define endl "\n"
    #define int long long
    #define LL long long
    const int mod = 1e9 + 7;
    const int N = 1e6 + 5;
    int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
    ​
    int n, m, a[N], s[N], tt, d[N];
    bool st[N];
    ​
    void solve()
    {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            d[a[i]]++;
        }
        for (int i = 1; i <= n; i++)
        {
            d[a[i]]--; // 这个数字出现过了一次
            if (st[a[i]])
                continue;
            while (s[tt] > a[i] && d[s[tt]]) // 栈顶大于当前元素,并且栈顶的元素在后面还有
                st[s[tt]] = 0, tt--;
            s[++tt] = a[i];
            st[a[i]] = 1;
        }
        for (int i = 1; i <= m; i++)
        {
            cout << s[i] << ' ';
        }
    }
    ​
    signed main()
    {
        FAST;
        int t = 1;
        // cin >> t;
        while (t--)
            solve();
    ​
        return 0;
    }

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/77654.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

node获取抖音直播间Id

node获取抖音直播间Id 信息位置 直播间信息存放在id是RENDER_DATA的script标签里 安装依赖 npm install fetch cheerio # 或 pnpm install fetch cheerionode代码 // room.js const fetch require("fetch"); const cheerio require("cheerio"); // co…

Qt读写Excel--QXlsx编译为静态库2

1、概述&#x1f954; 在使用QXlsx时由于源码文件比较多&#xff0c;如果直接加载进项目里面&#xff0c;会增加每次编译的时间&#xff1b; 直接将源码加载进项目工程中&#xff0c;会导致项目文件非常多&#xff0c;结构变得更加臃肿&#xff1b; 所以在本文中将会将QXlsx编译…

什么是字体堆栈(font stack)?如何设置字体堆栈?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 什么是字体堆栈&#xff08;Font Stack&#xff09;&#xff1f;⭐ 如何设置字体堆栈&#xff1f;⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 …

解密人工智能:线性回归 | 逻辑回归 | SVM

文章目录 1、机器学习算法简介1.1 机器学习算法包含的两个步骤1.2 机器学习算法的分类 2、线性回归算法2.1 线性回归的假设是什么&#xff1f;2.2 如何确定线性回归模型的拟合优度&#xff1f;2.3 如何处理线性回归中的异常值&#xff1f; 3、逻辑回归算法3.1 什么是逻辑函数?…

解析Python爬虫常见异常及处理方法

作为专业爬虫程序猿长期混迹于爬虫ip解决方案中&#xff0c;我们经常会遇到各种各样的异常情况。在爬虫开发过程中&#xff0c;处理这些异常是不可或缺的一部分。本文将为大家总结常见的Python爬虫异常&#xff0c;并分享相应的处理方法&#xff0c;帮助你避免绊倒在爬虫之路上…

题目:售货员的难题(状压dp)

售货员的难题 题目描述输入输出格式输入格式&#xff1a;输出格式&#xff1a; 输入输出样例输入样例#1&#xff1a;输出样例#1&#xff1a; 思路AC代码&#xff1a; 题目描述 某乡有n个村庄( 1 < n < 16 )&#xff0c;有一个售货员&#xff0c;他要到各个村庄去售货&am…

每天一道leetcode:433. 最小基因变化(图论中等广度优先遍历)

今日份题目&#xff1a; 基因序列可以表示为一条由 8 个字符组成的字符串&#xff0c;其中每个字符都是 A、C、G 和 T 之一。 假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。 例如&#xff0c;&quo…

数据结构----哈夫曼树

这里写目录标题 基本概念引子基本概念各种路径长度各种带权路径长度结点的带权路径长度树的带权路径长度哈夫曼树 哈夫曼树的构造理论基础构造思想总结 哈夫曼树的实现哈夫曼编码前缀编码哈夫曼编码的思想案例代码实现 编码与解码 基本概念 引子 哈夫曼树就是寻找构造最优二叉…

k8s RBAC授权普通系统用户对namespace访问权限

背景&#xff1a;最近遇到一个问题&#xff0c;那就是需要给别人共享一下 Kubernetes 的某个资源的使用和访问权限&#xff0c;这个仅仅存在于某个 namespace 下&#xff0c;但是我又不能把管理员权限全都给它&#xff0c;我想只给他授予这一个 Namespace 下的权限&#xff0c;…

OpenShift 4 - 基于 MinIO 安装 Red Hat Quay 镜像仓库

《OpenShift / RHEL / DevSecOps 汇总目录》 说明&#xff1a;本文已经在 OpenShift 4.13 Quay 3.9 的环境中验证 本文适合在单机 OpenShift 环境安装 Red Hat Quay 镜像仓库。 另外《OpenShift 4 - 安装 ODF 并部署红帽 Quay (1 Worker)》也可以在单节点部署。 而《OpenShif…

分布式版本控制系统(一)

分布式版本控制系统(一) 目录 分布式版本控制系统(一) 1、Git、Github、Gitlab 的区别2、Git 与 SVN 区别3、Git工作流程4、Git基本概念5、Git 客户端安装使用 5.1 git-server安装配置5.2 git-client配置免密登录git服务器5.3 文本编辑器5.4 差异分析工具5.5 查看配置信息5.6 常…

基于IMX6ULLmini的linux裸机开发系列一:汇编点亮LED

思来想去还是决定记录一下点灯&#xff0c;毕竟万物皆点灯嘛 编程步骤 使能GPIO时钟 设置引脚复用为GPIO 设置引脚属性(上下拉、速率、驱动能力) 控制GPIO引脚输出高低电平 使能GPIO时钟 其实和32差不多 先找到控制LED灯的引脚&#xff0c;也就是原理图 文件名 C:/Us…

动态内存分配及管理——C语言

目录 一、为什么存在动态内存分配 二、动态内存函数介绍 2.1 malloc 2.2 free 2.3 calloc 2.4 realloc 三、常见的动态内存错误 3.1 对NULL指针的解引用操作 3.2 对动态开辟空间的越界访问 3.3 对非动态开辟内存使用free释放 3.4 使用free释放一块动态开辟内存的一部…

Vue3 Vuex状态管理多组件传递数据简单应用

去官网学习→安装 | Vuex cd 项目 安装 Vuex&#xff1a; npm install --save vuex 或着 创建项目时勾选Vuex vue create vue-demo ? Please pick a preset: Manually select features ? Check the features needed for your project: (Press <space> to se…

Web3 solidity订单池操作

前面一篇文章因为一些原因 被设为了进自己可见 需要的朋友可以私信我 之前 我们编写的程序上来看 交易所无非是一个代币的托管上 只是它会更加专业 本文 我们继续来看交易所的一个功能 叫游泳池 例如 我们 100grToken 兑换 1ETH 前提 我们的代币已经能被估值了 例如 你想用人…

【JVM】如何判定一个对象已死以及“标记-清除”、“标记-复制”、“标记-整理”三种垃圾收集算法

文章目录 0、如何判定一个对象的生死&#xff1f;1、上文提到的引用又是什么1、强引用&#xff1a;2、软引用&#xff1a;3、弱引用&#xff1a;4、虚引用&#xff1a; 2、垃圾收集算法1、标记-清除2、标记-复制优化&#xff1a;&#x1f447; 3、标记-整理 0、如何判定一个对象…

item_password-获得淘口令真实url

一、接口参数说明&#xff1a; item_password-获得淘口令真实url &#xff0c;点击更多API调试&#xff0c;请移步注册API账号点击获取测试key和secret 公共参数 请求地址: https://api-gw.onebound.cn/taobao/item_password 名称类型必须描述keyString是调用key&#xff08…

用cpolar生成的公网地址,对位于本地的Cloudreve网盘进行访问

文章目录 1、前言2、本地网站搭建2.1 环境使用2.2 支持组件选择2.3 网页安装2.4 测试和使用2.5 问题解决 3、本地网页发布3.1 cpolar云端设置3.2 cpolar本地设置 4、公网访问测试5、结语 1、前言 自云存储概念兴起已经有段时间了&#xff0c;各互联网大厂也纷纷加入战局&#…

Springboot集成ip2region离线IP地名映射-修订版

title: Springboot集成ip2region离线IP地名映射 date: 2020-12-16 11:15:34 categories: springboot description: Springboot集成ip2region离线IP地名映射 1. 背景2. 集成 2.1. 步骤2.2. 样例2.3. 响应实例DataBlock2.4. 响应实例RegionAddress 3. 打开浏览器4. 源码地址&…

米尔瑞萨RZ/G2L开发板-02 ffmpeg的使用和RTMP直播

最近不知道是不是熬夜太多&#xff0c;然后记忆力减退了&#xff1f; 因为板子回来以后我就迫不及待的试了一下板子&#xff0c;然后发现板子有SSH&#xff0c;但是并没有ffmpeg&#xff0c;最近总是在玩&#xff0c;然后今天说是把板子还原一下哇&#xff0c;然后把官方的固件…