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) 之和。
思路
- 构造一个长度为 k 的数组 T 满足 T_i<=min(A_i, B_i)T 的所有方案数就是要求的答案。为什么能这么构造呢？其实就是 T 满足 T_i<=min(A_i, B_i)T 的所有方案数就是每一位种类数相乘，可以发现就是题目要求的东西
- 枚举 T 的和 i（ k 到 min(n,m) ），对于 T 的每种情况计算可能的情况数，累加
- 每种情况考虑用隔板法计算。对于 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 的讲解
代码
#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
代码
#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
代码：
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
代码
0.666667本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录