BC18hdoj5104&&hdoj5105&&hdoj5106 Primes Problem Math Problem Bits Problem

142 阅读 0 评论 94 点赞

我是靠谱客的博主留胡子硬币，这篇文章主要介绍BC18hdoj5104&&hdoj5105&&hdoj5106 Primes Problem Math Problem Bits Problem，现在分享给大家，希望可以做个参考。

Primes Problem

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2014 Accepted Submission(s): 926

Problem Description

Given a number n, please count how many tuple(p1, p2, p3) satisfied that p1<=p2<=p3, p1,p2,p3 are primes and p1 + p2 + p3 = n.

Input

Multiple test cases(less than 100), for each test case, the only line indicates the positive integer

n(n≤10000) .

Output

For each test case, print the number of ways.

Sample Input

3
9

Sample Output

0
2

Source

BestCoder Round #18

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<list>
#include<vector>
using namespace std;
const int maxn=10010;
int num[maxn];
int prime[maxn];
bool isprime[maxn];
int main()
{
int n,i,j,k,ans,cnt=0;
memset(isprime,false,sizeof(isprime));
isprime[0]=isprime[1]=true;
for(i=2;i<maxn;++i){
if(isprime[i])continue;
prime[cnt++]=i;
for(j=i*i;j<maxn;j+=i){
isprime[j]=true;
}
}
while(scanf("%d",&n)!=EOF){
int ans=0;//2 3 5 7
for(i=0;i<cnt&&prime[i]<=n;++i){
for(j=i;j<cnt&&prime[i]+prime[j]<=n;++j){
if(!isprime[n-prime[i]-prime[j]]&&(n-prime[i]-prime[j])>=prime[j])ans++;
}
}
printf("%dn",ans);
}
return 0;
}

Math Problem

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2418 Accepted Submission(s): 579

Problem Description

Here has an function:

f(x)=|a∗x3+b∗x2+c∗x+d|(L≤x≤R)
Please figure out the maximum result of f(x).

Input

Multiple test cases(less than 100). For each test case, there will be only 1 line contains 6 numbers a, b, c, d, L and R.

(−10≤a,b,c,d≤10,−100≤L≤R≤100)

Output

For each test case, print the answer that was rounded to 2 digits after decimal point in 1 line.

Sample Input


1.00 2.00 3.00 4.00 5.00 6.00

Sample Output


310.00

Source

BestCoder Round #18

注意a和b等于0的情况还有精度

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<list>
#include<vector>
#define eps 1e-10
using namespace std;
int main()
{
double a,b,c,d,l,r;
while(scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&l,&r)!=EOF){
if(fabs(a)<=eps){
if(fabs(b)<=eps){
printf("%.2lfn",max(fabs(a*l*l*l+b*l*l+c*l+d),fabs(a*r*r*r+b*r*r+c*r+d)));
}
else {
double x=-c/(2.0*b);
if(x-l>=-eps&&x-r<=eps){
printf("%.2lfn",max(max(fabs(a*l*l*l+b*l*l+c*l+d),fabs(a*r*r*r+b*r*r+c*r+d)),fabs(a*x*x*x+b*x*x+c*x+d)));
}
else {
printf("%.2lfn",max(fabs(a*l*l*l+b*l*l+c*l+d),fabs(a*r*r*r+b*r*r+c*r+d)));
}
}
continue;
}
double t=4.0*b*b-12.0*a*c;
if(t<=eps){
printf("%.2lfn",max(fabs(a*l*l*l+b*l*l+c*l+d),fabs(a*r*r*r+b*r*r+c*r+d)));
}
else {
t=sqrt(t);
double x1=(-2.0*b+t)/(6.0*a);
double x2=(-2.0*b-t)/(6.0*a);
if(x1-l>=-eps&&x1-r<=eps&&x2-l>=-eps&&x2-r<=eps)
printf("%.2lfn",max(max(fabs(a*l*l*l+b*l*l+c*l+d),fabs(a*r*r*r+b*r*r+c*r+d)),max(fabs(a*x1*x1*x1+b*x1*x1+c*x1+d),fabs(a*x2*x2*x2+b*x2*x2+c*x2+d))));
else if(x1-l>=-eps&&x1-r<=eps){
printf("%.2lfn",max(max(fabs(a*l*l*l+b*l*l+c*l+d),fabs(a*r*r*r+b*r*r+c*r+d)),fabs(a*x1*x1*x1+b*x1*x1+c*x1+d)));
}
else if(x2-l>=-eps&&x2-r<=eps){
printf("%.2lfn",max(max(fabs(a*l*l*l+b*l*l+c*l+d),fabs(a*r*r*r+b*r*r+c*r+d)),fabs(a*x2*x2*x2+b*x2*x2+c*x2+d)));
}
else {
printf("%.2lfn",max(fabs(a*l*l*l+b*l*l+c*l+d),fabs(a*r*r*r+b*r*r+c*r+d)));
}
}
}
return 0;
}

Bits Problem

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 701 Accepted Submission(s): 183

Problem Description

If the quantity of '1' in a number's binary digits is n, we call this number a n-onebit number. For instance, 8(1000) is a 1-onebit number, and 5(101) is a 2-onebit number. Now give you a number - n, please figure out the sum of n-onebit number belong to [0, R).

Input

Multiple test cases(less than 65). For each test case, there will only 1 line contains a non-negative integer n and a positive integer

R(n≤1000,0<R<21000) , R is represented by binary digits, the data guarantee that there is no leading zeros.

Output

For each test case, print the answer module 1000000007 in one line.

Sample Input


1 1000

Sample Output

Source

BestCoder Round #18

对于一个n-bit数，可以根据与R最高不同位的位置分成几类。比如R=100100010，可以分成0xxxxxxxx,1000xxxxx,10010000x三类。x处可任取0或者1。对于一类数，设与R不同的最高位为L（从低位数起，base 0)，设n0 = n - 高于L位的1的个数。此时和分两部分，高于L位的有

CLn0C^{n_0}_L

乘以L位之前的数字，低于L位的部分有

CLn0∗n0/L∗(2L−1)C^{n_0}_L * n0 / L * (2^{L-1})

(因为低于L位的部分每一个位的1的个数相同，1的个数总数有

CLn0∗n0C^{n_0}_L*n_0

，平均到每个位则是

CLn0∗n0/LC^{n_0}_L*n_0/L

。所以低位部分和有

CLn0∗n0/L∗(1+2+...+2L−1)=CLn0∗n0/L∗(2L−1)C^{n_0}_L*n_0/L*(1+2+...+2^{L-1}) = C^{n_0}_L*n_0/L*(2^{L-1})

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<list>
#include<vector>
#define MOD 1000000007
using namespace std;
const int maxn=1010;
char bit[maxn];
long long Pow[maxn];
int C[maxn][maxn];
void init(){
Pow[0]=1;
for(int i=0;i<maxn;++i){
C[i][i]=C[i][0]=1;
if(i)Pow[i]=(Pow[i-1]*2)%MOD;
}
for(int i=2;i<maxn;++i){
for(int j=1;j<i;++j){
C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
}
}
}
int main()
{
init();
int n,i,j,k;
while(scanf("%d %s",&n,bit)!=EOF){
int len=strlen(bit);
long long pre=0,cnt=0,ans=0;
for(i=0;i<len;++i){
if(bit[i]=='1'){
if((n-cnt)<=(len-i-1)){
if(n-cnt)ans=(ans+C[len-i-2][n-cnt-1]%MOD*(Pow[len-i-1]-1))%MOD;
ans=(ans+pre*C[len-i-1][n-cnt])%MOD;
pre=(pre+Pow[len-i-1])%MOD;cnt++;
}
}
if(cnt>n)break;
}
printf("%lldn",ans);
}
return 0;
}