Codeforces Global Round 7 C. Permutation Partitions

Leona ·

更新时间:2024-09-20

· 907 次阅读

C. Permutation Partitions

题目链接-C. Permutation Partitions
在这里插入图片描述

题目大意
给定一个 1−n 上的全排列，将这个全排列分成不相交的 k 段，定义该划分的value为各段最大值的和，求该全排列所有可能划分中 value的最大值和满足value最大的划分情况的个数
解题思路

求k个区间的最大值之和的最大值，显然value就是求k个数之和的最大值，也就是前k大的数字加起来我们选定了k个最大的数字，然后将原序列分成k个区间，每区间恰好包含一个选定的数字，所以区间的分界线必须要在选定的数之间如果两个相邻选定的数字位置是 posi,posi+1，也就是分界线可以插在前k大的数字的后面到下一个数字前，那么每个分界线可供选择的位置方案则有posi+1-posi个，依次乘起来就得到答案了具体操作见代码

附上代码

#include
#define int long long
#define lowbit(x) (x &(-x))
using namespace std;
const int INF=0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const double PI=acos(-1.0);
const double eps=1e-10;
const int M=1e9+7;
const int N=2e5+5;
typedef long long ll;
typedef pair PII;
const int mod=998244353;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n,k,p=-1,ans=1,sum=0;
	cin>>n>>k;
    for(int i=1;i>x;
        if(x>=(n-k+1)){
            sum+=x;
            if(p!=-1)
                ans=ans*(i-p)%mod;
            p=i;
        }
    }
	cout<<sum<<" "<<ans<<endl;
	return 0;
}

作者：Fiveneves

permutation CodeForces global round

1024 个赞