[NOIP2016 提高组] 组合数问题
题目大意
组合数C^m_n表示的是从n个物品中选出m个物品的方案数。小葱想知道如果给定n,m和k对于所有的0≤i≤n,0≤j≤min(i,m)0≤i≤n,0≤j≤min(i,m),有多少对 (i,j)(i,j)满足C_i^jC 是k的倍数。
解题思路
多次询问,肯定要预处理最朴素的思想,先把所有的C算出来,然后计算答案,但是这样肯定会爆空间,所以很自然地想到只记录C是不是k的倍数。用记录余数的方式线性处理,然后用一个前缀和记录一下到Cmn为止有多少对是k的倍数就行了,至于为什么是前缀和可以看下面的代码举出来的例子
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=min(m,i);j++){
printf("%d %d ",i,j);
}
puts("");
}
}
//5 1
//5 2
//5 3
//5 4
//5 5
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=4002,INF=0x3f3f3f3f;
int n,m,k;
int cnt[N][N];
int dp[N][N];
void cal_cnt(){
for(int i=1;i<N;i++){
for(int j=1;j<=i;j++){
if(i==j) cnt[i][j]=1;
else if(j==1) cnt[i][j]=i%k;
else cnt[i][j]=(cnt[i-1][j]+cnt[i-1][j-1])%k;
}
}
}
int main(){
//freopen("problem.in","r",stdin);
//freopen("problem.out","w",stdout);
int T;
scanf("%d%d",&T,&k);
cal_cnt();
if(k==1) for(int i=1;i<N;i++) dp[i][0]=dp[i-1][0]+1;
for(int i=1;i<N;i++){
for(int j=1;j<=i-1;j++){
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+(cnt[i][j]==0);//printf("%d %d %d\n",i,j,dp[i][j]);
}
dp[i][i]=dp[i][i-1];
}
while(T--){
int ans=0;
scanf("%d%d",&n,&m);
if(m>n) m=n;
printf("%d\n",dp[n][m]);
/*for(int i=1;i<=n;i++){
for(int j=1;j<=min(i,m);j++){
if(cnt[i]-(cnt[j]+cnt[i-j])>0) ans++;
}
}
printf("%d\n",ans);*/
}
fclose(stdin);
fclose(stdout);
return 0;
}
[NOIP2016 提高组] 蚯蚓
题目大意
给定 n 只蚯蚓,每一时刻会进行如下操作:
选取当前所有蚯蚓中最长的一只,假设其长度为 len ;
将这只蚯蚓切成两只,长度分别为 len*u/v和 (1 - p) ( p 已给出);
其余所有蚯蚓长度增加 q。
现在给出一个整数 m ,求从开始到 m 个时刻后的过程中每个时刻取出的最长的蚯蚓的长度,以及 m 个时刻后所有蚯蚓的长度(从大到小排列)。
注意:蚯蚓的长度可以为零。
解题思路
注意到每次要求取出当前最长的蚯蚓,可以想到用堆来维护。但是又因为 q 的存在而我们无法在堆上做区间修改,所以我们需要找到一个方式来避免这种”区间修改”。
对于任意一只蚯蚓,其切断后产生的两只新蚯蚓的长度一定不会大于它前面被选取过的蚯蚓所得出的两只新蚯蚓的长度。
这样,我们就得到了题目中隐含的单调性的信息。
所以我们就可以用三个队列 w, l, r 分别记录未被选取过的蚯蚓的长度、某只蚯蚓被切割完后得到的第一段蚯蚓的长度和某只蚯蚓被切割完后得到的第二段蚯蚓的长度。举个例子,对于一只还未被选取过的蚯蚓 a ,现在它的长度记录在 w 数组中。它被切割后得到两只新蚯蚓 a1 和 a2 ,其长度分别放入 l 数组和 r 数组中去。
这样一来,在将 w 数组排序后,我们每次只需要从这三个队列的三个队头中找到最大的那一个,即为这一次操作取出的蚯蚓。
算法时间复杂度 O(n + 2 * m)。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const int N=1e5+10,M=7e6+10,INF=0x3f3f3f3f;
int n,m,q,u,v,t;
int a[M];
int cut1[M],cut2[M];
//priority_queue<int> s;
bool cmp(int x,int y){
return x>y;
}
inline int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return x*f;
}
int main(){
//freopen("earthworm.in","r",stdin);
//freopen("earthworm.out","w",stdout);
n=read();m=read();q=read();u=read();v=read();t=read();
for(int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+n+1,cmp);
int t1=0,t2=0;
int p=1,p1=1,p2=1;
int x=0;
for(int i=1;i<=m;i++){
if(p>n){
if(cut1[p1]>cut2[p2])
x=cut1[p1++]+(i-1)*q;
else x=cut2[p2++]+(i-1)*q;
}
else if(a[p]>=cut1[p1]&&a[p]>=cut2[p2]) x=a[p++]+(i-1)*q;
else if(cut1[p1]>=a[p]&&cut1[p1]>=cut2[p2]) x=a[p1++]+(i-1)*q;
else x=a[p2++]+(i-1)*q;
LL x1=(LL)x*(LL)u/(LL)v;
LL x2=(LL)x-x1-i*q;
x1-=i*q;
cut1[++t1]=x1;
cut2[++t2]=x2;
if(i%t==0) printf("%d ",x);
}
puts("");
int sum=m*q;
for(int i=1;i<=m+n;i++){
if(p>n){
if(p1>t1) x=cut2[p2++]+sum;
else if(p2>t2) x=cut1[p1++]+sum;
else if(cut1[p1]>cut2[p2])
x=cut1[p1++]+sum;
else x=cut2[p2++]+sum;
}
else if(p1>t1){
if(p2>t2) x=a[p++]+sum;
else if(a[p]>cut2[p2]) x=a[p++]+sum;
else x=a[p2++]+sum;
}
else if(p2>t2){
if(a[p]>cut1[p1]) x=a[p++]+sum;
else x=a[p1++]+sum;
}
else if(a[p]>cut1[p1]&&a[p]>cut2[p2]) x=a[p++]+sum;
else if(cut1[p1]>cut2[p2]) x=a[p1++]+sum;
else x=a[p2++]+sum;
if(i%t==0) printf("%d ",x);
}
/*for(int i=1;i<=n;i++){
int a=read();
s.push(a);
}
for(int i=1;i<=m;i++){
int x=s.top()+(i-1)*q;
s.pop();
if(i%t==0) printf("%d ",x);
LL x1=(LL)x*(LL)u/(LL)v;
LL x2=(LL)x-x1-q*i;
x1-=q*i;
s.push(x1);s.push(x2);
}
puts("");
for(int i=1;i<=m+n;i++){
int x=s.top();
s.pop();
x+=m*q;
if(i%t==0) printf("%d ",x);
}*/
fclose(stdin);
fclose(stdout);
return 0;
}