2020牛客暑期多校训练营(第五场)

7.25 好像没啥特别的牛客5

C-Easy

题意

给定 $n$、$m$、$k$,问所有长度为 $k$ 且满足 $\sum A_i=n$、$\sum B_i=m$ 的 $A$、$B$ 数组的 $\prod \min(A_i,B_i)$ 之和。

思路

  1. 构造一个长度为 $k$ 的数组 $T$ 满足 $T_i<=min(A_i, B_i)$ ,$T$ 的所有方案数就是要求的答案。为什么能这么构造呢?其实就是 $T$ 满足 $T_i<=min(A_i, B_i)$ ,则 $T$ 的所有方案数就是每一位种类数相乘,可以发现就是题目要求的东西
  2. 枚举 $T$ 的和 $i$( $k$ 到 $min(n,m)$ ),对于 $T$ 的每种情况计算可能的情况数,累加
  3. 每种情况考虑用隔板法计算。对于 $T$ :隔出所有分配情况( $T$ 每位至少为 $1$ ),即 $C ^ {k-1} _ {i-1}$。对于 $A$ :先使 $A$ 和 $T$ 数组相同,剩下 $n-i$ 个自由分配(可以为 $0$ ),即 $C ^ {k-1} _ {n-i+k-1}$ 。$B$ 与 $A$ 同理。三个全部乘起来就是每个 $T$ 总和为 $i$ 的所有情况

感谢 $rls$ 的讲解

代码

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
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
const int mod = 998244353;
ll qpow(ll a,ll b,ll mod){
ll ans=1; while(b){
if(b&1) ans=ans*a%mod;
b>>=1; a=a*a%mod;
} return ans;
}
ll n,m,k,ans,jc[maxn],inv[maxn];
ll C(int s,int x){
return 1ll*jc[x]*inv[s]%mod*inv[x-s]%mod;
}
int solve(){
scl(n); scl(m); scl(k);
rep(i,k,min(n,m)+1){
ans+=C(k-1,i-1)*C(k-1,n-i+k-1)%mod*C(k-1,m-i+k-1)%mod;
if(ans>=mod) ans-=mod;
} return pf("%lld\n",ans),ans=0;
}
int main(){
jc[0]=inv[0]=1; rep(i,1,maxn) jc[i]=1ll*jc[i-1]*i%mod;
inv[maxn-1]=qpow(jc[maxn-1],mod-2,mod);
dep(i,maxn-2,1) inv[i]=1ll*inv[i+1]*(i+1)%mod;
int _; sc(_); while(_--) solve();
}

D-Drop Voicing

题意

给定一个 $1$ ~ $n$ 的排列,有两种操作:

  • 操作 $1$ : 可以将倒数第二个数放到开头
  • 操作 $2$ : 可以将开头的第一个数放到最后

一种操作重复若干次称为一段。

现在要将排列变成 $1$ ~ $n$ ,求需要的最少段数

思路

因为操作 $2$ 实际上是不会改变相对顺序的,所以只需要找 $LIS$(最长上升子序列)的长度,最后答案就是 $n-maxlen$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn],dp[maxn];
int qaq(int l,int r){
int cnt(0); rep(i,l,r){
if(a[i]>dp[cnt]){ dp[++cnt]=a[i]; continue; }
int p=lower_bound(dp+1,dp+cnt+1,a[i])-dp;
dp[p]=a[i];
} return cnt;
}
int solve(){
int n,ans(0); sc(n);
rep(i,1,n+1) sc(a[i]),a[i+n]=a[i];
rep(i,1,n+1) ans=max(ans,qaq(i,i+n));
return pf("%d\n",n-ans);
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}

E-Bogo Sort

题意

给定置换,求有多少排列可以通过这个置换变成顺序

思路

求所有环长的 $lcm$ ,无脑Java

备注

贼快朋友们,76ms

代码

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
import java.math.*;
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException {
// 这句是io流包装,记住就好
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
in.nextToken();
int n=(int) in.nval;
int[] a=new int[100005];
int[] vis=new int[100005];
for(int i=1;i<=n;i++){
in.nextToken();
a[i]=(int) in.nval;
}
BigInteger ans=BigInteger.ONE;
for(int i=1;i<=n;i++){
if(vis[i]==0){
int cnt=0,t=i;
while(vis[t]==0) {
cnt++; vis[t]=1; t=a[t];
}
ans=ans.multiply(BigInteger.valueOf(cnt)).divide(ans.gcd(BigInteger.valueOf(cnt)));
}
}
out.println(ans);
out.flush();
}
}

I-Hard Math Problem

题意

一个 $G$ 需要相邻一个 $H$ 和 $E$ ,问在无限大的网格中最多能放进多少个 $G$

代码

1
0.666667