小毅儿 - 个人主页动态 - 牛客网

发布(153) 评论刷题收藏

2021-08-05 04:38

山东师范大学游戏前端

普通母函数模板

int c1[250001]; //代表多项式的系数 int c2[250001]; //暂存 int a[55][2]; //0记录价值，1记录数量 int main() { int n; while(cin >> n){ if(n<0) break; int sum=0; for(int i=0;i<n;i++) { cin >> a[i][0] >> a[i][1]; sum+=a[i][0]*a[i][1]; } for (int i=0;i<=sum;i++){ c1[i] = 0; c2[i] = 0; } for (int i...

0 点赞评论收藏

分享

2021-08-01 03:38

山东师范大学游戏前端

int l=0,r=100,ans=0; while(l<=r){ mid=(l+r)/2; if (check(mid)) { l=mid+1;ans = mid; } else r=mid-1; //注意+1，-1否则死循环 }

0 点赞评论收藏

分享

2021-07-31 17:02

已编辑

山东师范大学游戏前端

树状数组、线段树模版

索引： （一）树状数组： a代表原始数组，c代表树状数组，n很重要！！！！ （1）在多种情况下，树状数组要初始化：void init(); （2）求最低位：int lowbit(int x); （3）单点更新：void update(int x,int y); （4）前x项求和：int getsum(int x); （二）线段树 a代表原始数组，segtree代表线段树结构体 （1）建线段树，相当于初始化：void build(int l,int r,int rt); （2）单点更新：void update(int L,int C,int l,int r,int rt); （3）区间求和：in...

0 点赞评论收藏

分享

2021-04-21 21:48

已编辑

山东师范大学游戏前端

计算几何基础运算

索引：double Dot(Vector,Vector) -> 求两个点的点积，点积可用于判断一个点是否在一个线段的范围内，+不在，-在double length(Vector) -> 利用点积求向量的长度double Angle(Vector,Vector) -> 利用点积和长度以及余弦定理求两个向量之间的夹角double Cross(Vector,Vector) -> 求两个向量之间的叉积，叉积为0，两条直线平行Vector Rotate(Vector,double) -> 向量旋转Point GetLineIntersection(Point,Vector,...

0 点赞评论收藏

分享

2021-03-22 19:58

山东师范大学游戏前端

离散化（缩小数据范围，如求逆序对）

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <vector> #include <queue> #include <map> #include <stack> using namespace std; typedef long long ll; struct sss { int val; //原来的数值 int order; ...

0 点赞评论收藏

分享

2021-03-08 19:00

山东师范大学游戏前端

解析几何-最小圆覆盖点

#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <s...

0 点赞评论收藏

分享

2020-11-25 19:48

山东师范大学游戏前端

树上启发式合并

#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include ...

0 点赞评论收藏

分享

2020-10-30 20:39

已编辑

山东师范大学游戏前端

Tarjan算法（有向图求强连通分量）

Tarjan算法是求 有向图 中 强连通分量 的算法 知识点：（1）有向图：由有向边构成的图（这是Tarjan算法的前提和条件）（2）强连通：如果两个顶点可以互相通达，则称两个顶点强连通。如果有向图G的每两个顶点都强连通，则称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量 Tarjan算法：Tarjan算法是用来求强连通分量的，它是一种基于DFS的算法，每个强连通分量为搜索树中的一棵子树。并且运用了数据结构栈。 引入两个非常重要的数组： (1)dfn[]:时间戳（被搜到的次数），一旦某个点被DFS后，这个时间戳就不再改变（且每个点只有唯一的时间戳）。所以经常根据dfn的值来...

0 点赞评论收藏

分享

2020-10-28 19:13

山东师范大学游戏前端

二维前缀和+二维差分（模版）

设a为原二维数组、c为二维前缀和、b为二维差分 1.（x1,y1)-(x2,y2)的查询用二维前缀和 二维前缀和的构造：c[i][j] = c[i-1][j] + c[i][j-1] - c[i-1][j-1] + a[i][j] （x1,y1)-(x2,y2)的查询：结果 = c[x2][y2] + c[x1][y1] - c[x1][y2] - c[x2][y1]  2.（x1,y1)-(x2,y2)范围内的值++，用二维差分 二维差分数组的构建：b[i][j] = a[i][j] + a[i-1][j-1] - a[i][j-1] - a[i-1][j] 二维差分数组的更新：（x1,y1...

0 点赞评论收藏

分享

2020-10-27 14:47

山东师范大学游戏前端

二维前缀和

我们用map[i][j]记录每一格的值、用DP[i][j]表示（1，1）这个点与（i,j）这个点两个点分别为左上角和右下角所组成的矩阵内的数的和。 转移方程：DP[i][j]=DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + map[i][j] DP[i][j]可以由DP[i-1][j]、DP[i][j-1]两块构成,注意：1.有一块矩阵重复了，我们要减掉这一块-> DP[i-1][j-1]2.有一小块没有加上，也就是map[i][j]这一个点，所以我们要再加上map[i][j]这一格的数. 那么如何计算以(x1,y1)为左上角，以(x2,y2)为右上角的...

0 点赞评论收藏

分享

2020-10-28 19:16

已编辑

山东师范大学游戏前端

差分和前缀和互为逆运算，即差分数组的前缀和数组为原数组，前缀和数组的差分数组为原数组。两者都利用了容斥原理，这一点在二维平面（或二维数组）中体现的更加明显。  一维差分  定义：差分就是将数列中的每一项分别与前一项数做差。 例子：一个序列1 2 5 4 7 3，差分后得到1 1 3 -1 3 -4 -3 性质：1.差分数组求前缀和可以得到原序列2.将愿序列区间[L,R]中的元素全部+1，可以转化操作为差分数组L处+1，R+1处-1.3.按照性质2得到，每次修改原序列一个区间+1，那么每次差分序列修改处增加的和减少的相同。  二维差分  其实二维差分和一维差分一样，就是更新时一维是更新两个点，二...

0 点赞评论收藏

分享

2020-10-26 21:31

山东师范大学游戏前端

I-Walking Machine

我是用DFS做的这道题，里面有很多细节记录一下。 试题链接：https://ac.nowcoder.com/acm/contest/7501/I #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include...

0 点赞评论收藏

分享

2020-10-25 15:56

山东师范大学游戏前端

指数型枚举

从1～n中随机选择数输出（可以什么也不输出），请输出所有的可能，每种可能占一行。（n最大值是16） 思路：一共有2^n种可能，可以用二进制解决。 #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include...

0 点赞评论收藏

分享

2020-10-21 20:06

山东师范大学游戏前端

set牛逼，简单记录一下set的find函数，因为set是红黑树维护的，且set里面的元素是按照从小到大排序的，所以set的find函数比vector的find函数省很多时间复杂度。 vector的find函数还要用到迭代器，而set可以直接.find()就可以了（更加方便），里面不写范围，固定是一整个set范围。 例子：  if(s.find(想要查找的元素)==s.end()) { s.insert(想要查找的元素); }

0 点赞评论收藏

分享

2020-10-21 21:26

已编辑

山东师范大学游戏前端

2020.10.18新生赛

A - Multiple of 9 C - Walk on Multiplication Table * E - Maximal Value * A、C 、E题为上次比赛原题，所以只做出三道题来的可以好好想想。 B - Where is the Marble?题意：给你n个数字，再给你m次查询，每次查询一个数字，问你这个数字在所有数字中排第几，如果不存在，输出这个数not found。 思路：这道题我用到了lower_bound()，有三个参数，前两个数查询的区间，第三个参数是要查询的数字x。返回的是大于等于x的地址，如果不存在，则返回最后的区间。如果想要详细了解lower_bound()可以...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客企业服务