CroMarmot - 个人主页动态

2021-11-02 18:01

题意 给两个字符串，求最小编辑次数让两个字符串相等。 其中编辑允许的操作 增加一个字符 修改一个字符 删除一个字符 限制：每个字符串长度小于500 方法 动态规划 考虑设计状态 dp[i][j] 表示，第一个字符串s匹配了i个字符，第二个字符串t匹配了j个字符的最小编辑代价 那么有转移方程 dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1, dp[i-1][j-1]+ s[i] != t[i]) 分别表示，删除s第i个字符，删除第j个字符，s[i]和t[j]配对的代价。 以样例 abcde abcdf 为例 - 空 a b c d e 空 0...

0 点赞评论收藏

2021-11-02 15:24

川大附小机械设计/制造

题解 | #输出单向链表中倒数第k个结点#

题意 读入一个链表 返回其倒数第k个元素 限制，链表长度不大于1000 方法 直接输出 因为数据是我们依次读入的，而不是只获取到链表头，所以我们存储如果按照数组依次存储，直接可以输出倒数第k个，就是下标n-k的输出即可 代码 #include<bits/stdc++.h> #define rep(i,a,b) for(int i = (a);i<(b);i++) using namespace std; struct ListNode { int m_nKey; ListNode* m_pNext; } node[1010]; int main(){ ...

0 点赞评论收藏

2021-10-27 14:32

已编辑

川大附小机械设计/制造

题解 | #字符串合并处理#

题意 给两个字符串 拼接它们 对拼接后的奇数位排序，偶数位排序 对 十六进制0~F以内的，按照二进制4位表示并颠倒，再转换成十六进制表示，转换后使用大写字母。其它字符不变 方法 利用ASCII运算 我们对于上面三个步骤分别如下处理 直接string相加合并 拆成两个 vector<char>数组，分别sort排序 利用ASCII转换 考虑第三步转换 注意到，数字，小写字母，大写字母，分别在ASCII上连续，同时C++中的char直接参与加减运算时，会以其ascii的值为准 那么我们可以利用这个性质，分别对数字，小写字母，大写字母，编写转换逻辑 对于数字，...

0 点赞评论收藏

2021-10-27 08:48

川大附小机械设计/制造

题解 | #字符串加解密#

题意 给定字符串加密方法，和多行字符串 要求对“一行字符串加密，一行字符串解密”的输出每一行 加密规则： 数字字符循环右移 字母字符循环右移并改变大小转换 方法 利用ASCII和数学得到解密函数 先考虑加密 注意到，数字，小写字母，大写字母，分别在ASCII上连续，同时C++中的char直接参与加减运算时，会以其ascii的值为准 那么我们可以利用这个性质，分别对数字，小写字母，大写字母，编写转换逻辑 对于解密 考虑数字：右移10位会得到本身，现在密文是右移了1位，所以只要再右移9位就能得到原文 考虑字母：（不考虑大小写的情况）右移26位会得到本身，现在是右移了一位，所以只要再右移25...

0 点赞评论收藏

2021-10-26 11:12

已编辑

川大附小机械设计/制造

题解 | #素数伴侣#

题意 给n个数字（偶数个），找出尽量多组（每组恰好2个），让每组的数的和都为质数。求最大组数 限制：每个数字最多属于其中一个组，每个值在[2,30000][2,30000][2,30000] 之间，n不大于100 方法 增广路径 首先所有数都不小于2，因此，所有和为质数必定是奇质数，那么两个整数相加为奇数，必定一个奇一个偶。 所以我们把数分成奇偶两部分，如果某个偶数和某个奇数相加是质数，那么我们建立一条从该偶数指向该奇数的边 实际要求的是，最大的可选边，且每个点至多属于一条边。 这样抽象后，就是一个典型的二分图最大匹配/网络流问题 以样例数据为例 首先我们给网络增加源点和汇点，并和现有的奇偶...

0 点赞评论收藏

2021-10-26 00:26

已编辑

川大附小机械设计/制造

题解 | #查找兄弟单词#

题意 给定一个字符串str，和一组字符串 寻找在这组字符串中有多少个和str不直接相等，但包含的内容相等的(可以交换字母得到) 这组字符串中满足条件的按照字典序排序，求第k个是哪个字符 方法 朴素实现 本题要3个工作 比较相等 比较是否可以交换得到 对给定字符串排序 我们分别如下实现 朴素比较 对两个字符串，一个辅助数组标记前一个字符是否匹配，遍历后一个字符串，在前一个字符串中找相同字符 内置的sort排序 代码 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i...

0 点赞评论收藏

2021-10-24 19:22

已编辑

川大附小机械设计/制造

题解 | #字符串排序#

题意 给定一行字符串, 要求对非字母固定位置不变, 字母 按照字母序排序,同字母大小写保持原字符串中的顺序. 限制: 每组数据有多行字符串 方法 pair与内置排序 对于字母的部分, 构建 pair<小写字母,下标>,利用C++内部sort排序(pair先比较first后比较second) 最后按下标输出. 以样例数据为例 A Famous Saying: Much Ado About Nothing (2012/8). 我们构建的pair 为 排序前 {a,0} {f,2} {a,3} {m,4} {o,5} {u,6} {s,7} ...

0 点赞评论收藏

2021-10-27 14:38

已编辑

川大附小机械设计/制造

题解 | #数据分类处理#

题意 这题目描述真的考语文呢, 给数组A(0-index),B 给B排序去重 遍历B,对每个值,找A中十进制表示中包含该值的下标,和A中的那个值 除此以外还有,还要输出每个值,输出下标的个数,在找不到时不输出,还要输出所有值的总个数 所以输出格式是 总数, [B中的值, 下标个数, [A中下标, A中的值,] ] 范围, 每个值 非负且不大于0xffffffff 方法 数值转换成字符串 我们把数组用 sort 进行排序,并利用b[i] != b[i-1]忽略掉重复. 此后就是朴素的实现题意即可 先遍历数组BBB,每次遍历数组AAA,如果满足字符包含，则记录下标。 对于每一个B的遍历,在统计...

0 点赞评论收藏

2021-10-24 05:36

川大附小机械设计/制造

题解 | #合唱队#

题意 给定一个数列,问最少删除多少个数,使得数列为先严格单调递增后严格单调递减的数列. 限制:有多组数据,每组数列个数不大于3000 方法 双重循环 要删除的人最少,就是要留下的人最多,所以我们以要留下的人最多的来思考 一个严格单调递增,再严格单调递减的序列,不妨把它拆分成两部分处理. 如果我们能计算从最左开始到当前位置的单增的最大长度,那么我们仅需要把数组翻转,再次计算单增的最大长度,就可以得到它在原数组中的向结尾方向的最大单调递减的长度. 这样再枚举每个位置,可以得到以每个位置为合唱队列的峰值的最大长度. 那么问题变成了如何计算最大单增的长度 既然我们有结果数组来记录, 那么一个位置的最...

0 点赞评论收藏

2021-10-24 04:38

已编辑

川大附小机械设计/制造

题解 | #删除字符串中出现次数最少的字符#

题意 给定一个仅含小写字母的字符串 每个测试有多组数据，每个数据字符串长度不大于20 方法 枚举 我们先枚举小写字母,每次枚举遍历字符串,统计该小写字母的出现次数. 并使用变量记录最小的出现次数以及对应的字母们 以样例数据 aabbcddd 为例 - 最小次数 字母们 初始化 0x3f3f(足够大的充当INF的值) {} a遍历字符串 2 {a} b遍历字符串 2 {a,b} c遍历字符串 1 {c} d遍历字符串 1 {c} 这样我们就能知道哪些字母出现的次数最少 最后遍历字符串s,如果位置上的字符是最小出现次数的则不要输出它即可. 代码 #include...

0 点赞评论收藏

2021-10-22 12:27

已编辑

川大附小机械设计/制造

题解 | #汽水瓶#

题意 数学抽象：给定n，初始计数为0，对于n>=2,每次n-=2,计数加1，求最终计数 每次最多10组数据，每个数据不超过100 方法 朴素实现 把数学抽象后的题意转换成代码 代码 #include<bits/stdc++.h> using namespace std; int main(){ while(true){ int n; cin>>n; if(n==0)break; // 结束标识 int r = 0; // 计数 while(n>=2){ // 不小于2 ...

0 点赞评论收藏

2021-10-22 11:11

已编辑

川大附小机械设计/制造

题解 | #简单密码#

题意 给定一个只包含数字和大小写字母的字符串，和一个映射规则，求映射后的字符串。 其中映射规则为： 数字不转换 小写字母按照手机九宫格键盘上转换成数字 大写字母转换成小写字母的循环右移一位 限制：字符串长度不大于100 方法 朴素实现 本题，直接把题意转换成代码即可 代码 #include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i = (a) ;i<(b);i++) int main(){ char pass[110]; scanf("%s",pa...

0 点赞评论收藏

2021-10-20 02:14

已编辑

川大附小机械设计/制造

题解 | #牛妹的招聘#

题意 给两个等长的数组。 选择一系列坐标，使得两个数组对应位置分别的和非负，且对应位置的值总和最大。求这个最大值。 范围：数组长度最大100，数值绝对值<1000 < 1000<1000 样例有误 应该是11 方法 dfs(TLE) 我们通过深搜，遍历每一个人选择或者不选择。遍历到最后一个人时，统计是否满足非负，同时返回和。 代码 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param number int整型 参加校招的同学人数 # @param si int整型一维数组 这个同学的聪明值 # @param fi int...

0 点赞评论收藏

2021-10-05 00:21

已编辑

川大附小机械设计/制造

题解 | #切割成本#

题意 长最大为100000010000001000000的线段上，给n个点。 其中每选择一个点，线断根据这个点分成两段，代价为这个线段的长度 找一个点的序列，使得代价总和最小，求这个最小代价。 其中n<300n<300n<300 方法 递归分治（TLE） 以题目为例[2,5,10,18] 表示成图就是 --|---|-----|--------|-- 任选一处分成两段后，子线段的分割方案对父线段的分割方案无影响。所以这个问题可以分治。 枚举所有点，每次选择一个点，f(线段)=线段长度+min(f(选点左侧的线段)+f(选点右侧的线段))f(线段) = 线段长度 + min(f...

0 点赞评论收藏

2021-10-20 02:01

已编辑

川大附小机械设计/制造

题解 | #取球放球#

题意 给一个有初始值的数组，并且其中每个位置单独限定最大值。 每次操作可以给任意一个位置在[0~最大值]的范围内加一减一 问在不超过k次操作后，相邻项的差的平方的最大值，最小为多少 算法 动态规划（TLE） 首先，虽然题目求的是相邻项差的平方的最大值的最小值。实际上绝对值越大平方越大，所以我们可以改为求相邻项绝对值的最大值的最小值。 根据题意，我们设计动态规划状态dp[下标][下标对应的值][当前最大的差]=最少的操作次数dp[下标][下标对应的值][当前最大的差] = 最少的操作次数dp[下标][下标对应的值][当前最大的差]=最少的操作次数 那么有状态转移 dp[idx][vnew][ma...

0 点赞评论收藏

关注他的用户也关注了：