Wannafly挑战赛6 A（二分）B（dfs）C（公式推导）D（思维）E（技巧）

时间：2021-12-19 21:01:28

A题：

题目描述

多次查询[l,r]范围内的完全平方数个数

定义整数x为完全平方数当且仅当可以找到整数y使得y*y=x

输入描述:

第一行一个数n表示查询次数
之后n行每行两个数l,r

输出描述:

对于每个查询，输出一个数表示答案
示例1

输入

5
1 3
1 4
2 4
4 4
1 1000000000

输出

1
2
1
1
31622

备注:

n <= 100000
0<= l <= r <= 1000000000


题解：

给出的查询次数很多，故不能暴力枚举，很容易想到用二分

最后注意 0 也是平方数，并且二分查找得到的数字并不一定在区间内部


#include<math.h>
#include<stdio.h>
#include<algorithm>
using namespace std;

int a[40000],len;
void init(){
    len=sqrt(1000000000.0)+1;
    for(int i=1;i<=len;i++)
        a[i]=i*i;
}

int binary_search(int key){
    int left=0,right=len,mid,ans;
    while(left<=right){
        mid=(left+right)/2;
        if(a[mid]<=key) ans=mid,left=mid+1;
        else            right=mid-1;
    }
    return ans;
}

int main()
{
    init();
    int n,l,r;
    //freopen("in.txt","r",stdin);
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d",&l,&r);
        int x=binary_search(l);
        int y=binary_search(r);
        int ans=y-x+1;
        int t=sqrt(l*1.0);
        if(t*t!=l) ans--;
        printf("%d\n",ans);
    }
    return 0;
}


B题：

题目描述

你在打比赛，这场比赛总共有12个题

对于第i个题，你的队伍有a[i]的几率解决她

如果解决不了她呢？

由于所有人讨论的都很大声

所以你有b[i]的概率从左边那个队那里听会这个题的做法

有c[i]的概率从右边那个队那里听会这个题的做法

请问最终你们队伍解出0-12题的概率分别是多少

输入描述:

第一行12个数表示a[1] -> a[12]
第二行12个数表示b[1] -> b[12]
第三行12个数表示c[1] -> c[12]

输出描述:

输出13行，第i行表示解出i-1题的概率
保留6位小数
示例1

输入

0.20 0.30 0.37 0.40 0.45 0.50 0.57 0.60 0.75 0.76 0.77 0.83
0.85 0.88 0.90 0.94 0.100 0.104 0.105 0.107 0.115 0.120 0.122 0.125
0.128 0.130 0.134 0.140 0.149 0.150 0.152 0.155 0.170 0.183 0.203 0.240

输出

0.000000
0.000000
0.000000
0.000011
0.000160
0.001508
0.009620
0.041938
0.124153
0.243773
0.301960
0.212453
0.064424

题解：

看清楚题意就很容易做，题目求做出来0 个题目的概率，到做出来12个题目的概率分别是多少

先计算出每一道题目做不出的概率：自己做不出*听不懂两边的人的题解

然后dfs暴力枚举当做出来 i 道题目的概率即可


#include<stdio.h>
#define maxn 20
double a[maxn],b[maxn],c[maxn],d[maxn];;

double dfs(int now,int num){
    double ans=1;
    if(now==13&&num) return 0;
    if(now==13) return ans;
    if(num==0){
        for(int i=now;i<=12;i++)
            ans*=(1-d[i]);
        return ans;
    }
    return ans*(dfs(now+1,num-1)*d[now]+dfs(now+1,num)*(1-d[now]));
}

int main()
{
    //freopen("in.txt","r",stdin);
    for(int i=1;i<=12;i++)
        scanf("%lf",&a[i]);
    for(int i=1;i<=12;i++)
        scanf("%lf",&b[i]);
    for(int i=1;i<=12;i++)
        scanf("%lf",&c[i]);

    double ans=1;
    for(int i=1;i<=12;i++)
        d[i]=1-(1-a[i])*(1-b[i])*(1-c[i]),ans*=(1-d[i]);
    printf("%0.6lf\n",ans);
    for(int i=1;i<=12;i++){
        ans=dfs(1,i);
        printf("%0.6lf\n",ans);
    }
    return 0;
}


C题：

题目描述

求所有长度为n的01串中满足如下条件的二元组个数：
设第i位和第j位分别位a i和a j（i<j），则a i=1,a j=0。
答案对1e9+7取模。

输入描述:

输入一个n
n <= 1018

输出描述:

输出答案对1e9+7取模
示例1

输入

3

输出

6

题解：

我们很容易发现这个 01 串中，所有2^n个数字中，0 1 数量是对等的

此时我们假设第 i 位为 0，那么前面有 i-1 位  后面有 n-i 位

那么前面有2^(i-1)个数，每一个数字有 i-1 个 0 或者 1 ，那么 1 可以出现 ( i - 1 ) * 2^( i - 1) / 2 次，即 ( i - 1 ) * 2^( i - 2)

此时已经组成了 1 0 串了（逆序正序其实都是一样的），第 i 位后面还有 2^(n-i) 个数，根据乘法原理得到 ( i - 1 ) * 2^( i - 2) * 2^(n-i)

化简得到第 i 位为 0 的时候满足条件的个数了 ( i - 1 ) * 2^( n - 2)

求个和得到 n*( n - 1 ) * 2^( n - 3)

快速幂搞一下即可


#include<stdio.h>
#define LL long long
#define mod 1000000007

LL fast_pow(LL a,LL b){
    LL ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int main()
{
    LL n;
    //freopen("in.txt","r",stdin);
    while(scanf("%lld",&n)!=EOF)
    {
        if(n<=1)       printf("0\n");
        else if(n==2)  printf("1\n");
        else printf("%lld\n",n%mod*((n-1)%mod)%mod*fast_pow(2,n-3)%mod);
    }
    return 0;
}

D题：

题目描述

106号房间共有n名居民， 他们每人有一个重要度。房间的门上可以装若干把锁。假设共有k把锁，命名为1到k。每把锁有一种对应的钥匙，也用1到k表示。钥匙可以复制并发给任意多个居民。每个106房间的居民持有若干钥匙，也就是1到k的一个子集。如果几名居民的钥匙的并集是1到k，即他们拥有全部锁的对应钥匙，他们都在场时就能打开房门。新的陆战协定规定，一组居民都在场时能打开房门当且仅当他们的重要度加起来至少为m。问至少需要给106号房间装多少把锁。即，求最小的k，使得可以适当地给居民们每人若干钥匙(即一个1到k的子集)，使得任意重要度之和小于m的居民集合持有的钥匙的并集不是1到k，而任意重要度之和大于等于m的居民集合持有的钥匙的并集是1到k。

输入描述:

第一行两个整数n和m，0<n<21，0<m<1000000001。
第二行n个整数表示居民们的重要度。
重要度在[1,1000000000]之间。

输出描述:

一个整数表示最少需要多少把锁。
示例1

输入

4 3
1 1 1 1

输出

6

说明

106号房共有4名居民，只有3人在场时才能打开门。这时共需6把锁。

题意：

中文题，自己看

题解：

答案就是：1~n 的满足下面条件的子集数量之和，设为 x

这些人的重要度之和小于 m ，但是加入任意一个人都会使得重要度之和大于等于 m

简要证明：

易知这 x 子集都至少缺少某一把钥匙，而任意两个子集缺的钥匙不能是同一把，如果缺同一把就不能满足加入任意一个人使得这个子集重要度之和大于等于 m 且刚好有全部的钥匙

#include<bits/stdc++.h>
using namespace std;
#define LL long long

int a[30],n,m;
LL dfs(int now,LL cnt,LL t)
{
    if(t==-1&&cnt+a[now+1]>=m) return 1;
    if(cnt+t>=m)  return 1;
    if(now>n) return 0;

    LL ans=0;
    if(cnt+a[now]<m) ans+=dfs(now+1,cnt+a[now],t);
    ans+=dfs(now+1,cnt,t==-1?a[now]:t);
    return ans;
}

int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        LL num=0;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]),num+=a[i];
        if(num<m) {puts("1");continue;}
        sort(a+1,a+1+n);a[n+1]=0;
        LL ans=dfs(1,0,-1);
        printf("%lld\n",ans);
    }
    return 0;
}


E题：

题目描述

对于一个数字串 s，若能找到一种将其分成左右两个非空部分 s1,s2 的方案，使得：
    1、s1,s2 均无前导零
    2、存在两个正整数 a,b，使得 b 整除 a，且 a/b=s1, a*b=s2
那么我们记这是一个合法的分法。特别地，如果一个串有两个或更多个不同的合法的分法，那么我们称这个数字串是双拆分数字串。
给定一个 n，要求构造一个长度恰为 n 的双拆分数字串。如果无解，输出 -1。

输入描述:

输入仅一行一个正整数 n(1 <= n <= 300)。

输出描述:

仅一行一个数字串或者 -1。
示例1

输入

8

输出

24419764


题意：

让你输出一个长度为n的数字，这个数字有两种或者更多的上叙的分解方法

题解：

分析得到n<=3无解

n = 4 ： 1144 是一个合法解

（s1 =  1，s2 = 144，a = 12，b = 12）

（s1 = 11, s2 =  44，a = 22，b =  2）

n = 5 ： 16400 是一个合法解

（s1 =  1，s2 = 6400，a = 80，b = 80）

（s1 = 16, s2 =  400，a = 80，b =  5）

之后 n = 6,7,8,,,,只需要将上面的 b 乘以 10 即可，输出即为答案 


#include<stdio.h>

int main()
{
    int n;
    //freopen("in.txt","r",stdin);
    while(scanf("%d",&n)!=EOF)
    {
        if(n<=3) puts("-1");
        else if(n&1){
            printf("16400");
            for(int i=6;i<=n;i++) printf("0");
            puts("");
        }
        else{
            printf("1144");
            for(int i=5;i<=n;i++) printf("0");
            puts("");
        }
    }
    return 0;
}


标签：

相关文章