恭喜你报名比赛成功，获得牛客专属邀请返现特权。朋友通过你的邀请链接报名比赛，可立减15.00元，你也能获得可立减15.00元现金奖励，邀请越多现金奖励越多，不设上限！快邀请大家来一起寒假集训提升吧，前往查看你的专属邀请链接：https://ac.nowcoder.com/order?itemId=28&itemType=ACM_CONTEST_CHARGE&couponId=ABONOnS。       用我链接购买成功后截图私聊我即可

题目链接： https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2?tpId=117  模拟入栈出栈即可  class Solution { public: /** * * @param s string字符串 * @return bool布尔型 */ bool isValid(string s) { // write code here if(s.size()&1) return false; stack<char> st; for(auto x:s){ if(x=='('||x...

class Solution { public:     /**      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可      *       * @param x string字符串       * @return int...

做法：st表+并查集 前置芝士： st表：https://oi-wiki.org/ds/sparse-table/ 思路：  令f[i][j]表示区间[i,i+ 2^j-1]这一段 对于一个限制可以拆成log 份，然后进行集合合并 答案就是是9*10^(集合个数-1)  代码  // Problem: [SCOI2016]萌萌哒 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/20310 // Memory Limit: 524288 MB // Time Limit: 2000 ms // Powered by...

做法：floyd+倍增 题意：  求最小正环的大小  思路：  利用floyd+倍增的方法跑最长路 路径数量从大到小的方法来判断是否成立（类似二分的思想） 1）若存在正环，则，则答案不需要增加 2）若不存在正环，则，则答案需要增加，并且更新f数组  代码  // Problem: Smile House // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/109328 // Memory Limit: 524288 MB // Time Limit: 6000 ms // Powered by CP Editor (...

做法：倍增+贪心 题意：必选一个区间后，找出剩余区间能覆盖整个环的最少区间数 思路：  1.先把环转化成链 2.再把这些区间按左端点排序 3.利用倍增来查询  代码  // Problem: [SCOI2015]国旗计划 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/20302 // Memory Limit: 524288 MB // Time Limit: 2000 ms // Powered by CP Editor (https://github.com/cpeditor/cpeditor) #incl...

做法：lca 题意：  已知两点，求到这两点距离相同的点的个数  思路：  如果存在到这两点距离相同的点，那么这两点的距离一定是偶数 如果这两点的深度相同，那么他们向上走到他们最近的公共祖先的子节点，然后n减去以这两个点为根节点的子树大小 否则求减去这两个点的中点一下的部分  代码  // Problem: A and B and Lecture Rooms // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/110856 // Memory Limit: 524288 MB // Time Limit: 4000 ...

做法：倍增+二分+贪心 思路：  1.类似于lca的方法，倍增预处理出fa父亲节点和depth到父亲节点的长度数组。 2.二分答案。 3.对于每个当前的mid，把每个军队上提到能够达到的最高位置（最高上提到根节点的子节点）。 4.对于可以上提到根节点的子节点，再经过根节点后还能行走的军队，存入rest_army数组中，同时求出根每个子节点空闲军队走到根节点后剩余行程最小的编号（restnum和restmin）。 5.判断根的子节点的空隙情况，存到gap数组中。 6.贪心。对于rest_army和gap数组进行从大到小排序。  代码  // Problem: 疫情控制 // Contest: N...

Crypto ​ 对称密码 分组密码 关键在于混乱、扩散和抗分析的设计 DES、AES等 序列密码 关键在于伪随机数的生成 RC4等 非对称密码 相关推荐资料：Introduction to Mathematical Cryptography 关键在于单向陷门函数的选取 基于整数分解 RSA等 RSA 预备数学知识： 相关推荐资料：华罗庚《数论导引》前四章  欧拉函数：  定义：在模n下，与n互素的整数的个数记作 容易知道，对于素数p，，对于合数n，，其中为n的所有素数因子 例子：，即是  欧拉定理：  定义：对于a，n，若，则有 例子：  模逆：  定义：在模n下，对于任意a，如果，则存在b...

做法：LCA 前置芝士： LCA的有关性质：https://oi-wiki.org/graph/lca/#_2 题意：  已知a,b,c,求某点到这三个点的最短距离以及该点的位置  思路：  先求a,b,c两两之间的最近公共祖先，其中可以得到三个点，其中两个点是相同的，取另一个点不与这两个相同的值点即为所求点。 简单证明下：根据LCA性质中的两点的最近公共祖先必定处在树上两点间的最短路上可以得出所求点必在上述所求的两个点之间。如果选择靠近之前相同的点，只需跑一次，否则需要跑两次。（简单画下图很容易的出） 在根据LCA另一性质求出距离即可  代码  // Problem: [AHOI2008]M...

做法：贪心 时间复杂度： 思路  这题实际上是在求 可利用贪心的思路维护在范围内最小即可，时间复杂度从将为代码 class Solution { public: /** * * @param prices int整型vector * @return int整型 */ int maxProfit(vector<int>& prices) { int ans=0,t=0x3f3f3f3f; for(auto x:prices){ t=min(x,t); ans=max(ans,x-t); } return ans; } };

思路  1.先对树从根结点进行一遍dfs求出每个点的深度 2.用大根堆把不满足要求的点存起来 3.按深度从大到小依次把该点的父亲结点与根结点相连 4.更新父亲结点和它的子节点的状态  代码 // Problem: Tree with Small Distances // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/113026 // Memory Limit: 524288 MB // Time Limit: 2000 ms // Powered by CP Editor (https://github.com/c...

思路  首先看到与运算立马想到和位运算有关 利用前缀和思想存连续的一段数的和 利用贪心的思想，最高到低枚举每一位，判断把这一位变1后是否满足（ps：枚举的那位尽可能大一点） 设dp[i][j]前i个物体被分为j组是否存在  代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a...

做法：dfs序+LIS 思路：  因为这是棵二叉树，所以可以使用结构体存储 由如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大可以得出根节点<左节点，根节点<右节点由如果在左子树选了一个点，在右子树中选的其他点要比它小可以得出右节点<左节点所以根节点<右节点<左节点 根据递增关系可以进行根节点->右节点->左节点的访问顺序遍历 选出尽量多的点可以转化为遍历二叉树的顺序求最长上升子序列（LIS）的长度，这里采用贪心的思想 不会的可以参考 最长不下降子序列 稍作修改即可  代码 #include <bits/stdc++.h> u...