7.25 好像没啥特别的牛客5
题意
给定 n、m、k,问所有长度为 k 且满足 \sum A_i=n、\sum B_i=m 的 A、B 数组的 \prod \min(A_i,B_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();
}
题意
给定一个 1 ~ n 的排列,有两种操作:
一种操作重复若干次称为一段。
现在要将排列变成 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();
}
题意:
给定置换,求有多少排列可以通过这个置换变成顺序
思路:
求所有环长的 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();
}
}
题意
一个 G 需要相邻一个 H 和 E ,问在无限大的网格中最多能放进多少个 G
代码
0.666667