第五届上海市青少年算法竞赛 T5 最大的余数(折半查找)

第五题:T5最大的余数

标签:折半查找
题意:给定 n n n个数字 a 1 , a 2 , … , a n a_1,a_2,…,a_n a1,a2,,an,在给定一个整数 m m m,请从给定的数字中挑选任意多个数字,使得它们的和模 m m m的余数尽量大,输出这个最大的余数。 ( 1 ≤ n ≤ 40 , 1 ≤ a i ≤ 1 0 9 , 1 ≤ m ≤ 1 0 9 ) (1≤n≤40,1≤a_i≤10^9,1≤m≤10^9) (1n401ai1091m109)
题解:一看到 n ≤ 40 n≤40 n40,下意识就是折半查找,因为暴力搜索 2 40 ≈ 1 0 12 2^{40}≈10^{12} 2401012,肯定会超时。把问题折半一下,分别预处理出各自一半的数的组成情况,时间复杂度是 2 ∗ 2 20 ≈ 2 ∗ 1 0 6 2*2^{20}≈2*10^6 22202106
比如样例: 1    10    100    1000    10000 1 \ \ 10 \ \ 100 \ \ 1000 \ \ 10000 1  10  100  1000  10000
前两个的所有情况之和为 0    1    10    11 0 \ \ 1 \ \ 10 \ \ 11 0  1  10  11
后三个的所有情况之和为 0    100    1000    10000    1100    10100    11000    11100 0 \ \ 100 \ \ 1000 \ \ 10000 \ \ 1100 \ \ 10100 \ \ 11000 \ \ 11100 0  100  1000  10000  1100  10100  11000  11100
前半部分搜索出来的所有情况的值存到 b b b数组中,后半部分搜索出来的所以情况存到 c c c数组中。
要找出前半部分 + + +后半部分对 m m m进行取模余数尽可能大的。那我们可以枚举前半部分的所有情况,然后二分查找( l o w e r _ b o u n d lower\_bound lower_bound)一下后半部分中 m − b [ i ] m-b[i] mb[i]的值,找到的是第一个大于等于 m − b [ i ] m-b[i] mb[i]的,所以往前减一位即可。
代码

#include <bits/stdc++.h>
using namespace std;

int n, m, a[50], ans = 0;
vector<int> b, c;
void dfs1(int p, int sum) {
    if (p == n / 2 + 1) {
        b.push_back(sum);
        return ;
    }
    dfs1(p + 1, (sum + a[p]) % m);
    dfs1(p + 1, sum % m);
}

void dfs2(int p, int sum) {
    if (p == n + 1) {
        c.push_back(sum);
        return ;
    }
    dfs2(p + 1, (sum + a[p]) % m);
    dfs2(p + 1, sum % m);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] %= m;
    }
    dfs1(1, 0);
    dfs2(n / 2 + 1, 0);
    sort(c.begin(), c.end());
    for (int i = 0; i < b.size(); i++) {
        int p = lower_bound(c.begin(), c.end(), m - b[i]) - c.begin();
        p--;
        ans = max(ans, (b[i] + c[p]) % m);
    }
    cout << ans << endl;
    return 0;
}

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

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

相关文章

LeetCode in Python 200. Number of islands (岛屿数量)

岛屿数量既可以用深度优先搜索也可以用广度优先搜索解决&#xff0c;本文给出两种方法的代码实现。 示例&#xff1a; 图1 岛屿数量输入输出示意图 方法一&#xff1a;广度优先搜索(bfs) 代码&#xff1a; class Solution:def numIslands(self, grid):if not grid:return 0…

【WSL报错】执行:wsl --list --online;错误:0x80072ee7

【WSL报错】执行:wsl --list --online&#xff1b;错误:0x80072ee7 问题情况解决方法详细过程 问题情况 C:\Users\17569>wsl --list --online 错误: 0x80072ee7 解决方法 开系统代理&#xff0c;到外网即可修复&#xff01;&#xff01;&#xff01;&#xff01;&#x…

Yolov8项目实践——基于yolov8与OpenCV实现目标物体运动热力图

概述 在数据驱动和定位的世界中&#xff0c;对数据进行解释、可视化和决策的能力变得日益重要。这表明&#xff0c;使用正确的工具和技术可能是项目成功的关键。在计算机视觉领域&#xff0c;存在许多技术来解释从视频&#xff08;包括录像、流媒体或实时视频&#xff09;中获…

「 网络安全常用术语解读 」软件成分分析SCA详解:从发展背景到技术原理再到业界常用检测工具推荐

软件成分分析&#xff08;Software Composition Analysis&#xff0c;SCA&#xff09;是一种用于识别和分析软件内部组件及其关系的技术&#xff0c;旨在帮助开发人员更好地了解和管理其软件的构建过程&#xff0c;同时可帮助安全人员揭秘软件内部结构的神秘面纱。SCA技术的发展…

递归、搜索与回溯算法:回溯,决策树

回溯算法是⼀种经典的递归算法&#xff0c;通常⽤于解决组合问题、排列问题和搜索问题等。 回溯算法的基本思想&#xff1a;从⼀个初始状态开始&#xff0c;按照⼀定的规则向前搜索&#xff0c;当搜索到某个状态⽆法前进时&#xff0c;回退到前⼀个状态&#xff0c;再按照其他…

【计算机组成原理】运算方法和运算器

数据与文字的表示方法 1. 数据格式1.1 定点数表示方法1.1.1 定点小数1.1.2 定点整数 1.2 浮点数表示方法1.2.1 浮点数表示1.2.2 浮点数的规格化1.2.2.1 尾数为原码表示的规格化1.2.2.2 尾数为补码表示的规格化 1.2.3 IEEE754标准⭐ 1.3 十进制数串的表示方法1.3.1 字符串形式1.…

网盘——私聊

在私聊这个功能实现中&#xff0c;具体步骤如下&#xff1a; 1、实现步骤&#xff1a; A、客户端A发送私聊信息请求&#xff08;发送的信息包括双方的用户名&#xff0c;聊天信息&#xff09; B、如果双方在线则直接转发给B&#xff0c;不在线则回复私聊失败&#xff0c;对方…

ProgressFlowmon的confluence接口存在任意命令执行漏洞(CVE-2024-2389)

声明&#xff1a; 本文仅用于技术交流&#xff0c;请勿用于非法用途 由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;文章作者不为此承担任何责任。 简介 ProgressFlowmon是一整套用于网络映射、应用程序性能…

客户端动态降级系统

本文字数&#xff1a;4576字 预计阅读时间&#xff1a;20分钟 01 背景 无论是iOS还是Android系统的设备&#xff0c;在线上运行时受硬件、网络环境、代码质量等多方面因素影响&#xff0c;可能会导致性能问题&#xff0c;这一类问题有些在开发阶段是发现不了的。如何在线上始终…

大气的免费wordpress模板

国产的wordpress模板&#xff0c;更适合中国人使用习惯&#xff0c;更符合中国老板的审美的大气wordpress企业官网建站模板。 WordPress模板&#xff0c;也称为主题&#xff0c;是用于定义WordPress网站或博客外观和功能的预设计文件集。这些模板使用HTML、CSS和PHP代码构建&a…

上传文件到HDFS

1.创建文件夹 hdfs -dfs -mkdir -p /opt/mydoc 2.查看创建的文件夹 hdfs -dfs -ls /opt 注意改文件夹是创建在hdfs中的&#xff0c;不是本地&#xff0c;查看本地/opt&#xff0c;并没有该文件夹。 3.上传文件 hdfs dfs -put -f file:///usr/local/testspark.txt hdfs://m…

【深度学习】Vision Transformer

一、Vision Transformer Vision Transformer (ViT)将Transformer应用在了CV领域。在学习它之前&#xff0c;需要了解ResNet、LayerNorm、Multi-Head Self-Attention。 ViT的结构图如下&#xff1a; 如图所示&#xff0c;ViT主要包括Embedding、Encoder、Head三大部分。Class …

Docker in Docker的原理与实战

Docker in Docker&#xff08;简称DinD&#xff09;是一种在Docker容器内部运行另一个Docker实例的技术。这种技术允许用户在一个隔离的Docker容器中创建、管理和运行其他Docker容器&#xff0c;从而提供了更灵活和可控的部署选项。以下是DinD的主要特点&#xff1a; 隔离性&am…

力扣打卡第一天

101. 对称二叉树 C&#xff1a; class Solution { public:bool isSymmetric(TreeNode* root) {return check(root->left,root->right);}bool check(TreeNode *p,TreeNode *q){ /**定义check方法用来检查两棵树是否是镜像的*/if (!p && !q) return true; /* 如…

基于SSM的物流快递管理系统(含源码+sql+视频导入教程+文档+PPT)

&#x1f449;文末查看项目功能视频演示获取源码sql脚本视频导入教程视频 1 、功能描述 基于SSM的物流快递管理系统2拥有三个角色&#xff1a; 管理员&#xff1a;用户管理、管理员管理、新闻公告管理、留言管理、取件预约管理、收件管理、货物分类管理、发件信息管理等 用户…

如何安全、高速、有效地利用IP代理爬取数据

陈老老老板&#x1f9d9;‍♂️ &#x1f46e;‍♂️本文专栏&#xff1a;生活&#xff08;主要讲一下自己生活相关的内容&#xff09;生活就像海洋,只有意志坚强的人,才能到达彼岸。 &#x1f934;本文简述&#xff1a;如何安全、高速、有效地利用IP代理爬取数据 &#x1f473…

【数据结构-串-数组-广义表】

目录 1 串-理解1.1 串的抽象定义&#xff1a;-理解1.2 串的存储结构-不断掌握1.2.1 顺序存储结构&#xff1a;1.2.2 链式存储结构&#xff1a; 1.3 串的模式匹配算法&#xff1a;-掌握1.3.1 BF暴力求解算法-代码 -掌握1.3.2 KMP求解算法-代码--掌握 2 数组-不断掌握2.1 顺序存储…

WWW ‘24 | EarnMore: 如何利用强化学习来处理可定制股票池中的投资组合管理问题

WWW 24 | EarnMore: 如何利用强化学习来处理可定制股票池中的投资组合管理问题 原创 QuantML QuantML 2024-04-16 09:04 上海 Content 本文主要探讨了如何利用强化学习&#xff08;Reinforcement Learning, RL&#xff09;来处理可定制股票池&#xff08;Customizable Stock …

Golang | Leetcode Golang题解之第40题组合总和II

题目&#xff1a; 题解&#xff1a; func combinationSum2(candidates []int, target int) (ans [][]int) {sort.Ints(candidates)var freq [][2]intfor _, num : range candidates {if freq nil || num ! freq[len(freq)-1][0] {freq append(freq, [2]int{num, 1})} else {…

LabVIEW卡尔曼滤波技术

LabVIEW卡尔曼滤波技术 在现代航空导航中&#xff0c;高精度和快速响应的方位解算对于航空安全至关重要。通过LabVIEW平台实现一种卡尔曼滤波方位解算修正技术&#xff0c;以改善传统导航设备在方位解算中的噪声干扰问题&#xff0c;从而提高其解算精度和效率。通过LabVIEW的强…