IT创新实验室19级阶段性测试二

说实话这次的题目比上次的简单，难度不算很大。比较适中，没有什么难度。

熊文静很怕冷

这题很简单，就是一个简单的循环，我做的时候一不小心忘记了当 n = 1 的时候要特判一下，所以直接给出代码

C 语言

#include <stdio.h>
int maxn = -0x3f3f3f;
int main()
{
    int n;
    int a[10005];
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    int cot = 1;
    if (n == 1)
    {
        printf("%d", n);
        return 0;
    }

    for (int i = 1; i < n; i++)
    {
        int t = a[i - 1];
        if (a[i] > t)
            cot++;
        else
        {
            if (cot > maxn)
                maxn = cot;
            cot = 1;
        }
    }
    printf("%d", maxn);
}

魔法火柴

这题是一题很老的题目了，暴力枚举就可以出答案。

C 代码

#include <stdio.h>
int a[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int getall(int i)
{
    if (i == 0)
        return a[i];
    int sum = 0;
    while (i)
    {
        sum += a[i % 10];
        i /= 10;
    }
    return sum;
}
int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        n -= 4;
        int ans = 0;
        for (int i = 0; i <= 1000; i++)
            for (int j = i; j <= 1000; j++)
                if (getall(i) + getall(j) + getall(i + j) == n)
                    if (i == j)
                        ans += 1;
                    else
                        ans += 2;
        printf("%d\n", ans);
    }
}

加减乘除

这题是一个模板题，考的是欧拉筛

直接给出代码

C 代码

#include <stdio.h>
#include <string.h>
const int N = 1E7 + 5;
long long prime[N];
bool vis[N];
double oula(int n)
{
    double ans = 0;
    int cot = 0;
    memset(vis, true, sizeof vis);
    for (int i = 2; i <= n; i++)
    {
        if (vis[i])
        {
            prime[cot++] = i;
            switch (cot % 4)
            {
            case 1:
                ans += prime[cot - 1];
                break;
            case 2:
                ans -= prime[cot - 1];
                break;
            case 3:
                ans *= prime[cot - 1];
                break;
            case 0:
                cot == 0 ? ans += prime[0] : ans /= prime[cot - 1];
                break;
            default:
                break;
            }
        }
        for (int j = 0; j < cot && i * prime[j] <= n; j++)
        {
            vis[i * prime[j]] = false;
            if (i % prime[j] == 0)
                break;
        }
    }
    return ans;
}

int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        printf("%.5lf\n", oula(n));
    }
}

A*B

和昨天的 A+B 差不多，模板题。

直接给出代码

C 代码

#include <stdio.h>
#include <string.h>
const int N = 100005; //取决于你的字符串的大小

void reverse(char s[])
{
    int len = strlen(s);
    for (int i = 0, j = len - 1; i < j; i++, j--)
    {
        char t = s[i];
        s[i] = s[j];
        s[j] = t;
    }
}

void mult(char s1[], char s2[], char ans[])
{
    int result[N] = {0};
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    reverse(s1);
    reverse(s2);
    for (int i = 0; i < len1; i++)
    {
        for (int j = 0; j < len2; j++)
        {
            result[i + j] += (s1[i] - '0') * (s2[j] - '0');
        }
    }
    int i;
    for (i = 0; i < len1 + len2; i++)
    {
        result[i + 1] += result[i] / 10;
        result[i] %= 10;
    }
    i = len1 + len2 - 1;
    while (i > 0 && result[i] == 0)
        i--;
    ans[i + 1] = '\0';
    for (; i >= 0; i--)
        ans[i] = result[i] + '0';
    reverse(ans);
}

int main()
{
    char s1[N], s2[N], ans[N];
    while (scanf("%s%s", s1, s2) != EOF)
    {
        mult(s1, s2, ans);
        printf("%s\n", ans);
    }
}

C++代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string mult(string a, string b)
{
    string ans;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int len1 = a.length(), len2 = b.length(), result[len1 + len2] = {0};
    for (int i = 0; i < len1; i++)
        for (int j = 0; j < len2; j++)
            result[i + j] += (a[i] - '0') * (b[j] - '0');
    for (int i = 0; i < len1 + len2 - 1; i++)
    {
        result[i + 1] += result[i] / 10;
        result[i] %= 10;
    }
    int i = len1 + len2 - 1;
    while (result[i] == 0 && i > 0)
        i--;
    for (; i >= 0; i--)
        ans += char(result[i] + '0');
    return ans;
}
int main()
{
    string a, b;
    while (cin >> a >> b)
        cout << mult(a, b) << endl;
}

8421BCD 码

这是一个看表题没什么难度

C 代码

#include <stdio.h>
#include <string.h>
char *s[10] = {
    "0000",
    "1000",
    "0100",
    "1100",
    "0010",
    "1010",
    "0110",
    "1110",
    "0001",
    "1001"};
char ans[1000];
int main()
{
    long long n;
    scanf("%lld", &n);
    while (n)
    {
        strcat(ans, s[n % 10]);
        n /= 10;
    }
    for (int i = strlen(ans) - 1; i >= 0; i--)
        printf("%c", ans[i]);
}

C++代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s[10] = {
        "0000",
        "0001",
        "0010",
        "0011",
        "0100",
        "0101",
        "0110",
        "0111",
        "1000",
        "1001"};
    long long n;
    while (cin >> n)
    {
        string ss;
        while (n)
        {
            ss = s[n % 10] + ss;
            n /= 10;
        }
        cout << ss << endl;
    }
}

跳方格

这题就是一般个找规律写出递归表达式，你就会发现规律：

假设第一个数为 m

n	(前 n+1 项和)F 前的项数	(前 n+1 项和)B 前的项数	第 n+1 项	前 n+1 项和 S
0	0	0	m	m
1	1	0	m+F	2m+F
2	2	-1	m+F-B	3m+2F-B
3	4	-2	m+2F-B	4m+4F-2B
4	6	-4	m+2F-2B	5m+6F-4B
5	9	-6	m+3F-2B	6m+9F-6B
6	12	-9	m+3F-3B	7m+12F-9B
7	16	-12	m+4F-3B	8n+16F-12B
8	20	-16	m+4F-4B	9m+20F-16B
9	…	…	…	…

令 t=(前 n+1 项和)F 前的项数,令 tt= (前 n+1 项和)B 前的项数。

很容易得出 t 和 tt 的递推公式。 t和tt

所以这题就很简单了。

列出等式

$$(n+1)M+tF-ttB=S$$

解得

$$M=\frac{S+ttB-tF}{n+1}$$

所以给出代码。

C 代码

#include <stdio.h>
int main()
{
    long long n, s, f, b;
    while (~scanf("%lld%lld%lld%lld", &n, &s, &f, &b))
    {
        long long t, tt;
        if (n & 1)
            t = ((n + 1) / 2) * ((n + 1) / 2), tt = (n - 1) / 2 * ((n - 1) / 2 + 1);
        else
            t = (n / 2) * (n / 2 + 1), tt = (n / 2) * (n / 2);
        printf("%lld\n", (s + tt * b - t * f) / (n + 1));
    }
}

C++代码

#include <iostream>
using namespace std;
using ll = long long;
int main()
{
    ll n, s, f, b;
    while (cin >> n >> s >> f >> b)
    {
        ll t, tt;
        if (n & 1)
            t = ((n + 1) / 2) * ((n + 1) / 2), tt = (n - 1) / 2 * ((n - 1) / 2 + 1);
        else
            t = (n / 2) * (n / 2 + 1), tt = (n / 2) * (n / 2);
        cout << (s + tt * b - t * f) / (n + 1) << endl;
    }
}

贾新远的旋转寿司

这题一开始我用 scanf("%s",s);但是不能过，后来想了想字符串可能有空格所以要用 gets 读才能读空格。C++ 用 cin.get 来读。

#include <stdio.h>
#include <string.h>
int main()
{
    char s[105];
    gets(s);
    for (int i = 0, j = strlen(s) - 1; i < j; i++, j--)
        if (s[i] != s[j])
        {
            printf("False\n");
            return 0;
        }
    printf("True");
}

Kruskal

这是一道数据结构题，也是模板题。需要用到图论，Kruskal 和并查集的算法。

C++代码

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
const int N = 1E5+7;
int father[N];
int get_root(int x){
    return x==father[x]?x:father[x]=get_root(father[x]);
}
void merge(int x,int y){
    father[get_root(x)]=get_root(y);
}
void init(int father[],int n){
    for(int i=1;i<=n;i++)
        father[i]=i;
}
struct Edge{
    int u,v,w;
    bool operator< (const Edge W)const{
        return w < W.w;
    }
};

int Kruskal(int n,int m,vector<Edge>edge){
    int res = 0;
    init(father,n);
    sort(edge.begin(),edge.end());
    for(int i=0;i<m;i++){
        int u=edge[i].u,v=edge[i].v;
        int father_u=get_root(u),father_v=get_root(v);
        if(father_u!=father_v){
            res+=edge[i].w;
            merge(father_u,father_v);
        }
    }
    return res;
}

int main(){
    int n,m;
    cin>>n>>m;
    vector<Edge>edge(m);
    for(auto &i:edge)
        cin>>i.u>>i.v>>i.w;
    cout<<Kruskal(n,m,edge)<<endl;
}

许钟乐的头发数量

这题是一题解密题，以前的蓝桥杯题目

szxyoj 上也有相似的题目可以看看。

阅读理解

首先将他转化出来

转化 C 代码

#include <stdio.h>
int main()
{
    // freopen("1.txt", "w", stdout);
    int a[20][6] = {0};
    for (int i = 0; i < 20; i++)
        for (int j = 0; j < 6; j++)
            scanf("%d", &a[i][j]);
    for (int i = 0; i < 20; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            for (int k = 16; k >= 0; k--)
                if ((a[i][j] >> k) & 1)
                    printf("1");
                else
                    printf(" ");
        }
        printf("\n");
    }
}

输出的图形是这样的


                  111    111                           1111                 111
                1 111    111                   11      111                  1111
    111111      1 11    1111          11111   1111     111                   111            11111
   11111111     1 11    111111111   11111111   1111   11111111111                          1111111
   111  1111  111 11111 111111111   111  111    111 1 11111111111    1111111111111111 111 1111 1111
   111   111  111   111111    111  111   1111    11 1111     1111         111             111   111
   111  111   111   111111    111        111         111 111 111          111                  1111
   11111111   111   11111     111       1111        111  111 111          111                  111
    111111    111   111 111   111     11111              111              11111111111         1111
   11111111   111 11111  111  111       1111     11 1    111              11111111111        111
  1111   111  111   111  111  111        1111    11 1   1111             1111     111        111
  111    111  111   111   111 11          111   111 1   11111            111      111
  111    111  111   111   11  11   111    111   111     11111            111      111
  1111  1111  111   111      111    111  111   111     111 111          1111      111
   11111111   111 11111      111    11111111  1111    1111 1111        1111       111        111
    111111    111 11111      111      1111    111    1111   11111      111       1111        111
              111   111   111111               11 1 111       1111   1111     111111
                          1111                    1 11         11    111      11111

其实就是 8 的三次方

所以很简单，手算 8 的三次方

C 代码

#include <stdio.h>
int main(){
	printf("%d\n",8*8*8-64);
}