998244353 - 个人主页动态 - 牛客网

发布(150) 评论刷题收藏

2020-05-08 14:30

门头沟学院后端

高精度乘法（仅整数位）

All in code.  //实现任意位的大整数相乘，修改N和M即可 #include<stdio.h> #include<string.h> const int N = 10010; const int M = 2 * 10010; char sn1[N], sn2[N]; int n1[N], n2[N], res[N]; void big_mul(int len1, int len2){ int i = 1, j = 1, x = 0; /*根据模拟乘法得到，将每个乘数的每一位从个位开始从1开始标序号 如数"89"中，9为第一位，8为第二位 ...

0 点赞评论收藏

分享

2020-05-08 14:30

门头沟学院后端

POJ2488简单DFS

本题是一个比较基础的DFS问题，但是坑点也有很多 1.字典序输出   2.如何处理输出过程中的字母的输出问题 AC后的恍然大悟： 本题要求的是棋盘的所有位置都必须经过一遍，且搜索是无方向性的。所以无论从哪个点开始，我们都必须经过每一点一次。（因此深搜只需一次） 而字典序最小的当然是从最左上角开始咯，我们只需要从(1,1)点开始深搜使所有点都被搜了一遍即可。如果无法搜完全部点，则impossible，否则输出   技巧：本题使用方向向量确定深搜的8个位置，注意，我们要将8个位置按照字典序大小排序，方便搜索时直接按序搜索即可   贴下AC代码：  #include<iostream> ...

0 点赞评论收藏

分享

2020-05-08 14:30

已编辑

门头沟学院后端

线性筛一般是接近线性的速度去进行素数筛，所以时间接近O(n) 而线性筛的原理是处理掉埃筛的不完美问题，即使被重复筛选过的数只被筛选过一次 而每个大于等于2的数都具有的特性是每个数都可以分解为n个素数相乘，即唯一分解定理。   结合代码实际来看：  const int N = 20010; int cnt = 0;//素数个数 int prime[N];//素数集合 bool ispri[N] = {true, true};//素数的判定集合，0和1不是素数 void EulerPrime(){ for(int i = 2; i < N; i++){ //如果是素数，放入素数集合中 if(...

0 点赞评论收藏

分享

2020-05-08 14:29

门头沟学院后端

欧拉函数及其快速打表

超棒的欧拉函数讲解：https://blog.csdn.net/ydd97/article/details/47805419 下面的大部分都是借鉴这位大佬的，加了点自己的理解。   我就比较懒，直接贴代码了。（讲解都在注释中）  /* 欧拉函数的作用：用于求小于n的与n互质数的个数 欧拉函数的公式： φ(n)=n*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…..(1-1/pn), 其中p1, p2……pn为n的所有质因数，n是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。 1-1/pi = (pi-1)/pi */ const int N = 10001...

0 点赞评论收藏

分享

2020-05-08 14:29

已编辑

门头沟学院后端

hdu5750 Dertouzos （线性筛加思路）

题意：给你数n和d，让你求小于n的数中，以d作为最大因子的数有多少个。 我们简单分析可得，这个数范围必定是 d + 1到n - 1。   本题刚开始就会被数据范围所限制，开1e9的数组显然不行，而这题作为一道练习题想到了线性筛。 但是不管怎样开1e9的数组是不合理的，所以就分析题意，果然，d作为数的最大真因子有 d * x = num（<n） 且x一定是个大于1的质数，即x一定是数的最小质因子，那么我们可以得到x的范围 即x <= d 且 x <= (n - 1) / d 即xmax = min(d, (n - 1) / d);   那么我们只需枚举小于等于xmax的素数即可...

0 点赞评论收藏

分享

2020-05-08 14:29

门头沟学院后端

哈希表与字符串哈希

哈希表是一种非常带劲的存储方法，它将一定个数内的数据以一种降低数据规模的方式存储着，哈希表的主要操作就是添加数据和查找数据，当然你也可以用标记来标记数据是否被删除（实际上，它只是被你标记删除了，并未被实际删除并释放内存）   上模板题让我们直观感受下： Acwing840 模拟散列表：传送门 ：https://www.acwing.com/problem/content/842/ 这题就让我们实现了哈希表的存储和查找： 比较好用的两种方法：拉链法和开放寻址法   1.拉链法 一个节点上存储着 取模后位置相同的数据，由于存储位置相同，为避免矛盾，采用拉链法将其以拉链形式展开存储 首先创建存储位置...

0 点赞评论收藏

分享

2020-05-08 14:28

已编辑

门头沟学院后端

树和图的存储与遍历

存储： 如a与b之间的边的存储 1.有向图。如果给出边的方向为a→b，则建立一条由a指向b的边即可 2.无向边。给出两点a与b之间存在一条边，则a→b和b→a全部成立，那么我们需要建立一条由a指向b的，一条由b指向a的边。   存储具体实现方式：一、使用邻接矩阵。 开二维数组以二维数组的两个下标指定边的指向，二维数组的初始化为-1，数组元素的值代表边的权重。但这种方法可能会浪费大量空间。   二、使用邻接表。 开一个一维数组记录每个点，以他们作为头结点作单链表存储与该点存在边的所有点。 更常用的是邻接表，较为省空间。   遍历：每个点只会被遍历一次。无需刻意从某个点开始遍历，因为树是无环连通图...

0 点赞评论收藏

分享

2020-05-08 14:28

门头沟学院后端

传送门：https://blog.csdn.net/qq_41713256/article/details/80805338

0 点赞评论收藏

分享

2020-05-08 14:28

门头沟学院后端

堆（priority_queue）及其手动模拟

C++STL中默认的优先队列是大根堆，即父结点总是比子结点大。 那么priority_queue<int> PQ即声明一个int型大根堆 如果想要声明一个小根堆则需要这么声明priority_queue<int, vector<int>, greater<int> > pq。 我们知道堆的模型就是完全二叉树（定义看不懂的自行补课） （完全二叉树：如果二叉树的深度为k，则除第k层外其余所有层节点的度都为2，且叶子节点从左到右依次存在。也即是，将满二叉树的最后一层从左到右依次删除若干节点就得到完全二叉树。满二叉树是一棵特殊的完全二叉树，但完全二叉树不...

0 点赞评论收藏

分享

2020-05-08 14:27

门头沟学院后端

scanf输入字符与字符串的一些问题

输入字符(%c)https://blog.csdn.net/qq_41282102/article/details/80246701 输入字符串(%s)   注意：之后单个字符可以使用char op[2]用char输入，多个字符还是老老实实用%c中间手动用空格做分隔符

0 点赞评论收藏

分享

2020-05-08 14:27

已编辑

门头沟学院后端

中国剩余定理

https://blog.csdn.net/qq_40772692/article/details/81872831

0 点赞评论收藏

分享

2020-05-08 14:27

已编辑

门头沟学院后端

即对增广矩阵进行初等行变换，将其转换为行最简阶梯形矩阵 AX = B与C(标准型)X = D是同解方程组。 来看算法实现过程： 有矩阵我们来进行初等行变换 一、先来枚举每一列： ①枚举第一列 1.找到第一列中绝对值最大的一行，这里即2 1 -3 -9这行 2.将绝对值最大的一行与第一行交换得到 3.将第一行第一个数变为1，得到 4.将下面所有行的第一列消成0，得到 这时候第一行已经固定了，所以接下来我们要从第二行开始的其他不固定的方程中寻找到第c列中绝对值最大的行。   ②枚举第二列 1.找到第二列中绝对值最大的一行（注意此时第一行已经固定，因此我们只能从第二行开始寻找）即0 3/2 1/2 ...

0 点赞评论收藏

分享

2020-05-08 14:26

门头沟学院后端

NIM游戏——博弈

这里默认两方均采取最优策略 1. 尼姆博弈 n堆石子，每堆的数量a1，a2，a3...an，一方取完后石子个数为0则该方获胜，问先手是否必胜 if ans = a1^a2^a3^...^an ≠ 0 先手必胜 else 先手必输   延伸1：在此问基础上添加一个集合，集合内的数字是每次操作可取的石子个数，每次从一堆中取，最后无法取者判输 对每堆石子算得其sg函数，sg函数异或后不为0，则先手必胜 否则先手必输   延伸2：在此问基础上添加一个条件：每次从不超过k堆中取任意多个石子，最后无法取者判输（Moore' s Nimk） 将每堆石子数换算为二进制，计算出二进制中每位的个数x mod (k...

0 点赞评论收藏

分享

2020-05-08 14:26

已编辑

门头沟学院后端

HDU6703 Fishing Master

比赛的时候想的是尽量先炖鱼，果然还是赛后牛逼，反应过来无论怎样总时间内一定有所有的炖鱼时间，所以只需要尽量缩减我们的钓鱼时间即可。 一、在炖鱼时间内可以把所有鱼都钓上来，那ans = k + t[1~n] 二、不能在炖鱼时间内把所有鱼都钓上来 即每次钓一条鱼上来后，鱼都会煮过。 如钓鱼时间为2，炖鱼时间为1，钓鱼上来后，炖的鱼煮过了1分钟。 而钓鱼时间为2，炖鱼时间为3，钓第一条鱼上来后，鱼还没煮熟，钓第二条鱼后才煮过1分钟，因此这时候可以在炖鱼时间内不花多的时间钓上来至少一条鱼。   由于我们可选择钓上来的鱼的先手顺序，因此我们可在煮鱼时间在x = (1~k-1)内尽量大的鱼中选择，即选择k...

0 点赞评论收藏

分享

2020-05-08 14:25

已编辑

门头沟学院后端

2019徐州网络赛K

算是学了下map的用法 题意就是找到最多的中心点，然后剩下就是得到没有匹配到最多中心点的数，这就是需要添加的点数  #include<bits/stdc++.h> using namespace std; typedef pair<int, int> PII; typedef map<PII, int> MII; MII::iterator iter; const int N = 1010; PII p[N]; MII M; int n; int main() { scanf("%d", &n); for(int i = 1; i...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客企业服务