西安高新区网站建设,教育网站制作要多少钱,网站需求定制表单,网页游戏知乎题目#xff1a;
样例#xff1a; 输入 3
5
1 2 3 4 5
3
3 3 3
3
1 2 1 输出 16 1 3 思路#xff1a; 依据题意#xff0c;再看数据范围#xff0c;可以知道暴力肯定是不可能了#xff0c;然后通过题目意思#xff0c;我们可以排列模拟一下#xff0c;这里排列所得结…题目
样例
输入 3
5
1 2 3 4 5
3
3 3 3
3
1 2 1 输出 16 1 3 思路 依据题意再看数据范围可以知道暴力肯定是不可能了然后通过题目意思我们可以排列模拟一下这里排列所得结果联系上我们数学的排列组合知识点可以知道这个山峰序列我们排列的时候是围绕 “山峰” 来进行排列即围绕最大的数值来进行排列而当出现多个最大值的时候我们必须将多个最大值绑定在一块通过排列得知我们排列左边是一个结果排列一样的右边也是一种结果所以有 排列个数 1这里的 1 是排列右边的结果相当于镜面翻转。
其次答案中至少有一种结果即ans 1因为直接 sort 排序一遍就是一个山峰序列然后当我们记录的 排列个数 1就有最终答案 ans ans * (排列个数 1) % MOD 这里注意一个条件就是我们的山峰序列是围绕的所以不用算进 ans ans * (排列个数 1) % MOD 例子1 [1 , 2 ]
ans 1
r[1] 1
r[2] 1 ans ans * (r[1] 1) % MOD 2
即答案只有 2 种分别是 [1 , 2 ] [2, 1 ]
代码详解如下
#include iostream
#include unordered_map
#define endl \n
#define x first
#define y second
#define int long long
#define YES puts(YES)
#define NO puts(NO)
#define umap unordered_map
#pragma GCC optimize(3,Ofast,inline)
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int MOD 998244353;
int n; // 数组大小
inline void solve()
{umapint,intr; // 记录元素个数int ans 1; // 答案最终结果int maxs -1; // 取出 峰顶值 即 最大值cin n;for(int i 0,x;i n;i){cin x;r[x]; // 统计元素个数maxs max(maxs,x); // 寻找 峰顶值}// 开始循环乘上每一种排列结果 除去峰顶值的计算for(auto i : r) if(i.x ! maxs) ans ans * (i.y 1) % MOD;// 输出答案cout ans endl;
}signed main()
{
// freopen(a.txt, r, stdin);___G;int _t 1;cin _t;while (_t--){solve();}return 0;
}
最后提交
