友谊赛题解

友谊赛~

A wyh的数字

A

——枚举

题意

T组数据，每组数据中给定一个数字，判断数字中有多少个 7

解题思路

遍历数字每一位即可，个人推荐用字符串写，更便捷

代码

C

#include <stdio.h>

int main()  
{   
    int t;
    scanf("%d", &t);
    while (t -- )
    {
        char s[20];
        scanf("%s", &s);
        int cnt = 0;
        for (int i = 0; i < sizeof(s) / sizeof(s[0]); i ++ ) 
            if (s[i] == '7') 
                cnt ++ ;

        printf("%d\n", cnt);
    }

    return 0;
}

C++

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

int main()  
{   
    int t;
    cin >> t;
    while (t -- )
    {
        string s;
        cin >> s;
        int cnt = 0;
        for (int i = 0; i < s.size(); i ++ ) 
            if (s[i] == '7') 
                cnt ++ ;

        cout << cnt << endl;
    }

    return 0;
}

B 越狱

B

题意

有一个长度为 n 的数组 a ，大意就是找到一个数 x ，然后在数组中所有小于 x 的数的数量 和 所有大于 x 的数的数量取min。

解题思路

要保证两个数量都尽可能的大，就要取中间排名 n / 2 的数字。找到这个数字然后 + 1 就是 x 的值。

代码

C

#include <stdio.h>

const int N = 1e5 + 10;

int a[N];

int main()  
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    int res = n / 2;
    int x = a[n / 2 - 1] + 1;
    printf("%d %d", res, x);
    return 0;
}

C ++

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

const int N = 1e5 + 10;

int a[N];

int main()  
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    int res = n / 2;
    int x = a[n / 2 - 1] + 1;
    cout << res << " " << x;
    return 0;
}

C 光之屏障

C

——暴力，思维

题意

给定两个数 x ,y，求一个数 z 满足 x <= z <= y, 且 z 是 2 的方幂

解题思路

数据不大，模拟暴力即可。

代码

C

#include <stdio.h>

int main()  
{
    int t;
    scanf("%d", &t);
    while (t -- )
    {
        int x, y;
        scanf("%d %d", &x, &y);

        int res = 1;
        bool flag = false;
        for (int i = 0; i < 31; i ++ )
        {
            if (x <= res && res <= y)
            {
                flag = true;
                break;  
            } 
            res *= 2;
        }
        if (flag == true) printf("%d\n", res); 
        else printf("-1\n");
    }

    return 0;
}

C++

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

int main()  
{
    int t;
    cin >> t;
    while (t -- )
    {
        int x, y;
        cin >> x >> y;
        
        int res = 1;
        bool flag = false;
        for (int i = 0; i < 31; i ++ )
        {
            if (x <= res && res <= y)
            {
                flag = true;
                break;  
            } 
            res *= 2;
        }
        if (flag == true) cout << res << endl;
        else cout << -1 << endl;
    }

    return 0;
}

D 熊熊，觅食！

D

——思维

题意

小熊初始在原点0，食物在 x 的位置上，现在小熊每一步有 3 种选择：1，2，3. 问最少需要多少步

解题思路

每一步都走3，直到距离食物小于3，如果没到再走一步就可以。

代码

C

#include <stdio.h>
#include <stdlib.h>

int main()  
{
    int t;
    scanf("%d", &t);
    while (t -- )
    {
        int x;
        scanf("%d", &x);

        x = abs(x);
        int res = x / 3;
        if (x % 3) res ++ ;
        printf("%d\n", res);    
    }

    return 0;
}

C++

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

int main()  
{
    int t;
    cin >> t;
    while (t -- )
    {
        int x;
        cin >> x;
        x = abs(x);
        int res = x / 3;
        if (x % 3) res ++ ;
        cout << res << endl;    
    }

    return 0;
}

E 多项式输出

E

——数字，字符串

题意

……详细看题目描述

解题思路

直接模拟即可， 需要注意的细节较多，详细看代码的注释

代码

C

#include <stdio.h>
#include <stdlib.h>

const int N = 1e2 + 10;

int a[N];

int main()  
{
    int n;
    scanf("%d", &n);

    for (int i = n; i >= 0; i -- )
    {
        scanf("%d", &a[i]);
        //等于0，这一项为空
        if (a[i] == 0) continue;
        //输出正负号，注意判断首项不输出正号
        if (a[i] > 0 && i != n) printf("+");
        if (a[i] < 0) printf("-");
        //系数为 1 ，不输出系数，只有尾项需要
        if (abs(a[i]) != 1 || i == 0) printf("%d", abs(a[i]));
        //除了最后一项，都要输出 x
        if (i != 0) printf("x");
        //在除了最后一项的基础上，倒数第二项也不用输出 ^i
        if (i > 1) printf("^%d", i);
    }

    return 0;
}

C++

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

const int N = 1e2 + 10;

int a[N];

int main()  
{
    int n;
    cin >> n;

    for (int i = n; i >= 0; i -- )
    {
        cin >> a[i];
        //等于0，这一项为空
        if (a[i] == 0) continue;
        //输出正负号，注意判断首项不输出正号
        if (a[i] > 0 && i != n) cout << '+';
        if (a[i] < 0) cout << '-';
        //系数为 1 ，不输出系数，只有尾项需要
        if (abs(a[i]) != 1 || i == 0) cout << abs(a[i]);
        //除了最后一项，都要输出 x
        if (i != 0) cout << 'x';
        //在除了最后一项的基础上，倒数第二项也不用输出 ^i
        if (i > 1) cout << '^' << i;
    }

    return 0;
}

F 啊，这居然是个质数

F

——质数判断

题意

输入 x ， 找到2~x之间最大的质数

解题思路

从大到小枚举，用试除法判断是否为质数即可

代码

C

#include <stdio.h>

//试除法判断质数
bool is_prime(int n)
{
    if (n < 2) return false;
    
    for (int i = 2; i <= n / i; i ++ )
        if (n % i == 0) return false;

    return true;
}

int main()  
{
    int x;
    scanf("%d", &x);
    
    for (int i = x; i >= 2; i -- ) 
        if (is_prime(i))
        {
            printf("%d", i);
            break;
        }    

    return 0;
}

C++

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

//试除法判断质数
bool is_prime(int n)
{
    if (n < 2) return false;
    
    for (int i = 2; i <= n / i; i ++ )
        if (n % i == 0) return false;

    return true;
}

int main()  
{
    int x;
    cin >> x;
    
    for (int i = x; i >= 2; i -- ) 
        if (is_prime(i))
        {
            cout << i;
            break;
        }    

    return 0;
}

G 小雨的三角形

G

前缀和，枚举，思维

题意

填满数字的三角形()，每一行的最左和最右两个位置的数确定，剩下的每个数等于上面和左上的两个数之和。

共有 m 次询问，每次询问 x 层到 y 层的所有数的和

解题思路

前缀和预处理出来每一行的值，然后再用一次前缀和求出前 i 行的值，每次询问直接输出即可，记得取模

代码

C

#include <stdio.h>

const int N = 1e3 + 10, mod = 1e9 + 7;

int n, m; 
int a[N][N];
int s[N];

void init()
{
    for (int i = 1; i <= n; i ++ )
        for(int j = 1; j <= i; j ++ )
            if (j == 1 || j == i) a[i][j] = i;
            else a[i][j] = (a[i - 1][j] + a[i - 1][j - 1]) % mod;


    for (int i = 1; i <= n; i ++ ){
        s[i] = (s[i] + s[i - 1]) % mod;
        for (int j = 1; j <= i; j ++ )
            s[i] = (s[i] + a[i][j]) % mod;
    }
}

int main()  
{
    scanf("%d %d", &n, &m);

    init();

    while (m -- )
    {
        int x, y;
        scanf("%d %d", &x, &y);
        //需要额外加一个mod, 因为求前缀和的时候，每一步都取余，可能会导致数组里所存的数中前大后小，相减出现负数
        printf("%d\n", (s[y] - s[x - 1] + mod) % mod);
    }

    return 0;
}

C++

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

const int N = 1e3 + 10, mod = 1e9 + 7;

int n, m; 
int a[N][N];
int s[N];

void init()
{
    for (int i = 1; i <= n; i ++ )
        for(int j = 1; j <= i; j ++ )
            if (j == 1 || j == i) a[i][j] = i;
            else a[i][j] = (a[i - 1][j] + a[i - 1][j - 1]) % mod;


    for (int i = 1; i <= n; i ++ ){
        s[i] = (s[i] + s[i - 1]) % mod;
        for (int j = 1; j <= i; j ++ )
            s[i] = (s[i] + a[i][j]) % mod;
    }
}

int main()  
{
    cin >> n >> m;
    init();

    while (m -- )
    {
        int x, y;
        cin >> x >> y;
        //需要额外加一个mod, 因为求前缀和的时候，每一步都取余，可能会导致数组里所存的数中前大后小，相减出现负数
        cout << ((s[y] - s[x - 1] + mod) % mod) << endl;
    }

    return 0;
}

H 九九八十一

H

题意

给定n n的乘法表，给定一个字符c，输出字符 c 在n n乘法表中出现的次数。

解题思路

给出了九九乘法表的输出模板，其实也就是告诉我们都有哪些字符，除了数字外，还有字符乘( * ), 等号( = ), 逗号( , ),这三个字符，遍历乘法表即可。

代码

C

#include <stdio.h>

int n; 
char c;

int check(int x)
{
    int ans = 0;
    while (x)
    {
        int t = x % 10;
        if (x % 10 + '0' == c) ans ++ ;
        x /= 10;
    }
    return ans;
}
 
int main()  
{
    scanf("%c %d", &c, &n);

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= i; j ++ )
        {
            if (c == '*' || c == '=' || c == ',') cnt ++ ;
            cnt += check(i);
            cnt += check(j);
            cnt += check(i * j);
        }
    }
    printf("%d", cnt);

    return 0;
}

C++

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

int n; 
char c;

int check(int x)
{
    int ans = 0;
    while (x)
    {
        int t = x % 10;
        if (x % 10 + '0' == c) ans ++ ;
        x /= 10;
    }
    return ans;
}
 
int main()  
{
    cin >> c >> n;

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= i; j ++ )
        {
            if (c == '*' || c == '=' || c == ',') cnt ++ ;
            cnt += check(i);
            cnt += check(j);
            cnt += check(i * j);
        }
    }
    cout << cnt;

    return 0;
}

I 图像识别

——思维，模拟

I

题意

现有一个” * “画成的坐标轴，有一个 “ # “代表目标点，” . “表示空。现在以二维矩阵的形式给出图像，需要求出目标点” # “，所在位置的坐标。

解题思路

找到坐标原点和目标点的位置即可。

上下左右四个方位都为” * “, 就是坐标原点， “ # “ 就是目标点

代码

C

#include <stdio.h>

const int N = 1e3 + 10;

char g[N][N];

int main()  
{
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%s", &g[i]);

    int x0, y0, x1, y1;
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            if (g[i][j] == '#') x1 = i, y1 = j;
            if (g[i][j] == '*' && g[i + 1][j] == '*' && g[i][j + 1] == '*' && g[i - 1][j] == '*' && g[i][j - 1] == '*')
                x0 = i, y0 = j;
        }
    }

    printf("%d %d", y1 - y0, x0 - x1);

    return 0;
}

C++

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

const int N = 1e3 + 10;

char g[N][N];

int main()  
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin >> g[i][j];

    int x0, y0, x1, y1;
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            if (g[i][j] == '#') x1 = i, y1 = j;
            if (g[i][j] == '*' && g[i + 1][j] == '*' && g[i][j + 1] == '*' && g[i - 1][j] == '*' && g[i][j - 1] == '*')
                x0 = i, y0 = j;
        }
    }

    cout << y1 - y0 << " " << x0 - x1;

    return 0;
}

J 汀博尔

——二分

J

题意

有n棵树，每棵树有初始高度，每个月会长高一些。

现在有个木料总量为S的订单，要求没块木料长度不小于L，而且木料必须是整棵树。需要求出要等多少个月才能满足订单

解题思路

数据很大，枚举天数会超时，所以需要用到二分，判断天数的时间复杂度降低为O(logn)。

代码

C

#include <stdio.h>

const int N = 2e5 + 10;

typedef long long ll;

ll n, s, L;
ll h[N], a[N];
ll mx;

ll max(ll a, ll b)
{
    if (a >= b) return a;
    else return b;
}

bool check(ll d)
{
    ll sum = 0;
    for (int i = 0; i < n; i ++ )
    {
        if (h[i] + d * a[i] >= L) sum += h[i] + d * a[i];
        if (sum >= s) return true;
    } 

    return false;
}

int main()  
{
    scanf("%lld %lld %lld", &n, &s, &L);
    for (int i = 0; i < n; i ++ ) scanf("%lld", &h[i]);
    for (int i = 0; i < n; i ++ ) scanf("%lld", &a[i]);

    for (int i = 0; i < n; i ++ )
    {
        mx = max(mx, max(L, s) / a[i]);
    }

    ll l = 0, r = mx;
    while (l < r)
    {
        ll mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%lld", l);

    return 0;
}

C++

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

typedef long long ll;

const int N = 2e5 + 10;

ll n, s, L;
ll h[N], a[N], c[N];
ll mx;

bool check(ll d)
{
    ll sum = 0;
    for (int i = 0; i < n; i ++ )
    {
        if (h[i] + d * a[i] >= L) sum += h[i] + d * a[i];
        if (sum >= s) return true;
    }

    return false;
}

int main()  
{
    cin >> n >> s >> L;
    for (int i = 0; i < n; i ++ ) cin >> h[i];
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    for (int i = 0; i < n; i ++ )
    {
        mx = max(mx, max(L, s) / a[i]);
    }

    ll l = 0, r = mx;
    while (l < r)
    {
        ll mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << l;

    return 0;
}