Deep_Dark_FAntasy♂ - 个人主页动态 - 牛客网

发布(240) 评论刷题收藏

2020-09-23 17:27

清华大学算法工程师

Codeforce Round #632(Div2）2019/4/9：

A. Little Artem Young boy Artem tries to paint a picture, and he asks his mother Medina to help him. Medina is very busy, that’s why she asked for your help. Artem wants to paint an n×m board. Each cell of the board should be colored in white or black. Lets B be the number of black cells that have a...

0 点赞评论收藏

分享

2020-09-23 17:26

已编辑

清华大学算法工程师

[Andrew凸包]Surround the Trees

Andrew求凸包裸题。 注意：这题WA点就是凸包如果只有一个点的时候，输出0，两个点的时候输出距离。 Andrew算法无法处理这两种特殊情况！

0 点赞评论收藏

分享

2020-09-23 17:26

清华大学算法工程师

除法表达式草稿

#include<bits/stdc++.h> using namespace std; const int N=1e6+7; char s[N]; string vs; int x[N/10]; int gcd(int a,int b) {  return b==0 ? gcd(b,a%b) : a; } int main() {  int n,vx,i; scanf("%d",&n); while(n--){  scanf("%s",s); int len=strlen(s); for(int i=0; i<len; i++...

0 点赞评论收藏

分享

2020-09-23 17:25

已编辑

清华大学算法工程师

无平方数草稿

#include<bits/stdc++.h> using namespace std;、 typedef long long ll; const int N=3e6+7; bool vis[N]; int main() {  int n,m; scanf("%d%d",&n,&m); int k=sqrt(m+0.5); memset(vis,0,sizeof(vis)); for(int i=2; i<=k; i++) if(!vis[i]) //从谁开始筛 //遍历  for(int j=i*i; j<=n; j+=i) //筛...

0 点赞评论收藏

分享

2020-09-23 17:25

清华大学算法工程师

例题：10-3 不爽的裁判

暴力枚举a，b #include<bits/stdc++.h> using namespace std; #define mod 10001 int x[300],a, b, t; //Ã¶¾Ùa£¬b void solve() {  bool flag; for(int i=0; i<=10000; i++) for(int j=0; j<=10000; j++) {  flag=1; a=i; b=j; for(int k=1; k<=2*t-1; k++) {  if((k+1)&1&&((a*x[k])%mod+b)%mod!=x[...

0 点赞评论收藏

分享

2020-09-23 17:25

已编辑

清华大学算法工程师

多重集的全排列

参见：多重集的全排列

0 点赞评论收藏

分享

2020-09-23 17:24

清华大学算法工程师

vector复合使用简单示例

#include <iostream> #include <vector> using namespace std; int main() {  vector<vector<int>> A; vector<int> B; B.push_back(0); B.push_back(1); B.push_back(2); B.push_back(3); A.push_back(B); //注意需要清空B B.clear(); B.push_back(4); B.push_back(5); B.push_back(6); B.push_bac...

0 点赞评论收藏

分享

2020-09-23 17:24

已编辑

清华大学算法工程师

map按值排序(众所周知map按key排序，但按值怎么排序呢)

map按值排序 map的两个值分别为key值和value值，map是按照key值进行排序的，无法直接对value排序。可以将map的key和value组成一个新的结构PAIR，用一个PAIR型的vector存储map中的所有内容，对vecor按照value值进行排序。按顺序输出key。 //map按值排序 #include <iostream> #include <string> #include <vector> #include <map> #include <algorithm> using namespace std; typ...

0 点赞评论收藏

分享

2020-09-23 17:24

清华大学算法工程师

5.16 (数论)E. Zeldain Garden解题报告

题目大意: 输入n,m , 计算[n,m]范围内的每个数的因子个数的总和。 数据范围n,m在1e12左右。 区间这么大，处理方式就是对区间端点的维护。 设置一个函数R(N)来计算[1,x]范围内的每个数的因子个数的总和，分别计算出R(m)和R(n-1)，二者一减，便得到题目需要的n~m区间的了。 再来处理一下时间复杂度，大数通常的处理思路就是计算到sqrt为止，复杂度：O(√n)。 思考过程： 小于sqrtN的因子在所有数中有多少：∑N/i (i=1,…,sqrtN) 大于sqrtN的因子在所有数中有多少: ∑N/i (i=1,…,sqrtN) 这里有重复！ “因子对”里的数都小于sqrtN的...

0 点赞评论收藏

分享

2020-09-23 17:23

已编辑

清华大学算法工程师

枚举 1.特点：一一列举 2.要点：不重复不遗漏 但是不充复不遗漏只能保证把题目求出来，但可能会被时间卡住 3.优化：把多余的操作去掉，减少枚举次数 ①选择合适的枚举对象 ②选择合适的枚举方向——方便排除非法和不是最优的情况 ③选择合适的数据维护方法——方便转化问题 最大正方形 --题目和图片来自https://blog.csdn.net/qq_46009744/article/details/106142716 题目描述： 在一个N*N(N<=100)矩阵中求一个最大的正方形使得该正方形的四个顶点都是有字符“#”构成。  暴力枚举四个点的话，是个4重循环，n^4 , 如果矩阵中每个点都...

0 点赞评论收藏

分享

2020-09-23 17:23

已编辑

清华大学算法工程师

尺取法枚举区间

尺取法也叫(追逐法 、 two pointer) ,顾名思义，像尺子一样，一块一块的截取。尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以说尺取法是一种高效的枚举区间的方法，是一种技巧。用尺取法来优化，可以使复杂度降为O(n)。是不是解释的有点让人纳闷～。。没关系，下面我们通过这个题目来体会尺取法的魅力。 题目内容：   给定长度为n的数列整数a0,a1,a2,a3 … an-1以及整数S。求出综合不小于S的连续子序列的长度的最小值。如果解不存在，则输出0。 这里我们拿第一组测试数据举例子，即 n=10, S = 15, a = {5,1,3,5,10,7,4,9,2,8} 尺取...

0 点赞评论收藏

分享

2020-09-23 17:23

清华大学算法工程师

贪心 P1223 排队接水

题目描述 有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。 输入格式： 输入文件共两行，第一行为n；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。 输出格式： 输出文件有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。 分析：虽然说让算平均等待时间最小，但实际上应当去分析等待时间的总合最小。 第一个人等待时间: 0 , 第二个人等待时间T1……以此类推， 第n个人等待时间就是 T1+T2+……+Tn-1， ...

0 点赞评论收藏

分享

2020-09-23 17:22

已编辑

清华大学算法工程师

博客主阵地已搬家至牛客

欢迎访问：https://blog.nowcoder.net/lirongao

0 点赞评论收藏

分享

2020-09-22 21:58

清华大学算法工程师

单调栈+dp Discrete Centrifugal Jumps

题目链接：https://vjudge.net/contest/396106#problem/B思路：这题显然是个dp，dp的思路也很简单~，就是dp[i]为到i的最短跳跃数，我们来主要分析一下它的状态转移方程dp[i]能从三种情况转移过来，1.dp[i-1] 2.dpj13.dpj2？？那么显而易见，从j1+1到i都是i最小，这不就是单调栈干的事情嘛？单调栈是解决以某个数为最小/最大的区间。这里需要注意，我在单调栈里去dp转移的时候,由于我栈的判断条件，导致我会对与我栈顶相同的一连串元素都转移，但按照题目是转移不过来的。代码： #include<bits/stdc++.h> us...

0 点赞评论收藏

分享

2020-09-23 16:48

已编辑

清华大学算法工程师

拉格朗日插值练习1

题目链接：https://codeforces.com/problemset/problem/622/F拉格朗日插值入门题，请熟悉一下要怎么传参就行update:注意虽然原理上是说要k次多项式的前k+1个值，但用模板的时候是a[i]的前k+1个值 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9+7; ll powmod(ll a, ll b){ ll ans = 1; while(b > 0){ if(b & 1){ ans = ans * a...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务