首页 > 其他分享 >UR #1

UR #1

时间:2024-10-04 11:44:41浏览次数:9  
标签:cnt int sum MAXV UR ++ dp

A. 缩进优化

题目描述

有 \(N\) 行,每行有 \(A_i\) 个空格。你可以选择一个默认 TAB 长度 \(x\)。并用一个 TAB 替换 \(x\) 个空格。求最终需要 TAB 和空格数量之和的最小值。

思路

我们先对值的出现次数做一个前缀和,然后枚举 \(x\)。并枚举 \(x\) 的倍数再统计答案即可。这样是一个调和级数的复杂度。

空间复杂度 \(O(N)\),时间复杂度 \(O(N\log N)\)。

代码

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

const int MAXV = 1000001;

int n, sum[MAXV];
ll ans = (ll)(1e18), cnt[MAXV];

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n;
  for(int i = 1, x; i <= n; ++i) {
    cin >> x;
    sum[x]++;
    cnt[x] += x;
  }
  for(int i = 1; i < MAXV; ++i) {
    sum[i] += sum[i - 1];
    cnt[i] += cnt[i - 1];
  }
  for(int i = 1; i < MAXV; ++i) {
    ll res = 0;
    for(int j = 0; i * j < MAXV; ++j) {
      res += 1ll * j * (sum[min(MAXV - 1, i * (j + 1) - 1)] - (!j ? 0 : sum[i * j - 1])) + (cnt[min(MAXV - 1, i * (j + 1) - 1)] - (!j ? 0 : cnt[i * j - 1])) - 1ll * i * j * (sum[min(MAXV - 1, i * (j + 1) - 1)] - (!j ? 0 : sum[i * j - 1]));
    }
    ans = min(ans, res);
  }
  cout << ans;
  return 0;
}

B. 外星人

题目描述

给定一个数 \(x\),和一个数列 \(A\),你要找到一个排列 \(P\),使得 \(x\bmod A_{P_1}\bmod A_{P_2}\bmod \dots \bmod A_{P_N}\) 最大。并求出有多少个这样的 \(P\)。

思路

显然当我们模完一个较小的数后,再模较大的数就没有意义了,所以如果我们想跳过一个数,那么只需把它丢到更小的数后面。因此先对 \(A\) 从大到小排序。

令 \(dp_{i,x}\) 表示考虑前 \(i\) 个数,当前数变成了 \(x\) 的方案数。如果我们选择模,那么有转移 \(dp_{i+1,x\bmod A_{i+1}}\leftarrow dp_{i,x}\)。如果不模,那么 \(dp_{i+1,x}\leftarrow dp_{i,x}\cdot (N-i)\)。最后看最大有方案数的答案即可。

时空复杂度均为 \(O(Nx)\)。

代码

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

const int MAXN = 1001, MAXV = 5001, MOD = 998244353;

int n, x, a[MAXN], dp[MAXN][MAXV];

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> x;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  sort(a + 1, a + n + 1, greater<int>());
  dp[0][x] = 1;
  for(int i = 0; i < n; ++i) {
    for(int j = 0; j <= x; ++j) {
      dp[i + 1][j] = (dp[i + 1][j] + 1ll * dp[i][j] * (n - i - 1) % MOD) % MOD;
      dp[i + 1][j % a[i + 1]] = (dp[i + 1][j % a[i + 1]] + dp[i][j]) % MOD;
    }
  }
  for(int i = x; i >= 0; --i) {
    if(dp[n][i]) {
      cout << i << "\n" << dp[n][i];
      return 0;
    }
  }
  return 0;
}

标签:cnt,int,sum,MAXV,UR,++,dp
From: https://www.cnblogs.com/yaosicheng124/p/18446464

相关文章

  • Cisco Secure Network Analytics 7.5.1 发布下载,新增功能概览
    CiscoSecureNetworkAnalytics7.5.1发布下载,新增功能概览CiscoSecureNetworkAnalytics7.5.1-领先的网络检测和响应(NDR)解决方案SecureNetworkAnalytics(formerlyStealthwatch)-NetworkVisibilityandSegmentation请访问原文链接:https://sysin.org/blog/ci......
  • Cisco Secure Network Analytics 7.5.1 - 领先的网络检测和响应 (NDR) 解决方案
    CiscoSecureNetworkAnalytics7.5.1-领先的网络检测和响应(NDR)解决方案SecureNetworkAnalytics(formerlyStealthwatch)-NetworkVisibilityandSegmentation请访问原文链接:https://sysin.org/blog/cisco-secure-network-analytics/,查看最新版。原创作品,转载请保......
  • SpringCloud入门(三)Eureka 注册中心
    一、Eureka注册中心简介假如我们的服务提供者user-service部署了多个实例,如图: 问题:-order-service在发起远程调用的时候,该如何得知user-service实例的ip地址和端口?-有多个user-service实例地址,order-service调用时该如何选择?-order-service如何得知某个user-service实例是......
  • 自然语言处理之话题建模:Neural Topic Models:神经主题模型的未来趋势与研究方向_
    自然语言处理之话题建模:NeuralTopicModels:神经主题模型的未来趋势与研究方向引言话题建模的定义与重要性话题建模是一种统计建模技术,用于发现文档集合或语料库中隐藏的主题结构。在自然语言处理(NLP)领域,话题建模被广泛应用于文本挖掘、信息检索、文本分类和推荐系统等......
  • 题解:洛谷P2339 [USACO04OPEN] Turning in Homework G
    题目链接:洛谷P2339[USACO04OPEN]TurninginHomeworkG首先我们考虑如何处理到达给定时间后才能交作业这一限制。其实在生活中,我们一般只会考虑什么时候交作业截止(除了某些卷王),这样我们只用考虑如何在最大结束时间之前交作业,而不是在所有作业都没开始交之前考虑如何转悠(前者明......
  • Educational Codeforces Round 95 (Rated for Div. 2) G. Three Occurrences
    首先我们随机两个数组\(valA_x,valB_x\)。对于数组\(a\),记\(cnt\)表示\(a_i\)在前缀中出现的次数。若\(cnt\equiv0\mod3\),则\(b_i=valA_x\)若\(cnt\equiv1\mod3\),则\(b_i=valB_x\)若\(cnt\equiv2\mod3\),则\(b_i=valA_x\oplusvalB_x\)记\(pre_i\)表示\(b\)的前......
  • 【Tourism】Luoyang(1)
    文章目录洛阳1、龙门石窟(AAAAA)2、白马寺(AAAA)洛阳洛阳市,简称“洛”,古称成周、神都、洛邑、洛京,是河南省辖地级市、世界文化名城、首批国家历史文化名城、国家区域性中心城市、中原城市群副中心城市、“一带一路”重要节点城市,三线城市,国务院批复确定的河南省副中心城......
  • WPF FindResource,Resource[key] SystemColors TryFindResource
    //xaml<Windowx:Class="WpfApp3.MainWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d="http://schemas.micr......
  • WPF image via web url or uri
    Thebasicroadmapistodownloadwebimageatfirst,second convertitintomemeorystream,thirdassignthememorystreamtobitmapimageasStreamSource. //xaml<Windowx:Class="WpfApp2.MainWindow"xmlns="http://schemas.micro......
  • CF589H Tourist Guide
    昨晚码敲完了没保存,导致还原卡直接把我码肘没了。。。气死了只能重新敲了一遍。题面TouristGuide分析考虑每一个联通块分开处理。先将每一个联通块变为生成树,任意生成方式皆可。对于每一个联通块,一定可以构造一种组合方法,使得该联通块中最多只有一个关键点无法被选择。并......