Contest ICT pFind

[TOC]

ICT pFind

机试：共五道，前两个签到，第三个大数乘法，第四个区间最值问题，第五个数据结构二叉树问题

机试-1

题目大意：将二维数组进行翻转

思路：储存在二维数组中，利用循环来进行翻转然后输出。

#include <iostream>
using namespace std;
const int maxn = 209;
int n, a[maxn][maxn];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) 
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            printf("%d ", a[n-j+1][i]);
        }
        printf("\n");
    }
    return 0;
}

机试-2

题目大意：括号匹配，非左右括号的按照异常处理，然后查看左右括号是否匹配

思路：维护一个常量来标注左右括号

// 95
#include <iostream>
using namespace std;
string str;
int cnt = 0;

int main() {
    cin>>str;
    for (int i = 0; i < str.length(); ++i) {
        if (str[i] == '(') cnt++;
        else if (str[i] == ')') cnt--;
        else {puts("NO");return 0;}
    }
    if (!cnt) puts("YES");
    else puts("NO");
    return 0;
}

机试-3

题目大意：查看某数的阶乘末尾有多少0

思路：大数乘法

#include <iostream>
using namespace std;
const int maxn = 1e5+9;
int a[maxn], lena, n;

int main() {
    scanf("%d", &n);a[1] = 1;lena = 3000;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= lena; ++j)
            a[j] *= i;
        for (int j = 1; j <= lena; ++j)
            if (a[j] > 10) a[j+1] += a[j]/10, a[j]%=10;
    }
    int flag = 1, ans = 0;
    for (int i = 1; i <= lena; ++i) if (flag && !a[i]) ans++;else flag = 0;
    printf("%d\n", ans);
}

机试-4

题目大意：找出数组最大子区间和

思路：维护一个tem变量，来判断下个元素是否要累加进来，如果下个元素加进来导致tem<0，那么就需要重置tem了，然后重新累加。

#include <iostream>
using namespace std;
const int maxn = 1e5+9;
int n, a[maxn], tem, ans;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a+i);
    for (int i = 1; i <= n; ++i){
        if (tem + a[i] < 0) tem = 0;
        else tem += a[i], ans = max(ans, tem);}
        printf("%d\n", ans);
    return 0;
}

机试-5

题目大意：给出二叉树前中序遍历，得到后序遍历

思路：维护二叉链表，先建树，然后在后序遍历

#include <iostream>
using namespace std;
const int maxn = 1e5+9;
int n, pre[maxn], in[maxn];
struct node {
    int val;
    node * l, * r;
} *root;

// pre root-l-r  in l-root-r => bg:pre, l/r:in
node * build(int bg, int l, int r) {
    if (l > r) return NULL;
    // 遍历查找根的位置
    node * nw = new node();
    for (int i = l; i <= r; ++i) {
        if (pre[bg] == in[i]) {
            // 找到分界点
            nw->val = pre[bg];
            nw->l = build(bg+1, l, i-1);
            nw->r = build(bg+1+(i-l), i+1, r);
        }
    }
    return nw;
}

// post l-r-root
void post_traverse(node * nw) {
    if (nw->l) post_traverse(nw->l);
    if (nw->r) post_traverse(nw->r);
    printf("%d ", nw->val);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", pre+i);
    for (int i = 1; i <= n; ++i) scanf("%d", in+i);
    root = build(1, 1, n);
    post_traverse(root);
    return 0;
}

笔试算法题：3个基础算法题+2个附加算法题

基础算法题1

题目：快排最好、最差、平均各自的比较次数；快排最差情况举一个例子；复杂度分析

思路：

基础算法题2

题目：将数n拆成m个，求这m个数最大乘积是多少

思路：DFS+剪枝

基础算法题3

题目：给出一个数组，得到逆序对的个数

思路：归并排序途中计数

附加算法题1

题目：给一堆石子，然后每个人每次可以抽取1～m个，每个人都按照最优的方法抽取，最后一颗石子谁抽谁输。问是否有策略

思路：博弈论，巴士博弈的变式。巴士博弈是如果谁拿最后一颗石子谁赢。那么只要$n%(m+1)\ne0$ 那么先手必定赢，因为先手只需要保证每轮都是m+1个进行消耗即可；但是如果$n%(m+1)= 0$ 那么后手就可以保证每次都消耗m+1个，让最后先手抽的时候剩下m+1个，那么后手就必赢

Posted on Feb 4, 2020