CF1326C Permutation Partitions 题解,
2024-10-09 00:16:08
简要题意:
给定一个 \(1\) ~ \(n\) 的置换,将数组分为 \(k\) 个区间,使得每个区间的最大值之和最大。求这个值,和分区的方案数。
关键在于 \(1\) ~ \(n\) 的置换。
显然,你只要把从 \(n - k + 1\) 到 \(n\) 这一段,每个区间分一个(其余的随便分)。
显然可以得出第一个答案:
\[(n-k+1) + (n-k+1) + \cdots + (n-1) + n
\]
\]
(很显然,你可以用等差数列求和,可是没这个必要,一会儿求第二个答案的时候,可以顺便求啊)
比方说:(以第三个样例为例)
7 3
2 7 3 1 5 4 6
这时你把 \(5\),\(6\),\(7\) 作为每个区间的最大值。
此时你会发现,比方说 \(3 \space 1\) 这一段。
它要么全归 \(7\),全归 \(5\) ,或者分两段,左边归 \(7\),右边归 \(5\).
那么,你想,这就相当于你可以在任意的位置把它分段。(包括最左边和最右边,此时尽属一段)
那么,方案数是 \(3\).
就是 \(5\) 的位置减去 \(7\) 的位置,即 \(5 - 2 = 3\).
而一共三段,分别计算。根据 乘法原理 可得:
\[1 \times 3 \times 2 = 6
\]
\]
所以,第二个答案是:
每个 \(\geq n - k + 1\) 的数和前面一个 \(\geq n - k + 1\) 的数的位置之差的乘积。
第零个 \(\geq n - k + 1\) 的数的位置,我们认为是 \(0\).
记得开 \(\texttt{long long}\).
十年OI一场空,不开long long见祖宗
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=998244353;
inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
int n,k,last;
ll s=0,cnt=1;
int main(){
n=read(),k=read();
for(int i=1,t;i<=n;i++) {
t=read(); if(t>n-k) {
s+=t; if(!last) last=i; //维护上一个 >= n - k + 1 的数的位置
else cnt=cnt*(i-last)%MOD,last=i; //计数
}
} printf("%lld %lld\n",s,cnt);
return 0;
}
最新文章
- linux下 mysql数据库的备份和还原
- code complete part1
- webpack配置备份
- GCJ 2015-Qualification-B Infinite House of Pancakes 枚举,思路,误区 难度:3
- linux服务之ntp与chrony
- javascript中出现identifier starts immediately after numeric literal错误原因以及解决方法
- 如果你喜欢Python 那么你不得不知的几个开源项目
- Pythonchallenge一起来闯关
- Linux内核ROP学习
- Speech Module
- javascript每日一练(一)——javascript基础
- js 上一天、下一天
- webpack配置这一篇就够
- 关于this的指向
- IncDec Sequence(差分)
- 【ftp】主动模式和被动模式
- SDWebImage之UIView+WebCache
- java8 Optional正确使用姿势
- springMVC源码学习地址
- Linux文件目录介绍及文件颜色区别
热门文章
- 一个简单的爬取b站up下所有视频的所有评论信息的爬虫
- pika使用报错queue_declare() missing 1 required positional argument: &#39;queue&#39;
- 动态构造任意复杂的 Linq Where 表达式
- 【新功能】MaxCompoute禁止Full Scan功能开放
- 由一个项目需求引发的 - textarea中的换行和空格
- 基础JavaScript练习(二)总结
- &#160;FPGA边沿检测Verilog代码
- Java原来还可以这么学:如何搞定面试中必考的集合类
- Ubuntu 16 编译装python2.7
- RocketMQ-2.RocketMQ的负载均衡