[练习]PTA2021_520钻石争霸赛

### 1、自动编程

思路:水题

#include<iostream>
using namespace std;
int n;
int main(){
    cin>>n;
    cout<<"print("<<n<<")"<<endl;
    return 0;
    
}

2、加油冲鸭 (10 分)

思路:水题

#include<iostream>
using namespace std;
int main(){
    int n,m,s;
    cin>>n>>m>>s;
    int x=m*s;
    if(x>=n/2) printf("hai sheng %d mi! chong ya!\n",n-x);
    else printf("hai sheng %d mi! jia you ya!\n",n-x);
    return 0;
}

3、520的表白 (10 分)

思路:水题

#include<iostream>
using namespace std;
int main(){
    string a;
    cin>>a;
    for(int i=0;i<520;i++)
        cout<<a<<endl;
    return 0;
}

4、奇葩楼层 (15 分)

思路:直接暴力

#include<iostream>
using namespace std;
int n,d;
bool check(int x){
    while(x){
        if(x%10==d) return true;
        x/=10;
    }
    return false;
}
int main(){
    cin>>n>>d;
    int res=n;
    for(int i=1;i<=n;i++)
        if(check(i)) res--;
    
    cout<<res<<endl;
    return 0;
}

5、大勾股定理 (15 分)

思路:下列代码抄的,给各位大佬看的,自己用的前缀和打表,只有14分,就这道题耗费了我半小时..

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int ans = 3, step = 7;
    for (int i = 1; i < n; i++) {
        ans += step;
        step += 4;
    }
    for (int i = 0; i < n + 1; i++) {
        cout << ans++ << "^2" << (i == n ? " =\n" : " + ");
    }
    for (int i = 0; i < n; i++) {
        cout << ans++ << "^2" << (i == n - 1 ? "\n" : " + ");
    }
    return 0;
}

6、矩阵列平移 (20 分)

思路:

遵循人类的主观思维,我选择转置它,/(ㄒoㄒ)/~~
    1、转置输入矩阵A(问题转换为求列的值)
    2、遍历矩阵A,将A的元素复制到矩阵B来(初始化矩阵B全为x)
        这里注意条件:若为偶数则需要在开头添加x元素
        所以位移k个位置后再来添加矩阵A中的元素
    3、遍历矩阵B求得列和输出即可
#include<iostream>
#include<cstring>
using namespace std;
#define N 10010
int g[N][N];
int nums[N][N];
int sum[N];
int n, k, x;
int main() {
    //转置输入
    cin >> n >> k >> x;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> g[j][i];
    //初始化矩阵B 
    int flag = 1;//标记
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n + n; j++)
            nums[i][j] = x;
    //将矩阵A复制到矩阵B 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i % 2 == 0)
                nums[i][j + flag] = g[i][j];//偶数行需要位移
            else nums[i][j] = g[i][j];
        }
        if (i % 2 == 0) flag++;
        if (flag > k) flag = 1;//flag回调
    }
    //计算列和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            sum[i] += nums[j][i];
    }
    //输出
    for (int i = 1; i <= n; i++) {
        printf("%d", sum[i]);
        if (i < n) printf(" ");
    }
    return 0;
}

7、约会大作战

思路:

定义一个结构体:
    前两个不成功得吸引值[用数组存]
    询问次数
    是否成对
    

不能约会:
    (询问次数<2)
    (需要大于数组内的元素)
    (a、b均不能有 [ 不能约会 ] 的条件在内)
    (必须没有成对)
#include<iostream>
#include<cstring>
using namespace std;
#define N 1050
typedef struct Attlist {
    int pres[2];//前两次的好感值
    int num;//询问次数
    bool tag;//是否成对
}Att;
Att att[N];
int g[3][N][N];
//第 x 组 y 对 z 的好感值
int n, m, k;
bool check(int a, int b) {
    if (att[a].tag || att[b].tag) return false;//其中有人成对
    //数组中选出最大的跟当前好感值做比较
    int x = att[a].pres[0] > att[a].pres[1] ? att[a].pres[0] : att[a].pres[1];
    int y = att[b].pres[0] > att[b].pres[1] ? att[b].pres[0] : att[b].pres[1];
    if (g[1][a][b] > x && g[2][b][a] > y) return true;
    return false;
}
int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[1][i][j];

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

    while (k--) {
        int a, b;
        cin >> a >> b;
        //若满足不能成对条件,记得更新 [ 前两人好感值 ]
        if ((att[a].num < 2 || att[b].num < 2) || !check(a, b)) {
            att[a].num++; att[b].num++;
            att[a].pres[att[a].num % 2] = g[1][a][b];
            att[b].pres[att[b].num % 2] = g[2][b][a];
        }
        else {
            att[a].tag = att[b].tag = true;//标记成对
            printf("%d %d\n", a, b);
        }
    }
    return 0;
}

8、浪漫侧影 (25 分)

思路:

只需要利用[ 后序序列(左-右-根) ] 和 [ 中序序列(左-根-右) ]
将后序序列逆过来:每次从后序序列中找到根 然后去中序序列中确定左右子树
创建好树后:
左视图:先序遍历每层第一个结点输出,每过一层将该层标记
右视图:[ 根-右-左 ] 序列每层第一个结点输出,同样记录,具体看代码
#include<iostream>
#include<cstring>
using namespace std;
#define N 100010
int Tree[N];//构造的树
int post_Tree[N];//后序序列
int in_Tree[N];//中序序列
bool st[N];//标记数组:用于层次标记
int leftsq[N], rightsq[N];
int leftSize, rightSize;
int n, idx;
int find(int L, int R, int x) {//中序序列中找x 
    for (int i = L; i <= R; i++)
        if (in_Tree[i] == x) return i;
    return -1;
}
void Create(int L, int R, int root) {
    int x = find(L, R, post_Tree[idx]);
    if (x == -1) return;//该[L,R]区间不存在x,代表x不属于这个根的子树,返回上一层
    idx--;
    Tree[root] = in_Tree[x];
    Create(x + 1, R, root * 2 + 1);//通过中序序列划分左右子树进行创建
    Create(L, x - 1, root * 2);
    return;
}
void left_traverse(int root,int lever) {
    if (Tree[root]) {
        if (!st[lever]) {//若该层未被标记,则这一层第一个遍历到的结点就是我们要的
            st[lever] = true;
            leftsq[leftSize++] = Tree[root];
        }
        left_traverse(root * 2, lever + 1);
        left_traverse(root * 2 + 1, lever + 1);
    }
    return;
}
void right_traverse(int root, int lever) {
    if (Tree[root]) {
        if (!st[lever]) {
            st[lever] = true;
            rightsq[rightSize++] = Tree[root];
        }
        right_traverse(root * 2+1, lever + 1);
        right_traverse(root * 2, lever + 1);
    }
    return;
}
int main() {
    cin >> n;
    idx = n;
    for (int i = 1; i <= n; i++) cin >> in_Tree[i];
    for (int j = 1; j <= n; j++) cin >> post_Tree[j];

    Create(1, n, 1);
    
    left_traverse(1, 1);
    memset(st, false, sizeof st);
    right_traverse(1, 1);
    

    printf("R:");
    for (int i = 0; i < leftSize; i++) {
        printf("%d", leftsq[i]);
        if (i < leftSize - 1) printf(" ");
    }
    printf("\n");
    printf("L:");
    for (int i = 0; i < rightSize; i++) {
        printf("%d", rightsq[i]);
        if (i < rightSize - 1) printf(" ");
    }

    return 0;
}

520快乐~佬们

本文链接:

https://nullcode.fun/148.html
1 + 3 =
快来做第一个评论的人吧~