Peterliang

分类

PAT挑战日记(15) 《算法竞赛进阶指南》系列题解(4) 心路历程(1) 未归档(5) 模板(2) 题解(145)

/ 注册

全部文章（共171篇）

树上求LCA两种方法

一、向上标记法比如求x，y的lca，我们先从x向上走到根节点，中途标记每个被走过的点，然后从y向上标记，直到遇到第一个被标记的点就是他们的lca了。(不适用于多次查询操作）时间复杂度：O(n) 二、树上倍增法这种方法主要是利用了倍增的思想，不断地向上试探，同时利用dp不断转移到上面，然后即可求出...

LCA DP

2020-10-05

0 689

NCU九月测试赛

A、U131732 Woft6c看两任摸鱼王抢咸鱼思路：逻辑思维题，首先可以自己进行模拟，找到规律。但是要注意开long long。代码： #include<stdio.h> int main(){ int t; scanf("%d",&t)...

2020-09-30

0 620

牛客小白月赛27题解

B、乐***对题意：给出n个人，将这些人分为若干个组，每个人对应的一个值a[i]，表示这个人所在队伍的人数只要有a[i]个人才可以，问最多可以组成多少个队伍？若不能组成队伍，则输出-1.思路：我们考虑贪心的算法，我们令dp[i]表示当前到i的时候我们可以组成的最多的队伍数量。那么，我们可以直到，...

题解刷题

2020-09-17

1 701

牛客IOI周赛18-普及组

数字计数题意：求最大的数字与次大的数字之差,最大的数字与次小的数字之差,次大的数字与次小的数字之差,次大的数字与最小的数字之差。思路：题目的数据量比较小，直接用一个sort排好序后进行求解即可，注意去重即可。代码： #include<bits/stdc++.h> using names...

题解刷题

2020-09-05

0 597

牛客编程巅峰赛S1第9场 - 青铜&白银

牛牛的字符反转题意：给出一个数字n和k，我们可以进行的操作是将1-n的排列进行选择区间进行反转，问得到将1-n序列向右循环移动k个位置的序列所需要操作的最少的次数为多少。思路：我们反过来思考，我们先将1-n向右进行循环位移k个单位，然后选择合适的区间进行反转，问回到1-n的排列所需要的操作次数为多...

题解刷题

2020-09-04

0 667

牛客练习赛67

牛牛爱字符串题意：给出一个字符串，提取出这个字符串中的所有的数字，然后依次输出这些数字。思路：简单模拟。但是这里要注意的是不能有前导0，还有全为0的情况输出即可。代码： #include<bits/stdc++.h> using namespace std; int main(){ ...

题解刷题

2020-09-03

0 725

杭电第二场比赛题解

The Oculus 题意：给出一个费波纳希数列的某几个表示a，b，c，问ab的乘积原本是c，但c修改了某一位，求修改了哪位。思路：直接暴力冲，主要是找出一个适合的mod使得它们形成一一映射，但是似乎用unsigned long long可以直接表示。也就是先进行预处理，然后再进行求出a，b，最后直...

题解英文题挑战

2020-08-30

0 561

2020牛客暑期多校训练营（第六场）

Combination of Physics and Maths 题意：给出一个矩阵，求出它的一个子矩阵，使得这个子矩阵中F/S最大，F指的是这个矩阵中所有数字的和，s指的是最后一列的元素的和。思路：一个贪心的思路。刚开始想复杂了，后面仔细一想，我只要对每列求一下平均，取最大的即可。为什么呢？可以这...

题解英文题挑战

2020-08-27

0 702

2020牛客暑期多校训练营（第五场)

Drop Voicing 题意：给你一个序列，可以执行两种操作，第一种操作就是将序列的倒数第二个数移到最前面，第二种操作就是将序列的最后一个数移到最前面。要求问至少要进行几次第二种操作才能使得整个序列是一个升序的排列。思路：我们先观察两种操作的区别，我们发现，对于第一种操作，就是可以改变序列的LIS...

题解英文题挑战

2020-08-24

0 571

2020杭电暑假多校算法集训营第10场

写在前面，这场比赛是这个暑假最后一场多校比赛了，打得很不好，特别是在杭电的比赛，总是感觉水土不服一样。感觉自己比赛的时候总喜欢看榜，怎么说呢，看榜有看榜的好处吧，但是感觉在牛客和杭电的几场比赛都被榜带偏了，赛后补题的时候我觉得这题我是可以做出来的。说这么多，关键还是自己的比赛时的心态有问题，别一天天...

题解

2020-08-22

1 903