2023 级新生周赛第二周题解

注意

　　该博客是为了帮助同学学习，并非为了协助同学刷题，请读者保持自觉，请勿做CV工具人。另外为了节省篇幅，代码中不再赘述题干。

群规复读机

　　这道题是一个签到题，非常的简单，只需要判断输入的第一个字符就能区分出不同的指令，当然你要是想的话也可以进行严格匹配。

• C/C++
• Java

#include <stdio.h>

int main() {
    switch (getchar()) {
        case 'a':
            printf("掌握提问艺术，从你我他做起");
            break;
        case 'b':
            printf("严禁发布色情内容，严禁涉政")；
            break;
        case 'm':
            printf("萌新不推荐使用 vs");
            break;
        case 'o':
            printf("oj 平台如果自己原来有一个账号的话用学校注册的账户继续往后写就行了，不需要把写过的题再交一遍。");
            break;
        case 's':
            printf("编写代码务必注意代码规范");
            break;
        case 't':
            printf("多读书多动手，编程能力是练出来的不是想出来的");
            break;
        case 'w':
            printf("本群可以灌水但不要一直灌水");
            break;
    }
    return 0;
}

#include <stdio.h>
#include <string.h>

int main() {
    char input[20];
    gets(input);
    if (strcmp(input, "base") == 0)
        printf("严禁发布色情内容，严禁涉政");
    else if (strcmp(input, "attention ms") == 0)
        printf("萌新不推荐使用 vs");
    else if (strcmp(input, "water") == 0)
        printf("本群可以灌水但不要一直灌水");
    else if (strcmp(input, "train") == 0)
        printf("多读书多动手，编程能力是练出来的不是想出来的");
    else if (strcmp(input, "ask question") == 0)
        printf("掌握提问艺术，从你我他做起")
    else if (strcmp(input, "oj") == 0)
        printf("oj 平台如果自己原来有一个账号的话用学校注册的账户继续往后写就行了，不需要把写过的题再交一遍。");
    else
        printf("编写代码务必注意代码规范");
    return 0;
}

import java.util.Scanner;
 
public class Main {
 
    static Scanner scanner = new Scanner(System.in);
 
    public static void main(String[] args) {
        String command = scanner.next();
        switch (command) {
            case "base":
                System.out.println("严禁发布色情内容，严禁涉政");
                break;
            case "ms":
                System.out.println("萌新不推荐使用 vs");
                break;
            case "water":
                System.out.println("本群可以灌水但不要一直灌水");
                break;
            case "train":
                System.out.println("多读书多动手，编程能力是练出来的不是想出来的");
                break;
            case "ask":
                System.out.println("掌握提问艺术，从你我他做起");
                break;
            case "oj":
                System.out.println("oj 平台如果自己原来有一个账号的话用学校注册的账户继续往后写就行了，不需要把写过的题再交一遍。");
                break;
            default:
                System.out.println("编写代码务必注意代码规范");
                break;
        }
    }
 
}

糟心的十字路口

　　这道题考验同学对 C/C++ 中printf的掌握，如果熟练掌握了输出函数，将精度作为变量并不复杂，printf的星号的使用方法这里不再讲解，详情见：如何理解c/c++中的输入/输出函数？。

• C/C++
• Java

#include <stdio.h>
#include <math.h>

int main () {
    double m, n;
    int p;
    scanf("%lf %lf %d", &m, &n, &p);
    double ans = m * pow(2.718281828459045, -0.114514 * n);
    printf("%.*f", p, ans);
//  char exp[10];
//  sprintf(exp, "%%.%df", p);
//  printf(exp, ans);
    return 0;
}

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        double m = scanner.nextDouble();
        double n = scanner.nextDouble();
        int p = scanner.nextInt();
        double ans = m * Math.pow(2.718281828459045, -0.114514 * n);
        System.out.printf("%." + p + "f", ans);
    }
 
}

数之国

　　这道题也是一道签到题，读入一个整数之后判断下一个字符是不是小数点就能判断是不是小数了。

　　注意以 0 作为输入的结尾、可能存在直接输入 0 的情况、可能输入全部都是小数这些特殊情况即可。

• C/C++
• Java

#include <stdio.h>
#include <stdbool.h>

int main() {
    int n;
    int sum = 0;
    char p;
    while (true) {
        scanf("%d", &n);
        int c = scanf("%c", &p);    // 1 2 2 0.0 2 0
        if (c != EOF && p == '.') {
            scanf("%*d");   // 使用 %*d 跳过下一个整数
            continue;
        } else if (n == 0) break;
        sum += n;
    }
    printf("%d", sum);
    return 0;
}

import java.io.IOException;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        int input = readInt();
        int ans = 0;
        while (input != Integer.MIN_VALUE) {
            ans += input;
            input = readInt();
        }
        System.out.println(ans);
    }
 
    static int readInt() throws IOException {
        int res = 0, flag = 1, input = System.in.read();
        while (!Character.isDigit(input)) {
            if (input == '-') flag = -1;
            input = System.in.read();
        }
        do {
            res = (res << 1) + (res << 3) + (input ^ 48);
            input = System.in.read();
        } while (Character.isDigit(input));
        if (input == '.') {
            readInt();
            return 0;
        } else if (res == 0) return Integer.MIN_VALUE;
        return res * flag;
    }
 
}

群友发言统计器

　　这道题考验同学是否知道如何将数据映射到数组中进行计数，起始是一个简易的哈希表的实现。

• C/C++
• Java

#include <stdio.h>
#include <string.h>

int main() {
    int record[1001];
    memset(record, 0, sizeof(record));
    int id;
    int result = 0;
    while (~scanf("%*s %d %*s", &id)) {
        if (++record[id - 100000000] == 1) ++result;
    }
    printf("%d", result);
    return 0;
}

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Set<Integer> record = new HashSet<>();
        while (scanner.hasNext()) {
            scanner.next();
            int id = scanner.nextInt();
            scanner.next();
            record.add(id);
        }
        System.out.println(record.size());
    }
 
}

读心卡牌魔术

　　这道题考验同学的理解能力，仔细思考就会发现每张卡牌上的最大值都是一样的，均是二进制位全为 1，注意使用无符号数即可。

• C/C++
• Java

#include <stdio.h>
#include <limits.h>

int main() {
    int input;
    scanf("%d", &input);
    unsigned result = UINT_MAX >> (32 - input);
    // unsigned result = ((unsigned) -1) >> (32 - input);
    for (int i = 0; i != input; ++i) {
        printf("%u\n", result);
    }
    return 0;
}

import java.util.Scanner;
 
public class Main {
 
    static Scanner scanner = new Scanner(System.in);
 
    public static void main(String[] args) {
        int n = scanner.nextInt();
        String ans = Integer.toUnsignedString(-1 >>> (32 - n));
        for (int i = 0; i < n; i++) {
            System.out.println(ans);
        }
    }
 
}

读心卡牌魔术 2.0

　　这道题也没有难度，直接暴力遍历就行。

• C/C++
• Java

#include <stdio.h>

int main () {
    int n, k, code;
    scanf("%d %d", &n, &k);
    int end = 1 << n;
    while (k--) {
        scanf("%d", &code);
        int mask = 1 << (code - 1);
        for (int i = 1; i != end; ++i) {
            if ((i & mask) != 0)
                printf("%d ", i);
        }
        printf("\n");
    }
    return 0;
}

import java.util.Scanner;
 
public class Main {
 
    static Scanner scanner = new Scanner(System.in);
 
    public static void main(String[] args) {
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int end = (1 << n) | 1;
        for (int i = 0; i < k; i++) {
            int code = scanner.nextInt();
            int mask = 1 << (code - 1);
            for (int j = 1; j != end; ++j) {
                if ((j & mask) != 0) System.out.printf("%d ", j);
            }
            System.out.println();
        }
    }
 
}

读心卡牌魔术 3.0

　　这道题稍微有些难度，有两种解法。

法一

　　我们观察可以发现，每张卡牌上数字出现的规律都是连续出现 X 个，然后跳过 X 个，再连续出现 X 个，以此往复，现在我们只需要计算出 X 的值就能套用公式计算出任意位置的数字。

　　计算 X 的值的方法也很简单，观察数字的二进制表达式规律，不难发现这个间隔正好等于每张卡的二进制编号（0b1、0b10、0b100……）。

　　接下来只需要用代码进行实现即可：

• C/C++
• Java

#include <stdio.h>

typedef unsigned long long LLU;

int main () {
    int k;
    LLU i;
    while (~scanf("%*d %d %llu", &k, &i)) {
        if (k == 0 && i == 0) break;
        LLU interval = LLU(1) << (k - 1);
        LLU div = i / interval;
        LLU mod = i % interval;
        LLU result = (div * interval << 1) + (mod == 0 ? 0 : interval + mod) - 1;
        printf("%llu\n", result);
    }
    return 0;
}

import java.util.Scanner;
 
public class Main {
 
    static Scanner scanner = new Scanner(System.in);
 
    public static void main(String[] args) {
        while (scanner.hasNext()) {
            scanner.nextInt();
            int k = scanner.nextInt();
            long i = Long.parseUnsignedLong(scanner.next());
            if (n == 0 && k == 0 && i == 0) break;
            long interval = 1L << (k - 1);
            long div = Long.divideUnsigned(i, interval);
            long mod = Long.remainderUnsigned(i, interval);
            long result = (div * interval << 1) + (mod == 0 ? 0 : interval + mod) - 1;
            System.out.println(Long.toUnsignedString(result));
        }
    }
 
}

法二

　　仔细观察二进制表达式，实际上有一个非常简单得二进制规律。

　　现在假设我们要求第 i 张卡牌得第 k 个数字，那么我们只需要将第 i 位置 1，然后在此基础上做k - 1次加一即可（加一时要跳过第 i 位）。所以我们将数字 k 减一后以第 i 位为界分为两部分，第 i 位及其左边得数字向左移一位，右边数字保持不变，第 i 位置 1 就是最终答案。

#include <stdio.h>
#include <limits.h>

typedef unsigned long long LLU;

int main() {
    int k;
    LLU i;
    while (~scanf("%*d %d %llu", &k, &i)) {
        if (k == 0 && i == 0) break;
        LLU j = i - 1;
        LLU left = j >> (k - 1);
        LLU right = j & (ULLONG_MAX >> (64 - k + 1));
        LLU result = (left << k) | (((LLU) 1) << (k - 1)) | right;
        printf("%llu\n", result);
    }
    return 0;
}

Time Machine

　　这道题考验同学对于scanf函数的掌握程度，使用scanf可以轻松地读入八进制和十六进制的数字，不需要手写进制转换。

• C/C++
• Java

#include <stdio.h>

typedef unsigned long long LLU;

int main() {
    LLU var, real;
    scanf("%llx %llo", &var, &real);
    printf("%d", (int) (var - real));
    return 0;
}

import java.util.Scanner;
 
public class Main {
 
    static Scanner scanner = new Scanner(System.in);
 
    public static void main(String[] args) {
        long d = Long.parseUnsignedLong(scanner.next(), 16);
        long s = Long.parseUnsignedLong(scanner.next(), 8);
        System.out.println(d - s);
    }
 
}

CJJJ 的白给抓取机

　　这道题是防 AK 题，逻辑其实很简单，实现稍微有点复杂，具体这里不再细讲，详情见哔哩哔哩直播。

• C/C++
• Kotlin

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

typedef long long LL;
typedef struct Mark Mark;
// 用链表实现一个栈
struct Mark {
    Mark* prev;     // 上一个节点
    char* type; // 节点名称
};

bool readln(char* str);
bool invoke();
void pushItem(char* name, int start, int end);
char* popItem();
int indexOfAny(const char* src, int start, int end, char* items);
char* indexOfInRange(char* src, int length, const char* that);
bool strEquals(char* src, int length, const char* that);
bool isSelfClosing(char* src, int start, int end);

char distId[1010] = {'i', 'd', '=', '"'};  // 目标 ID
char input[1001];   // 单行输入
char content[3001];  // 结果
bool hit = false;   // 判断是否找到了 id 为指定字符串的标签
Mark* linkedList = NULL;

int main() {
    readln(distId + 4);
    int idLength = (int) strlen(distId);
    distId[idLength] = '"';
    distId[idLength + 1] = '\0';
    if (!invoke()) printf("duo lao a cjmm");
    else if (!hit) printf("duo lao a cjjj");
    else {
        bool isNotBlank = false;
        for (int i = 0; content[i] != '\0'; ++i) {
            switch (content[i]) {
                case ' ': case '\t': case '\n':
                    break;
                default:
                    isNotBlank = true;
                    goto skipFor;
            }
        }
        skipFor:
        if (!isNotBlank) printf("QAQ");
        else {
            int start = 0;
            for (; content[start] != '\0'; ++start) {
                if (content[start] != '\n') break;
            }
            printf("%s", content + start);
        }
    }
    return 0;
}

bool invoke() {
    bool skip = false;
    char* contentStartFlag = NULL;
    int contentStartIndex;
    int contentLength = 0;
    while (readln(input)) {
        int length = (int) strlen(input);
        int i = 0;
        if (skip) {
            LL endIndex = (LL) (strstr(input, "-->") - input);
            if (endIndex < 0) continue;
            i = (int) (endIndex + 3);
        }
        while (i != length) {
            LL tmp = (LL) (strchr(input + i, '<') - input);
            if (tmp < 0) break;
            int startIndex = (int) tmp;
            // 判断是否是注释
            if (startIndex + 3 < length && input[startIndex + 1] == '!' && input[startIndex + 2] == '-' && input[startIndex + 3] == '-') {
                LL endIndex = (LL) (strstr(input + i, "-->") - input);
                if (endIndex < 0) { // endIndex < 0 表明注释不在一行内结束
                    skip = true;
                    break;
                }
                i = (int) (endIndex + 3);   // 如果在一行内结束就跳过注释中的内容
                continue;
            }
            int endIndex = (int) (strchr(input + startIndex + 1, '>') - input);
            if (input[startIndex + 1] == '/') { // 如果是结束标记
                char* oldName = popItem();
                if (oldName == NULL) return false;  // 没有开始标记，结构错误
                bool isEquals = strEquals(input + startIndex + 2, endIndex - startIndex - 2, oldName);
                bool isContent = oldName == contentStartFlag;
                free(oldName);
                if (!isEquals) return false;    // 开始标记和结束标记不对应，结构错误
                if (isContent) {
                    contentStartFlag = NULL;
                    int len = startIndex - contentStartIndex;
                    memcpy(content + contentLength, input + contentStartIndex, sizeof(char) * len);
                    contentLength += len;
                }
            } else {    // 如果是开始标记
                int nameEndIndex = indexOfAny(input, startIndex + 1, endIndex + 1, " >");
                bool selfClosing = input[endIndex - 1] == '/' || isSelfClosing(input, startIndex + 1, nameEndIndex);
                if (!selfClosing) pushItem(input, startIndex + 1, nameEndIndex);
                char* idIndex = indexOfInRange(input + startIndex + 1, endIndex - startIndex - 1, distId);
                if (idIndex != NULL) {  // 如果找到了对应的 ID
                    hit = true;
                    if (!selfClosing) {
                        contentStartFlag = linkedList->type;
                        contentStartIndex = endIndex + 1;
                    }
                }
            }
            i = endIndex + 1;
        }
        if (contentStartFlag != NULL) {
            int len = length - contentStartIndex;
            memcpy(content + contentLength, input + contentStartIndex, sizeof(char) * len);
            contentLength += len;
            contentStartIndex = 0;
            content[contentLength++] = '\n';
        }
    }
    content[contentLength] = '\0';
    return !skip && linkedList == NULL;
}

/** 读取一行数据 */
bool readln(char* str) {
    memset(str, 0, sizeof(char) * 1000);
    char *flag = gets(str);
    return flag != NULL;
}

// 在字符串的指定范围内查找 items 中字符最早出现的那一个的下标
int indexOfAny(const char* src, int start, int end, char* items) {
    for (int i = start; i != end; ++i) {
        char value = src[i];
        char* dist = strchr(items, value);
        if (dist != NULL) return i;
    }
    return -1;
}

// 推送一个节点到栈中
void pushItem(char* name, int start, int end) {
    Mark* newItem = malloc(sizeof(Mark));
    newItem->prev = linkedList;
    int length = end - start;
    newItem->type = malloc(sizeof(char) * (length + 1));
    memcpy(newItem->type, name + start, sizeof(char) * length);
    newItem->type[length] = '\0';
    linkedList = newItem;
}

// 弹出栈顶元素
char* popItem() {
    if (linkedList == NULL) return NULL;
    Mark* oldItem = linkedList;
    char* oldType = oldItem->type;
    linkedList = oldItem->prev;
    free(oldItem);
    return oldType;
}

// 在指定范围内比较字符串是否相等
bool strEquals(char* src, int length, const char* that) {
    char tmp = src[length];
    src[length] = '\0';
    bool result = strcmp(src, that) == 0;
    src[length] = tmp;
    return result;
}

// 在指定范围内查找字符串
char* indexOfInRange(char* src, int length, const char* that) {
    char tmp = src[length];
    src[length] = '\0';
    char* result = strstr(src, that);
    src[length] = tmp;
    return result;
}

const char SELF_LIST[][11] = {"br", "hr", "img", "input", "link", "meta", "area"};

// 判断是否是自闭合标签
bool isSelfClosing(char* src, int start, int end) {
    src = src + start;
    int length = end - start;
    for (int i = 0; i != 7; ++i) {
        if (strEquals(src, length, SELF_LIST[i]))
            return true;
    }
    return false;
}

/* 这个代码没有验证对不对，应该没啥问题 */
import java.util.LinkedList
import kotlin.text.StringBuilder

var content: String? = null

fun main() {
    val distId = readln()
    val sb = StringBuilder()
    var input = readlnOrNull()
    while (input != null) {
        sb.append(input).append('\n')
        input = readlnOrNull()
    }
    val code = sb.toString()
    if (!invoke(code, distId)) {
        println("duo lao a cjmm")
        return
    }
    if (content == null) println("duo lao a cjjj")
    else if (content!!.isBlank()) println("QAQ")
    else println(content!!.substring(content!!.indexOfFirst { it != '\n' }))
}

fun invoke(code: String, distId: String): Boolean {
    val stack = LinkedList<Mark>()
    var index = 0
    var startMark: Mark? = null
    do {
        val mark = findMark(code, index) ?: break
        when (mark.type) {
            MarkType.START -> stack.addLast(mark)
            MarkType.END -> {
                if (stack.isEmpty()) return false
                val last = stack.removeLast()
                if (last.tagName != mark.tagName)
                    return false
                if (last === startMark) {
                    content = code.substring(last.endIndex, mark.startIndex)
                }
            }
            MarkType.ERROR -> return false
            else -> {}
        }
        index = mark.endIndex
        val sub = code.substring(mark.startIndex, mark.endIndex)
        val idIndex = sub.indexOf("id=\"$distId\"")
        if (idIndex != -1) {
            if (mark.type == MarkType.SELF) content = ""
            else startMark = mark
        }
    } while (index < code.length)
    return stack.isEmpty()
}

/** 查找下一个开始/闭合标记 */
fun findMark(code: String, index: Int): Mark? {
    val startIndex = code.indexOf("<", index)
    if (startIndex == -1) return null
    if (code[startIndex + 1] == '!' && code[startIndex + 2] == '-' && code[startIndex + 3] == '-') {
        // 如果遇到了注释开头
        val endIndex = code.indexOf("-->", startIndex + 4)
        if (endIndex == -1) return Mark("", MarkType.ERROR, 0, 0)
        return Mark("", MarkType.SELF, startIndex + 4, endIndex + 3)
    }
    var type = MarkType.ERROR
    var leftIndex = startIndex + 1
    if (code[leftIndex] == '/') {
        ++leftIndex
        type = MarkType.END
    }
    val tagName = findTagName(code, leftIndex)
    if (isSelfClosing(tagName)) {
        type = if (type == MarkType.END) MarkType.ERROR else MarkType.SELF
    } else if (type == MarkType.ERROR) {
        type = MarkType.START
    }
    return Mark(tagName, type, startIndex, code.indexOf('>', leftIndex) + 1)
}

/** 从指定位置截取标签名称 */
fun findTagName(code: String, index: Int): String {
    val endIndex = code.indexOfAny(listOf(" ", ">", "/>"), index)
    return code.substring(index, endIndex)
}

/** 判断指定类型的标签是否是自闭合的 */
fun isSelfClosing(tagName: String): Boolean = when (tagName) {
    "hr", "br", "img", "input", "link", "meta", "area" -> true
    else -> false
}

data class Mark(
    val tagName: String,
    val type: MarkType,
    val startIndex: Int,
    val endIndex: Int
)

enum class MarkType {
    START, END, SELF, ERROR
}