1024问

Codeforces Global Round 7 C. Permutation Partitions（思维）

Sara/Sarah ·
更新时间:2024-11-14
· 945 次阅读

传送门 题意：

给两个数n,k
把长度为n的数组分成k个不相交的区间
把分成每个区间的最大值加在一起
找到和的最大值，并输出共有多少种分法等于该最大值

思路：

要想值最大，那前k大的数肯定在不同的区间
分法的话，就看这k个区间，每两个相邻的区间有几个数，该区间与下一个区间就有几种情况，把所有的乘起来即可

代码： #include #include #include #include #include #include #include #include #include #include #define pb push_back #define lb lower_bound #define ub upper_bound #define debug(x) cout<<x<<endl #define rep(i,a,b) for(int i=a;i=b;i--) typedef long long ll; using namespace std; const int MAXN=2e5+50; const int inf=0x3f3f3f3f; const int M=5000*4; const int mod=998244353; ll a[MAXN]; ll b[MAXN]; int main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); ll n,k; cin>>n>>k; rep(i,1,n){ cin>>a[i]; } if(n==k){ ll ans=n*(n+1)/2; cout<<ans<<" "<<1<<endl; return 0; } if(k==1){ cout<<n<<" "<<1<<endl; return 0; } ll ans=n*(n+1)/2-(n-k)*(n-k+1)/2; int p=n-k+1;//找前k大的数 int cnt=0; for(int i=1;i=p)b[++cnt]=i; } // cout<<cnt<<endl; ll lp=1; for(int i=2;i<=cnt;i++){ ll op=(b[i]-b[i-1]); lp=(lp*op)%mod; } cout<<ans<<" "<<lp<<endl; return 0; } /* 5 abbaxyzyx */
作者：_Alexander



permutation CodeForces global round

1024 个赞
编辑 举报
需要 登录 后方可回复, 如果你还没有账号请 注册新账号
相关文章
AppML 架构
Olathe 2020-02-04
833
css关于position属性的用法详解(绝对定位和相对定位的混淆)
Nita 2020-03-20
619
ASP.NET之Response.Cookies.Remove 无法删除COOKIE的原因
Kefira 2020-07-10
864
正则表达式解二元方程式代码
Cerelia 2020-04-18
720
global.php
Rowena 2020-01-29
720
PHP const定义常量及global定义全局常量实例解析
Cady 2021-03-15
615
python中round函数如何使用
Raissa 2020-06-12
760
Python全局变量与global关键字常见错误解决方案
Samira 2021-04-09
645
简单了解python关键字global nonlocal区别
Carly 2020-06-22
600
python中round函数保留两位小数的方法
Prunella 2021-01-31
912
postgresql 中round函数的用法说明
Bena 2020-05-29
682
python global的创建和修改实例讲解
Jade 2021-12-16
1970
Python全局变量关键字global的简单使用
May 2022-06-22
53
Python nonlocal关键字 与 global 关键字解析
Hazel 2022-07-15
849
Python函数命名空间和作用域(Local与Global)
Kiona 2022-07-15
1942
Python关键字之global与nonlocal
Catherine 2022-07-15
699
JavaScript 中的单例内置对象Global 与 Math
Sabah 2022-07-21
856
Python 局部变量global详解
Elina 2022-08-14
1220
PHP变量作用域（全局变量&局部变量）&global&static关键字用法实例分析
Catherine 2022-09-29
736
python修改全局变量可以不加global吗?
Orenda 2022-10-23
678