首页 > 其他分享 >NAC

NAC

时间:2024-09-28 14:00:59浏览次数:8  
标签:NAC int sr tr tl MAXN sl

QOJ 8777

题目描述

你有 \(P\) 页的护照,你要进行 \(N\) 次旅游。第 \(i\) 次旅游需要在连续 \(A_i\) 页没有盖章的护照上盖章。求最坏情况下你能进行几次旅游。

思路

我们枚举那一次不成功的旅游,考虑最坏情况:每一次盖章都和上一次盖章的末尾中间有 \(A_i-1\) 个空页,这样中间的空页就全都不能用。这样总共需要 \((i-1)\cdot (A_i-1)+\sum \limits_{j=1}^i A_j\) 页,如果这个 \(>P\),则输出 \(i-1\)。

代码

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

const int MAXN = 100005;

int n;
ll p, a[MAXN];
__int128 sum[MAXN];

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> p;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
    sum[i] = sum[i - 1] + a[i];
  }
  for(int i = 1; i <= n; ++i) {
    if((__int128)(a[i] - 1) * (i - 1) + sum[i] > p) {
      cout << i - 1;
      return 0;
    }
  }
  cout << n;
  return 0;
}

QOJ 8780

题目描述

有 \(N\) 道题,每道题都有实现,思维难度上限和下限,只有你的实现和思维能力都在范围之内才能解决这道题。每道能做的题你都可以选择跳过。每当你解决一道题就可以选择提升思维能力或实现能力。

给定你的初始实现和思维能力 \(S,T\) ,求你最多能解决多少道题。

思路

令 \(dp_{i,j,k}\) 表示考虑前 \(i\) 道题,实现和思维能力分别为 \(S+j,S+k\) 是否可能。很容易发现其解决题目数量 \(=j+k\)。由于只用记录是否可能,所以可以使用 bitset 优化。而空间用降维优化。

空间复杂度 \(O(\frac{N^2}{w})\),时间复杂度 \(O(\frac{N^3}{w})\),其中 \(w=32\)。

代码

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

const int MAXN = 5001;

int n, s, t, ans;
bitset<MAXN> dp[2][MAXN];

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> s >> t;
  dp[0][0][0] = 1;
  for(int i = 1, sl, sr, tl, tr; i <= n; ++i) {
    cin >> sl >> sr >> tl >> tr;
    sl -= s, sr -= s, tl -= t, tr -= t;
    sl = max(0, sl), sr = min(n, sr), tl = max(0, tl), tr = min(n, tr);
    bitset<MAXN> b;
    for(int j = tl; j <= tr; ++j) {
      b[j] = 1;
    }
    for(int j = 0; j < i; ++j) {
      dp[i & 1][j] |= dp[!(i & 1)][j];
    }
    for(int j = sl; j <= sr; ++j) {
      dp[i & 1][j + 1] |= (dp[!(i & 1)][j] & b);
      dp[i & 1][j] |= ((dp[!(i & 1)][j] & b) << 1);
    }
  }
  for(int i = 0; i <= n; ++i) {
    for(int j = 0; j <= n; ++j) {
      if(dp[n & 1][i][j]) {
        ans = max(ans, i + j);
      }
    }
  }
  cout << ans;
  return 0;
}

标签:NAC,int,sr,tr,tl,MAXN,sl
From: https://www.cnblogs.com/yaosicheng124/p/18437591

相关文章

  • 【赛博炼丹】深度学习软件安装及环境配置:Anaconda、CUDA、cuDNN、PyTorch及PyCharm
    前言建议大伙自己建一个文件夹(不能有中文),专门放深度学习的软件,后续添加环境,比较方便。1.安装Anaconda1.1下载AnacondaAnaconda官网:https://www.anaconda.com清华大学镜像网站:Indexof/anaconda/archive/|清华大学开源软件镜像站|TsinghuaOpenSourceMirror安装A......
  • Anaconda - Installation and Initialization
    InstallAnaconda:https://docs.anaconda.com/anaconda/install/linux/ CreateaCondavirtualenvironment: (base)zzh@ZZHPC:~/zd/Github$condacreate-nzpytorchanacondaChannels:-defaultsPlatform:linux-64Collectingpackagemetadata(repodata.json):d......
  • Manacher 算法浅谈
    \(Zero.\)\(~~\)前言杂谈认识我的人都喜欢叫我马拉车,如今,马拉车来浅谈Manacher了(不就是某天打板子的时候打错了吗,不就是啪啪打脸了吗)。首先大家需要知道,Manacher不是很常考,但是也是一项必备的算法。当遇到回文串之类的问题时,别人辛辛苦苦打一堆哈希,你用Manacher算法两个并......
  • nacos配置持久化到mysql数据库
    以版本2.4.1为例,要实现Nacos2.4.1的配置持久化,你需要按照以下步骤操作:准备数据库:首先,确保你已经安装并配置好了MySQL数据库,并且版本符合Nacos的要求(MySQL5.6及以上)。创建数据库:在MySQL中创建一个新的数据库,例如命名为nacos。执行SQL脚本:从Nacos的conf......
  • Anaconda 安装与使用教程
    1.介绍Anaconda是一个用于科学计算的Python和R的发行版,包含了众多流行的科学、数学、工程和数据分析的Python包。它不仅是一个包管理器,还是一个环境管理工具,可以帮助用户创建隔离的环境,安装特定版本的软件包及其依赖项。2.安装Anaconda2.1下载-访问[Anaconda......
  • Anaconda 安装与使用教程
    目录1.[Anaconda简介](#anaconda-简介)2.[安装Anaconda](#安装-anaconda)3.[环境管理](#环境管理)1.[创建新环境](#创建新环境)2.[激活与退出环境](#激活与退出环境)3.[列出所有环境](#列出所有环境)4.[删除环境](#删除环境)5.[环境包管理](#环境包管理)1.......
  • Anaconda 安装与使用教程
    目录1.[什么是Anaconda](#什么是anaconda)2.[安装Anaconda](#安装anaconda)-[Windows系统安装](#windows系统安装)-[macOS系统安装](#macos系统安装)-[Linux系统安装](#linux系统安装)3.[Anaconda的基本组件](#anaconda的基本组件)-[AnacondaNavigator](#anaco......
  • 使用nssm将nacos注册为系统服务教程
    每次启动项目之前,都需要去启动nacos服务,感觉非常的麻烦,所以想办法将它注册为系统服务,想用的时候,直接用命令启动,不想用的时候,直接用命令停止,最终找到一个不错的解决方案,操作起来也比较简单。nssm官网地址:https://nssm.cc/这里我们选择日期比较新的版本下载使用,当然你可以通过下面的......
  • 在Ubuntu 16.04上安装Anaconda Python发行版的方法
    前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。简介Anaconda是一个开源的包管理器、环境管理器和Python和R编程语言的发行版。它通常用于大规模数据处理、科学计算和预测性分析,为数据科学家、开发人员、业务分析师......
  • 重谈 manacher
    名称:马拉车,即manacher。实现问题方面:处理出整字符串\(s\)的回文串个数、位置。中心数组:数组\(p\),\(p_i\)表示以第\(i\)个字符为中心最长回文半径。预处理:将字符串间加入特殊字符(一般是$),以及结尾和开头的特殊处理。优势:马拉车的时空复杂度和字符集的大小无关......