题目 1排位 2训练 3构造数组
排位
有 n 个人排成了一队，小明就在其中。
他不知道自己的确切排位，但是他能确定的是，排在他前面的人不少于 a 个，排在他后面的人不超过 b 个。
请问，对于他的具体排位，一共有多少种可能性？
输入格式
第一行包含整数 T，表示共有 T 组数据。
每组数据占一行，包含三个整数 n,a,b。
输出格式
每组数据输出一行结果，一个整数，表示小明具体排位的可能数量。
数据范围
本题共两个测试点。
小测试点，如样例所示。
大测试点满足：1≤T≤50，0≤a,b<n≤100。
输入样例：
2
3 1 1
5 2 3
输出样例：
2
3
#include<iostream>
using namespace std;
int main()
{
int T;
scanf("%d", &T);
while (T -- ){
int n,a,b,res;
scanf("%d%d%d", &n, &a, &b);
res=min(n-a,b+1);
printf("%d\n",res);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
训练
达尔星有 n 个强大的下级战士，编号 1∼n。
其中第 i 名战士的战斗力为 ri。
战士 a 可以成为战士 b 的战斗导师，当且仅当 ra>rb 且两人之间不存在矛盾。
给定每个战士的战斗力值以及战士之间存在的 k 对矛盾关系。
请你计算，每个战士可以成为多少战士的战斗导师。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数 r1,r2,…,rn。
接下来 k 行，每行包含两个整数 x,y，表示战士 x 和战士 y 之间存在矛盾。同一对矛盾关系不会在输入中重复给出，即出现了 x,y 以后，后面就不会再次出现 x,y 或 y,x。
输出格式
共一行，n 个整数，表示每个战士可以作为战斗导师的战士数量。
数据范围
前三个测试点满足， 2 ≤ n ≤ 10 ， 0 ≤ k ≤ 10 2≤n≤10，0≤k≤10 2≤n≤10，0≤k≤10。
所有测试点满足， 2 ≤ n ≤ 2 × 1 0 5 ， 0 ≤ k ≤ m i n ( 2 × 1 0 5 , n ( n − 1 ) 2 ) ， 1 ≤ r i ≤ 1 0 9 ， 1 ≤ x , y ≤ n ， x ≠ y 2≤n≤2×10^5，0≤k≤min(2×10^5,{n(n−1)\over2})，1≤r_i≤10^9，1≤x,y≤n，x≠y 2≤n≤2×105，0≤k≤min(2×105,2n(n−1))，1≤ri≤109，1≤x,y≤n，x=y。
输入样例：
4 2
10 4 10 15
1 2
4 3
输出样例：
0 0 1 2
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <iterator>
#include <map>
using namespace std;
const int N = 200010;
unordered_map<int,int>map1;//分数，名次映射
int sub[N],tc[N],a[N],b[N];
int main()
{
int n,k;
scanf("%d%d", &n, &k);
//a[i]有重复，映射会出错。
for (int i = 1; i <= n; i ++ ){
scanf("%d", &a[i]);
b[i]=a[i];
}
for (int i = 1; i <= k; i ++ ){
int x,y;
scanf("%d%d", &x, &y);
if(a[x]<a[y])sub[y]+=1;
if(a[x]>a[y])sub[x]+=1;
}
//for (int i = 1; i <= n; i ++ )printf("%d ",sub[i]);
//cout<<'\n';
sort(b+1,b+n+1);
int cnt=1;
map1[b[1]]=1;
for (int i = 2; i <= n; i ++ ){
if(b[i]!=b[i-1])cnt=i;
map1[b[i]]=cnt;
}
for (int i = n; i >= 1; i -- ){
int res= map1[a[i]]-sub[i]-1;
tc[i]=res;
}
for (int i = 1; i <= n; i ++ ){
printf("%d ",tc[i]);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
有序数组
题目描述
现在需要构造一对数组 (a,b)，要求：
数组 a 和数组 b 的长度都为 m。
两个数组中的元素的取值范围都是 [1,n]。
∀i∈[1,m]，ai≤bi。
数组 a 中元素非严格单调递增。
数组 b 中元素非严格单调递减。
请问，共能构造出多少对满足条件的数组？
输出对 1 0 9 + 7 10^9+7 109+7 取模后的结果。
输入格式
一行，两个整数 n,m。
脑筋急转弯
由于 ai≤bi，结合 a 递增 b 递减的要求，只要满足 a m ≤ b m a_m≤b_m am≤bm 就满足 a i ≤ b i a_i≤b_i ai≤bi。
于是我们完全可以把 b 倒过来拼在 a 的后面，这样题目就简化成了求长为 2m，元素范围在 [ 1 , n ] [1,n] [1,n] 的非严格单调递增数组个数。
这是一个经典组合数学问题，等价于把 2m个无区别的球放入 n 个有区别 （ 因 为 数 组 有 顺 序 ） （因为数组有顺序） （因为数组有顺序）的盒子中，且允许空盒的方案数，这里第 i 个盒子放的球就表示值为 i i i 的元素。
我们采用隔板法来解决：把 n 个盒子当做 n−1 个隔板，球加上隔板总共有 2m+n−1 个位置，从中选择 n−1 个位置放隔板，这样就把 2m 个球划分成了 n 份，放入对应的盒子中。
因此方案数为 C 2 m + n − 1 n − 1 C_{2m+n−1}^{n−1} C2m+n−1n−1。
（大家可以在本人的下面这篇看到组合数的求法）
AcWing 886. 求组合数 II
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010, mod = 1e9 + 7;
//利用快速幂与费马小定理
int fact[N], infact[N];
int qmi(int a, int k, int p)
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
int main()
{
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;//利用快速幂求逆元
}
int n,m,a,b;
scanf("%d%d", &n, &m);
a=2*m+n-1,b=n-1;
printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);//随时取模，防止溢出
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
文章来源: blog.csdn.net，作者：irrationality，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/weixin_54227557/article/details/120926329
- 点赞
- 收藏
- 关注作者
评论（0）