欢乐
求最小的
K
K
K 使得
K
!
≥
N
!
K
!
K!\geq\frac{N!}{K!}
K!≥K!N!。
log
a
(
M
×
N
)
=
log
a
M
+
log
a
N
log
a
M
N
=
log
a
M
−
log
a
N
\log _{a}(M \times N)=\log _{a} M+\log _{a} N \\ \\ \log _{a} \frac{M}{N}=\log _{a} M-\log _{a} N
loga(M×N)=logaM+logaNlogaNM=logaM−logaN
比较阶乘的大小可以取对数，因为
log
(
a
)
<
log
(
b
)
⟺
a
<
b
\log(a) < \log(b) \iff a < b
log(a)<log(b)⟺a<b。那么
ln
n
!
=
ln
∏
i
=
1
n
i
=
∑
i
=
1
n
ln
(
i
)
ln
n
!
k
!
=
ln
(
n
)
−
ln
(
k
)
\ln n! = \ln \prod_{i=1}^n i \\= \sum_{i=1}^n \ln(i) \\ \ \\ \ln\frac{n!}{k!} = \ln(n) -\ln(k)
lnn!=lni=1∏ni=i=1∑nln(i) lnk!n!=ln(n)−ln(k)
所以用数学库中的 log 函数预处理前缀和，二分一个
k
k
k 判断一下。
能判断阶乘的大小，是不是也可以判断组合数的大小？
水题
b
:[a
]:2;c
:[a
]:3;a
:[]:1/2
#include <bits/stdc++.h>
using namespace std
;
const int N
= 2000 + 5, INF
= 0x3f3f3f3f;
inline int read() {
int x
= 0, f
= 0; char ch
= 0;
while (!isdigit(ch
)) f
|= ch
== '-', ch
= getchar();
while (isdigit(ch
)) x
= (x
<< 3) + (x
<< 1) + (ch
^ 48), ch
= getchar();
return f
? -x
: x
;
}
map
<string
, int> mp
;
string s
;
struct node
{
int need
, num
;
vector
<int> rely
;
string name
;
int ac
;
}a
[N
];
string name
[N
];
int len
, n
, dian
, cnt
, lim
, now
;
bool cmp(node a
, node b
) {
if (a
.ac
!= b
.ac
) return a
.ac
< b
.ac
;
return a
.name
< b
.name
;
}
bool kil
[N
], vis
[N
];
int id
[N
];
int cd
[N
];
int okt
[N
];
signed main() {
cin
>> s
;
len
= s
.size(), n
= 0, dian
= 0, cnt
= 0;
for (int i
= 0; i
< len
; i
++) {
if (s
[i
] == ';') dian
= i
+ 1;
if (s
[i
] == ';' || s
[i
] == '/') {
int d
= 0;
for (int j
= i
- 1, mul
= 1; j
>= 0 && isdigit(s
[j
]); j
--, mul
*= 10) d
+= mul
* (s
[j
] - '0');
a
[++cnt
].need
= d
;
}
if (s
[i
] == ':' && dian
!= -1) a
[++n
].name
= s
.substr(dian
, i
- dian
), dian
= -1;
if (s
[i
] == '/') {
for (int j
= i
+ 1; j
< len
; j
++) lim
= lim
* 10 + (s
[j
] - '0');
}
}
for (int i
= 1; i
<= n
; i
++) mp
[a
[i
].name
] = i
;
int kh
= 0; cnt
= 0;
for (int i
= 0; i
< len
; i
++) {
if (s
[i
] == '[') kh
= i
, cnt
++;
if (s
[i
] == ']') {
string t
= "";
for (int j
= kh
+ 1; j
<= i
; j
++) {
if (s
[j
] == ',' || s
[j
] == ']' && t
!= "") {
a
[cnt
].rely
.push_back(mp
[t
]);
t
= "";
}
else t
+= s
[j
];
}
}
}
int ans
= 0, ok
= 1;
for (int i
= 1; i
<= n
; i
++) a
[i
].num
= i
;
while (ok
) {
vector
<node
> cur
;
for (int i
= 1; i
<= n
; i
++) {
if (kil
[i
] || vis
[i
]) continue;
bool flg
= 1;
int maxn
= -1;
for (int j
= 0; j
< a
[i
].rely
.size(); j
++) {
if (!kil
[a
[i
].rely
[j
]]) {
flg
= 0;
break;
}
maxn
= max(maxn
, okt
[a
[i
].rely
[j
]]);
}
if (flg
) {
a
[i
].ac
= maxn
;
cur
.push_back(a
[i
]);
}
}
sort(cur
.begin(), cur
.end(), cmp
);
int p
= 0;
for (int i
= 1; i
<= lim
; i
++) if (!cd
[i
] && cur
.size()) {
node task
= cur
[0];
cd
[i
] = task
.need
;
id
[i
] = cur
[0].num
;
vis
[id
[i
]] = 1;
cur
.erase(cur
.begin());
}
int minn
= INF
;
for (int i
= 1; i
<= lim
; i
++) if (cd
[i
]){
minn
= min(minn
, cd
[i
]);
}
if (minn
!= INF
) {
for (int i
= 1; i
<= lim
; i
++) if (cd
[i
]) {
cd
[i
] -= minn
;
if (cd
[i
] == 0) kil
[id
[i
]] = 1, okt
[id
[i
]] = ans
+ minn
;
}
ans
+= minn
;
}
ok
= 0;
for (int i
= 1; i
<= n
; i
++)
if (!kil
[i
]) {
ok
= 1;
break;
}
}
printf("%d\n", ans
);
return 0;
}
模拟
赛
求
∑
l
=
1
n
∑
r
=
l
n
f
(
a
l
∼
r
)
\sum_{l=1}^n\sum_{r=l}^nf(a_{l\sim r})
∑l=1n∑r=lnf(al∼r) 其中
f
f
f 为 V 字三元组
i
<
j
<
k
,
a
i
>
a
j
,
a
k
>
a
j
i < j < k,a_i > a_j,a_k >a_j
i<j<k,ai>aj,ak>aj 的个数。
套路题，可惜没时间了，这告诉我们除了 T1 外其它题可能不按难度排序。
转换成每个三元组出现在多少个区间内，我们枚举中间数
x
x
x，那么两边的数都比它大，所以线段树预处理一下，假设
l
l
l 为左边的符合要求的数的下标和为
l
l
l，右边符合要求的数与
n
n
n 之差的和为
r
r
r，匹配一下答案是
l
×
r
l \times r
l×r。值得一提的是，两棵线段树要一个个加数来满足相对位置的限制。
其实这是一个对数字相对大小有限制的套路了，那么如果是对下标大小有限制呢。假设是
a
1
∼
a
n
a_1 \sim a_n
a1∼an，我们处理到了
i
i
i，如果
a
i
a_i
ai 出现过了，那么线段树中
a
i
=
1
a_i = 1
ai=1，那么
1
∼
i
1 \sim i
1∼i 的所有位置是
1
1
1 的，代表这个位置在
i
i
i 之前出现过，其它是
0
0
0 的位置那么在
i
i
i 之后出现过，当然也可以搞成一个桶相当于求出现的次数，这个
01
01
01 的花也可以上线段树哈希。
