cxposition-CSDN博客

原创最长公共子序列（上海交通大学考研机试题）

给出两个长度为 n 的整数序列，求它们的最长公共子序列（LCS）的长度，保证第一个序列中所有元素都不重复。一个序列中的某些元素可能不在另一个序列中出现。第一个序列中的所有元素均不重复。第二个序列中可能有重复元素。我们用另一种方式模拟这个过程。

2023-09-10 20:24:58 414

那么对于字符串"PIPIisaboy"，大魔术师PIPI可以通过2次魔咒将"PIPIisaboy"变成"POPOisagirl"。接下来N行，每一行输入一个转换规则 X Y，代表可以将字符串X转化为Y。现在你知道了PIPI的所有魔咒，想让他把字符串A变成字符串B，请输出变换所需的最少步数。如果在10次之内能将A变为B，输出从字符串A变为字符串B的最少次数。大魔术师PIPI有N个转换魔咒，每个转换魔咒可以将一个字符串变成另一个字符串。输入包含单组测试样例。

2023-07-29 16:58:00 220

原创 1321-全为1面积最大正方形Ⅲ

PIPI有一个n*m的01矩阵，它现在想在矩阵中找到一个全由1构成且面积最大的正方形，请你输出这个最大正方形的面积。第一行两个正整数n,m,n<=3000,m<=3000.接下来n行，每行m个数字，数字仅由0和1组成。输出一个整数，代表最大全1正方形的面积。

2023-07-23 08:22:55 246

原创 1169-PIPI倒水

PIPI有三个杯子，容量分别为 a ,b ,c,最初只有第三个杯子有c升水，其余两个杯子都是空的，PIPI想知道至少要倒出多少升水才能够让某一个杯子中的水有 d 升，如果无法做到恰好 d 升，就让某个杯子中的水是 d’ 升，d’

2023-07-14 17:32:38 131

原创手撕单链表创建并反转全过程

#include <bits/stdc++.h>using namespace std;struct node{ int val; struct node * next; node(){} ///空参构造器 node(int x) : val(x), next(NULL){} ///带参构造器 };int main() { int n; scanf("%d", &n); node* dummy = new node; ///dummy表示头节点 n

2022-01-20 14:12:20 680

原创 NC82 滑动窗口的最大值

描述给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2

2021-12-30 00:33:36 343

原创 NC78 反转链表

描述给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。数据范围： n\leq1000n≤1000要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。如当输入链表{1,2,3}时，经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。以上转换过程如下图所示：示例1输入：{1,2,3}返回值：{3,2,1}示例2输入：{}返回值：{}说明：空链表则输出空/*struct ListNode { int val; stru

2021-12-27 11:18:24 540

原创 NC76 用两个栈实现队列

class Solution{public: void push(int node) { ///s1进栈即可，s1相当于队首 stack1.push(node); } ///s2相当于队尾 int pop() { if(stack2.empty()){ ///先检查stack是否为空 while(!stack1.empty()){ ///如果

2021-12-18 16:01:43 255

原创经典DSF问题

acwing-842. 排列数字题目描述：给定一个整数 n ，将数字 1∼n 排成一排，将会有很多种排列方法。现在，请你按照字典序将所有的排列方法输出。输入格式共一行，包含一个整数 n。输出格式按字典序输出所有排列方案，每个方案占一行。数据范围1≤n≤7输入样例：3输出样例：1 2 31 3 22 1 32 3 13 1 23 2 1题解代码如下#include<bits/stdc++.h>using namespace std;const int N

2021-11-25 15:54:37 198

原创洛谷.P3374 树状数组

题目描述如题，已知一个数列，你需要进行下面两种操作：将某一个数加上 x求出某区间每一个数的和输入格式第一行包含两个正整数 n,mn,m，分别表示该数列数字的个数和操作的总个数。第二行包含 nn 个用空格分隔的整数，其中第 ii 个数字表示数列第 ii 项的初始值。接下来 mm 行每行包含 33 个整数，表示一个操作，具体如下：1 x k 含义：将第 xx 个数加上 kk2 x y 含义：输出区间 [x,y][x,y] 内每个数的和输出格式输出包含若干行整数，即为所有操作 22 的结果。

2021-08-20 21:37:34 411

原创洛谷.P3375-KMP字符串匹配

原题连接 P3375-KMP字符串匹配题解代码如下#include<bits/stdc++.h>using namespace std;const int N = 1e6 + 7;char s1[N],s2[N];int ne[N];int main(){ scanf("%s%s",s1+1,s2+1); int n = strlen(s1+1);///字符串 int m = strlen(s2+1);///模式串 for(in

2021-07-27 08:40:15 212

原创 leetcode.73-矩阵置0

难度级别（中等难度）给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。进阶：一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。你能想出一个仅使用常量空间的解决方案吗？题解代码如下class Solution {public: void setZeroes(vector<vector<int&gt

2021-07-23 13:44:22 80

原创 leetcode.92-反转链表II

题目描述(难度级别：中等)给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。题解代码如下：/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(n

2021-07-22 23:19:05 98 1

原创 1084-最长公共子序列Ⅱ

题目描述PIPI又来刁难胖虎了~现在PIPI有n个字符串项链，它要你求出这n个环的最长公共子序列，并输出~PS：注意每个字符串都成环了，首尾相连~输入多组数据第一行为一个整数n，1<=n<=10接下来n行，每行一个字符串，保证字符串长度不超过8.输出输出一个字符串，代表n个串的最长公共子序列。若不存在，输出0.若有多个答案，输出字典序最小的。样例输入2abcdefgzaxcdkgb5abcdefkedajceuadbacabcdefabcdafc2abc

2021-06-28 18:21:04 142

原创 1066-竖式问题

题目描述找出所有形如 abc∗de (三位数乘以两位数)的算式,使得在完整的竖式中，所有数字都属于一个特定的数字集合。输入数字集合(相邻数字之间没有空格),输出所有竖式。每个竖式前应有编号,之后应有一个空行。最后输出解的总数。具体格式见样例输出。输入输入包含多组测试用例。对于每组测试用例，输入一个字符串s,代表数字集合。输出输出所有竖式。每个竖式前应有编号，之后应有一个空行。最后输出解的总数。(竖式按照3位数的大小从小到大输出~)样例输入2357样例输出<1> 775X

2021-06-28 12:29:37 167

原创 acwing-835.Trie字符串统计

题目描述：维护一个字符串集合，支持两种操作：I x 向集合中插入一个字符串 x；Q x 询问一个字符串在集合中出现了多少次。共有 N 个操作，输入的字符串总长度不超过 105，字符串仅包含小写英文字母。输入格式第一行包含整数 N，表示操作数。接下来 N 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。输出格式对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。每个结果占一行。数据范围1≤N≤2∗10^4输入样例5I abcQ ab

2021-06-14 18:07:07 82

原创 acwing.3578-最大中位数（acwing第一场周赛第2题）

给定一个由 n 个整数组成的数组 a，其中 n 为奇数。你可以对其进行以下操作：选择数组中的一个元素（例如 ai），将其增加 1（即，将其替换为 ai+1）。你最多可以进行 k 次操作，并希望该数组的中位数能够尽可能大。奇数长度的数组的中位数是数组以非降序排序后的中间元素。例如，数组 [1,5,2,3,5] 的中位数为 3。输入格式第一行包含两个整数 n 和 k。第二行包含 n 个整数 a1,a2,…,an。输出格式输出一个整数，表示通过操作可能得到的最大中位数。数据范围对于 30%

2021-06-02 11:30:07 380

原创 acwing-849dijkstra朴素版(链式前向星)

Dijkstra求最短路 I题目描述给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。输入格式第一行包含整数 n 和 m。接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。输出格式输出一个整数，表示 1 号点到 n 号点的最短距离。如果路径不存在，则输出 −1。数据范围1≤n≤500,1≤m≤105,图中涉及边长均

2021-05-29 14:20:23 198

原创 acwing-861.二分图最大匹配（匈牙利算法）

题目描述给定一个二分图，其中左半部包含 n1 个点（编号 1∼n1），右半部包含 n2 个点（编号 1∼n2），二分图共包含 m 条边。数据保证任意一条边的两个端点都不可能在同一部分中。请你求出二分图的最大匹配数。二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数输入格式第一行包含三个整数 n1、 n2 和 m。

2021-05-28 14:32:48 177

原创 string matching-上海交通大学研究生复试机试题

题目描述:Time Limit: 1000 msMemory Limit: 256 mbFinding all occurrences of a pattern in a text is a problem that arises frequently in text-editing programs. Typically,the text is a document being edited,and the pattern searched for is a particular word

2021-05-27 12:39:01 442

原创 acwing-843.n-皇后问题

题目描述n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。现在给定整数 n，请你输出所有的满足条件的棋子摆法。输入格式共一行，包含整数 n。输出格式每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。每个方案输出完成后，输出一个空行。注意：行末不能有多余空格。输出方案的顺序任意，只要不重复且没有

2021-05-02 13:58:43 1288

原创 1344-PIPI的字符串问题Ⅱ

题目描述PIPI又来考察大家字符串处理的能力了。给定一个字符串S，以及字符串T，你需要回答：(1)T是否是S的子串。如果是输出YES，并回答问题(2)；如果不是，输出NO。(2)T作为S的子串在S中出现了几次？请你来解决这个简单的问题。注意：子串不是子序列。子串要求连续，如”abc"为"aabcc“的子串。输入第一行给出字符串S。|S|<=1e6.第二行给出字符串T。|T|<=1e6.输出首先回答问题(1),若T为S子串，输出YES，第二行回答问题(2).若不是，直接输出N

2021-04-20 10:38:07 101

原创 acwing-841.字符串哈希

题目描述给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。字符串中只包含大小写英文字母和数字。输入格式第一行包含整数 n 和 m，表示字符串长度和询问次数。第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。接下来 m 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。注意，字符串的位置从 1 开始编号。输出格式

2021-04-19 14:28:56 333

原创 acwing-837.连同块中点的数量

题目描述给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。现在要进行 m个操作，操作共有三种：C a b，在点 a 和点 b 之间连一条边，a 和 b可能相等；Q1 a b，询问点 a和点 b 是否在同一个连通块中，a 和 b可能相等；Q2 a，询问点 a所在连通块中点的数量；输入格式第一行输入整数 n 和 m。接下来 m行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。输出格式对于每个询问指令 Q1 a b，如果 a和 b在

2021-04-16 15:29:48 73

原创 acwing-797,798.差分，差分矩阵

一：差分题目描述输入一个长度为 n的整数序列。接下来输入 m个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r] 之间的每个数加上 c。请你输出进行完所有操作后的序列。输入格式第一行包含两个整数 n 和 m。第二行包含 n个整数，表示整数序列。接下来 m行，每行包含三个整数 l，r，c，表示一个操作。输出格式共一行，包含 n 个整数，表示最终序列。数据范围1≤n,m≤100000,1≤l≤r≤n,−1000≤c≤1000,−1000≤整数序列中元素的值≤1000

2021-04-14 11:44:02 146

原创 acwing-803. 区间合并

题目描述给定 n 个区间 [li,ri]，要求合并所有有交集的区间。注意如果在端点处相交，也算有交集。输出合并完成后的区间个数。例如：[1,3]和 [2,6] 可以合并为一个区间 [1,6]。输入格式第一行包含整数 n。接下来 n行，每行包含两个整数 l 和 r。输出格式共一行，包含一个整数，表示合并区间完成后的区间个数。数据范围1≤n≤100000,−109≤li≤ri≤109输入样例51 22 45 67 87 9输出样例3题解代码#include&l

2021-04-12 14:52:42 105

原创 acwing-789.数的范围

题目描述给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。如果数组中不存在该元素，则返回 -1 -1。输入格式第一行包含整数 n 和 q，表示数组长度和询问个数。第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。接下来 q 行，每行包含一个整数 k，表示一个询问元素。输出格式共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。如果数组中不存在该元素，则返回 -1 -

2021-04-10 00:14:06 62

原创 acwing-802.区间和(离散化,整数二分,前缀和)

题目描述假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。输入格式第一行包含两个整数 n 和 m。接下来 n 行，每行包含两个整数 x 和 c。再接下来 m 行，每行包含两个整数 l 和 r。输出格式共 m 行，每行输出一个询问中所求的区间内数字和。数据范围−109≤x≤109 ,1≤n,m≤105,−

2021-04-07 17:53:30 237

原创 acwing-3302.表达式求值(中缀)

题目描述给定一个表达式，其中运算符仅包含 +,-,*,/（加减乘整除），可能包含括号，请你求出表达式的最终值。注意：数据保证给定的表达式合法。题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。题目保证表达式中所有数字均为正整数。题目保证表达式在中间计算过程以及结果中，均不超过 231−1题目中的整除是指向 0取整，也就是说对于大于 0 的结果向下取整，例如 5/3=1，对于小于 0 的结果向上取整，例如 5/(

2021-04-04 18:06:33 175 1

原创 1028-可乐(中南大学18年研究生复试机试题)

题目描述猪年快乐！在这个快乐的日子里我们当然要去超市买可乐喝啦!现在超市有n种可乐，第 i 种可乐的价格为C[i] ，体积为 2i-1 毫升，每种可乐都是无限供应的，现在你想买至少 L毫升的可乐，作为一个省钱小能手，聪明的你能够想到最少要花多少钱吗?输入输入包含多组测试用例。每组测试用例第一行包含两个数字 n 和 L (1 ≤ n ≤ 30; 1 ≤ L ≤ 109) ， n是可乐的种类数， L是我们最终要买的可乐体积。第二行包含 n 个数字 C1，C2,…Cn n (1 ≤ ci ≤ 10

2021-03-10 14:47:57 574

原创 1111-最小花费(中南大学19年研究生招生夏令营)

题目描述在n个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收到100元。输入输入包含多组测试用例。对于每组样例，第一行输入两个正整数n,m,分别表示总人数和可以互相转账的人的对数。（0<n<=2000）以下m行每行输入三个正整数x,y,z。表示标号为x的人和标号为y的人之间互相转账需要扣除z%的手续费（z<100）。最后一行输入两个正整数A,B。数据保证A与B之间

2021-03-08 16:01:17 294

原创 1025-最短距离(中南大学18年研究生复试机试题)

题目描述小王和小明是好朋友，两人最开始各有一个初始位置 p 和一个恒定速度 v，从0时刻起开始，他们从初始位置以恒定速度开始行走，请告诉我行走过程中两人的最短距离是多少。输入第一行输入T代表测试样例数目。对于每个样例，第一行包含四个整数 x1，y1，x2，y2，表示人的起点（x1，y1），（x2，y2）。第二行是四个整数u1，v1，u2，v2，表示人的初始速度（u1，v1），（u2，v2）（分别为x轴和y轴方向的分速度）。T <= 1000 , x1，y1，x2，y2，u1，v1，u2，

2021-03-07 12:13:04 379

原创 1027-逃离迷宫(中南大学18年研究生复试机试题)

题目描述PIPI被困在一个迷宫中了!给定一个m × n (m行, n列)的迷宫，迷宫中有两个位置，PIPI想从迷宫的一个位置走到另外一个位置，当然迷宫中有些地方是空地，PIPI可以穿越，有些地方是障碍，她必须绕行，从迷宫的一个位置，只能走到与它相邻的4个位置中,当然在行走过程中，PIPI不能走到迷宫外面去。令人头痛的是，PIPI是个没什么方向感的人，因此，她在行走过程中，不能转太多弯了，否则她会晕倒的。起点和终点也有可能为障碍，初始时，PIPI所面向的方向未定，她可以选择4个方向的任何一个出发，而不算成

2021-03-06 16:28:34 404

空空如也

空空如也