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;
}
}