[CQUOJ 21412] 软妹币!软妹币!软妹币! (数学+DP)

news/2024/4/19 20:08:54/

CQUOJ - 21412
题意大致是,用若干不同的数中的某些数加减得到 1…n之间的所有数,需要的最少几个不同的数
赛上是找规律做的,虽然过了,但是感觉不太稳,赛后看了题解恍然大悟

首先有这样一个事实,如果有 3个数可以表示 1..13
那么对于小于 13的n,答案至多为 3
所以我们可以考虑,用 i个数能够构造出的最大的数是多少

设 dp[i]表示 i个数最大能表示 [1, dp[i]]
此时我想表示大于 dp[i]的数,就势必要加入一个大于 dp[i]的数,设为 x
则此时我可以额外表示 [x-dp[i], x+dp[i]]区间里的数,而这个区间可能和 [1, dp[i]]重合
为了使右端点最大,将 x不断向右移,直至 x-dp[i]=dp[i]+1,此时新增区间于原区间无公共点
所以 x=2*dp[i]+1,右端点为 3*dp[i]+1
所以加入 x后 i+1个数能表示 [1, 3*dp[i]+1]
转移方程:
1) dp[1]=1;
2) dp[i]=dp[i-1]*3+1

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef pair<int,int> Pii;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define LL long long
#define ULL unsigned long long
#define Pow2(a) a*a
int maxx(int a,int b){return a>b?a:b;}
int minn(int a,int b){return a<b?a:b;}
int abss(int a){return a<0?(-a):a;}int N;
int dp[13];int main()
{dp[1]=1;for(int i=1; i<13; i++) dp[i]=dp[i-1]*3+1;while(~scanf("%d", &N)){for(int i=1; i<13; i++){if(dp[i]>=N){printf("%d\n", i);break;}}}return 0;
}

http://www.ppmy.cn/news/727241.html

相关文章

软妹币!软妹币!软妹币!——重大4月月赛

Time Limit: 1000ms Memory Limit: 65536KB 64-bit integer IO format: %lld Java class name: Main Submit Status 大家都喜欢的软妹币面值是1、2、5、10&#xff0c;为什么是这个数值呢&#xff1f; 果姐姐作为一个软妹纸&#xff0c;分析了下发现&#xff0c;从1-10的每个数…

VS Code软妹音程序员鼓励师插件安装

Win10的VS Code位置&#xff1a;C:\Users\hao\AppData\Local\Programs\Microsoft VS Code\Code.exe 插件安装&#xff1a; https://saekiraku.github.io/vscode-rainbow-fart/#/zh/ Rainbow Fart 插件现以发布到 VSCode 商店&#xff0c;安装过 VSIX 版本的用户请卸载之前的版…

LIS系统源码 基于互联网技术的医院实验室信息管理系统源码

LIS系统&#xff0c;即实验室信息管理系统&#xff0c;是一种基于互联网技术的医疗行业管理系统&#xff0c;它可以帮助实验室进行样本管理、检测流程管理、结果报告等一系列工作&#xff0c;提高实验室工作效率和质量。下面将从LIS系统的功能、特点方面对其进行详细介绍。 一、…

springboot整合shiro实现认证和授权(非常详细)

Shiro和Spring Sercurity应该是我们比较常用的权限框架了&#xff0c;这篇文章教大家怎么通过springboot整合shiro从0开始搭建一个包含权限控制的后台管理系统。 第一步&#xff1a;创建一个springboot项目 创建springboot项目&#xff0c;这里项目就命名为shiro 第二步&#…

ROS学习之从yaml文件中读取多传感器坐标系之间的静态TF关系并发布Topic

文章目录 0 引言1 工作空间创建并初始化2 创建ROS程序包3 创建yaml读取函数3.1 yaml文件3.2 读取函数 4 创建静态TF关系的发布主函数5 创建launch文件6 编辑CMakeLists.txt7 编译运行7.1 编译7.2 运行 0 引言 机器人中经常使用多种传感器来做定位和建图&#xff0c;而多个传感…

显示器方案

概述&#xff1a; USB HUB连接Host与Device之间&#xff0c;可以扩展出多个USB设备接口&#xff0c;使得一个Host能同时与多个Device进行数据连接。 注&#xff1a;普遍而言&#xff0c;一颗HUB扩展芯片可扩展4个USB下行接口&#xff0c;市面上1 to 7的HUB&#xff0c;一般使用…

qq聊天框代码

弹出QQ为12345的窗口 <a hfer"tencent://message/?uin12345&Site&Menu-yes">弹出QQ为12345的窗口</a>

编辑聊天框

新建mypro包 运行如图

jq制作QQ简易聊天框

以下代码展示&#xff1a; * {margin: 0;padding: 0;line-height: 22px;font-family: "Arial", "微软雅黑";}#chat {margin: 3px auto 0 auto;width: 436px;border: 1px #999999 solid;}.chatBody {width: 100%;height: 220px;overflow: auto;}.chatText …

Jquery- QQ简易聊天框写法

<style> * { margin: 0; padding: 0; line-height: 22px; font-family: "Arial", "微软雅黑"; } #chat { margin: 3px auto 0 auto; width: 436px; border: 1px #999999 solid; } .chatBody { width: 100%; height: 220px; overflow: auto; } .chatT…

模拟聊天对话框

利用原生JS里的事件对象我们可以来模拟下聊天软件的对话框效果如下&#xff1a; CSS: *{margin: 0;padding: 0;font-size: 16px;font-family: "微软雅黑";}li{list-style: none;}.main{width: 800px;height:600px ;margin: 50px auto;border: 4px solid #B6B6B6;bord…

在多人音视频聊天中插入现场直播

如何在聊天中插入现场直播呢&#xff1f; 今天我就教给大家怎样在我们的聊天中插入现场直播。&#xff08;本文聊天以多人音视频为例&#xff09; 首先&#xff0c;我们要知道现场直播是什么呢&#xff1f; 它是通过流媒体技术来实现实时在线播放 什么是流媒体呢&#xff1…

如何抓取QQ2010的聊天框

做这件事难点在于&#xff0c;QQ2010 的聊天框用的是无窗口RichEdit&#xff0c;因此不能像普通的RichEdit那样通过FindWindow找到窗口然后发送WM_GETTEXT来获取文本&#xff0c;但是是不是就没有办法了呢&#xff0c;当然不是&#xff0c;这篇文章就要告诉大家抓取QQ2010&…

聊天信息框显示消息

聊天信息框显示消息 有趣的小案例池子&#xff1a; JS实现定时器 JS实现关闭图片窗口 JS实现输入检验 获取焦点后隐藏提示内容的输入框 JS实现获取鼠标在画布中的位置 聊天信息框显示消息 JS点击切换背景图 自动切换背景的登录页面 JS制作跟随鼠标移动的图片 JS实现记住用…

matlab中omg什么意思,英文聊天中omg,jk,lol,Lmao是什么意思

英文聊天中omg&#xff0c;jk&#xff0c;lol&#xff0c;Lmao的意思如下&#xff1a; 1、omg意思是“哦,我的上帝”或者“哦&#xff0c;我的天啊”&#xff0c;omg是英文“Oh My God”的缩写&#xff0c;通常是表达惊叹、惊讶的含义。 2、jk意思是“只是开个玩笑罢了”或者“…

微信语音聊天框样式+功能

仿微信语音聊天播放效果&#xff08;左右朝向的动态小喇叭&#xff09; 效果图&#xff1a; 暂停/播放用动态的class控制&#xff0c;语音聊天框的长度通过动态的style控制&#xff08;依据当前语音的秒数&#xff09;<!-- 音频文件 --><div :class"{anima…

QML做一个聊天框

用QML做聊天界面的思路一般都是用ListView来展示聊天记录。我也做了一个简易的聊天框&#xff0c;效果如下&#xff1a; 虽然思路很简单&#xff0c;但是实现时遇到不少QML的Bug&#xff0c;比如滚动时图片闪烁、拉伸时位置/宽度绑定错误&#xff08;所以我放弃了Layout&#x…

聊天界面的制作(三)——表情列表发送功能

基本功能 1. 自定义标题栏。&#xff08;标题栏不做任何功能&#xff09; 2. 有左右发送按钮。&#xff08;这个只能自己和自己聊天哦&#xff0c;所以有左右发送按钮&#xff09; &#xff08;1&#xff09;点击左边按钮发送按钮&#xff0c;在ListView的左侧显示。   &…

简易QQ聊天框

<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>QQ建议聊天框</title><script src"../../jquery-1.12.4.js"></script><style>*{margin: 0; padding: 0; line-heig…

UE4多人聊天框实现

在GameMode实现存储聊天信息的方法&#xff0c;相当于是游戏规则的一部分---------队友之间的互相交流&#xff0c;更因为GameMode是服务端才有的&#xff0c;所以得写在GameMode里面&#xff0c;能够在客户端对数据完成同步 在GameState存放聊天的数据&#xff0c;注意&#x…