蓝桥杯练习 Day1 题解 - dblank

蓝桥杯练习 Day1 题解

one

A - Little Elephant and Numbers

题意:

小象爱数字。
他有一个正整数X。小象想找到正整数d的数目,例如d是x的因子,d和x在它们的十进制表示中至少有一个相同的数字。

思路:

暴力枚举因子,分解数位判断,时间复杂度O(sqrt(n)).

代码:

#include<bits/stdc++.h>

typedef long long ll;
using namespace std;
const int N = 100000 + 10, inf = 0x3f3f3f3f, Mod = 1000000007;
int check(int num, int *vis)
{
    while(num)
    {
        if(vis[num%10])
        {
            return 1;
        }
        num /= 10;
    }
    return 0;
}
int main()
{
    int vis[10] = {0}, x, tmp;
    cin>>x;
    tmp = x;
    while(tmp)
    {
        vis[tmp%10] = 1;
        tmp /= 10;
    }
    int ans = 0;
    for(int i = 1; i*i<=x; i++)
    {
        if(x % i == 0)
        {
            ans += check(i, vis);
            if(i != x/i)
                ans += check(x/i, vis);
        }
    }
    cout<<ans<<endl;
    return 0;
}

B.Dasha and Stairs

题意:

已知有a个偶数b个奇数,判断这些数能不能组成连续正整数数列.(注意可能不是从1开始)

思路:

注意a和b同时为0.

代码:

#include<bits/stdc++.h>
#define f first
#define s second
typedef long long ll;
using namespace std;
const int N = 100000 + 10, inf = 0x3f3f3f3f;
int main()
{
    int a, b;
    while(cin>>a>>b)
    {
        if(abs(b-a)<=1 && (a || b))
            puts("YES");
        else puts("NO");
    }
    return 0;
}

C - Grade School Multiplication

题意:

把两个数相乘的过程输出出来.

思路:

和模拟数字相乘一样,中间可以先求出字符矩阵的大小,然后过程填充,比较恶心的模拟,注意补零的那种情况.

代码:

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
char ans[100][100];
int getlen(ll x)
{
    int res = 0;
    while(x)
    {
        res ++;
        x /= 10;
    }
    return max(res, 1);
}
ll quick_pow(ll x, ll n)
{
    ll res = 1;
    while(n)
    {
        if(n&1) res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}
void handle(char *str, int len1, int len, ll x, int zero)
{
    int sp = len - len1, i = 0;
    for(i = 0; i<sp; i++)
        str[i] = ' ';
    ll res = quick_pow(10, len1-1);
    while(res)
    {
        str[i] = '0' + x/res%10;
        res /= 10;
        i++;
    }
    while(zero)
    {
        str[i] = '0';
        i++;
        zero --;
    }
}
int main()
{
    int a, b, cas = 1;;
    int arr1[100], arr2[100];
    while(cin>>a>>b && (a || b))
    {
        memset(arr1, 0, sizeof(arr1));
        memset(arr2, 0, sizeof(arr2));
        memset(ans, 0, sizeof(ans));
        ll muli = 1LL*a*b, tmp;
        int len = getlen(muli), len1 = getlen(a), len2 = getlen(b);
        int cnt = 3;
        if(muli == 0)
            len = max(len1,len2);
        handle(ans[0], len1, len, a, 0);
        handle(ans[1], len2, len, b, 0);
        for(int i = 0; i<len; i++)
            ans[2][i] = '-';
        int id = 0, zero = 0, mark = 0;
        while(b)
        {
            if(b%10 != 0)
                handle(ans[cnt], getlen(b%10*a), len-id, b%10*a, zero),cnt++,zero = 0, mark ++;
            else zero ++;
            id++;
            b /= 10;
        }
        if(mark>1)
        {
            for(int i = 0; i<len; i++)
                ans[cnt][i] = '-';
            cnt++;
            handle(ans[cnt++],getlen(muli), len, muli, 0);

        }
        printf("Problem %d\n", cas++);
        for(int i = 0; i<cnt; i++)
            puts(ans[i]);
    }
    return 0;
}

D - Find Small A

题意:

给出一个数字代表一个4位的字符,就是说一个数可以用32位二进制表示,每8位代表一个字符(ASCII码),问给出的数字里面包含多少个A(即ASCII码为97)。

思路:

位运算写起来比较简单

代码:

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

int main()
{
    int n;
    while(~ scanf("%d", &n))
    {
        int a, num = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &a);
            while(a)
            {
                if(a%256 == 97) num++;
                
                a /= 256;
            }
        }
        printf("%d\n", num);
    }
    return 0;
}

E - Solving Order

题意:

把颜色由多到少进行排序,从大到小的输出。

思路:

map或者结构题排序

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct node
{
    char ch[110];
    int num;
} s[110];

bool cmp(node a,node b)
{
    return a.num>b.num;
}

int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n;
        scanf("%d",&n);
        for (int i=0; i<n; i++)
        {
            scanf("%s%d",s[i].ch,&s[i].num);
        }
        sort(s,s+n,cmp);
        for (int i=0; i<n; i++)
        {
            printf("%s%c",s[i].ch,i!=n-1?' ':'\n');
        }
    }
    return 0;
}

F - Digit Count

题意:

给你一些数字1~9不重复,这些数可以无限使用,问你可以构成多少种给n位数,并且满足相邻的两位数差值不超过2。

思路:

dpi表示第i位为j的方案数,最后累加dpn就可以的了。

代码:

#include<bits/stdc++.h>  

using namespace std;  
const double eps = 1e-10; 
const int inf = 0x3f3f3f3f, N = 5e4 + 10, Mod = 1000000007;  
typedef long long ll;  
struct node  
{  
    int x, y;  
} p[N];  
int c[20][20];  
ll dp[20][20];  
int main()  
{  
    int t, n, m, x;  
    cin>>t;  
    for(int cas = 1; cas<=t; cas++)  
    {  
        scanf("%d%d", &m, &n);  
        
        int vis[10];  
        memset(vis, 0, sizeof(vis));  
        memset(dp, 0, sizeof(dp));  
        
        for(int i = 1; i<=m; i++)  
            scanf("%d", &x), vis[x] = 1;  
            
        for(int i = 1; i<=9; i++)  
            if(vis[i]) dp[1][i] = 1LL;  
            
        for(int i = 2; i<=n; i++)  
            for(int j = 1; j<=9; j++)  
                for(int k = 1; k<=9; k++)  
                {  
                    if(dp[i-1][k] && vis[j] && abs(k - j)<=2)  
                    {  
                        dp[i][j] += dp[i-1][k];  
                    }  
                }  
                
        ll ans = 0;  
        for(int i = 1; i<=9; i++)  
            ans+=dp[n][i];  
        printf("Case %d: %lld\n", cas, ans);  
    }  
    return 0;  
} 

G - Babaei and Birthday Cake

题意:

有n个圆柱形蛋糕,给你r和h,然后每个蛋糕可以放在前面的比它小的蛋糕上面,求最大总体积。这是上升子序列最大和。

思路:

先把体积离散化,对于每个蛋糕,可以知道肯定是放在它前面比它小的最大体积和的蛋糕上,这样可以保证以i结尾的和最大,于是dp[i]表示以i结尾的最大蛋糕体积和,线段树每次查询离散化后的区间[1, num[i]-1]的最大值,就是找到那个比它小最大的,然后加上去就可以了,更新线段树,最后过一遍就可以得到ans。

代码:

#include<iostream>  
#include<cstdio>  
#include<algorithm>  
#include<map>  
#include<cstring>  
#include<map>  
#include<set>  
#include<queue>  
#include<stack>  
#include<cmath>  
using namespace std;  
const double eps = 1e-10;  
const int inf = 0x3f3f3f3f, N = 1e5 +10;  
typedef long long ll;  
const double pi = acos(-1);  
using namespace std;  
struct Node  
{  
    double r, h;  
} p[N];  
double V(Node a)  
{  
    return a.r*a.r*a.h*pi;  
}  
double dp[N], now[N], v[N], f[N];  
int num[N];  
struct node  
{  
    int l, r;  
    double maxn;  
} s[100010 * 4];  
int n, m;  
void pushup(int cnt)  
{  
    s[cnt].maxn = max(s[cnt<<1].maxn, s[cnt<<1|1].maxn);  
}  
void build_tree(int l, int r,int cnt)  
{  
    s[cnt].l = l;  
    s[cnt].r = r;  
    if(l == r)  
    {  
        s[cnt].maxn = 0.0;  
        return ;  
    }  
    int mid = (l + r)>>1;  
    build_tree(l, mid, cnt*2);  
    build_tree(mid+1, r, cnt*2+1);  
    pushup(cnt);  
}  
void update(int x, double numx, int cnt)  
{  
    if(s[cnt].l == x && s[cnt].r == x)  
    {  
        s[cnt].maxn = max(s[cnt].maxn, numx);  
        return ;  
    }  
    int mid = (s[cnt].l + s[cnt].r)>>1;  
    if(x<=mid) update(x, numx, cnt*2);  
    if(x>mid) update(x, numx, cnt*2+1);  
    pushup(cnt);  
}  
double query(int l , int r, int cnt)  
{  
    if(s[cnt].l >= l && s[cnt].r <= r)  
        return s[cnt].maxn;  
    int mid = (s[cnt].l + s[cnt].r)>>1;  
    double res = 0.0;  
    if(l<=mid)  
        res = max(query(l, r, cnt*2), res);  
    if(r>mid) res = max(query(l, r, cnt*2+1), res);  
    return res;  
}  
int main()  
{  
    int n;  
    while(cin>>n)  
    {  
        build_tree(1, n, 1);  
        memset(dp, 0, sizeof(dp));  
        for(int i = 0; i<n; i++)  
        {  
            scanf("%lf%lf", &p[i].r, &p[i].h);  
            v[i] = V(p[i]);  
            f[i] = v[i];  
        }  
        sort(f, f+n);  
        for(int i = 0; i<n; i++)  
            num[i] = lower_bound(f , f+n, v[i]) - f + 1;  
        for(int i = 0; i<n; i++)  
        {  
            if(num[i]-1==0)  
                dp[i] = v[i];  
            else dp[i] = query(1, num[i]-1, 1) + v[i];  
            update(num[i], dp[i], 1);  
        }  
        double ans = 0.0;  
        for(int i = 0; i<n; i++)  
            ans = max(dp[i], ans);  
        printf("%.10f\n", ans);  
    }  
    return 0;  
}

发表新评论