分类 算法竞赛 下的文章

计算机的构成

作者为蒟蒻高中牲，若有不妥之处请多多包含，并望于评论区指正，不胜感激！

目录：

计算机由软件和硬件构成。

-　硬件是指看得见摸得着的各种电子元器件。如主机、键盘、鼠标等。 -　软件看不见摸不着，但在逻辑上，我们确实可以感知到它的存在，它由人们事先编制的具有某种功能的程序组成。比如操作系统、编程语言等。

计算机的软件通常又分为：系统软件和应用软件。

  • 系统软件：又称为系统程序，主要用来管理整个计算机系统，监视服务，使系统资源得到合理调度。它包括：操作系统、语言处理程序、数据库管理系统、网络软件、服务程序等。
  • 应用软件：又称为应用程序，它是用户根据需要事先编制的程序。比如 QQ、微信等。

硬件系统

在冯 · 诺依曼体系中，计算机硬件系统是由运算器、控制器、存储器、输入设备和输出设备五大部件组成的。

随着计算机技术的发展，计算机硬件系统的组织结构发生了许多重大的变化，如运算器和控制器已组合成一个整体，称为中央处理器（Central Processing Unit，CPU）。

存储器已成为多级存储器体系，包含主存、高速缓存和外存三个层次。

软件系统

软件类别：系统软件和应用软件。

  • 系统软件：又称为系统程序，主要用来管理整个计算机系统，监视服务，使系统资源得到合理调度。它包括：操作系统、语言处理程序、数据库管理系统、网络软件、服务程序等。
  • 应用软件：又称为应用程序，它是用户根据需要事先编制的程序。比如 QQ、微信等。

题目传送门

目录：

这是一道我弟拿给我做题目，本来想着普及−应该挺简单的，结果翻车了

题目解读

本题要求我们找出给定区间内的所有“回文质数”1。我一看就想着：先筛质数，再判断是不是回文数~~，结果大意失荆州——开了一个占用4G内存的prime[100000000]~~于是我终于注意到了题目中的提示：

说明/提示

Hint 1: Generate the palindromes and see if they are prime.

提示 1: 找出所有的回文数再判断它们是不是质数（素数）.

Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.

提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。

题目翻译来自NOCOW。

USACO Training Section 1.5

产生长度为 5 的回文数：

for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
    for (d2 = 0; d2 <= 9; d2++) {
        for (d3 = 0; d3 <= 9; d3++) {
          palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
        }
    }
}

于是我便把提示里的代码复制了几份～

AC 代码

#include <bits/stdc++.h>
using namespace std;

// 判断一个数是否为质数
bool isPrime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

vector<int> palindromes;

int main() {
    int st, ed;
    scanf("%d%d", &st, &ed);
    
    // 生成所有可能的回文数
    
    // 1位回文数
    for (int i = 1; i <= 9; i++) {
        palindromes.push_back(i);
    }
    // 偶数位回文数(除了11)都能被11整除，不是回文数
    // 2位回文数
    palindromes.push_back(11);
    
    // 3位回文数
    for (int i = 1; i <= 9; i += 2) { // 只考虑奇数开头，偶数开头的必不是质数
        for (int j = 0; j <= 9; j++) {
            palindromes.push_back(i * 101 + j * 10); // iji形式
        }
    }
    
    // 5位回文数
    for (int i = 1; i <= 9; i += 2) { 
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k <= 9; k++) {
                palindromes.push_back(i * 10001 + j * 1010 + k * 100); // ijkji形式
            }
        }
    }
    
    // 7位回文数
    for (int i = 1; i <= 9; i += 2) { 
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k <= 9; k++) {
                for (int l = 0; l <= 9; l++) {
                    palindromes.push_back(i * 1000001 + j * 100010 + k * 10100 + l * 1000); // ijklkji形式
                }
            }
        }
    }
    
    // 9位回文数（虽然超出了1亿，但为了完整性）
    for (int i = 1; i <= 9; i += 2) { 
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k <= 9; k++) {
                for (int l = 0; l <= 9; l++) {
                    for (int m = 0; m <= 9; m++) {
                        int palindrome = i * 100000001 + j * 10000010 + k * 1000100 + l * 100010 + m * 10000;
                        if (palindrome <= 100000000) { // 只添加不超过1亿的
                            palindromes.push_back(palindrome);
                        }
                    }
                }
            }
        }
    }
    
    // 排序
    sort(palindromes.begin(), palindromes.end());
    
    // 遍历回文数数组，找出其中的质数并输出
    for (int palindrome : palindromes) {
        if (palindrome > ed) break;
        if (palindrome >= st && isPrime(palindrome)) {
            printf("%d\n", palindrome);
        }
    }
    
    return 0;
}

Over!

  1. 即既是回文数又是质数的数 ↩