MENU

2020年粤澳热身赛题目题解

April 19, 2020 • 未分类

2020年粤澳热身赛题目题解

A题:莫斯方块

该题属于作业题,可以使用DP,贪心模拟也可以过,不过需要考虑多种情况。

DP AC代码:

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <time.h>

#define MAXN 105

using namespace std;

struct node {
    int four, two, one;
    node(int _f, int _t, int _o) : four(_f), two(_t), one(_o) {}
};

vector<node> v;
bool mark[15][15][15];
int dp[MAXN][MAXN][MAXN];

void dfs(int four, int two, int one) {
    if (four < 0 || two < 0 || one < 0) {
        return ;
    }
    if (!mark[four][two][one]) {
        mark[four][two][one] = true;
        v.push_back(node(four, two, one));
        dfs(four - 1, two + 2, one);
        dfs(four - 1, two, one + 4);
        dfs(four, two - 1, one + 2);
    }
}

void init() {
    v.clear();
    memset(mark, false, sizeof(mark));
    dfs(1, 2, 1);
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < (int) v.size(); i++) {
        for (int f = v[i].four; f < MAXN; f++) {
            for (int t = v[i].two; t < MAXN; t++) {
                for (int o = v[i].one; o < MAXN; o++) {
                    dp[f][t][o] = max(dp[f][t][o], dp[f - v[i].four][t - v[i].two][o - v[i].one] + 1);
                }
            }
        }
    }
}

void print() {
    for (int i = 0; i < (int) v.size(); i++) {
        printf("%d %d %d\n", v[i].four, v[i].two, v[i].one);
    }
}

int main() {
    init();
//    print();
    int T, cas = 1;
    scanf("%d", &T);
    while (T--) {
        int four, two, one;
        scanf("%d %d %d", &one, &two, &four);
        printf("Case #%d: %d\n", cas++, dp[four][two][one]);
    }
}

贪心AC代码:

#include <bits/stdc++.h>

using namespace std;

int main() {
    int T;
    scanf("%d", &T);
    for(int t = 1; t <= T; t++) {
        int a, b, c, res = 0;
        scanf("%d%d%d", &a, &b, &c);
        while(true) {
            if(a >= 1 && b >= 2 && c >= 1) {
                a--;
                b -= 2;
                c--;
                res++;
            } else if(a >= 1 && b >= 4) {
                a--;
                b -= 4;
                res++;
            } else if(a >= 3 && b >= 1 && c >= 1) {
                a -= 3;
                b--;
                c--;
                res++;
            } else if(a >= 3 && b >= 3) {
                a -= 3;
                b -= 3;
                res++;
            } else if(a >= 5 && c >= 1) {
                a -= 5;
                c--;
                res++;
            } else if(a >= 5 && b >= 2) {
                a -= 5;
                b -= 2;
                res++;
            } else if(a >= 7 && b >= 1) {
                a -= 7;
                b--;
                res++;
            } else if(a >= 9) {
                a -= 9;
                res++;
            } else break;
        }
        printf("Case #%d: %d\n", t, res);
    }
    return 0;
}

B题:互评成绩计算

基础题

AC代码:

#include <bits/stdc++.h>
#define MAXN 105
using namespace std;
int main() {
    int n, m;
    while (~scanf("%d %d", &n, &m)) {
        for (int t = 0; t < n; t++) {
            int tot = 0, flag = 0, tmp, mn, mx, p;
            scanf("%d", &p);
            for (int i = 1; i < n; i++) {
                scanf("%d", &tmp);
                if (tmp <= m && tmp >= 0) {
                    if (!flag) {
                        mn = mx = tmp;
                    }
                    mn = min(mn, tmp);
                    mx = max(mx, tmp);
                    tot += tmp;
                    flag++;
                }
            }
            printf("%d\n", (int) ((p + (tot - mn - mx) * 1.0 / (flag - 2)) / 2.0 + 0.5));
        }
    }
}

C题:活动总台

按题意模拟,唯一有坑的地方是卡了c++的map,用hashmap或者字典树都可以,题目中用户数不超过1000000已经极大的提示了用红黑树实现的map会超时。

AC代码:

#include <bits/stdc++.h>
#include <time.h>
#define LOGIN 1
#define OPEN 2
#define CLOSE 3
#define IMPORT 4
#define ADD 5
#define DELETE 6
#define UPDATE 7
#define EXIT 8
#define CHECK 9

#define MAXN 27
#define pss pair<string, string> 

using namespace std;

map<string, int> OPERATE;

bool auth;
bool isLogin;
map<string, string> userList;

char s1[MAXN], s2[MAXN], s3[MAXN], s4[MAXN];
char username[MAXN], password[MAXN];
string operate;

struct node{
    bool is;
    node *next[MAXN];
    char code[MAXN];
    node(){
        code[0] = '\0';
        is = false;  
        memset(next, 0, sizeof(next));  
    }
};

bool insert(node *rt, char *name, char *code) {
    node *p = rt;
    int len = strlen(name);
    for (int i = 0; i < len; i++) {
        int k = name[i] - 'a';
        if (p -> next[k] == NULL) {
            p -> next[k] = new node();
        }
        p = p -> next[k];
    }
    if (p -> is) {
        return false;
    }
    p -> is = true;
    strcpy(p -> code, code);
    return true;
}

bool update(node *rt, char *name, char *code) {
    node *p = rt;
    int len = strlen(name);
    for (int i = 0; i < len; i++) {
        int k = name[i] - 'a';
        if (p -> next[k] == NULL) {
            return false;
        }
        p = p -> next[k];
    }
    if (!(p -> is)) {
        return false;
    }
    strcpy(p -> code, code);
    return true;
}

bool del(node *rt, char *s) {
    node *p = rt;
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        int k = s[i] - 'a';
        if (p -> next[k] == NULL) {
            return false;
        }
        p = p -> next[k];
    }
    if (p -> is) {
        p -> is = false;
        return true;
    }
    return false;
}

int search(node *rt, char *name, char *code) {
    int len = strlen(name);
    node *t = rt;
    for (int i = 0 ;i < len ;i++) {
        if (t -> next[name[i] - 'a'] != NULL) {
            t = t -> next[name[i] - 'a'];
        } else {
            return 1;
        }
    }
    if (t -> is) {
        if (strcmp(t -> code, code) == 0) {
            return 2;
        }
        return 0;
    }
    return 1;
}

void destory(node *rt) {
    for (int i = 0; i < 26; i++) {
        if (rt -> next[i] != NULL) {
            destory(rt -> next[i]);
        }
    }
    free(rt);
}

node *rt;

void init() {
    OPERATE["login"] = LOGIN;
    OPERATE["open"] = OPEN;
    OPERATE["close"] = CLOSE;
    OPERATE["import"] = IMPORT;
    OPERATE["add"] = ADD;
    OPERATE["delete"] = DELETE;
    OPERATE["update"] = UPDATE;
    OPERATE["exit"] = EXIT;
    OPERATE["check"] = CHECK;
    auth = isLogin = false;
    userList.clear();
}

bool checkIsLogin() {
    if (!isLogin) {
        cout << "wrong operation, please login!";
        return false;
    }    
    return true;
}

void login(char *checkUsername, char *checkPassword) {
    if (strcmp(checkUsername, username) == 0 
        && strcmp(checkPassword, password) == 0) {
        if (isLogin) {
            printf("has logged!");
        } else {
            isLogin = true;
            printf("login success!");
        }
    } else {
        printf("login failed!");
    }
}

void openAuth() {
    if (!checkIsLogin()) {
        return ;
    }
    if (auth) {
        printf("auth has opened!");
    } else {
        printf("auth successfully opened!");
        auth = true;
    }
}

void closeAuth() {
    if (!checkIsLogin()) {
        return ;
    }
    if (auth) {
        printf("auth successfully shut down!");
        auth = false;
    } else {
        printf("auth has closed!");    
    }
}

void importList(int k) {
    char name[MAXN], code[MAXN];
    if (!checkIsLogin()) {
        while (k--) {
            scanf("%s %s", name, code);
        } 
        return ;
    }
    while (k--) {
        scanf("%s %s", name, code);
        insert(rt, name, code);
    }
    printf("import list success!");
}

void addUser(char *name, char *code) {
    if (!checkIsLogin()) {
        return ;
    }
    if (insert(rt, name, code)) {
        printf("operation successful!");
    } else {
        printf("user already exists!");
    }
}

void deleteUser(char *name) {
    if (!checkIsLogin()) {
        return ;
    }
    if (del(rt, name)) {
        printf("operation successful!");
    } else {
        printf("user does not exist!");
    }
}

void updateUser(char *name, char *code) {
    if (!checkIsLogin()) {
        return ;
    }
    if (update(rt, name, code)) {
        printf("operation successful!");
    } else {
        printf("user does not exist!");
    }
}

void exitAdmin() {
    if (!checkIsLogin()) {
        return ;
    }
    isLogin = false;
    printf("logout success!");
}

void checkUser(char *name, char *code) {
    int msg = search(rt, name, code);
    if (auth) {
        if (msg == 1) {
            printf("user does not exist!");
        } else if (msg == 2) {
            printf("successful verification!");
        } else {
            printf("code invalid!");
        }
    } else {
        if (msg == 1) {
            printf("user does not exist!");
        } else {
            printf("successful verification!");
        }
    }
}

int main() {
    int T, cas = 1;
    int n, k;
    char c;
    scanf("%d", &T);
    while (T--) {
        init();
        rt = new node();
        printf("Case #%d:\n", cas++);
        scanf("%d", &n);
        scanf("%s %s", username, password);
        while (n--) {
            cin >> operate;
            switch (OPERATE[operate]) {
                case LOGIN:
                    scanf("%s %s %s", s1, s2, s3);
                    login(s2, s3);
                    break;
                case OPEN:
                    scanf("%s", s1);
                    openAuth();
                    break;
                case CLOSE:
                    scanf("%s", s1);
                    closeAuth();
                    break;
                case IMPORT:
                    scanf(" list(%d)", &k);
                    importList(k);
                    break;
                case ADD:
                    scanf("%s %s", s1, s2);
                    addUser(s1, s2);
                    break;
                case DELETE:
                    scanf("%s", s1);
                    deleteUser(s1);
                    break;
                case UPDATE:
                    scanf("%s %s", s1, s2);
                    updateUser(s1, s2);
                    break;
                case EXIT:
                    scanf("%s", s1);
                    exitAdmin();
                    break;
                case CHECK:
                    scanf("%s %s", s1, s2);
                    checkUser(s1, s2);
            }
            puts("");
        }
        destory(rt);
    }    
}

D题:找出字符串中出现次数最多的字母

AC代码:

import java.util.Scanner;
public class Main {
     public static int[] countLetters(String str) {
         int[] result = new int[26];
         for(int i=0;i<str.length();i++) {
             result[str.charAt(i) - 'a']++;
         }
         return result;
     }
     
     public static int[] max(int[] num) {
         int[] result = new int[2]; 
        int maxNum = num[0], index = 0;
        for(int i=1;i<num.length;i++) {
                if(maxNum < num[i]) {
                    maxNum = num[i];
                    index = i;
                }
        }
        result[0] = maxNum;
        result[1] = index;
        return  result;
        
     }
     public static void main(String[] args) {
         Scanner input = new Scanner(System.in);
         
         String str =input.nextLine();
         int[] result = max(countLetters(str));
         int count = result[0];//出现最多的次数
         char ch = (char)('a' + result[1]);//出现次数最多的字符        
         
         for(int i = 0;i<str.length();i++) {
             if(str.charAt(i)  == ch) {
                 System.out.print(str.charAt(i) + "(出现了" + count + "次)");
             }else {
                 System.out.print(str.charAt(i));
             }
         }
         System.out.print("\n");
     }
}

E题:度假酒店

简单题

AC代码:

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <map>
#include <string.h>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <iostream>
#include <math.h>

#define ll long long
using namespace std;

int main(){
    ll n,m,total,num[10];
    while(~scanf("%lld %lld %lld",&num[0],&num[1],&num[2])){
        sort(num,num + 3);
        ll min = num[2] - 1;
        ll ans = 0;
        if(min - num[1] > 0)
            ans += min - num[1];
        if(min - num[0] > 0)
            ans += min - num[0];
        printf("%lld\n",ans);
    }
}

F题:三人成百

AC代码:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
/**
 * @author OliverWu
 *
 */
public class ThreeSum {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);
        int a = input.nextInt() ;
        if (a <=0 || a>=100 ){
            System.out.println("NO");
            return ;
        }
        List<Integer> inputList = new ArrayList<>();
        while(a >0 ){
            inputList.add(a);
            a = input.nextInt() ;            
        }        
        //int[] nums = {10,2,48,2,48,3,47,1,60,2,80,48,53,90,91,30,59,90,60,99,50,60};
        //10 2 48 2 48 3 47 1 60 2 80 48 53 90 91 30 59 90 60 99 50 60  0 
        int[] nums = inputList.stream().mapToInt(Integer::valueOf).toArray(); 
        List<List<Integer>> result = threeSum(nums,100) ;
        if(result.size() ==0 ){
            System.out.println("NO");
        }
        for( List<Integer> l : result ){
            for (int e : l){
                System.out.print(e+" ");
            }
            System.out.println();            
        }
            
        //System.out.println("*****************");

    }
    //三人成百

    //https://www.programcreek.com/2012/12/leetcode-3sum/
    public static List<List<Integer>> threeSum(int[] nums,int target) {
        Arrays.sort(nums);
     
        ArrayList<List<Integer>> result = new ArrayList<>();
     
        for (int i = 0; i < nums.length; i++) {
            int j = i + 1;
            int k = nums.length - 1;
     
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
     
            while (j < k) {
                if (k < nums.length - 1 && nums[k] == nums[k + 1]) {
                    k--;
                    continue;
                }
     
                if (nums[i] + nums[j] + nums[k] > target) {
                    k--;
                } else if (nums[i] + nums[j] + nums[k] < target) {
                    j++;
                } else {
                    ArrayList<Integer> l = new ArrayList<>();
                    l.add(nums[i]);
                    l.add(nums[j]);
                    l.add(nums[k]);
                    result.add(l);
                    j++;
                    k--;
                }
            }
        }     
        return result;
    }

}
Last Modified: September 8, 2021