一些神奇的C语言题目

今天做了做2024年春季学期的C语言期末题目，恐怖如斯。OI退役已经两年多，很多代码脑子里面有想法，就是写不出来，尤其是C++转向C后，用不了STL，实在是有点不知所措。这个第二题，一眼顶针鉴定为字典树，但实际上它的数据量很小，如果用map会很快解决，但是没有如果，这里用不了map，我只能苦逼的写字典树。

(题目)[https://lexue.bit.edu.cn/mod/programming/view.php?id=484192]

输入一篇文章，以空行结束，希望统计一下其中单词出现的次数。

所谓“单词”，是仅由大写字母和/或小写字母组成的连续子串，且不区分大小写。例如，about是一个单词，a_out会被认为是a和out两个单词，about和About会被认为是同一个单词。

输出时，每个不同的单词输出一行，包括单词（全小写）和出现次数，以空格分隔。优先输出出现次数多的单词；出现次数相同的，按字典序输出。

数据范围 文章中，每个单词不超过20个字符，每行不超过80个字符，有效行数不超过100行。

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

#define MAX_WORD_LEN 20
#define MAX_LINE_LEN 80
#define MAX_WORD_COUNT 1000

#define lamaper 0

typedef struct TrieNode {
    struct TrieNode* children[26];//有26个子节点，对应26个字母
    int count; //一般为0，如果不为零就代表到这里截至有单词出现，那么这里的数字就是单词出现的次数
} TrieNode;

TrieNode* create_node() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));//神奇的初始化，没有面向对象就少了很多爽点
    for(int i = 0; i < 26; i++){
        node->children[i] = NULL;
    }
    node->count = 0;
    return node;
}

TrieNode* insert_char(TrieNode* current, char c) {
    if('a' <= c && c <= 'z'){//按照题目要求进行大小写切换
        int index = c - 'a';//把字母变成数字索引
        if(current->children[index] == NULL){
            current->children[index] = create_node();
        }
        return current->children[index];
    }else if ('A' <= c && c <= 'Z'){
        int index = tolower(c) - 'a';
        if (current->children[index] == NULL) {
            current->children[index] = create_node();
        }
        return current->children[index];
    }
    return NULL;
}

typedef struct WordCount{//这个用来统计词语
    char word[MAX_WORD_LEN + 1];
    int count;
}WordCount;

WordCount word_list[MAX_WORD_COUNT]; 
int word_count = 0;

void dfs(TrieNode* node, char* prefix, int len){//简单的树的前序遍历
    if(node->count > 0){//如果这里被截断了
        strncpy(word_list[word_count].word, prefix, len);//把prefix复制到word_list[word_count].word中
        word_list[word_count].word[len] = '\0';//补加一个截断，养成好习惯
        word_list[word_count].count = node->count;
        word_count++;
    }

    for(int i = 0; i < 26; i++){
        if(node->children[i] != NULL){
            prefix[len] = 'a' + i;//把字母加到prefix里面
            prefix[len + 1] = '\0';
            dfs(node->children[i], prefix, len + 1);//len既可以理解为长度也可以理解为搜索的深度
        }
    }
}

int compare(const void* a, const void* b){//这个是专门给qsort排序用的，qsort类似于STL的sort
    WordCount* w1 = (WordCount*)a;
    WordCount* w2 = (WordCount*)b;
    if(w1->count != w2->count){
        return w2->count - w1->count; // 出现次数多的排在前面
    }else{
        return strcmp(w1->word, w2->word); 
        //strcmp 是 C 标准库中的一个字符串比较函数，用于按字典顺序比较两个字符串
    }
}

signed main(){
    TrieNode* root = create_node();
    TrieNode* current = root;

    char line[MAX_LINE_LEN + 1]; 

    while(fgets(line, sizeof(line), stdin) != NULL){
        int len = strlen(line);
        if(len == 1 && line[0] == '\n'){ 
            break;
        }
        for(int i = 0; i < len; i++){
            char c = line[i];
            if(isalpha(c)){ //如果是字母
                current = insert_char(current, c);
            }else{ //不是就退回根节点
                if(current != root){ 
                    current->count++;
                }
                current = root; 
            }
        }
    }

    if(current != root){
        current->count++;
    }

    char prefix[MAX_WORD_LEN + 1];
    prefix[0] = '\0';
    dfs(root, prefix, 0);

    qsort(word_list, word_count, sizeof(WordCount), compare);

    for(int i = 0; i < word_count; i++){
        printf("%s %d\n", word_list[i].word, word_list[i].count);
    }


    return lamaper;//防伪
}

BIT历年真是神人辈出，这些题目很有技巧性。 比如NH-02. 【选做题】Having a lunch

NH-02. 【选做题】Having a lunch

题目描述：

​ 聪明的你轻松的解开了门口的密码锁，打开了门锁，可是大门被一群饥饿的小朋友堵住的，善良的你并不想靠蛮力打开，于是打算去旁边的食品摊买点巧克力讨好小朋友。食品摊一共有六种巧克力，第一种巧克力只有一个，第二种巧克力有两个，第三种巧克力有三个，第四、五、六种巧克力均有无数个，但是你每次购买的数量必须有所限制：第四种巧克力每次购买的数量必须是1的倍数，第五种巧克力每次购买的数量必须是2的倍数，第六种巧克力每次购买的数量必须是3的倍数。你一共要买N块巧克力，你想知道你一共有多少种不同的购买方案。就算一个N也太简单了，你打算挑战一下一次性算两个。

输入格式：一行，两个整数，N1和N2，分别表示两个情况下的N。

输出格式：一行，两个用一个空格隔开的整数，分别表示当N=N1，和N=N2时候的答案。

样例输入：4 96

样例输出：34 18434

样理解释：对于N=4，记（a1,a2,a3,a4,a5,a6）表示六种巧克力的购买数量，可以知道，共有方案：

(0,0,0,0,4,0) (0,0,0,1,0,3) (0,0,0,2,2,0) (0,0,0,4,0,0) (0,0,1,0,0,3) (0,0,1,1,2,0) (0,0,1,3,0,0) (0,0,2,0,2,0) (0,0,2,2,0,0) (0,0,3,1,0,0) (0,1,0,0,0,3) (0,1,0,1,2,0) (0,1,0,3,0,0) (0,1,1,0,2,0) (0,1,1,2,0,0) (0,1,2,1,0,0) (0,1,3,0,0,0) (0,2,0,0,2,0) (0,2,0,2,0,0) (0,2,1,1,0,0) (0,2,2,0,0,0) (1,0,0,0,0,3) (1,0,0,1,2,0) (1,0,0,3,0,0) (1,0,1,0,2,0) (1,0,1,2,0,0) (1,0,2,1,0,0) (1,0,3,0,0,0) (1,1,0,0,2,0) (1,1,0,2,0,0) (1,1,1,1,0,0) (1,1,2,0,0,0) (1,2,0,1,0,0) (1,2,1,0,0,0)

数据范围：4≤N≤10^9

（买了当然自己也要吃，所以至少买四个！）

——by smzzl

这个题第一眼看上去想搜索，但仔细看看数据范围在1E9就知道这是个时间复杂度为常数的题目。 回看这个问题，第一第二第三种巧克力的数量是确定的，所以根据组合数的结论，我们可以直接计算出这几种情况。

接下来就需要讨论第四第五第六种巧克力，这三种巧克力的数量是无限的。实际上抽象模型就是求a+2b+3c=M的非负整数解个数。 其中a、b、c分别是第四第五第六中巧克力的选择次数。如此我们可以化简公式，求a+2b=M-3c，然后设K=M-3c， 用奇妙的数论方法（丢翻图方程）可以知道，对于任意的一元二次方程ax+by=c的非负整数解个数等于=⌊ c/ab/gcd(a,b) ⌋+1， 所以我们很容易知道对于a+2b=K有（K/2）向下取整+1个非负整数解，那么只需要遍历c，再求和就行。

经过计算，这个数列求和的结果是S=(m+3)^2 + 3 / 12，所以就有如下程序。

#include<stdio.h>  
#define int long long  
  
int coe[7] = {1,3,5,6,5,3,1};  
int cnt;  
  
int min(int a,int b){  
    return (a > b)? b : a ;  
}  
  
int calculate(int k){  
    return (k / 2) + 1;  
}  
  
int work(int n){  
    int cnt = 0;  
    for(int i = 0 ; i <= min(n , 6) ; ++i){  
        int m = n - i;  
int S =((m+3) *(m+3)+3)/12;;  
  
       cnt += S  * coe[i];  
          
    }  
    return cnt;  
}  
  
signed main(){  
    int n1,n2;  
    scanf("%lld %lld",&n1,&n2);  
    printf("%lld %lld\n",work(n1),work(n2));  
    return 0;  
}  

NH-3. 【选做题】Distribute

题目描述：

巧克力买来了肯定要分发呀，但是你的力气是有限的，你丢出去的糖果只能被距离你小于等于R的小朋友接到。因此你想知道，对于在某一个位置的小朋友，是否能接到你丢出去的糖果。

输入格式：

第一行一个整数T，表示数据组数

接下来T行，每行五个数，x,y,R,x0,y0，表示你的坐标(x,y)，你能丢出去的距离R，某一个小朋友的位置(x0,y0)

输出格式：

T行，每行为YES或NO，第i行表示的是对应第i组的答案。若第i组的小朋友能接到糖果，输出“YES”，否则输出“NO” （均不加引号）

样例输入：

2

0 0 1 1 1

0 0 2 1 0

样例输出：

NO

YES

数据范围：0<R<100000，

x

,

y

,

x0

,

y0

<100000 保证所有数的最多有四位小数

这个题需要注意的是精度问题，如何处理【四位小数】是重点。我们需要知道的是，在计算机中处理小数的难度是远大于整数的， 很容易精度丢失，因为浮点数的构造无法准确的表示很多小数。所以为了解决这个问题，我们先要把小数变成整数，然后在整数的基础上操作。

实际上我们并不真正关心二人的距离，只关心能不能到达，所以不用太在意最后距离的值正不正确。

最后要注意的是，小数乘1000为整数后，也会造成精度丢失，所以为了保持精确，我们一定要对其进行四舍五入，也就是round()

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

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        double x, y, R, x0, y0;
        scanf("%lf%lf%lf%lf%lf", &x, &y, &R, &x0, &y0);
        
        // 将各值乘以10000并四舍五入转换为整数，保留四位小数精度
        long long x_int = (long long)round(x * 10000.0);
        long long y_int = (long long)round(y * 10000.0);
        long long R_int = (long long)round(R * 10000.0);
        long long x0_int = (long long)round(x0 * 10000.0);
        long long y0_int = (long long)round(y0 * 10000.0);
        
        // 计算dx和dy
        long long dx = x0_int - x_int;
        long long dy = y0_int - y_int;
        
        // 计算平方距离和R的平方
        long long dis_sq = dx * dx + dy * dy;
        long long R_sq = R_int * R_int;
        
        // 比较并输出结果
        printf(dis_sq <= R_sq ? "YES\n" : "NO\n");
    }
    return 0;
}