【jzoj】2018.1.30NOIP普及组——模拟赛D组
@aaa@qq.com
前言
写博客时间 2018/1/30 22:36。
感想：出数据的dalao我服！
正题
题目1：二项式展开式（jzoj2254）
输入一个整数，求展开(a+b)^n。展开方式为 (a+b)^n=?a^n+?a^(n-1)b+?a^(n-2)b^2+…+?b^n
其中” ? “为系数。如果系数为 1，则需要省略系数；如果次数为 1，则需要省略次数；如果次数为 0，则需要省略；如果系数为 0，则需要省略这一项。注意：前面(a+b)^n 的次数n是必有的。
这里求组合我用的是杨辉三角。
样例输入
样例输入1
3
样例输入2
5
样例输出
样例输出1
(a+b)^3=a^3+3a^2b+3ab^2+b^3
样例输出2
(a+b)^5=a^5+5a^4b+10a^3b^2+10a^2b^3+5ab^4+b^5
代码
#include<cstdio>
using namespace std;
int n;
unsigned long long f[67][67];
int main()
{
//freopen("power.in","r",stdin);
//freopen("power.out","w",stdout);
scanf("%d",&n);
if (n==1) {printf("(a+b)^1=a+b");return 0;}//特殊情况
if (n==2) {printf("(a+b)^2=a^2+2ab+b^2");return 0;}//特殊情况
f[0][0]=1;
for (int i=1;i<=n;i++)
{
f[i][0]=1;
for (int j=1;j<=n;j++)
{
f[i][j]=f[i-1][j]+f[i-1][j-1];
}
}//杨辉三角
printf("(a+b)^%d=",n);//开头输出
for (int i=0;i<=n;i++)
{
if (i==0) printf("a^%d",n);//头
else if (i==1) printf("%da^%db",n,n-1);
else if (i==n-1) printf("%dab^%d",n,n-1);
else if (i!=n) printf("%llda^%db^%d",f[n][i],n-i,i);//输出不解释
if (i!=n) printf("+");//加号
if (i==n) printf("b^%d",n);//尾
}
}题目2：溜冰（jzoj2255）
一个冰道，长L，有N个转弯点。每个转弯点限速S[i]，距离起点D[i]米处。每一米速度可以加1或减1。求这条道能加速到的最快速度。
因此最快速度是5。
输入
第一行两个整数L和N。
第二行到第N+1行：第i+1行表示第i个转弯处的两个参数D[i]，S[i]。
输出
输出仅一行，一个整数表示滑行过程中的最大速度（包括起点和终点的速度）。
样例输入
14 3
11 1
7 3
13 8
样例输出
5
首先为了方便处理，我们先根据距离进行一次快排。
我们不难发现这冰道有3种情况。
1.从一个点无论如何加速都无法到达下一个的最大限速，如图：
这里我们就不停加速就是 s[i]=s[i-1]+d[i]-d[i-1] ans=max(ans,s[i])
2.
那我们先假设距离第一个点x米前减速，之后加速。那我们可以推一下x是前一段距离，s[i]+x是加速到达的高度，s[i]+x-s[i+1]是需要减速的距离，用两段距离加起来就是它们之间的长度也就是x+s[i]+x-s[i+1]=d[i+1]-d[i]，然后就可以推出 x=(s[i]+s[i+1]+d[i])/2。
3.
如果到达前一个点的最大限速，就算不停减速也到不了下一个点的最大限速，那我们只能提前到推一遍推出新的最大限速。就算：s[i-1]=s[i]+d[i]-d[i-1]
代码
#include<cstdio>
#include<algorithm>
using namespace std;
struct point{
int x,w;
};//结构体，快排用
point a[100001];
int sp,l,ll,nsp,n,s;
bool cmp(point dx,point dy)
{
return dx.x<dy.x;
}//快排函数
int main()
{
//freopen("skate.in","r",stdin);
//freopen("skate.out","w",stdout);
scanf("%d %d",&l,&n);
for (int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].w);
}//输入
sort(a+1,a+n+1,cmp);//排序
for (int i=n;i>=1;i--)
{
a[i-1]=min(a[i-1].w,a[i].w+a[i].x-a[i-1].x);//第三种情况
}
a[0].w=1;//起点速度为1
for (int i=1;i<=n;i++)
{
ll=a[i].x-a[i-1].x;//距离
if (a[i].w>a[i-1].w)
{
if (a[i-1].w+ll<=a[i].w) {a[i].w=a[i-1].w+ll;s=max(a[i].w,s);}//第一种情况
else {s=max(s,(int)(a[i].w+a[i-1].w+ll)/2);}//第二种
}
else {s=max(s,(int)(a[i].w+a[i-1].w+ll)/2);}//第二种
}
s=max(s,a[n].w+l-a[n].x);//终点前的加速
printf("%d",s);//输出
}题目3：方案数（jzoj2256）
有N个人，无数块黑白巧克力。其中每个人只能拿一种巧克力，至少c个人拿了巧克力。接下来2行，分别表示每个同学最多拿黑巧克力的个数和最多拿白巧克力的个数。输出他们拿巧克力的方案数%10007。
样例输入
样例输入1
2 2
1 1
1 1
样例输入2
2 2
2 2
2 3
样例输出
样例输出1
1
样例输出2
4
我们用f[i][j]来表示前i个人拿了j个巧克力的方案数，然后把f[i][c+1]+f[i][c+2]+f[i][c+3]…都合并到f[i][c]那里。动态转移方程：
f[i][j]=f[i-1][j]*b[i] + f[i-1][j-1]*a[i]（j!=c）
f[i][j]=f[i-1][j](a[i]+b[i]) + f[i-1][j-1]a[i] (j=c)
f[i-1][j]*b[i]表示白巧克力
f[i-1][j-1]*a[i]表示黑巧克力
f[i-1][j-1]*a[i]表示已经到达或超过20个人选的黑巧克力
#include<cstdio>
#include<iostream>
using namespace std;
int f[100001][21],n,c,bl[100001],wh[100001],s;
int main()
{
//freopen("fas.in","r",stdin);
//freopen("fas.out","w",stdout);
scanf("%d%d",&n,&c);
s=1;f[0][0]=1;//初始化
for (int i=1;i<=n;i++)
{
scanf("%d",&bl[i]);
bl[i]%=10007;
}
for (int i=1;i<=n;i++)
{
scanf("%d",&wh[i]);
wh[i]%=10007;
f[i][0]=(f[i-1][0]*(wh[i]%10007))%10007;//初始化2
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=c;j++)
{
if (j<c) f[i][j]+=(f[i-1][j]*wh[i]%10007+f[i-1][j-1]*bl[i]%10007)%10007;
else f[i][j]+=((f[i-1][j]*((wh[i]+bl[i])%10007))%10007+(f[i-1][j-1]*bl[i])%10007)%10007;//动态转移
}
}
printf("%d",f[n][c]);//输出
}题目4：小L（jzoj2257）
给你N个数对(a[i], b[i])，计算函数
函数y四舍五入取整。
将N个数对去掉其中的K个后计算一个新的y值，均能满足y ≤ λ，求最小的λ 值。
输入
输入包含多组数据，每组测试数据包含：
第一行两个整数N和 K；
第二行为N个数：a[1] a[2] … a[n]
第三行为N个数：b[1] b[2] … b[n]
当N、K均为0时输入结束。
输出
对应每组数据输出一行，即找到的最小的λ值。
样例输入
3 1
5 0 1
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0
样例输出
83
100
设函数值y的最小值为x,则：
则：
则：
最后二分答案
代码
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
long long n,k;
long long s,s1,s2,sa,sb,m1,m2,left,right;
struct point{
long long n1,n2;
long long c;
};
point a[10001];
bool cmp(point x,point y)
{
return x.c>y.c;
}
bool ok(int x)
{
long long s1=0,s2=0;
for (int i=1;i<=n-k;i++)
{
s1+=a[i].n1;s2+=a[i].n2;//累加
}
return round(100.0*s1/s2)>x;//四舍五入
}
int main()
{
freopen("math.in","r",stdin);
freopen("math.out","w",stdout);
while (true)
{
scanf("%d%d",&n,&k);
if (n==0 && k==0) break;
m2=(long long)1e18;sa=0;sb=0;m1=0;
for (int i=1;i<=n;i++)
{scanf("%d",&a[i].n1);sa+=a[i].n1;m1=max(m1,(long long)a[i].n1);}
for (int i=1;i<=n;i++)
{scanf("%d",&a[i].n2);sb+=a[i].n2;m2=min(m2,(long long)a[i].n2);}
left=100*sa/sb;right=100*m1/m2;//确定范围
while (left<=right)//二分答案
{
long long mid=(left+right)/2;
for (int i=1;i<=n;i++) a[i].c=a[i].n1*100-mid*a[i].n2;//计算
sort(a+1,a+1+n,cmp);//快排
if (ok(mid)) left=mid+1;//判断
else right=mid-1;
}
printf("%d\n",left);//输出
}
}后序
其实这后面是我第二天来写的，好了去做题了(^o^)/