zzu_lmc

未归档

acm(2) codeforces(5) java(3) leetcode(1) other(1) 博弈论(2) 并查集(1) 数论(1) 水题(1) 百度之星(1) 算法(44) 莫比乌斯反演(1) 计算几何(1) 贪心(3)

/ 注册

全部文章 / 未归档（共133篇）

51nod 1289 大鱼吃小鱼栈模拟

就是用栈进行模拟，只有两条鱼相向而行才能进行相消操作，第一次写do-while循环条件写错了，wa一次。。 #include<cstdio> #include<stack> using namespace std; const int maxn = 100003; str...

2018-08-05

0 388

51nod 1091 线段重叠的问题

重点是维护当前扫过的最远的（最右）的点，排序之后贪心扫一遍，ans=max(ans,min(p[i].r,last)-p[i].l),last = max(last,p[i].r); 重叠部分就是min(p[i].r,last)-p[i].l #include<cstdio> #i...

2018-08-04

0 379

牛客多校 G-max

题目描述给定两个正整数 c,n，求一个数对 (a,b)，满足 1<=a,b<=n，且 gcd(a,b)=c 要求输出最大的 ab 1<=c,n<=10^9 思路：首先如果 c> n 那么无解其次 a 和 b 一定都是 c 的倍数，如果 c>n/2，那么...

2018-08-02

0 318

牛客多校（第五场）E room

将一个房间当做一个点，后来的房间与之前的房间中不用搬的人作为权值，建图，跑最大权匹配，就是不用搬的人数，在减一下即可，KM算法，O(n^3） #include<cstring> #include<cstdio> #include<iostream> #i...

2018-08-02

0 473

计算几何 51nod1298圆与三角形

挺基础的一道题就是情况比较多，细节也比较多，代码里有注释 #include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f #define emin 1e-10 #define ll long long #def...

2018-08-02

0 331

51nod 1240莫比乌斯函数

打表会爆只能判断单个 #include<bits/stdc++.h> using namespace std; int mu(int n) { int m = 0; for(int i = 2; i*i<=n; i++){ if(n%i==0)...

2018-07-31

0 378

51nod 1183 编辑距离问题（dp）

编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。例如将kitten一字转成sitting： sitten （k->s） si...

2018-07-31

0 318

dp测模板ORZ 51nod 1134最长递增子序列

在劝退边缘徘徊…… 复习了下lower_bound 和 upper_bound #include<bits/stdc++.h> using namespace std; const int maxn = 1e5; int dp[maxn]; int a[maxn]; int len=...

2018-07-30

0 349

dp练习 51nod1049最大字段和

注意初始化 #include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 5e4+4; ll a[maxn]; int n; ll dp[maxn]; ll ans; int m...

2018-07-29

0 256

dp训练 51nod 1006

先跑一遍lcs得到最长公共子序列长度，再倒着跑一遍记录路径，即dp[i][j]刚开始发生改变的地方 #include<bits/stdc++.h> using namespace std; const int maxn = 1010; char s1[maxn],s2[maxn],p...

2018-07-29

0 288