ACM训练日记—4月14日（2018年长沙理工大学第十三届程序设计竞赛）

本文主要是介绍ACM训练日记—4月14日（2018年长沙理工大学第十三届程序设计竞赛），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

主要整理下今天的题目，数学题挺多的。

C题：取手机

题意：durong有a台iphonex和b台s8，并且放在一个保险箱里，durong现在一台一台从保险箱随机拿出这些手机，现在他想知道第k次拿出s8的概率是多少。

问题等价于:

a个红球b个白球排队,排在第k个位置的是红球的概率，所以是C(a,1)A(a+b-1,a+b-1)/A(a+b,a+b)=a/(a+b)。

D题：zzq的离散数学教室1

对于任意两个正整数a和b(a<b)来说，如果b%a==0,并且不存在一个正整数c（a<c<b），使得条件b%c==0和c%a==0同时成立，那么我们就在节点a和节点b之间连一条边。
现在问题是，给你们2个数L，R(1<=L,R<=1e6)。

暴力水题，看代码吧。

using namespace std;
const int MAXN = 1000005;
bool flag[MAXN];
int primes[MAXN / 3], pi;
void Prime()//筛素数
{
int i, j;
pi = 0;
memset(flag, false, sizeof(flag));
for (i = 2; i < MAXN; i++)
{
if (!flag[i])
primes[++pi] = i;
for (j = 1; (j <= pi) && (i * primes[j] < MAXN); j++)
{
flag[i * primes[j]] = true;
if (i % primes[j] == 0) //这句保证每个非素数只被筛去一次
break;
}
}
}
int main()
{
Prime();
int l,r;
while(scanf("%d%d",&l,&r)!=EOF)
{
ll ans=0;
for(int i=1;i<=pi&&primes[i]<=r;i++)
{
int t=r/primes[i];// t 代表1-t的数乘一个素数小于r
if(t>=l) ans=ans+(t-l+1);取出大于l的部分
}
cout<<ans<<endl;
}
}

H题：数学考试

今天qwb要参加一个数学考试，这套试卷一共有n道题，每道题qwb能获得的分数为ai，qwb并不打算把这些题全做完，他想选总共2k道题来做，并且期望他能获得的分数尽可能的大，他准备选2个不连续的长度为k的区间,
即[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,...,R+k-1]（R >= L+k）。(1<=n<=200,000)

思路：先压缩一下，将所有k个连续的数加起来存线段树求出区间最大值，然后暴力每一个新数，查找满足条件的区间里最大值。。。还是看代码吧。

#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
ll a[200005];
ll b[200005];
ll n,k;
ll sum[200005*4];
ll cnt;
void pushup(ll rt)
{
sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
}
void build(ll l,ll r,ll rt)
{
if(l==r)
{
sum[rt]=b[++cnt];
return;
}
ll m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
ll quert(ll L,ll R,ll l,ll r,ll rt)
{
if(L<=l&&r<=R)
{
return sum[rt];
}
ll m=(l+r)>>1;
ll ret=-99999999999;
if(L<=m) ret=max(ret,quert(L,R,lson));
if(R>m) ret=max(ret,quert(L,R,rson));
return ret;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld",&n,&k);
if(n<k*2)
{
cout<<0<<endl;
continue;
}
ll sum=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
sum+=a[i];
if(i>k) sum=sum-a[i-k];
if(i-k+1>=1) b[i-k+1]=sum;//先压缩，存新数组
}
n=n-k+1;
//cout<<n<<endl;
/*for(int i=1;i<=n;i++)
{
cout<<b[i]<<" ";
}*/
cnt=0;
build(1,n,1);//建树
ll ans=-999999999999;
for(int i=1;i+k<=n;i++)
{
ll e=quert(i+k,n,1,n,1);//查找满足条件区间最大值
if(e+b[i]>ans)
{
ans=e+b[i];
}
//cout<<i<<" "<<i+k<<endl;
}
cout<<ans<<endl;
}
}

J题：杯子

题意：一天durong同学买了一个无限长的杯子，同时买了n个球，并且标号为1，2，3......n，durong同学突然想到一个问题----如果他把n个球依次，也就是按照1，2，3...n的顺序放进杯子里，然后在全部拿出来（注意不一定要等到全部放进去才能拿出球），并且会记录放进和拿出球的顺序，

durong想知道，要满足当第m个球进去后，杯子中此时恰好有k个球，然后仍然要把剩下的n-m个球放进去，最后杯中的球要取光，这样的放进和拿出球的顺序有多少种，答案有可能很大，所以mod上1e9+7

这个题后来才知道居然在牛客上出现过，只是题目不一样。

正好总结下卡特兰数

来自：https://blog.csdn.net/haut_ykc/article/details/79426135

题解：进栈出栈问题是组合数学课程中所讲的经典卡特兰数问题之一，其余的还有：

（1）n个左括号，m个右括号的合法组合
（2）n个节点构成的二叉树，共有多少种情形？
（3）买票找零（一开始柜台没零钱）
（4）n*n棋盘从左下角走到右上角而不穿过主对角线的走法
（5）求一个凸多边形区域划分成三角形区域的方法数？
（6）矩阵连乘的括号化
（7）在圆上选择2n个点，将这些点成对连接起来使得所得到的n条线段不相交的方法数？
（8）一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列

这些问题都可以用卡特兰数公式求解，具体证明略。。

对于本题，明显的卡特兰数，对于前m个数，对于当前任意一个元素之前的操作，一定是进栈大于等于出栈，对于当前元素后边的元素则一定是出栈大于等于进栈，两者相乘即为答案。//最关键就是这句。。。。

一般公式：ans=C(n+m,n)-C(n+m,n+1)//卡特兰数公式，n代表0，m代表1，ans求满足任何时间都1个数大于等于0

下面来自：https://blog.csdn.net/logzhangrui/article/details/43083549

n个1，n个0组成的2n为二进制数，从左往右，1的个数>=0的个数。从2n个位置填入n个1的方法有C(2n，n)种，
其他位置自动填0；从C(2n,n)中减去不合法的即可；
不合法发生在某奇数位2m+1上，前面有m+1个0，m个1；而此后的2n-2m-1个位置上，会有n-m个1，n-m-1个0；如果这后面2n-2m-1的位置上0，1位置互换，即有n-m个0，n-m-1个1；结果得n+1个0，和n-1个1组成的2n为二进制数，所以一个不合法的数对应一个n-1个1，n+1个0组成的一个排列；
反过来，任何一个有n+1个0，n-1个1组成的2n位二进制，因为0个个数多两个，所以会在某一奇数位2m+1上出
现0的统计个数>1的个数，前面有m+1个0，m个1；而此后的2n-2m-1个位置上，会有n-m-1个1，n-m个0；同样
后面的0，1互换，这样就组成了一个由n个1，n个0组成的2n位二进制数！而此序列是不合法的。即n+1个1，n-1

个0组成的2n位数比对应一个不合法的n个1，n个0组成的2n位数！

来自：https://blog.csdn.net/haut_ykc/article/details/79426135

#define maxn 2000005
#define mod 1000000007
#define ll long long
ll fac[maxn],inv[maxn],n,m,k;
ll q(ll x,ll y)
{
ll res=1ll;
while(y)
{
if(y%2)
res=res*x%mod;
x=x*x%mod;
y/=2;
}
return res;
}
ll C(ll x,ll y)
{
if(y<0 || y>x) return 0;
return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}
ll cal(ll x,ll y)
{
return (C(x+y,x)-C(x+y,x+1)+mod)%mod;
}
int main(void)
{
int T;
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(ll i=2;i<=maxn-5;i++)
{
fac[i]=fac[i-1]*i%mod;
inv[i]=q(fac[i],mod-2);
}
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld%lld",&n,&m,&k);
printf("%lld\n",cal(m-1,m-k)*cal(n-(m-k),n-m)%mod);
}
return 0;
}