codeforce#938 (div3) 题解

C. Inhabitant of the Deep Sea

数组第一个元素减一下，最后一个元素减一下，一共能减k次，问有多少元素能减到0.细节模拟我是傻逼，有问题建议直接看tc面像tc编程

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <set>
#include <map>
#include <queue>

#define IOS     ios::sync_with_stdio(0);cin.tie(0);
#define mem(A,B) memset(A,B,sizeof(A));
#define rep(index,start,end) for(int index = start;index < end; index ++)
#define drep(index,start,end) for(int index = start;index >= end; index --)

using namespace std;

typedef long long ll;

const int maxn = 2e5+5;

int n;
ll k;
ll store[maxn];
int main() {
    IOS
    
    int t;
    cin>>t;
    while(t--) {
        cin>>n>>k;
        rep(i,0,n) cin>>store[i];
        
        ll m_right = k/2LL;
        ll m_left = m_right + k % 2LL;
        int ans = 0;
        int inf = 0, sup = n-1;
        while((m_right>0 || m_left>0) && inf<=sup) {
            if (inf == sup) {
                if (m_right + m_left >= store[inf]) {
                    ans ++;
                }
                break;
            }
            if (m_left >= store[inf]) {
                ans ++;
                m_left -= store[inf];
                inf ++;
            } else {
                store[inf] -= m_left;
                m_left = 0;
            }
            
            if (m_right >= store[sup]) {
                ans ++;
                m_right -= store[sup];
                sup --;
            } else {
                store[sup] -= m_right;
                m_right = 0;
            }
        }
        
        cout<<ans<<endl;
    }
    
    return 0;
}

D. Inaccurate Subsequence Search

给数组a和数组b，问a中有多少子数组在重排后有至少k个元素相同。

滑动窗口。首先遍历b得出有多少种字母以及每个字母有多少。然后滑动窗口维护窗口内字母的个数，窗口前进时pop首位push末尾，update维护信息，然后每次窗口移动进行对比是否符合条件
finish

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <set>
#include <map>
#include <queue>

#define IOS     ios::sync_with_stdio(0);cin.tie(0);
#define mem(A,B) memset(A,B,sizeof(A));
#define rep(index,start,end) for(int index = start;index < end; index ++)
#define drep(index,start,end) for(int index = start;index >= end; index --)

using namespace std;

typedef long long ll;

const int maxn = 2e5+5;

const int sub_maxn = 1e6+5;

int n,k,m;
int store[maxn], partten[maxn];
map<int,bool> matches;
map<int, int> used, have;
int main() {
    IOS
    
    int t;
    cin>>t;
    while(t--) {
        cin>>n>>m>>k;
        rep(i,0,n) cin>>store[i];
        rep(i,0,m) cin>>partten[i];
        
        matches.clear();
        used.clear();
        rep(i,0,m)
            if (matches[partten[i]]) {
                have[partten[i]] ++;
            } else {
                matches[partten[i]] = true;
                have[partten[i]] = 1;
            }
        
        int pos = 0,match_num = 0;
        int ans = 0;
        while(pos<n) {
            int num = store[pos];
            if (pos < m) {
                if (matches[num]) {
                    if(used[num] < have[num]) match_num ++;
                    used[num] ++;
                }
            } else {
//                cout<<"pos:"<<pos<<" match:"<<match_num<<endl;
                if (match_num >= k) {
                    ans ++;
                }
                // pop
                int pop_pos = pos - m;
                int pop_num = store[pop_pos];
                if (matches[pop_num]){
                    used[pop_num] --;
                    if (used[pop_num] < have[pop_num]) match_num --;
                }
                
                // push
                if (matches[num]) {
                    if(used[num] < have[num]) match_num ++;
                    used[num] ++;
                }
            }
            pos ++;
        }
        if (match_num >= k) ans ++;
        
        cout<<ans<<endl;
    }
    
    return 0;
}

E. Long Inversions

给出一个二进制序列s，每次可以选择长度为k的连续子列取反，问能让s的每一位都变成1的最大k是多少

枚举暴力k值，倒序遍历n，发现可以直接输出。毕竟 n 2 n^2 n2也不大。
然后再说下怎么验证可以让s全变1.当我们在s中发现一个0，那么肯定是要反转一次的，然后继续下一位，这样全部遍历一遍看还有没有0，没有就是可以

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <set>
#include <map>
#include <queue>

#define IOS     ios::sync_with_stdio(0);cin.tie(0);
#define mem(A,B) memset(A,B,sizeof(A));
#define rep(index,start,end) for(int index = start;index < end; index ++)
#define drep(index,start,end) for(int index = start;index >= end; index --)

using namespace std;

typedef long long ll;

const int maxn = 5e3+5;

string store;
bool check(int);
int main() {
    IOS
    
    int t;
    cin>>t;
    while(t--) {
        int n;
        cin>>n;
        cin>>store;
        
        int inf = n;
        drep(inf,n,0) {
            if(check(inf)) {
                cout<<inf<<endl;
                break;
            }
        }
    }
    
    return 0;
}
bool check(int k) {
    int pos = 0;
    int len = store.length();
    vector<int> cnt(len+1,0);
    int inv_cnt = 0;
    
    bool res = true;
    while(pos<len) {
        inv_cnt += cnt[pos];
        
        int num = store[pos] - '0';
        if (inv_cnt%2)
            num = num ^ 1;
        
        if (!num) {
            if (pos+k<=len) {
                inv_cnt ++;
                cnt[pos+k] = -1;
            } else {
                res = false;
                break;
            }
        }
        
        pos ++;
    }
    
    return res;

F. Unfair Game

给一堆1234，如果这些数XOR结果是0会赢，现在每次拿走一个，问最多能赢几次。

显然4和123不属于一类，单纯考虑4，那么就赢4的个数/2次。然后我们来看123.

记dp[i][j][k]为1个数为i个，2个数为j，3个数为k时赢的次数。初始dp[0][0][0]为0。当且仅当i个1，j个2，k个3XOR时dp[i][j][k] + 1(由于XOR性质，这里只需要判断奇偶再运算就可以)，转移方程
d p [ i ] [ j ] [ k ] = m a x ( d p [ i − 1 ] [ j ] [ k ] , d p [ i ] [ j − 1 ] [ k ] , d p [ i ] [ j ] [ k − 1 ] dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1] dp[i][j][k]=max(dp[i−1][j][k],dp[i][j−1][k],dp[i][j][k−1]

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <set>
#include <map>
#include <queue>

#define IOS     ios::sync_with_stdio(0);cin.tie(0);
#define mem(A,B) memset(A,B,sizeof(A));
#define rep(index,start,end) for(int index = start;index < end; index ++)
#define drep(index,start,end) for(int index = start;index >= end; index --)

using namespace std;

typedef long long ll;

int p[5];
int dp[205][205][205];
void pre();
int main() {
    IOS
    
    pre();
    
    int t;
    cin>>t;
    while(t--) {
        rep(i,0,4) cin>>p[i];
        
        int ans = p[3] / 2 + dp[p[0]][p[1]][p[2]];
        cout<<ans<<endl;
    }
    
    return 0;
}
void pre() {
    int lim = 201;
    dp[0][0][0] = -1;
    rep(i,0,lim) {
        rep(j,0,lim) {
            rep(k,0,lim) {
                if (i) dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]);
                if (j) dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k]);
                if (k) dp[i][j][k] = max(dp[i][j][k], dp[i][j][k-1]);
                
                int ans = ((i&1) * 1 ) ^ ((j&1) * 2) ^ ((k&1) * 3);
                if (!ans)
                    dp[i][j][k] ++;
            }
        }
    }
}

G. GCD on a grid

求从(1,1)到(n,m)的最大公约数。

这个题其实也是枚举，但是根据题意，答案一定是(1,1)和(n,m)公约数的因数。
然后我们拿着因数num对整个矩阵求余，看有没有一条路径从(1,1)到(n,m)上所有的元素都是num的倍数，如果有，那么就是候选答案，遍历所有因数后从候选答案选最大。
至于路径的查询用的dp。记dp[i][j]为(i,j)是否是因数num的倍数。当且仅当 s t o r e [ i ] [ j ] m o d    n u m store[i][j] \mod num store[i][j]modnum为true，转移方程
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] ∥ d p [ i ] [ j − 1 ] dp[i][j] = dp[i-1][j] \parallel dp[i][j-1] dp[i][j]=dp[i−1][j]∥dp[i][j−1]

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <set>
#include <map>
#include <queue>

#define IOS     ios::sync_with_stdio(0);cin.tie(0);
#define mem(A,B) memset(A,B,sizeof(A));
#define rep(index,start,end) for(int index = start;index < end; index ++)
#define drep(index,start,end) for(int index = start;index >= end; index --)

using namespace std;

typedef long long ll;

const int maxn = 128;

ll gcd(ll,ll);

int n,m;
int store[maxn][maxn];
bool dp[maxn][maxn];
void init();
void show();
bool check(int);
int main() {
    IOS
    
    int t;
    cin>>t;
    while(t--) {
        cin>>n>>m;
        rep(i,0,n) rep(j,0,m)
            cin>>store[i][j];
        
        int ans = 1;
        int num = gcd(store[0][0], store[n-1][m-1]);
        int lim = sqrt(num);
        for(int i=1;i*i<=num;i++) {
            if (num % i) continue;
            
            if (check(i)) {
                ans = max(ans, i);
            }
            if (check(num/i))
                ans = max(ans, num/i);
        }
        cout<<ans<<endl;
    }
    
    return 0;
}
ll gcd(ll a, ll b){
    ll t;
    while(b){
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}
void init() {
    rep(i,0,n) rep(j,0,m) dp[i][j] = false;
}
void show() {
    rep(i,0,n) {
        rep(j,0,m) cout<<dp[i][j]<<' ';
        cout<<endl;
    }
}
bool check(int num) {
    if (num == 1) return true;
    rep(i,0,n) {
        rep(j,0,m) {
            dp[i][j] = (store[i][j] % num) == 0;
            
            bool tmp = false;
            if (i && dp[i-1][j]) tmp = tmp || dp[i-1][j];
            if (j && dp[i][j-1]) tmp = tmp || dp[i][j-1];
            if (i || j) dp[i][j] = dp[i][j] && tmp;
        }
    }
    return dp[n-1][m-1];
}

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

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

相关文章

Vue按照顺序实现多级弹窗（附Demo）

Vue按照顺序实现多级弹窗（附Demo）

目录 前言1. 单个弹窗2. 多级弹窗 前言 强化各个知识点&#xff0c;以实战融合&#xff0c;以下两个Demo从实战提取 1. 单个弹窗 部署按钮框以及确定的方法即可 截图如下所示&#xff1a; 以下Demo整体逻辑如下&#xff1a; 点击“生成周月计划”按钮会触发showWeekPlanDia…
阅读更多...
FLIR LEPTON3.5 热像仪wifi 科研实验测温采集仪

FLIR LEPTON3.5 热像仪wifi 科研实验测温采集仪

点击查看详情!点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情 1、描述 这是一款桌面科研实验测温热成像多功能热像记录仪&#xff0c;小巧轻便…
阅读更多...
STM32微秒级别延时--F407--TIM1

STM32微秒级别延时--F407--TIM1

基本配置&#xff1a; TIM1挂载在APB2总线上&#xff0c;150MHz经过15分频&#xff0c;得到10MHz计数频率&#xff0c;由于disable了自动重装载&#xff0c;所以只需要看下一次计数值是多少即可。 void TIM1_Delay_us(uint16_t us) //使用阻塞方式进行延时&#xff0c;ARR值不…
阅读更多...
记录vue报错问题 in ./node_modules/axios/lib/platform/index.js

记录vue报错问题 in ./node_modules/axios/lib/platform/index.js

今天这个问题困扰了我许久 报错内容如下&#xff1a; 最初一直以为是我没装axios&#xff0c;又重新装了一次&#xff0c;后面才发现是axios版本原因&#xff0c;真的总是被版本的原因困住真的很烦 解决方法如下&#xff1a; 将axios的版本改为1.5.0 1、打开项目的文件夹“…
阅读更多...
Linux命令--查找占磁盘空间最大的文件

Linux命令--查找占磁盘空间最大的文件

原文网址&#xff1a;Linux命令--查找占磁盘空间最大的文件-CSDN博客 简介 本文介绍Linux怎样查找占磁盘空间最大的文件。 1.找到占空间最大的分区 命令 df -h 结果 2.查找分区里最大的文件 法1&#xff1a;直接查找最大的文件 sudo find my_folder -type f -exec du -…
阅读更多...
LangChain-RAG学习之 LangChain框架入门

LangChain-RAG学习之 LangChain框架入门

什么是LangChain LangChain是一个强大的框架&#xff0c;旨在帮助开发人员使用语言模型构建端到端的应用程序。它提供了一套工具、组件和接口&#xff0c;可简化创建由大型语言模型 (LLM) 和聊天模型提供支持的应用程序的过程。LangChain 可以轻松管理与语言模型的交互&#x…
阅读更多...
使用FastGPT+OneAPI在本地使用Llama3

使用FastGPT+OneAPI在本地使用Llama3

FastGPT 是一个基于 LLM 大语言模型的知识库问答系统&#xff0c;提供开箱即用的数据处理、模型调用等能力。同时可以通过 Flow 可视化进行工作流编排&#xff0c;从而实现复杂的问答场景&#xff01;他的重要特点就是工作流编排。 工作流编排&#xff1a;基于 Flow 模块的工作…
阅读更多...
OneNote导出白色背景文件时将笔记墨迹转换颜色

OneNote导出白色背景文件时将笔记墨迹转换颜色

今天用OneNote导出笔记时发现在文件上做的黑色墨迹笔记全部转成了白色。推测是因为onenote会根据背景色自动转换黑色和白色的墨迹&#xff0c;但是其他颜色好像导出的时候不会转换。 于是&#xff0c;我们首先要转换背景&#xff0c;将黑色背景转成白色背景&#xff0c; 然后将…
阅读更多...
国内各种免费AI聊天机器人(ChatGPT)推荐(中)

国内各种免费AI聊天机器人(ChatGPT)推荐(中)

作者主页&#xff1a;点击&#xff01; 国内免费AI推荐(ChatGPT)专栏&#xff1a;点击&#xff01; 创作时间&#xff1a;2024年4月29日15点20分 随着人工智能技术的不断发展&#xff0c;AI聊天机器人已经逐渐融入我们的日常生活。它们可以提供各种服务&#xff0c;例如聊天、…
阅读更多...
【数据结构】链表专题2

【数据结构】链表专题2

前言 本篇博客继续探讨有关链表的专题&#xff0c;这片博客的题&#xff0c;提前打个预防针&#xff0c;有点意思哦&#xff0c;哈哈哈&#xff0c;话不多说&#xff0c;进入正文 &#x1f493; 个人主页&#xff1a;小张同学zkf ⏩ 文章专栏&#xff1a;数据结构 若有问题 评论…
阅读更多...
【C语言】分支和循环（上）

【C语言】分支和循环（上）

【C语言】分支和循环&#xff08;上&#xff09; 1、if语句1.2 else1.3分支中包含多条语句1.4嵌套if1.5悬空else问题 2、关系操作符3、条件操作符4、逻辑操作符&#xff1a;与、或、非&#xff08;取反&#xff09;&#xff08;&&&#xff0c;||&#xff0c;&#xff0…
阅读更多...
小程序引入 Vant Weapp 极简教程

小程序引入 Vant Weapp 极简教程

一切以 Vant Weapp 官方文档 为准 Vant Weapp 官方文档 - 快速入手 1. 安装nodejs 前往官网下载安装即可 nodejs官网 安装好后 在命令行&#xff08;winr&#xff0c;输入cmd&#xff09;输入 node -v若显示版本信息&#xff0c;即为安装成功 2. 在 小程序根目录 命令行/终端…
阅读更多...
mac nvm install node＜version＞ error 404

mac nvm install node＜version＞ error 404

mac m2芯片遇到的问题&#xff0c;估计m系列的应该也有这个问题&#xff0c;在这里记录一下 解决方案&#xff1a; ## 需要先处理一下兼容就OK了arch -x86_64 zsh nvm install returns curl: (22) The requested URL returned error: 404 Issue #2667 nvm-sh/nvm GitHub
阅读更多...
关于YOLO8学习（五）安卓部署ncnn模型--视频检测

关于YOLO8学习（五）安卓部署ncnn模型--视频检测

前文 关于YOLO8学习（一）环境搭建，官方检测模型部署到手机 关于YOLO8学习（二）数据集收集，处理 关于YOLO8学习（三）训练自定义的数据集 关于YOLO8学习（四）模型转换为ncnn 简介 本文将会讲解： （1）使用前文生成的ncnn模型，部署到安卓端，并且实现视频中，人脸的检测…
阅读更多...
FileBird Pro插件下载：革新您的WordPress媒体库管理

FileBird Pro插件下载：革新您的WordPress媒体库管理

WordPress媒体库是您网站的重要组成部分&#xff0c;它存储了所有的图片、视频、文档等文件。但随着网站的扩展&#xff0c;媒体库的管理变得越来越复杂。FileBird Pro插件&#xff0c;作为一款专为WordPress用户设计的媒体库管理工具&#xff0c;以其直观的界面和强大的功能&a…
阅读更多...
【PowerJob】从源码编译到k8s部署

【PowerJob】从源码编译到k8s部署

前言 虽然PowerJob官方说支持JPA各种数据源&#xff0c;但在PG数据库的兼容性上&#xff0c;确实存在小问题&#xff0c;issue也有相关原理描述&#xff0c;官方采用的优雅方式并未真正解决问题&#xff0c;因为只解决了从Lob字段读取的时候&#xff0c;自动建表的时候还是会生…
阅读更多...
去哪儿网机票服务请求头pre逆向

去哪儿网机票服务请求头pre逆向

作者声明&#xff1a;文章仅供学习交流与参考&#xff01;严禁用于任何商业与非法用途&#xff01;否则由此产生的一切后果均与作者无关&#xff01;如有侵权&#xff0c;请联系作者本人进行删除&#xff01; url&#xff1a;aHR0cHM6Ly9tLmZsaWdodC5xdW5hci5jb20v 一、加密位…
阅读更多...
噪声嵌入提升语言模型微调性能

噪声嵌入提升语言模型微调性能

在自然语言处理&#xff08;NLP&#xff09;的快速发展中&#xff0c;大模型&#xff08;LLMs&#xff09;的微调技术一直是研究的热点。最近&#xff0c;一篇名为《NEFTUNE: NOISY EMBEDDINGS IMPROVE INSTRUCTION FINETUNING》的论文提出了一种新颖的方法&#xff0c;通过在训…
阅读更多...
网络基础-网络设备介绍

网络基础-网络设备介绍

本系列文章主要介绍思科、华为、华三三大厂商的网络设备 网络设备 网络设备是指用于构建和管理计算机网络的各种硬件设备和设备组件。以下是常见的网络设备类型&#xff1a; 路由器&#xff08;Router&#xff09;&#xff1a;用于连接不同网络并在它们之间转发数据包的设备…
阅读更多...
Unity 编辑器工具 - 资源引用查找器

Unity 编辑器工具 - 资源引用查找器

在Unity项目开发过程中&#xff0c;管理和维护资源之间的引用关系是至关重要的。当然我们项目也是需要这个功能 毕竟项目大了之后查找资源引用还是交给 资源引用查找器 比较好。 功能概述 资源引用查找器允许开发者选择一个目标资源&#xff0c;并在整个项目中查找引用了该资…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站