ACwing897-最长公共子序列
最长公共子序列链接:https://www.acwing.com/problem/content/898/
来源:ACWing 算法基础课
题目描述给定两个长度分别为 N 和 M 的字符串 A 和 B,求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串,表示字符串 A。
第三行包含一个长度为 M 的字符串,表示字符串 B。
字符串均由小写字母构成。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N,M≤1000
输入样例:
1234 5acbdabedc
输出样例:
13
算法描述状态表示本题使用二维数组dp来分别描述a,b两个char数组,在相应长度下的最长公共字符长度。
集合划分以b[j]为结尾基准,可以这么理解——在i长度下,与b[j]的最大公共长度。
让dp[i] [j]=dp[i-1] [j],应为i长度下肯定能包含i-1长度下的最大公共值
判断更新dp[i] [j] = max(dp[i] [j-1],dp[i-1] [j]),因为在前面的1~ ...
牛客小白月赛-环上食虫
题目来源链接:https://ac.nowcoder.com/acm/contest/11229/D来源:牛客网
题目描述牛牛参加了牛妹的派对。 牛牛面前有一个圆桌,圆桌边缘按顺序摆上了 n 个蛋糕(第一个蛋糕和第 n个蛋糕相邻)。 每个蛋糕都有一个饱腹值和奶油含量。 牛牛不喜欢吃奶油,所以他想要在保证自己能吃饱(所吃蛋糕的饱腹度的和大于等于 sss)的情况下,所选择的蛋糕中奶油含量最大的那一个的奶油含量越低越好。我们知道,牛牛一直都是个绅士。所以他选择的蛋糕应该是相邻的(也就是对应圆上的一段弧(也可以是整个圆))。 现在它想请你帮它计算在能够吃饱的情况下,他吃到蛋糕中奶油含量最高的那一个最低会是多少?
输入描述:
123456输入共三行。第一行两个正整数 n,s 。接下来的一行 n 个整数 a1...a代表第一个到第 n 个蛋糕每个蛋糕的饱腹值。接下来的一行 n个整数 b1...bn 代表第一个到第 n 个蛋糕每个蛋糕的奶油含量。保证:1≤n≤2×105; 1≤s≤109; 1≤ai,bi≤109 (1≤i≤n);
输出描述:
12输出共一行代表答案。特别的,若牛牛吃掉所有 ...
cf1676-D.X-Sum
D. X-Sumtime limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Timur’s grandfather gifted him a chessboard to practice his chess skills. This chessboard is a grid $$$a$$$ with $$$n$$$ rows and $$$m$$$ columns with each cell having a non-negative integer written on it.
Timur’s challenge is to place a bishop on the board such that the sum of all cells attacked by the bishop is maximal. The bishop attacks in all directions diagonally, and there ...
ACwing4484-有限小数
题目来源:ACwing4484-有限小数给定三个整数 p,q,b,请你计算十进制表示下的 p/q 的结果在 b进制下是否为有限小数。
输入格式第一行包含整数 TT,表示共有 TT 组测试数据。
每组数据占一行,包含三个整数 p,q,b。
输出格式每组数据输出一行结果,如果 p/q的结果在 b 进制下是有限小数,则输出 YES,否则输出 NO。
数据范围前五个测试点满足 1≤T≤101≤T≤10。所有测试点满足 1≤T≤105,0≤p≤1018,1≤q≤1018,2≤b≤1018。
输入样例1:12326 12 104 3 10
输出样例1:12YESNO
输入样例2:1234541 1 29 36 24 12 33 5 4
输出样例2:1234YESYESYESNO
笔者解析本题为ACwing的周赛困难题。所运用到的主要知识为:
小数进制转换计算十进制小数→R进制小数
乘R取整顺序法:乘基数取整,连续乘以基数,并取其整数,直到积为零或达到所要求的精度时,将所得整数正序排列即可。
由此题将小数转换为二进制,可看出是小数不断的乘2,取最整数位为结果位,取小数 ...
牛客小白月赛-说谎的机器
链接:https://ac.nowcoder.com/acm/contest/11229/C来源:牛客网
题目描述牛牛在和它的机器玩猜数字,可是机器好像坏了…… 具体来说,机器首先会随机生成一个 1…n的数字 k,紧接着机器会给牛牛 m 条指令,指令的格式有如下三种: 1、op x y;这里,op=1 代表有 x≤k≤y 2、op x;这里, op=2 代表有 x≤k≤n 3、op x;这里, op=3 代表有 1≤k≤x 牛牛知道这台机器已经学会了说谎,所以它所描述的指令可能都是错误的,现在牛牛想知道机器错误的程度以便来制定修理它的方案。
所以牛牛想请你告诉它,当 k 取 1…n 这个范围内的值时,机器最多有多少条指令是错误的,而 k 又有多少种取值方式使得机器的错误指令数最多。
输入描述:12345第一行两个整数代表 n,mn,mn,m 接下来 mmm 行每行一条指令,指令格式见题面。保证:1≤n≤106; 1≤m≤2×105; 1≤op≤3;
输出描述:1输出共一行两个整数,分别代表机器最多的错误指令数,以及有多少种 k 的取 ...
ACwing4269-校庆
题目2019年浙江大学将要庆祝成立 122 周年。
为了准备校庆,校友会收集了所有校友的身份证号。
现在需要请你编写程序,根据来参加校庆的所有人士的身份证号,统计来了多少校友。
输入格式输入在第一行给出正整数 N。
随后 N 行,每行给出一位校友的身份证号(18 位由数字和大写字母 X 组成的字符串)。题目保证身份证号不重复。
随后给出前来参加校庆的所有人士的信息:
首先是一个正整数 M。
随后 M 行,每行给出一位人士的身份证号。题目保证身份证号不重复。
输出格式首先在第一行输出参加校庆的校友的人数。
然后在第二行输出最年长的校友的身份证号 —— 注意身份证第 7−14位给出的是 yyyymmdd 格式的生日。
如果没有校友来,则在第二行输出最年长的来宾的身份证号。题目保证这样的校友或来宾必是唯一的。
数据范围1≤N,M≤105
输入样例:12345678910111213537292819690611871061048119780620221344068419861215041713072819571002001X1507021936041909126530125197901260 ...
ACwing4268-性感素数
题目“性感素数 ”是指形如 (p,p+6) 这样的一对素数。
之所以叫这个名字,是因为拉丁语管“六”叫“sex”(即英语的“性感”)。
现给定一个整数,请你判断其是否为一个性感素数。
输入格式输入在一行中给出一个正整数 NN。
输出格式若 N 是一个性感素数,则在一行中输出 Yes,并在第二行输出与 N 配对的另一个性感素数(若这样的数不唯一,输出较小的那个)。
若 N 不是性感素数,则在一行中输出 No,然后在第二行输出大于 N 的最小性感素数。
数据范围1≤N≤108
输入样例1:147
输出样例1:12Yes41
输入样例2:121
输出样例2:12No23
笔者解析本题运用了经典求素数的方法求解,使用的判断素数算法模板如下
1234567public static boolean prime (int num){ if(num<=1){return false;} for (int i = 2; i <= num/i; i++) { if(num%i == 0){r ...
哈夫曼树
题目笔者使用来自于acwing-148. 合并果子这题来对哈夫曼树的构建及其使用做出声明
在一个果园里,达达已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。
达达决定把所有的果子合成一堆。
每一次合并,达达可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。
可以看出,所有的果子经过 n−1 次合并之后,就只剩下一堆了。
达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家,所以达达在合并果子时要尽可能地节省体力。
假定每个果子重量都为 1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使达达耗费的体力最少,并输出这个最小的体力耗费值。
例如有 33种果子,数目依次为 1,2,9。
可以先将 1、2堆合并,新堆数目为 3,耗费体力为 3。
接着,将新堆与原先的第三堆合并,又得到新的堆,数目为 12,耗费体力为 12。
所以达达总共耗费体力=3+12=15。
可以证明 15 为最小的体力耗费值。
输入格式输入包括两行,第一行是一个整数 n,表示果子的种类数。
第二行包含 n 个整数,用 ...
计算机网络复习
计算机网络1. 为什么要对计算机网络进行分层?分层的原则?a.因为计算机网络是一个复杂的系统,采用层次化结构的方法来描述它,可以将复杂的网络间题分解为许多比较小的、界线比较清晰简单的部分来处理;
b.分层的一般原则是将一组相近的功能放在一起,形成一个网络的结构层次。
2. 冗余码及所给的计算数据M尾部加上多项式最高幂次个0,然后再将多项式的各个常数项进行提取,有就写1没有就写0,然后诸位异或计算,若最后的余数不为0,则M的数据就有问题。(P77)
3. CSMA/CD(载波监听多点接入/碰撞)工作方式:许多计算机以多点接入的方式连接到一根总线上(MA)。每一个站在发送帧之前有检测冲突就等待发送。发送数据之中,每个站都必须继续不停的检测信道,发现冲突停止发送(CS/CD)
优缺点: 原理比较简单,技术上易实现,网络中各工作站处于平等地位 ,不需集中控制,不提供优先级控制。但在网络负载增大时,发送时间增长,发送效率急剧下降。
4. TCP/UDP简述:TCP和UDP都是传输层协议。TCP/IP是一个协议簇,里面包含了很多协议,UDP ...
HTML学习总结
入门基础知识1.前端三大件首先我们要知道HTML、CSS、Javascript三者并称为前端三大件,一个正常的网页可以
通过HTML进行基本的框架构建,通过CSS进行页面美化和排版,通过JS来实现网页的功能
2.HTML简介HTML的全称为超文本标记语言,是一种标记语言。它包括一系列标签.通过这些标签可以将网络上的文档格式统一,使分散的Internet资源连接为一个逻辑整体。HTML文本是由HTML命令组成的描述性文本,HTML命令可以说明文字,图形、动画、声音、表格、链接等。
超文本是一种组织信息的方式,它通过超级链接方法将文本中的文字、图表与其他信息媒体相关联。这些相互关联的信息媒体可能在同一文本中,也可能是其他文件,或是地理位置相距遥远的某台计算机上的文件。这种组织信息方式将分布在不同位置的信息资源用随机方式进行连接,为人们查找,检索信息提供方便。
3.HTML版本须知HTML历史上有如下版本: [5]
①HTML 1.0:在1993年6月作为互联网工程工作小组(IETF)工作草案发布。 [5]
②HTML 2.0:1995年1 1月作为RFC 1866发布,于2000年6月 ...





