寻找素数对——杭电1262

杭电ACM试题分类枚举1002 10041013 1015 1017 1020 1022 1029 1031 1033 1034 1035 1036 1037 10391042 10471048 1049 1050 1057 1062 1063 1064 1070 1073 1075 1082 1083 10841088 11061107 1113 1117 1119 1128 1129 1144 1148 1157 1161 1170 1172 117711971200 1201 1202 1205 1209 1212（大数取模）1216 （链表）1218 1219 12251228 12291230 1234 1235 1236 1237 1239 1250 1256 1259 1262 1263 1265 12661276 1279 1282 1283 1287 1296 1302 1303 1304 1305 1306 1309 1311 1314搜索，递归求解1010 1016 1026 1043（双广）1044 （BFS+DFS） 1045 1067 1072 1104 1175 1180 11951208 1226 1238 1240 1241 1242 1258 1271 1312 1317动态规划1003 1024 1025 1028 1051 1058 1059 1069 1074 1078 1080 1081 1085 1087 1114 1158 1159 1160 1171 1176 1181 1203 1224 1227 1231 1244 1248 1253 1254 1283 1300数学，递推，规律1005 1006 1012 1014 1018 1019 1021 1023 1027 1030 1032 1038 1041 1046 1059 1060 1061 1065 1066 1071（微积分）1097 1098 1099 1100 1108 1110 1112 1124 1130 1131 1132 1134 1141 1143 1152 1155（物理题）1163 1165 1178 1194 1196（lowbit） 1210 1214 1200 1221 1223 1249 1261 1267 1273 1290 1291 1292 1294 1297 1313 1316数论1164 1211 1215 1222 1286 1299计算几何1086 1115 1147贪心1009 1052 1055 1257 并查集11981213 1232 1272线段树，离散化11991255图论最短路相关的问题1142 1162 1217 1301二分图问题1054 1068 1150 1151 1281其他1053 (huffman) 1102(MST) 1116 (欧拉回路)1233(MST) 1269 (强连通)数据结构1103 (堆+模拟)1166 (数状树组)1247 1251 1285 (Topol) 1298以下是详细介绍1002简单的大数1003 DP经典问题，最大连续子段和1004简单题1005找规律（循环点）1007经典问题，最近点对问题，用分治1008简单题1010搜索题，剪枝很关1009贪心1012简单题1013简单题（有个小陷阱）1014简单题1015可以看作搜索题吧1016经典的搜索1017简单数学题1018简单数学题1019简单数学题1020简单的字符串处理找规律的数学题数据结构的题（栈的应用）特殊的数（Catalan Number）经典DP,最大M 子段和经典DP,最长递增子序列（要用NLogN的方法过）搜索数学题（或用STL）经典问题，整数拆分，用母函数做简单题（一般方法容易超时）简单题，可用模拟过简单题简单题模拟题Candy Sharing Game模拟题简单题简单题，不是一般的简单简单题字符串处理简单题，排序简单题，用大数大数经典搜索题，八数码问题稍微有点麻烦的搜索题搜索题，可用匹配做简单题简单的大数简单字符串处理简单题贪心经典贪心，也可以用DP贪心贪心，关于Huffman编码二分匹配二分匹配简单题模拟题经典问题，丑数，DP经典问题，可以用母函数或DP （不针对题目优化都会超时）数学题数学题简单字符串处理模拟大数简单题1065简单题1066数学题，找规律1068经典二分匹配1069经典DP1070简单题1071简单数学题1072搜索1073字符串处理1074 DP1075字典树1076简单题1078DP1079博弈(DP)1080DP 1081经典DP1082简单题1083二分匹配1084简单题1085母函数1086简单几何题1087简单DP1088字符串处理1089~1096 （练习输入输出的8个题目）1097简单数学题1098数学题，注意找规律1099数学HrH1500DP1501DP1502DP or记忆化1503DP1504模拟1505DP1506DP15072分匹配1508记忆化容易点1509模拟1510 DP1511搜索可以过1512左偏树1513DP1514DP1515DFS1516DP1517博奕搜索DP （不确定）树状DP 数学题稳定婚姻DP 博弈博弈Maxflow博弈2分匹配简单题最大团差分约束Maxflow入门题KM Or > 小费用流差分约束差分约束博弈模拟加置换群的理论CODE可以短些，其实没必要。

Problem DescriptionCalculate A + B.InputEach line will contain two integers A and B. Process to end of file.OutputFor each case, output A + B in one line.Sample Input1 1Sample Output2#include<stdio.h>void main(){int a,b;while(scanf("%d %d",&a,&b)!=EOF){printf("%d\n",a+b);}}Problem DescriptionHey, welcome to HDOJ(Hangzhou Dianzi University Online Judge).In this problem, your task is to calculate SUM(n) = 1 + 2 + 3 + ... + n.InputThe input will consist of a series of integers n, one integer per line.OutputFor each case, output SUM(n) in one line, followed by a blank line. You may assume the result will be in the range of 32-bit signed integer.Sample Input1100Sample Output15050#include<stdio.h>void main(){int n,sum,i;while(scanf("%d",&n)!=EOF){sum=0;for( i=0;i<=n;i++)sum+=i;printf("%d\n\n",sum);}}Problem DescriptionI have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B.InputThe first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000.OutputFor each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line is the an equation "A + B = Sum", Sum means the result of A + B. Note there are some spaces int the equation. Output a blank line between two test cases.Sample Input21 2112233445566778899 998877665544332211Sample OutputCase 1:1 +2 = 3Case 2:112233445566778899 + 998877665544332211 = 1111111111111111110 #include<stdio.h>#include<string.h>int main(){char str1[1001], str2[1001];int t, i, len_str1, len_str2, len_max, num = 1, k;scanf("%d", &t);getchar();while(t--){int a[1001] = {0}, b[1001] = {0}, c[1001] = {0};scanf("%s", str1);len_str1 = strlen(str1);for(i = 0; i <= len_str1 - 1; ++i)a[i] = str1[len_str1 - 1 - i] - '0';scanf("%s",str2);len_str2 = strlen(str2);for(i = 0; i <= len_str2 - 1; ++i)b[i] = str2[len_str2 - 1 - i] - '0';if(len_str1 > len_str2)len_max = len_str1;elselen_max = len_str2;k = 0;for(i = 0; i <= len_max - 1; ++i){c[i] = (a[i] + b[i] + k) % 10;k = (a[i] + b[i] + k) / 10;}if(k != 0)c[len_max] = 1;printf("Case %d:\n", num);num++;printf("%s + %s = ", str1, str2);if(c[len_max] == 1)printf("1");for(i = len_max - 1; i >= 0; --i){printf("%d", c[i]);}printf("\n");if(t >= 1)printf("\n");}return 0;}Problem DescriptionGiven a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.InputThe first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).OutputFor each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.Sample Input25 6 -1 5 4 -77 0 6 -1 1 -6 7 -5Sample OutputCase 1:14 1 4Case 2:7 1 6注：最大子序列是要找出由数组成的一维数组中和最大的连续子序列。

2023杭电多校4题解【最新版】目录1.2023 杭电多校 4 题解概述2.第一题：编写一个计算两个日期之间相隔天数的程序3.第二题：编写一个检查字符串是否为回文字符串的程序4.第三题：编写一个求解数组中两个数之和等于目标值的程序5.第四题：编写一个判断两个矩阵是否相等的程序6.总结与建议正文一、2023 杭电多校 4 题解概述本文将介绍 2023 年杭州电子科技大学多校联合编程竞赛的第四题解。

题目包括四个编程题目，分别涉及到日期计算、字符串处理、数组操作和矩阵操作。

本文将逐一解析每个题目的解法。

二、第一题：编写一个计算两个日期之间相隔天数的程序这道题目要求编写一个程序，输入两个日期字符串，输出它们之间相隔的天数。

需要注意的是，日期的格式为 "yyyy-MM-dd"，且要求能处理跨年和跨月的情况。

我们可以使用 Python 的 datetime 库来处理日期对象，通过计算两个日期对象之间的差值来得出它们之间相隔的天数。

三、第二题：编写一个检查字符串是否为回文字符串的程序这道题目要求编写一个程序，输入一个字符串，输出该字符串是否为回文字符串。

回文字符串是指正序和倒序都相同的字符串，例如"abcdcba" 和 "level" 都是回文字符串。

我们可以使用双指针法，分别从字符串的两端向中间遍历，如果遇到不相等的字符，则说明该字符串不是回文字符串。

四、第三题：编写一个求解数组中两个数之和等于目标值的程序这道题目要求编写一个程序，输入一个整数数组、一个目标值和一个整数 k，输出数组中两个数之和等于目标值的那 k 对数。

我们可以使用哈希表来存储数组中的元素及其对应的索引，遍历数组，对于每个元素，如果哈希表中存在与其对应的元素，则输出这两对数；否则，将该元素及其索引存入哈希表。

五、第四题：编写一个判断两个矩阵是否相等的程序这道题目要求编写一个程序，输入两个二维数组，输出它们是否表示同一个矩阵。

杭电OJ：1089----1096（c++）（ACM⼊门第⼀步：所有的输⼊输出格式）1089:输⼊输出练习的A + B（I）问题描述您的任务是计算a + b。

太容易了？！当然！我专门为ACM初学者设计了这个问题。

您⼀定已经发现某些问题与此标题具有相同的名称，是的，所有这些问题都是出于相同的⽬的⽽设计的。

输⼊项输⼊将由⼀系列由空格隔开的整数对a和b组成，每⾏⼀对整数。

输出量对于每对输⼊整数a和b，应该在⼀⾏中输出a和b的总和，并且在输⼊中每⾏输出⼀⾏。

样本输⼊1 5 10 20样本输出6 30题解：#include<cstdio>#include<iostream>using namespace std;int main(){int a, b,sum;while(cin >> a >> b){sum = a+b;cout << sum << endl;}return 0;}1090：投⼊产出练习的A + B（II）问题描述您的任务是计算a + b。

输⼊项输⼊的第⼀⾏包含⼀个整数N，然后是N⾏。

每⾏由⼀对整数a和b组成，每对之间⽤空格隔开，每⾏⼀对整数。

输出量对于每对输⼊整数a和b，应该在⼀⾏中输出a和b的总和，并且在输⼊中每⾏输出⼀⾏。

样本输⼊2 1 5 10 20样本输出6 30题解：#include<cstdio>#include<iostream>using namespace std;int a,b,n,sum;cin >> n;while (n){cin >> a >> b;sum = a + b;cout << sum << endl;n--;}return 0;}1091：投⼊产出练习的A + B（III）问题描述您的任务是计算a + b。

数字逻辑电路课内仿真实验第六章Quartusll 原理图设计初步二、实验仪器: Quartusll 软件。

三、实验内容:6-1用Quartusll 库中的宏功能模块 74138和与非门实现指定逻辑函数按照6.3节和6.4节的流程，使用 Quartusll 完整图6-2电路的设计，包括：创建工程， 在原理图编辑窗中绘制此电路， 全程编译，对设计进行时序仿真， 根据仿真波形说明此电路一、实验目的: 初步了解学习使用 Quartusll 软件进行电路自动化设计。

的功能，引脚锁定编译，编程下载于FPGA 中进行硬件测试。

最后完成实验报告。

1、原理图 両诬YDN A V1M ftv?NlCY 酬 G1 T4IM <?£AhY 州G 比hve'i^N0~、r冋幅亍 —j — ................ _y p -' :n ：tl； ......................■■ .!・■ ■・[・・—・・・・UI •■■I■!■■且■ b 0 b J …J k ■ L J …―年1 一… ■ - ■ -p - pJ ip k ■ L JFN W ・・I HN 91… I PPJ 49I....… gk 八却拽：f=>E|| II- !■ i|E qi 1|1 ^1 1|1, JI 1|1 :JI 1|1 i_.i !■■_ i IIB -II iih.-i |ih»M^ii Liiqii i;=iqii l^iRn ■^■Rn审厂 恥1"=il2 T|H_3 刊毗J 刊口=1 匸10 吨112、 波形设置M^AIrimEdAT 皿rjs& 科B n* 1 [■遶 * L-r p. > ■-i h' M7 :to5 F B V 4Z3Si 出EwJ I弓舞"5 平“ 15 単“；[> 弩"：*“30 号"呼"4竽 E «^竽"mq- 36 字“也4 366 呼 6鬥5 ra3、仿真波形rlKi.It WirMl¥iuFF4位二进制数值比较器 7485串联扩展为8位比较器，使用Quartusll 完成全部设 计和测试，包括创建工程、编辑电路图、全程编译、时序仿真及说明此电路的功能、弓I 脚锁 定、编程下载，进行硬件测试。

集合实现筛选法求素数素数在数学领域中有着重要的地位，不仅在数学本身中拥有广泛的应用，而且在计算机科学中也具有重要的意义。

我们知道，素数指的是只能被1和它本身整除的数，那么如何求解素数？一般来说，我们可以使用试除法或者埃拉托色尼筛法等方法来求解素数。

而今天我们要介绍的是集合实现筛选法求素数。

1. 筛选法的基本原理筛选法求素数的基本原理是通过枚举法把小于等于N的合数筛去，最后剩下的就是质数。

具体而言，我们可以定义一个长度为N的数组来表示1~N这些数的是否为质数的状态，然后通过遍历数组并对其状态进行处理来找出所有的素数。

具体实现方法可以分为两类，分别是埃氏筛法和欧拉筛法。

2. 埃氏筛法埃氏筛法的核心思想是，对于一个素数p，可以将小于等于N 中可以被p整除的数全部排除掉。

例如，对于素数2，我们需要把4、6、8……都去掉，再对素数3进行筛选时，需要去掉9、12、15……以此类推。

实现时，我们可以先定义一个长度为N的bool类型数组，每个元素默认为true。

然后从2开始枚举每个数，如果该数为素数，则将其倍数全部筛除。

具体代码如下：bool isPrime[10001]; // 用于标记素数状态void eratosthenes(int n) {memset(isPrime, true, sizeof(isPrime)); // 初始化全部为素数for (int i = 2; i * i <= n; i++) {if (isPrime[i]) {for (int j = i * 2; j <= n; j += i) { // 筛除素数i的所有倍数 isPrime[j] = false;}}}}3. 欧拉筛法欧拉筛法和埃氏筛法原理类似，但是有一些优化策略，可以大大提升算法效率。

首先，我们仍然需要定义一个长度为N的bool类型数组来标记素数状态，但是这里我们将其作为一个集合来操作。

具体而言，在进行筛选时，我们使用一个数组primes来记录当前已知的素数，然后针对每个数n，依次将其与primes中的每个素数进行比较。

埃⽒筛法（素数筛）--⽬前我学过的找素数最快的⽅法
：给定⼀个正整数n(n<=10^6)，问n以内有多少个素数？
做法：做法其实很简单，⾸先将2到n范围内的整数写下来，其中2是最⼩的素数。

将表中所有的2的倍数划去，表中剩下的最⼩的数字就是3，他不能被更⼩的数整除，所以3是素数。

再将表中所有的3的倍数划去……以此类推，如果表中剩余的最⼩的数是m，那么m就是素数。

然后将表中所有m的倍数划去，像这样反复操作，就能依次枚举n以内的素数，这样的时间复杂度是O(nloglogn)。

题解：如果要是按照⼀个⼀个判断是否是素数然后把ans+1，时间复杂度为O(n√n)，对于10^6的数据时间复杂度就是O(10^9)，必定会超时，但此时埃⽒筛法的时间复杂度只有O(nloglogn)。

1 int prime[MAXN];//第i个素数
2 bool is_pri[MAXN+10];//is_pri[i]表⽰i是素数
3 //返回n以内素数的个数
4 int sieve(int n){
5 int p=0;
6 for(int i=0;i<=n;i++)is_pri[i]=true;
7 is_pri[0]=is_pri[1]=false;
8 for(int i=2;i<=n;i++){
9 if(is_pri[i]){
10 prime[++p]=i;
11 for(int j=2*i;j<=n;j+=i)is_pri[j]=false;
12 }
13 }
14 return p;
15 }。