编程练习与题解汇总
本系列文章记录了在学习编程过程中遇到的各类编程题目及其解决方案，涵盖了从基础算法到特定场景应用的多种题型。
L1-007 念数字
该题目要求将输入的整数按顺序念出，并处理负数和零。关键在于正确处理负号和数字之间的空格，以及递归调用以实现数字的逐位输出。
#include <stdio.h>
#include <math.h>
char nums[10][5] = {"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
void print_num_in_words(int num) {
int last_digit = num % 10;
num /= 10;
if (num != 0) {
print_num_in_words(num);
printf(" %s", nums[last_digit]);
} else {
printf("%s", nums[last_digit]);
}
}
int main() {
int number;
scanf("%d", &number);
if (number < 0) {
number = -number;
printf("fu ");
}
print_num_in_words(number);
printf("\n"); // Ensure a newline at the end
return 0;
}
L1-017 到底有多二
此题需要处理一个可能长达50位的数字，因此必须使用字符串存储。核心逻辑是计算数字中 '2' 的出现次数占总位数（去除负号）的比例，并根据是否为负数和末位是否为偶数进行相应调整。
#include <stdio.h>
#include <string.h>
char number_str[55];
int main() {
scanf("%s", number_str);
int len = strlen(number_str);
int is_even_last_digit = 0;
int is_negative = 0;
int significant_digits = len;
int count_of_twos = 0;
if (number_str[0] == '-') {
is_negative = 1;
significant_digits -= 1;
}
if ((number_str[len - 1] - '0') % 2 == 0) {
is_even_last_digit = 1;
}
for (int i = 0; i < len; ++i) {
if (number_str[i] == '2') {
count_of_twos += 1;
}
}
double ratio = (double)count_of_twos / (double)significant_digits;
if (is_negative) {
ratio *= 1.5;
}
if (is_even_last_digit) {
ratio *= 2.0;
}
printf("%.2f%%\n", ratio * 100.0);
return 0;
}
L1-015 跟奥巴马一起画方块
题目要求根据给定的宽度和字符，绘制一个实心矩形。关键在于计算矩形的高度，即向上取整的"行数"。
#include <stdio.h>
#include <math.h>
int main() {
int width, height;
char fill_char;
scanf("%d %c", &width, &fill_char);
// Calculate height, rounding up
height = (width + 1) / 2;
for (int j = 0; j < height; ++j) {
for (int i = 0; i < width; ++i) {
printf("%c", fill_char);
}
printf("\n");
}
return 0;
}
L1-016 查验身份证
该题目涉及身份证号码的校验。需要根据给定的权重计算校验码，并与输入的校验码进行比对。需要处理输入的身份证号是否为纯数字以及校验码是否正确的情况。
#include <stdio.h>
int main() {
char id_cards[110][20];
char valid_check_chars[] = {'1', '0', 'X', '9', '8', '7', '6', '5', '4', '3', '2'};
int weights[17] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
int n = 0, passed_count = 0;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
int calculated_sum = 0;
scanf("%s", id_cards[i]);
int is_valid = 1;
for (int j = 0; j < 17; ++j) {
if (id_cards[i][j] < '0' || id_cards[i][j] > '9') {
printf("%s\n", id_cards[i]);
is_valid = 0;
break;
}
calculated_sum += (id_cards[i][j] - '0') * weights[j];
}
if (is_valid) {
if (id_cards[i][17] == valid_check_chars[calculated_sum % 11]) {
passed_count++;
} else {
printf("%s\n", id_cards[i]);
}
}
}
if (passed_count == n) {
printf("All passed\n");
}
return 0;
}
L1-018 到底有多二
本题要求根据输入的时钟时间（HH:MM），判断是"太早了"还是敲钟。需要处理24小时制和12小时制的转换，以及判断是否需要输出"Dang"。
#include <stdio.h>
int main() {
int hour = 0, minute = 0;
scanf("%d:%d", &hour, &minute);
if (hour < 0 || hour > 23 || minute < 0 || minute > 59) {
// Assuming invalid time format could be represented by error, though problem implies valid HH:MM input.
// For this problem's logic, we'll proceed assuming valid ranges or handle specific problem outputs.
// The original code had error messages for out of bounds, but the problem structure implies specific outputs.
}
// Handle the "Too early to Dang" case
if (hour < 12 || (hour == 12 && minute == 0)) {
printf("Only ");
if (hour < 10) printf("0");
printf("%d:", hour);
if (minute < 10) printf("0");
printf("%d. Too early to Dang.\n", minute);
} else {
// Handle the "Dang" case for times from 12:01 to 23:59
int bells_to_ring;
if (minute == 0) {
bells_to_ring = hour - 12;
} else {
bells_to_ring = hour - 12 + 1;
}
// Special case for 12:00, which is "Too early to Dang"
// For other times after 12:00, ring the bell.
if (hour == 12 && minute == 0) {
// Already handled by "Too early to Dang"
} else {
for (int i = 0; i < bells_to_ring; ++i) {
printf("Dang");
}
printf("\n");
}
}
return 0;
}
L1-008 求整数段和
该题要求计算从给定的起始整数到结束整数（包含两端）的和，并按每行输出5个数字的格式进行打印。
#include <stdio.h>
int main() {
int start, end;
scanf("%d %d", &start, &end);
int current_sum = 0;
int numbers_on_line = 0;
for (int i = start; i <= end; ++i) {
printf("%5d", i);
current_sum += i;
numbers_on_line++;
if (numbers_on_line == 5 && i != end) {
printf("\n");
numbers_on_line = 0;
}
}
printf("\n"); // Ensure a newline after the last number
printf("Sum = %d\n", current_sum);
return 0;
}
L1-056 猜数字
这道题模拟了一个猜数字游戏。玩家会给出数字，系统会提示"太高"、"太低"或"正确"。需要根据这些提示，在给定的猜测次数内找到正确的数字。这里我们采用二分查找的思路，并记录每次猜测的差距。
#include <stdio.h>
#include <string.h>
#include <stdlib.h> // For abs
int main() {
int num_players, guess_val;
char player_name[10005][10];
int player_guesses[10005];
int total_guesses = 0;
scanf("%d", &num_players);
for (int i = 0; i < num_players; ++i) {
scanf("%s %d", player_name[i], &player_guesses[i]);
total_guesses += player_guesses[i];
}
int half_average = (total_guesses / num_players) / 2;
int min_diff = abs(half_average - player_guesses[0]);
int winning_player_index = 0;
for (int i = 1; i < num_players; ++i) {
int current_diff = abs(half_average - player_guesses[i]);
if (current_diff < min_diff) {
min_diff = current_diff;
winning_player_index = i;
}
}
printf("%d %s\n", half_average, player_name[winning_player_index]);
return 0;
}
L1-011 A-B
该题要求从输入的一行字符串A和一行字符串B中，移除A中所有在B中出现过的字符。提供了两种解法，一种是O(N^2)的朴素比较，另一种是O(256N)利用额外空间标记。
#include <stdio.h>
#include <string.h>
int main() {
char string_a[10005] = {0};
int delete_flags[10005] = {0};
int len_a = 0;
char ch;
// Read string A
while ((ch = getchar()) != '\n') {
string_a[len_a] = ch;
len_a++;
}
// Process string B to mark characters for deletion
int char_seen[260] = {0}; // Assuming ASCII characters
while ((ch = getchar()) != '\n') {
if (char_seen[(unsigned char)ch]) continue; // Already processed this character
char_seen[(unsigned char)ch] = 1;
for (int i = 0; i < len_a; ++i) {
if (string_a[i] == ch) {
delete_flags[i] = 1;
}
}
}
// Print characters from A that are not marked for deletion
for (int i = 0; i < len_a; ++i) {
if (!delete_flags[i]) {
printf("%c", string_a[i]);
}
}
printf("\n");
return 0;
}
L1-039 古风排版
此题要求将输入的字符串按照古风排版方式（从左上到右下，每列长度相同）进行输出。关键在于二维数组的巧妙使用，以及按列倒序输出。
#include <stdio.h>
#include <string.h>
char output_grid[100][1000];
char input_str[1005] = {0};
int main() {
int num_columns, i, j;
scanf("%d", &num_columns);
char ch;
int str_len = 0;
getchar(); // Consume the newline character after reading num_columns
while ((ch = getchar()) != '\n') {
input_str[str_len] = ch;
str_len++;
}
// Initialize the grid with spaces
for (i = 0; i < num_columns; ++i) {
for (j = 0; j < (str_len / num_columns + 1); ++j) {
output_grid[i][j] = ' ';
}
}
int max_row_index = 0;
for (i = 0; i < str_len; ++i) {
int row = i % num_columns;
int col = i / num_columns;
output_grid[row][col] = input_str[i];
if (col > max_row_index) {
max_row_index = col;
}
}
// Print the grid column by column in reverse order of columns
for (i = 0; i < num_columns; ++i) {
for (j = max_row_index; j >= 0; --j) {
printf("%c", output_grid[i][j]);
}
printf("\n");
}
return 0;
}
L1-071 前世档案
本题要求将输入的二进制字符串（'y'代表0，'n'代表1）转换为十进制整数。需要处理字符串的顺序，并根据位权计算。
#include <stdio.h>
int main() {
int n, m; // n: length of binary string, m: number of test cases
char binary_str[30];
scanf("%d %d", &n, &m);
for (int i = 0; i < m; ++i) {
scanf("%s", binary_str);
int decimal_value = 0;
int base = 1; // Represents powers of 2
// Iterate from right to left (least significant bit to most significant bit)
for (int j = n - 1; j >= 0; --j) {
int bit_value;
if (binary_str[j] == 'y') {
bit_value = 0;
} else { // 'n'
bit_value = 1;
}
decimal_value += bit_value * base;
base *= 2;
}
printf("%d\n", decimal_value + 1); // Add 1 as per problem statement
}
return 0;
}
L1-043 阅览室
这是一个模拟题，需要统计在阅览室的阅读人数和平均阅读时间。输入包含开始 ('S') 和结束 ('E') 事件，需要根据这些事件计算每个人的阅读时长，并最后计算总人数和平均时长（四舍五入）。
#include <stdio.h>
#include <math.h> // For ceil
int main() {
int n_entries;
scanf("%d", &n_entries);
for (int entry_count = 0; entry_count < n_entries; ++entry_count) {
int book_id;
char event_type;
int hour, minute;
int record_start_hour[1005] = {0};
int record_start_minute[1005] = {0};
int book_is_checked_out[1005] = {0}; // 0: not checked out, 1: checked out
int reading_duration[1005] = {0};
int total_books_read = 0;
int total_reading_minutes = 0;
while (scanf("%d", &book_id) == 1 && book_id != 0) {
scanf(" %c %d:%d", &event_type, &hour, &minute);
if (event_type == 'S') {
book_is_checked_out[book_id] = 1;
record_start_hour[book_id] = hour;
record_start_minute[book_id] = minute;
} else if (event_type == 'E') {
if (book_is_checked_out[book_id] == 1) {
book_is_checked_out[book_id] = 0;
int start_time_in_minutes = record_start_hour[book_id] * 60 + record_start_minute[book_id];
int end_time_in_minutes = hour * 60 + minute;
int duration = end_time_in_minutes - start_time_in_minutes;
reading_duration[book_id] = duration; // Store duration if needed, though problem asks for sum
total_books_read++;
total_reading_minutes += duration;
}
}
}
int average_reading_time = 0;
if (total_books_read > 0) {
// Calculate average with rounding
average_reading_time = (int)ceil((double)total_reading_minutes / total_books_read);
}
printf("%d %d\n", total_books_read, average_reading_time);
}
return 0;
}
L1-054 福到了
此题要求判断一个N*N的字符矩阵是否中心对称，然后输出镜像翻转后的矩阵。需要处理'@'字符和空格，以及判断对称性。
#include <stdio.h>
#include <string.h>
char grid[105][105] = {0}; // Using 0 for space, 1 for '@'
int main() {
int n, count = 0;
char fill_char;
char temp_char;
scanf("%c %d", &fill_char, &n);
getchar(); // Consume the newline
for (int i = 0; i < n; ++i) {
int j = 0;
while ((temp_char = getchar()) != '\n') {
if (temp_char == '@') {
grid[i][j] = 1;
} else {
grid[i][j] = 0;
}
j++;
}
}
// Check for symmetry
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == grid[n - 1 - i][n - 1 - j]) {
count++;
}
}
}
if (count == n * n) {
printf("bu yong dao le\n");
}
// Print the mirrored and flipped grid
for (int i = n - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (grid[i][j] == 1) {
printf("%c", fill_char);
} else {
printf(" ");
}
}
printf("\n");
}
return 0;
}
L1-048 矩阵A乘以B
该题要求实现两个矩阵的乘法。需要先读取两个矩阵的维度和元素，然后判断是否可以相乘，最后计算并输出结果矩阵。
#include <stdio.h>
int matrix_a[105][105], matrix_b[105][105], result_matrix[105][105];
int main() {
int rows_a, cols_a, rows_b, cols_b;
int num = 0;
// Read Matrix A
scanf("%d %d", &rows_a, &cols_a);
for (int i = 0; i < rows_a; ++i) {
for (int j = 0; j < cols_a; ++j) {
scanf("%d", &matrix_a[i][j]);
}
}
// Read Matrix B
scanf("%d %d", &rows_b, &cols_b);
for (int i = 0; i < rows_b; ++i) {
for (int j = 0; j < cols_b; ++j) {
scanf("%d", &matrix_b[i][j]);
}
}
// Check if matrices can be multiplied
if (cols_a == rows_b) {
printf("%d %d\n", rows_a, cols_b);
for (int i = 0; i < rows_a; ++i) {
for (int j = 0; j < cols_b; ++j) {
num = 0;
for (int k = 0; k < cols_a; ++k) {
num += matrix_a[i][k] * matrix_b[k][j];
}
if (j != cols_b - 1) {
printf("%d ", num);
} else {
printf("%d", num);
}
}
printf("\n");
}
} else {
printf("Error: %d != %d\n", cols_a, rows_b);
}
return 0;
}
L1-006 连续因子
此题要求找到一个正整数N的连续因子（例如，12 = 2*3*4），并输出最长的连续因子序列及其起始值。如果不存在连续因子（除N本身外），则输出N本身。
#include <stdio.h>
#include <math.h>
int main() {
int n;
scanf("%d", &n);
int max_len = 0;
int start_factor = 0;
int end_factor = 0;
// Iterate through possible starting factors from 2 up to sqrt(N)
for (int i = 2; i <= sqrt(n); ++i) {
int current_n = n;
int current_len = 0;
int current_start = 0;
// Check for a sequence starting from i
for (int j = i; current_n % j == 0; ++j) {
current_n /= j;
if (current_len == 0) {
current_start = j;
}
current_len++;
if (current_n == 1) break; // Fully factorized
}
// Update if a longer sequence is found
if (current_len > max_len) {
max_len = current_len;
start_factor = current_start;
end_factor = i + current_len - 1; // Calculate the end of the sequence
}
}
if (max_len > 0) {
printf("%d\n", max_len);
for (int i = start_factor; i <= end_factor; ++i) {
if (i != end_factor) {
printf("%d*", i);
} else {
printf("%d", i);
}
}
printf("\n");
} else {
// If no sequence found (other than N itself), print N
printf("1\n"); // Length is 1
printf("%d\n", n); // The number itself
}
return 0;
}
L1-009 N个数求和
本题要求计算N个分数之和，并以最简分数形式输出。需要处理分数的加法，包括通分和约分。
#include <stdio.h>
#include <stdlib.h> // For abs()
// Function to calculate the Greatest Common Divisor (GCD)
int gcd(int a, int b) {
a = abs(a);
b = abs(b);
while (b) {
a %= b;
int temp = a;
a = b;
b = temp;
}
return a;
}
int main() {
int n;
scanf("%d", &n);
int total_numerator = 0;
int total_denominator = 1;
for (int i = 0; i < n; ++i) {
int current_numerator, current_denominator;
scanf("%d/%d", ¤t_numerator, ¤t_denominator);
// Add the current fraction to the total sum
// Formula: (a/b) + (c/d) = (ad + bc) / bd
total_numerator = total_numerator * current_denominator + current_numerator * total_denominator;
total_denominator = total_denominator * current_denominator;
// Simplify the resulting fraction
int common_divisor = gcd(total_numerator, total_denominator);
total_numerator /= common_divisor;
total_denominator /= common_divisor;
}
// Format the output
int integer_part = total_numerator / total_denominator;
int remaining_numerator = total_numerator % total_denominator;
if (integer_part != 0) {
printf("%d", integer_part);
if (remaining_numerator != 0) {
printf(" "); // Space between integer and fractional part
}
}
if (remaining_numerator != 0) {
printf("%d/%d", remaining_numerator, total_denominator);
} else if (integer_part == 0) {
// If the result is 0 and there's no fractional part
printf("0");
}
printf("\n");
return 0;
}
L1-087 机工士姆斯塔迪奥
此题为一道模拟题，需要根据输入的指令（行操作或列操作）来计算最终有多少个单元格未被覆盖。关键在于准确记录被操作过的行和列，并利用集合思想计算未被覆盖的单元格总数。
#include <stdio.h>
#include <stdbool.h> // For bool type
int main() {
int n_rows, m_cols, q_operations;
scanf("%d %d %d", &n_rows, &m_cols, &q_operations);
bool row_is_covered[100005] = {false};
bool col_is_covered[100005] = {false};
int covered_row_count = 0;
int covered_col_count = 0;
for (int i = 0; i < q_operations; ++i) {
int op_type, index; // 0 for row, 1 for column
scanf("%d %d", &op_type, &index);
// Adjust index to be 0-based
index--;
if (op_type == 0) { // Row operation
if (!row_is_covered[index]) {
row_is_covered[index] = true;
covered_row_count++;
}
} else { // Column operation
if (!col_is_covered[index]) {
col_is_covered[index] = true;
covered_col_count++;
}
}
}
// Total cells = N * M
// Cells covered by row operations = covered_row_count * M
// Cells covered by column operations = covered_col_count * N
// Cells covered by both (intersection) = covered_row_count * covered_col_count
// Using the principle of inclusion-exclusion:
// Total covered = (covered_row_count * M) + (covered_col_count * N) - (covered_row_count * covered_col_count)
// Cells not covered = Total cells - Total covered
// Cells not covered = N * M - (covered_row_count * M + covered_col_count * N - covered_row_count * covered_col_count)
// This can be simplified:
// Cells not covered = (N - covered_row_count) * (M - covered_col_count)
int uncovered_cells = (n_rows - covered_row_count) * (m_cols - covered_col_count);
printf("%d\n", uncovered_cells);
return 0;
}
B3927 \[GESP202312 四级\] 小杨的字典
该题要求实现一个简单的英文字典翻译功能。需要将输入的A-B词对存储起来，然后根据输入的句子，将句子中的单词替换为对应的B词，如果找不到则替换为"UNK"。
#include <stdio.h>
#include <string.h>
char dict_a[105][15] = {0};
char dict_b[105][15] = {0};
char sentence[1000];
// Function to translate a word starting at index `start_idx` in `sentence`
// `num_pairs` is the number of dictionary entries
// Returns the index in `sentence` after the translated word
int translate_word(int start_idx, int num_pairs) {
int word_len = 0;
// Find the end of the current word
while (sentence[start_idx + word_len] >= 'a' && sentence[start_idx + word_len] <= 'z') {
word_len++;
}
// Search for the word in dict_a
for (int j = 0; j < num_pairs; ++j) {
// Check if lengths match
if (word_len == strlen(dict_a[j])) {
int match = 1;
// Compare characters
for (int k = 0; k < word_len; ++k) {
if (sentence[start_idx + k] != dict_a[j][k]) {
match = 0;
break;
}
}
// If match found, print dict_b and return the index after the word
if (match) {
printf("%s", dict_b[j]);
return start_idx + word_len - 1; // Return index of last char of word
}
}
}
// If no match found, print "UNK"
printf("UNK");
return start_idx + word_len - 1; // Return index of last char of word
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%s", dict_a[i]);
scanf("%s", dict_b[i]);
}
scanf("%s", sentence);
int len = strlen(sentence);
for (int i = 0; i < len; ++i) {
// If it's not a lowercase letter, print it directly
if (sentence[i] < 'a' || sentence[i] > 'z') {
printf("%c", sentence[i]);
} else {
// If it's a letter, translate the word starting from here
i = translate_word(i, n); // Update i to the end of the translated word
}
}
printf("\n");
return 0;
}
B3939 \[GESP样题 四级\] 绝对素数
此题要求找出一定范围内（A到B）的"绝对素数"。绝对素数是指一个数本身是素数，并且将其数字颠倒后得到的数也是素数。
#include <stdio.h>
#include <math.h>
// Function to check if a number is prime
int is_prime(int num) {
if (num <= 1) {
return 0; // Not prime
}
for (int i = 2; i * i <= num; ++i) {
if (num % i == 0) {
return 0; // Not prime
}
}
return 1; // Prime
}
// Function to reverse a number
int reverse_number(int num) {
int reversed_num = 0;
while (num > 0) {
reversed_num = reversed_num * 10 + num % 10;
num /= 10;
}
return reversed_num;
}
int main() {
int start_range, end_range;
scanf("%d %d", &start_range, &end_range);
for (int i = start_range; i <= end_range; ++i) {
if (is_prime(i)) {
int reversed_i = reverse_number(i);
if (is_prime(reversed_i)) {
printf("%d\n", i);
}
}
}
return 0;
}
B3940 \[GESP样题 四级\] 填幻方
本题要求生成一个奇数阶幻方。经典的算法是"暹罗算法"（Siamese method）。该算法的规则是：从第一行的中间列开始填1，然后每次将数字往右上角移动一格；如果右上角超出边界，则绕到另一边；如果右上角已被占用，则向下移动一格。
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int magic_square[25][25] = {0};
int current_num = 1;
int row = 0;
int col = n / 2; // Start at the middle of the first row
while (current_num <= (n * n)) {
magic_square[row][col] = current_num;
current_num++;
int next_row = (row - 1 + n) % n; // Move diagonally up-right
int next_col = (col + 1) % n;
if (magic_square[next_row][next_col] == 0) { // If the next position is empty
row = next_row;
col = next_col;
} else { // If the next position is occupied, move down
row = (row + 1) % n;
}
}
// Print the magic square
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
printf("%d", magic_square[i][j]);
if (j != n - 1) {
printf(" ");
}
}
printf("\n");
}
return 0;
}
B3850 \[GESP202306 四级\] 幸运数
此题定义了一种"幸运数"的判定规则。需要对输入的数字的各位进行特殊处理：奇数位上的数字乘以7，若结果大于9则对其各位数字求和（循环），然后累加；偶数位上的数字直接累加。最后判断累加和能否被8整除。
#include <stdio.h>
// Function to check if a number is a "lucky number" based on the given rules
int is_lucky_number(long long int num) {
int sum_of_digits = 0;
int position = 1; // 1-based index for digit position (from right)
while (num > 0) {
int digit = num % 10;
num /= 10;
if (position % 2 != 0) { // Odd position (from the right)
int processed_digit = digit * 7;
// If processed_digit is still greater than 9, sum its digits repeatedly
while (processed_digit > 9) {
processed_digit = (processed_digit % 10) + (processed_digit / 10);
}
sum_of_digits += processed_digit;
} else { // Even position
sum_of_digits += digit;
}
position++;
}
// Check if the sum of digits is divisible by 8
return (sum_of_digits % 8 == 0);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
long long int number;
scanf("%lld", &number);
if (is_lucky_number(number)) {
printf("T\n");
} else {
printf("F\n");
}
}
return 0;
}
B3870 \[GESP202309 四级\] 变长编码
本题要求实现一种变长编码。将输入的十进制数转换为二进制，然后按每7位一组进行编码。最后7位为一组，如果不是最后一个组，则在组内最高位添加'1'；最后一个组最高位添加'0'。然后将每组7位（加上可能的前导1）的二进制数转换为十六进制表示（两位）。
#include <stdio.h>
// Helper function to convert a digit (0-15) to its hex character representation
char to_hex_char(int digit) {
if (digit < 10) {
return '0' + digit;
} else {
return 'A' + (digit - 10);
}
}
// Function to convert a number to its binary representation in an array `bits`
// Returns the number of bits used.
int to_binary(long long int num, int bits[]) {
int len = 0;
if (num == 0) {
bits[0] = 0;
return 1;
}
while (num > 0) {
bits[len++] = num % 2;
num /= 2;
}
return len;
}
int main() {
long long int num;
scanf("%lld", &num);
int binary_bits[100] = {0};
int len = to_binary(num, binary_bits);
// Pad with leading zeros so that length is a multiple of 7
while (len % 7 != 0) {
binary_bits[len++] = 0;
}
for (int i = 0; i < len; i += 7) {
int group_value = 0;
// Construct the 7-bit group value
for (int j = 6; j >= 0; --j) {
group_value = (group_value * 2) + binary_bits[i + j];
}
// Add the continuation bit if it's not the last group
if (i + 7 < len) {
group_value += 128; // Set the 8th bit (MSB) to 1
}
// Convert the 8-bit value (or 7-bit for the last group) to two hex characters
printf("%c%c ", to_hex_char(group_value / 16), to_hex_char(group_value % 16));
}
printf("\n"); // Ensure a newline at the end
return 0;
}
B3851 \[GESP202306 四级\] 图像压缩
该题要求对输入的十六进制图像数据进行压缩。首先统计每个灰阶（00-FF）出现的次数，然后将出现次数最多的前16种灰阶作为新的调色板。最后，将原图像中的每个像素替换为调色板中最接近的灰阶的索引。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
typedef struct {
int color_value; // The 0-255 gray scale value
int count; // How many times this color appears
} gray_scale_info;
// Function to convert a hexadecimal character to its integer value
int hex_char_to_int(char c) {
if (c >= '0' && c <= '9') return c - '0';
else return c - 'A' + 10;
}
// Function to convert an integer (0-15) to its hexadecimal character
char int_to_hex_char(int x) {
if (x < 10) return '0' + x;
else return 'A' + (x - 10);
}
// Comparison function for qsort: sort by count (descending), then by color_value (ascending)
int compare_gray_scales(const void *a, const void *b) {
gray_scale_info *info_a = (gray_scale_info *)a;
gray_scale_info *info_b = (gray_scale_info *)b;
if (info_b->count != info_a->count) {
return info_b->count - info_a->count; // Sort by count descending
} else {
return info_a->color_value - info_b->color_value; // Sort by color_value ascending
}
}
// Absolute value function
int abs_val(int x) {
return (x < 0) ? -x : x;
}
gray_scale_info gray_scales[256]; // Array to store count for each 0-255 gray scale
int main() {
int n_lines;
scanf("%d", &n_lines);
// Initialize gray_scales array
for (int i = 0; i < 256; ++i) {
gray_scales[i].color_value = i;
gray_scales[i].count = 0;
}
char hex_line[50][50] = {0}; // Store the input hex strings
int line_len = 0;
for (int i = 0; i < n_lines; ++i) {
scanf("%s", hex_line[i]);
line_len = strlen(hex_line[i]);
for (int j = 0; j < line_len; j += 2) {
int color_val = hex_char_to_int(hex_line[i][j]) * 16 + hex_char_to_int(hex_line[i][j + 1]);
gray_scales[color_val].count++;
}
}
// Sort the gray scales based on count and color value
qsort(gray_scales, 256, sizeof(gray_scale_info), compare_gray_scales);
// Print the new color palette (first 16 gray scales)
for (int i = 0; i < 16; ++i) {
printf("%c%c", int_to_hex_char(gray_scales[i].color_value / 16), int_to_hex_char(gray_scales[i].color_value % 16));
}
printf("\n");
// Reconstruct the image using the new palette
for (int i = 0; i < n_lines; ++i) {
for (int j = 0; j < line_len; j += 2) {
int original_color_val = hex_char_to_int(hex_line[i][j]) * 16 + hex_char_to_int(hex_line[i][j + 1]);
int best_match_index = 0; // Index in gray_scales array for the closest color
int min_diff = abs_val(original_color_val - gray_scales[0].color_value);
// Find the closest color in the new palette
for (int k = 1; k < 16; ++k) {
int current_diff = abs_val(original_color_val - gray_scales[k].color_value);
if (current_diff < min_diff) {
min_diff = current_diff;
best_match_index = k;
}
}
// Output the index of the closest color in the new palette as a hex digit
printf("%c", int_to_hex_char(best_match_index));
}
printf("\n");
}
return 0;
}
B3869 \[GESP202309 四级\] 进制转换
此题要求实现一个通用的进制转换功能。输入一个数字的表示形式（在一个给定的进制K下），将其转换为十进制。
#include <stdio.h>
#include <string.h>
#include <math.h> // For pow
// Function to convert a character digit to its integer value in a given base
long long int char_to_value(char c, int base) {
int digit_value;
if (c >= '0' && c <= '9') {
digit_value = c - '0';
} else { // Assuming characters 'A'-'Z' for bases > 10
digit_value = c - 'A' + 10;
}
// Check if the digit value is valid for the given base
if (digit_value >= base) {
// Handle error: invalid digit for base
return -1; // Indicate error
}
return digit_value;
}
int main() {
int n; // Number of test cases
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
int base_k;
char number_str[15];
scanf("%d %s", &base_k, number_str);
long long int decimal_value = 0;
int len = strlen(number_str);
for (int j = 0; j < len; ++j) {
long long int digit_val = char_to_value(number_str[j], base_k);
if (digit_val == -1) {
// Handle invalid input case if necessary, though problem assumes valid input
break;
}
// Add the value of the digit considering its position (power of base_k)
decimal_value += digit_val * (long long int)pow(base_k, len - 1 - j);
}
printf("%lld\n", decimal_value);
}
return 0;
}
B3928 \[GESP202312 四级\] 田忌赛马
这是一道经典的田忌赛马问题。将双方的马匹按速度排序，然后采用贪心策略：让己方最快的马去挑战对方最快的马，如果能赢则赢一场；否则，己方最快的马去挑战对方最慢的马，以求最小损失（或最大化胜利）。
#include <stdio.h>
#include <stdlib.h>
int my_horses[50005];
int your_horses[50005];
// Comparison function for qsort
int compare_ints(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int main() {
int n;
scanf("%d", &n);
// Read and sort my horses
for (int i = 0; i < n; ++i) {
scanf("%d", &my_horses[i]);
}
qsort(my_horses, n, sizeof(int), compare_ints);
// Read and sort your horses
for (int i = 0; i < n; ++i) {
scanf("%d", &your_horses[i]);
}
qsort(your_horses, n, sizeof(int), compare_ints);
int wins = 0;
int my_fastest_idx = n - 1;
int your_fastest_idx = n - 1;
int your_slowest_idx = 0;
// Greedy approach: try to win with the fastest horses first
while (my_fastest_idx >= 0) {
if (my_horses[my_fastest_idx] > your_horses[your_fastest_idx]) {
// My fastest horse beats their fastest horse
wins++;
my_fastest_idx--;
your_fastest_idx--;
} else if (my_horses[my_fastest_idx] < your_horses[your_slowest_idx]) {
// My fastest horse loses to their slowest horse. Sacrifice my slowest.
// This scenario implies we lose this round, but it might be necessary
// to save faster horses for other matchups.
// The problem asks for maximum wins, so if my fastest can't beat their fastest,
// it's best to make it beat their slowest if possible.
// However, the optimal strategy is to only consider winning matches.
// If my fastest cannot beat their fastest, consider if my slowest can beat their slowest.
// The provided solution uses a simpler greedy approach focusing on wins.
// Let's stick to the logic of prioritizing wins. If my fastest can't beat their fastest,
// maybe my slowest can beat their slowest.
// Simplified greedy: If my fastest can beat their fastest, do it. Otherwise,
// sacrifice my slowest to their fastest to minimize loss.
// More correct greedy: compare my fastest vs their fastest, my slowest vs their slowest.
// Let's refine the strategy:
// Try to win: my fastest vs your fastest
// If cannot win: my slowest vs your fastest (to sacrifice)
// The provided example solution actually iterates from fastest to slowest,
// trying to win. If my current horse is faster than your current fastest, win.
// If my current horse is slower than your current fastest, it means this horse
// cannot win against the current fastest opponent. In this case, we should
// sacrifice our slowest horse against their fastest opponent.
if (my_horses[my_fastest_idx] <= your_horses[your_fastest_idx]) {
// My fastest cannot beat their fastest.
// Let my slowest horse fight their fastest horse. This is a guaranteed loss for this round,
// but might save my faster horses for other matchups.
// However, the goal is maximum wins. If my fastest can't beat their fastest,
// maybe it can beat their slowest.
// The standard greedy approach involves comparing:
// 1. My fastest vs Your fastest: If win, use both, increment wins.
// 2. If not win: My slowest vs Your fastest: Use both (lose this round), decrement wins (effectively).
// This logic is a bit tricky. Let's follow a common successful greedy strategy:
// Iterate through my horses from fastest to slowest. For each of my horses,
// find the weakest opponent horse it can beat.
// Let's use two pointers for my horses (fastest_my, slowest_my)
// and two for yours (fastest_your, slowest_your).
// Strategy:
// If my fastest > your fastest: win, my_fastest--, your_fastest--
// Else if my fastest < your slowest: lose, my_fastest--, your_slowest-- (lose)
// Else: my slowest vs your fastest. (This is a tricky case, often implies losing)
// A simpler, often correct greedy strategy:
// Iterate my horses from fastest to slowest.
// Try to beat opponent's fastest horse.
// If I win: use both horses, increment wins.
// If I lose: sacrifice my slowest horse against opponent's fastest horse.
// Let's re-implement using two pointers for both arrays, focusing on wins.
// my_fastest_idx, your_fastest_idx, your_slowest_idx
// If my current fastest cannot beat their current fastest:
// This means my_horses[my_fastest_idx] <= your_horses[your_fastest_idx].
// To maximize wins, we should try to make my horse beat their *slowest* horse if possible.
// If my fastest horse cannot beat their fastest horse, it implies it might be able to beat their slowest.
// If my_horses[my_fastest_idx] < your_horses[your_slowest_idx], then even my fastest horse
// cannot beat their slowest horse. This implies a loss for this matchup.
// In this losing scenario, we sacrifice our slowest horse against their fastest horse.
// The problem is to maximize wins.
// Let's try the strategy from common solutions:
// Iterate from my fastest horse.
// If my horse > their fastest horse: WIN, use both, increment wins.
// If my horse <= their fastest horse: Sacrifice my slowest horse against their fastest.
// This essentially means my fastest horse is matched against their fastest, and it loses.
// To make progress, we consume my slowest and their fastest.
wins--; // This round is a loss, effectively.
my_fastest_idx--; // Use my slowest horse for this matchup
your_fastest_idx--; // Use their fastest horse for this matchup
}
} else { // my_horses[my_fastest_idx] == your_horses[your_fastest_idx]
// If speeds are equal, it's effectively a loss for winning strategy.
wins--;
my_fastest_idx--;
your_fastest_idx--;
}
// Correction: the initial loop structure `for(i=n-1;i>=0;--i)` suggests iterating my horses.
// `j` should be tracking opponent's horses.
// Let's use the standard two-pointer approach.
}
// Standard Greedy Approach:
int wins_count = 0;
int my_ptr_fast = n - 1;
int my_ptr_slow = 0;
int your_ptr_fast = n - 1;
int your_ptr_slow = 0;
while (my_ptr_slow <= my_ptr_fast) {
if (my_horses[my_ptr_fast] > your_horses[your_ptr_fast]) {
// My fastest beats their fastest
wins_count++;
my_ptr_fast--;
your_ptr_fast--;
} else if (my_horses[my_ptr_fast] < your_horses[your_ptr_slow]) {
// My fastest horse cannot beat their fastest horse.
// Sacrifice my slowest horse against their fastest horse (guaranteed loss).
// This is to free up faster horses for potentially winnable matches.
my_ptr_slow++;
your_ptr_fast--;
} else {
// my_horses[my_ptr_fast] == your_horses[your_ptr_fast]
// This is also a losing match for maximizing wins if they are equal.
// Sacrifice my slowest horse against their fastest horse.
my_ptr_slow++;
your_ptr_fast--;
}
}
printf("%d\n", wins_count);
return 0;
}
L1-095 分寝室
此题要求在满足一定条件下，使得女生宿舍和男生宿舍人数差最小。需要枚举所有可能的宿舍分配方案，并计算人数差，找到最小值。
#include <stdio.h>
#include <stdlib.h> // For abs()
int main() {
int total_girls, total_boys, total_rooms;
scanf("%d %d %d", &total_girls, &total_boys, &total_rooms);
int min_diff = 1000000000; // Initialize with a very large value
int best_girls_rooms = -1;
int best_boys_rooms = -1;
// Iterate through all possible numbers of girls' rooms (from 0 to total_rooms)
for (int girls_rooms = 0; girls_rooms <= total_rooms; ++girls_rooms) {
int boys_rooms = total_rooms - girls_rooms;
// Check if it's possible to assign students to these rooms
// Condition: Each room must have at least one student, and no room is empty.
// This means girls_rooms * avg_girls_per_room = total_girls
// and boys_rooms * avg_boys_per_room = total_boys
// For simplification, the problem implies that the total number of students
// must be distributed such that each room gets at least one student.
// A simpler interpretation might be: if the number of rooms allows for it.
// Let's assume the constraint is about having enough students for the rooms.
// If there are 'g' girls' rooms and 'b' boys' rooms, and total students N = G + B.
// The problem states "n0/i!=1" and "n1/(n-i)!=1", meaning each room must have at least 2 students.
// This is a crucial interpretation. Let's re-evaluate based on that.
// Re-interpreting:
// If `girls_rooms` are for girls, then `total_girls` must be divisible by `girls_rooms`,
// and each room must have >= 2 girls.
// If `boys_rooms` are for boys, then `total_boys` must be divisible by `boys_rooms`,
// and each room must have >= 2 boys.
if (girls_rooms > 0 && total_girls % girls_rooms == 0 && total_girls / girls_rooms >= 2) {
if (boys_rooms > 0 && total_boys % boys_rooms == 0 && total_boys / boys_rooms >= 2) {
// Possible valid distribution
int girls_per_room = total_girls / girls_rooms;
int boys_per_room = total_boys / boys_rooms;
int diff = abs(girls_per_room - boys_per_room);
if (diff < min_diff) {
min_diff = diff;
best_girls_rooms = girls_rooms;
best_boys_rooms = boys_rooms;
}
}
}
// Edge case: What if one gender has 0 students but rooms are assigned?
// Or what if total_rooms = 1? The problem structure implies distribution.
// The original code logic seemed to check divisibility and avoid single-student rooms.
// Let's stick to the original code's apparent logic for "at least two students per room".
}
// Recalculating based on the provided C code's apparent logic:
// n0 = total_girls, n1 = total_boys, n = total_rooms
// i = girls_rooms, n-i = boys_rooms
// Condition: n0 % i == 0 AND n0 / i != 1 AND n1 % (n-i) == 0 AND n1 / (n-i) != 1
min_diff = 1000000000; // Reset for original logic interpretation
best_girls_rooms = -1;
best_boys_rooms = -1;
for (int i = 1; i < total_rooms; ++i) { // i is number of girls' rooms, so must be > 0 and < total_rooms
int num_girls_in_room = total_girls / i;
int num_boys_in_room = total_boys / (total_rooms - i);
if (total_girls % i == 0 && num_girls_in_room != 1 &&
total_boys % (total_rooms - i) == 0 && num_boys_in_room != 1) {
int diff = abs(num_girls_in_room - num_boys_in_room);
if (diff < min_diff) {
min_diff = diff;
best_girls_rooms = i;
best_boys_rooms = total_rooms - i;
}
}
}
if (best_girls_rooms != -1) { // If a solution was found
printf("%d %d\n", best_girls_rooms, best_boys_rooms);
} else {
printf("No Solution\n");
}
return 0;
}
L1-082 种钻石
这是一道非常简单的题目，只需要根据给定的总容量和每单位容量的钻石数量，计算最多能种多少钻石。
#include <stdio.h>
int main() {
int capacity, diamonds_per_unit;
scanf("%d %d", &capacity, &diamonds_per_unit);
// Integer division automatically handles finding the maximum whole number of diamonds
printf("%d\n", capacity / diamonds_per_unit);
return 0;
}
L1-093 猜帽子游戏
该题模拟一个猜帽子的游戏。有多轮游戏，每轮玩家需要猜自己头上的帽子颜色（用数字表示）。系统会给出提示：如果猜错，则"Ai Ya"；如果猜对，则"Da Jiang!!!"。需要处理玩家全猜错（"Ai Ya"）、部分猜对（"Da Jiang!!!"）以及全猜对（"Ai Ya"）的情况。
#include <stdio.h>
int main() {
int n_players;
scanf("%d", &n_players);
int hats[105] = {0}; // Stores the correct hat color for each player
for (int i = 0; i < n_players; ++i) {
scanf("%d", &hats[i]);
}
int k_rounds;
scanf("%d", &k_rounds);
for (int round = 0; round < k_rounds; ++round) {
int answers[105] = {0}; // Stores the player's guesses for this round
int zero_guesses = 0; // Count of players who guessed 0 (pass/unknown)
int correct_guesses = 0; // Count of players who guessed correctly
int wrong_guess_made = 0; // Flag if any player guessed incorrectly
for (int i = 0; i < n_players; ++i) {
scanf("%d", &answers[i]);
if (answers[i] == 0) {
zero_guesses++;
} else if (answers[i] == hats[i]) {
correct_guesses++;
} else {
wrong_guess_made = 1;
}
}
if (wrong_guess_made) {
printf("Ai Ya\n");
} else if (zero_guesses == n_players) {
// All players guessed 0
printf("Ai Ya\n");
} else if (correct_guesses >= 1) {
// At least one correct guess, and no incorrect guesses
printf("Da Jiang!!!\n");
}
// Note: The logic here assumes that if there are correct guesses and no wrong guesses,
// and not all are zero, it's "Da Jiang!!!". If all guesses were wrong, "Ai Ya".
// If some are zero and some are correct (and no wrong), it's "Da Jiang!!!".
}
return 0;
}
L1-094 剪切粘贴
该题要求实现字符串的剪切和粘贴操作。需要定义函数来执行这些操作，并根据给定的参数找到目标位置。
#include <stdio.h>
#include <string.h>
// Cuts a substring from `str` from index `l` to `r` (1-based) and stores it in `cut`.
// Modifies `str` in place.
void cut_string(int l, int r, char *str, char *cut) {
int len = strlen(str);
int cut_len = r - l + 1;
// Copy the substring to `cut`
strncpy(cut, str + l - 1, cut_len);
cut[cut_len] = '\0'; // Null-terminate `cut`
// Shift the remaining part of `str` to the left
memmove(str + l - 1, str + r, len - r + 1); // +1 to include the null terminator
}
// Finds the position in `str` where `front` and `end` would match.
// Returns the index *after* `front` where `end` should start.
// If no match is found, returns the position after the last character.
int find_paste_position(const char *str, const char *front, const char *end) {
int len_str = strlen(str);
int len_front = strlen(front);
int len_end = strlen(end);
// Iterate through `str` looking for potential start of `front`
for (int i = 0; i <= len_str; ++i) { // i is the potential insertion point
// Check if `front` matches the string starting from `i - len_front`
int front_match = 1;
if (i >= len_front) { // Ensure there's enough space for `front`
for (int k = 0; k < len_front; ++k) {
if (str[i - len_front + k] != front[k]) {
front_match = 0;
break;
}
}
} else {
front_match = 0; // Not enough characters before insertion point for `front`
}
// Check if `end` matches the string starting from `i`
int end_match = 1;
if (i + len_end <= len_str) { // Ensure there's enough space for `end`
for (int k = 0; k < len_end; ++k) {
if (str[i + k] != end[k]) {
end_match = 0;
break;
}
}
} else {
end_match = 0; // Not enough characters after insertion point for `end`
}
if (front_match && end_match) {
return i; // Found the insertion point (after `front`, before `end`)
}
}
// If no specific position is found, return the end of the string
return len_str;
}
// Pastes the `cut` string into `str` at index `x` (0-based).
// Modifies `str` in place.
void paste_string(int x, char *str, const char *cut) {
int len_str = strlen(str);
int len_cut = strlen(cut);
// Shift the original string to make space for `cut`
memmove(str + x + len_cut, str + x, len_str - x + 1); // +1 for null terminator
// Copy `cut` into the space created
memcpy(str + x, cut, len_cut);
}
int main() {
char str[215] = {0};
int n_operations;
scanf("%s", str);
scanf("%d", &n_operations);
while (n_operations--) {
int l, r;
char front[10] = {0};
char end[10] = {0};
char cut_buffer[205] = {0};
scanf("%d %d %s %s", &l, &r, front, end);
// Perform cut operation
cut_string(l, r, str, cut_buffer);
// Find paste position
int paste_pos = find_paste_position(str, front, end);
// Perform paste operation
paste_string(paste_pos, str, cut_buffer);
}
printf("%s\n", str);
return 0;
}
L1-047 装睡
该题要求根据输入的姓名、身高和体重，判断哪些人"没装睡"。"没装睡"的标准是身高在150-200cm之间，体重在50-70kg之间。需要处理输入格式，并输出不符合条件的人的姓名。
#include <stdio.h>
int main() {
int n_people;
scanf("%d", &n_people);
for (int i = 0; i < n_people; ++i) {
char name[10] = {0};
int height, weight;
scanf("%s %d %d", name, &height, &weight);
// Check if the person is "not pretending to sleep" (i.e., meets the criteria)
// The problem asks to print names of people who are NOT pretending to sleep,
// which means they ARE within the valid ranges.
// However, the typical interpretation of such problems is to print those who DON'T meet the criteria.
// Let's assume the goal is to print names of people who FAIL the condition (are "pretending to sleep").
// If the condition is `height < 150 || height > 200 || weight < 50 || weight > 70`,
// then they fail the "not pretending" criteria.
// The provided incorrect code snippet prints if `x < 15 || x > 20 || y < 50 || y > 70`.
// This seems to be a misinterpretation of height/weight ranges.
// Assuming the problem statement's implied ranges are correct:
// Height: 150 <= height <= 200
// Weight: 50 <= weight <= 70
// Let's follow the logic that triggers printing: If they DON'T meet the criteria.
if (height < 150 || height > 200 || weight < 50 || weight > 70) {
// This person does NOT meet the criteria to be awake.
// Thus, they are either pretending to sleep or outside the expected ranges.
// The problem asks to print those who are "not pretending to sleep".
// This implies we should print those who ARE pretending to sleep (i.e., fail the criteria).
printf("%s\n", name);
}
}
return 0;
}
L1-033 出生年
本题要求找到一个年份Y，使得Y与给定年份y的各位数字组成的集合相同，并且Y尽量大。如果y本身满足条件，则y是答案。否则，从y+1开始递增查找。
#include <stdio.h>
// Function to count the number of distinct digits in a year
int count_distinct_digits(int year) {
int digits[10] = {0}; // Array to mark presence of digits 0-9
int count = 0;
// Handle year 0 specifically if needed, though problem implies positive years
if (year == 0) return 1;
while (year > 0) {
int digit = year % 10;
if (digits[digit] == 0) {
digits[digit] = 1; // Mark digit as seen
count++;
}
year /= 10;
}
return count;
}
int main() {
int start_year, required_distinct_digits;
scanf("%d %d", &start_year, &required_distinct_digits);
int current_year = start_year;
int distinct_digit_count = count_distinct_digits(current_year);
// Keep searching until the number of distinct digits matches
while (distinct_digit_count != required_distinct_digits) {
current_year++;
distinct_digit_count = count_distinct_digits(current_year);
}
// Calculate how many years we advanced
int years_advanced = current_year - start_year;
printf("%d %04d\n", years_advanced, current_year); // %04d ensures leading zeros for the year
return 0;
}
L1-059 敲笨钟
该题没有提供具体代码，但根据题目名称"敲笨钟"，可能涉及到根据时间输出"Dang"的次数，类似于L1-018。需要根据输入的时间（可能为24小时制），计算敲钟的次数。
L1-083 谁能进图书馆
此题没有提供具体代码，但题目名称"谁能进图书馆"暗示可能与人数限制或排队问题有关。可能需要计算在满足特定条件下能够进入图书馆的人数。
