[题解]2024ICPC上海站-InSearchoftheUltimateArtifact

题源：I - In Search of the Ultimate Artifact Abstract： n n n 个非负整数构成的数组 a a a，可任选 k k k 个融合为一个新数，新数为 ∏ i = 1 k a i \prod\limits_{i=1}^{k}a_i i=1∏k​ai​。求进行若干次(可为0次)融合后的最大值。答案对 998244353 998244353 998244353 取模。Keyword：贪心(签到题)Solution：观察合并操作，发现本质上每次在减少 k − 1 k-1 k−1 个元素。因此采用堆进行维护，贪心的先默认答案为堆顶，每次取出堆中 k − 1 k-1 k−1 个元素对答案相乘即可。注意每次相乘都需要进行取模操作。Code： /* * Copyright (c) 2025 - Yerosius All Rights Reserved. * @Author: Yerosius * @Date: 2025-02-18 14:12:44 * @FilePath: /VSCodeProject/I_In_Search_of_the_Ultimate_Artifact.cpp */ #include<bits/stdc++.h> using namespace std; using ll=long long; #define int ll #define endl "\n" const int MOD=998244353; void solve(){ int n,k;cin>>n>>k; priority_queue<int>pq; while(n--){ int _;cin>>_; if(_) pq.push(_);//0对答案极其不利，因此读入时直接忽略0 } int ans=0; if(pq.size()){//先默认答案为堆顶 ans=pq.top(); ans%=MOD; pq.pop(); } while(pq.size()>=k-1){ for(int i=0;i<k-1;i++){//取堆中k-1个元素对答案相乘 int _=pq.top(); _%=MOD; ans*=_; ans%=MOD; pq.pop(); } } cout<<ans%MOD<<'\n'; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t;cin>>t; while(t--) solve(); return 0; }