AcWing第 100 场周赛
4953. 比赛
n 个人参加乒乓球比赛。
比赛一共进行了 n−1 场。
每场比赛举办方都需要准备 2×b+1 瓶水，其中 2×b 瓶水给选手（每场比赛 2 人参加，每人 b 瓶），1 瓶水给裁判。
此外，所有参加比赛的 n 名选手，每名选手在比赛期间总共会得到举办方准备的 p 条毛巾。
请你计算，举办方一共需要准备多少瓶水和多少条毛巾。
输入格式
共一行，三个整数 n,b,p。
输出格式
两个整数，表示所需准备的水的数量和毛巾的数量。
数据范围
前 33 个测试点满足 1≤n,b,p≤10。
所有测试点满足 1≤n,b,p≤500。
输入样例1：
5 2 3
输出样例1：
20 15
输入样例2：
8 2 4
输出样例2：
35 32// Online C++ compiler to run C++ program online
#include <iostream>
using namespace std;
int main() {int n,b,p;cin>>n>>b>>p;cout<<(n-1)*(2*b+1) << " "<< p*n;
}4954. 挑选
给定一个包含 n 个正整数 a1,a2,…,an 的集合。
集合中可能存在数值相同的元素。
请你从集合中挑选一些元素，要求同时满足以下所有条件：
- 被选中元素不少于 2 个。
- 所有被选中元素之和不小于 l 且不大于 r。
- 所有被选中元素之中最大元素与最小元素之差不小于 x。
请问，一共有多少种不同的选法。
注意：
- 不考虑元素顺序，{a1,a2} 和 {a2,a1} 应当视为同一种选法。
- 不同元素即使数值相同，也应当视为不同个体，即使 a1=a2
输入格式
第一行包含四个整数 n,l,r,x。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
一个整数，表示不同选法的数量。
数据范围
前 33 个测试点满足 1≤n≤5。
所有测试点满足 1≤n≤15，1≤l≤r≤109，1≤x≤106，1≤ai≤106。
输入样例1：
3 5 6 1
1 2 3
输出样例1：
2
输入样例2：
4 40 50 10
10 20 30 25
输出样例2：
2
输入样例3：
5 25 35 10
10 10 20 10 20
输出样例3：
6
#include<bits/stdc++.h>
using namespace std;int main()
{int n, l, r, x, ans = 0;scanf("%d%d%d%d", &n, &l, &r, &x);vector<int> a(n);for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);for (int i = 1; i < 1 << n; i ++ ){int mi = 2e9, mx = 0, cnt = 0;long long sum = 0;for (int j = 0; j < n; j ++ )if (i >> j & 1){cnt ++ ;mi = min(mi, a[j]);mx = max(mx, a[j]);sum += a[j];}if (cnt == 1) continue;if (sum >= l && sum <= r && mx - mi >= x) ans ++ ;}printf("%d", ans);return 0;
}4955. 牌堆
有 n 张纸牌，编号 1∼n。
其中，第 i 张纸牌的价值为 vi。
你要玩一个游戏，具体流程如下：
首先，你要将 n 张牌一张叠一张地堆成一个牌堆，牌堆中纸牌的具体排列顺序由你决定。
接下来，你需要依次进行 m 次操作。
关于第 i 次操作：
- 你的任务是将编号为 ai 的纸牌从牌堆中抽出，并置于牌堆顶部。
- 如果执行此次操作时，不存在纸牌位于纸牌 ai 之上，即纸牌 ai 本来就位于牌堆顶部，则此次操作无需付出任何代价。
- 如果执行此次操作时，存在纸牌位于纸牌 ai 之上，则此次操作需要付出代价，具体代价为所有位于纸牌 ai 之上的纸牌的价值之和（不要将价值和编号混淆）。
请你合理安排初始时牌堆中的纸牌排列顺序，从而使得执行完所有操作需要付出的总代价尽可能小。
输出总代价的最小可能值。
例如，如果一共有 3 张纸牌，价值分别为 1,2,3 一共需要进行 5 次操作，每次操作需要置于牌堆顶部的卡牌分别为 1,3,2,3,1。
那么一种最佳的初始时牌堆中纸牌排列顺序为从上到下依次为纸牌 1,3,2。
具体操作过程如下：
- 第 11 次操作，需要将纸牌 11 置于牌堆顶部，由于纸牌 11 本来就在牌堆顶部，因此，所需代价为 00，执行完此次操作后，牌堆中纸牌排列顺序仍为 1,3,21,3,2。
- 第 22 次操作，需要将纸牌 33 置于牌堆顶部，由于纸牌 11 位于纸牌 33 之上，因此，所需代价为 v1=1�1=1，执行完此次操作后，牌堆中纸牌排列顺序为 3,1,23,1,2。
- 第 33 次操作，需要将纸牌 22 置于牌堆顶部，由于纸牌 1,31,3 位于纸牌 22 之上，因此，所需代价为 v1+v3=4�1+�3=4，执行完此次操作后，牌堆中纸牌排列顺序为 2,3,12,3,1。
- 第 44 次操作，需要将纸牌 33 置于牌堆顶部，由于纸牌 22 位于纸牌 33 之上，因此，所需代价为 v2=2�2=2，执行完此次操作后，牌堆中纸牌排列顺序为 3,2,13,2,1。
- 第 55 次操作，需要将纸牌 11 置于牌堆顶部，由于纸牌 2,32,3 位于纸牌 11 之上，因此，所需代价为 v2+v3=5�2+�3=5，执行完此次操作后，牌堆中纸牌排列顺序为 1,3,21,3,2。
付出的总代价为 0+1+4+2+5=120+1+4+2+5=12。
输入格式
第一行包含两个整数 n,m。
第二行包含 n 个整数 v1,v2,…,vn。
第三行包含 m 个整数 a1,a2,…,am。
输出格式
一个整数，表示总代价的最小可能值。
数据范围
前 33 个测试点满足 2≤n≤3，1≤m≤5。
所有测试点满足 2≤n≤500，1≤m≤1000，1≤vi≤100，1≤ai≤n。
输入样例：
3 5
1 2 3
1 3 2 3 1
输出样例：
12
#include <bits/stdc++.h>
using namespace std;const int N = 1010;
int v[N], p[N], e[N], q[N], tot;
bool st[N];
int main()
{int n, m;scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ ) scanf("%d", &v[i]);for (int i = 1; i <= m; i ++ ) scanf("%d", &p[i]);for (int i = 1; i <= m; i ++ ) if (!st[p[i]]) {e[++ tot] = p[i]; q[p[i]] = tot; st[p[i]] = true; }int ans = 0; for (int i = 1; i <= m; i ++ ){int k = p[i];for (int j = q[p[i]] - 1; j >= 1; j -- ) {ans += v[e[j]];q[e[j]] = j + 1;e[j + 1] = e[j];}e[1] = k, q[e[1]] = 1; }printf("%d", ans);return 0;
}