江新宇Bernard

分类

Tips(3) 未归档(6) 模板(4) 赛后分析(14) 面试(1) 题解(13)

/ 注册

全部文章（共40篇）

数据结构课上习题

奇偶半排序设计算法将顺序线性表中的所有奇数集中到数组的左边，所有的偶数集中到数组的右边，要求算法的时间复杂度为O(n)。 #include<iostream> #include<algorithm> using namespace std; int main() { ...

算法学习

2020-02-27

2 1298

寒假训练赛6 贪心匹配循环继承TLE upper_bound

这次比赛我不应该贪B题的，看到钟涛做出来了我就觉得我应该也可以（但是我没搜洛谷，如果主攻D题可能就做出来了。 D题 https://ac.nowcoder.com/acm/contest/3007/D 思路其实我的思路是对的，就是对每个Bi，找有多少个比相应位置Ai后面的Ai可以换到这个位置来。...

二分 STL 数学思维模板

2020-02-16

3 629

寒假训练赛5 三分贪心博弈

总结是收获颇丰的一场，明天醒来补题，现在记下来，免得忘记了。圆周率的表示方法const double PI=acos(-1);，我之前记过，但是忘记了，这次还是写的 const double PI=3.14159264354;(这个也是我背下来的【J题】https://ac.nowcoder...

二分计算几何

2020-02-14

2 788

寒假训练赛4 子段异或 mod 双指针栈

本次训练赛大量涉及STL。 D题题意 https://ac.nowcoder.com/acm/contest/3005/D长度为n数组，求子段异或值为0的个数。这道题据说是滴滴还是字节跳动面试题改编，原题是不可分割求最大，用DP，这一题是可分割，应该是简单了不少。思路与其说思路不如说是教训。 ...

STL 位运算

2020-02-12

2 603

寒假训练赛3 因数埃筛汉诺塔

H题题意统计1~n“k合因子数”数量。一个数的k合因子数是指这个数所有是合数的因子的数量。思路使用埃氏筛标记出来[1,n]所有的合数，因为埃氏筛的模板是标记质数，要特别注意1和0既不是质数又不是合数，所以记得要改一下标记。完成了这一步以后，我们得到一个[1,n]是否是合数的bool数组chk...

数论欧拉筛规律打表

2020-02-09

3 649

寒假训练赛2 mod pow 数三角 dp inv

https://ac.nowcoder.com/discuss/364961?tdsourcetag=s_pctim_aiomsg题解传送门本次比赛C题DP挺经典的，值得回顾。 G题判正误判断最早觉得是大数，一开始想直接用python糊过去。pythonTLE了以后还搞了很久的大数快速...

取模快速幂数学思维数论 DP

2020-02-07

2 814

股票买卖问题纪念品 2019CSP-J普及组C题 DP学习

中间一度怀疑是牛客的测评机出问题了……才发现是自己的数组越界。太艰难了。https://ac.nowcoder.com/acm/contest/2340/C题目是比较简单的，思路大概就是求解第一天到第t-1天的最佳策略，所以大概也可以说是一道贪心的题目。那么怎么确定最佳策略呢——填表。每个纪念品都会...

DP

2020-02-06

1 695

寒假训练赛1 双指针 --cnt[s[l++]]

每次打比赛都能有一些收获，这次主要有以下几个点：最早在看《算法竞赛入门到进阶》的时候看到了《代码规范》，我觉得很多都很好，因为这样规范不只可以让代码更统一，很多的细节的地方更可以避免不必要的问题，但是有一个点我当时不是很明白，就是“变量定义”，他建议变量在离使用最近的地方定义，我主要有两个点比较疑惑...

二分 STL TLE 双指针

2020-02-05

2 668

2019 ICPC ECfinal M题终于看懂了

非常感谢YLM大佬的指导。https://ac.nowcoder.com/acm/contest/3732/M首先是按幂分组，这和我当时和CZL说的是一样的。 #include<bits/stdc++.h> typedef long long ll; using namespace s...

算法学习 ICPC 位运算穷举

2020-02-03

2 827

POJ 2456 二分贪心

拿来练了一下二分，对于本菜鸡而言，光看不写肯定是学不会的。顺便测试了一下内联函数 #include <iostream> #include <algorithm> using namespace std; const int N=1e5+5; int a[N],n,c,ans...

二分 water

2020-02-02

1 516