- 博客(519)
- 收藏
- 关注
RSS订阅原创 Codeforces Round #488 by NEAR (Div. 2) B. Knights of a Polygonal Table
k最大是10， 按照power排序后 维护每个位置的前k大，注意k为0的情况#include <bits/stdc++.h>using namespace std;const int maxn = 1e6 + 10;const int N = maxn;typedef long long ll;#define gcd __gcdstruct Node{ ...
2018-06-17 07:48:12
406
原创 Codeforces Round #487 (Div. 2) C. A Mist of Florescence
问题： 构造出一个n*m的网格使得其包含 ‘A’,’B’,’C’,’D’的块， 他们的个数分别是a,b,c,d（大于1，小于100） 同一块的定义是2个格子有公共的边，而且他们的颜色也是相同的， AA：是一个块， AB是2个块，A是一个，B是一个。构造的网格最大是50*50的，输出任何一个结果都可以 结合数据范围，可以考虑 ‘A’作为背景， 在A上填b-1个‘B’， ‘B’作为背景，在...
2018-06-13 19:09:45
285
原创 LeetCoder 33. Search in Rotated Sorted Array(二分)
是把一个升序的数组，前面的连续的一部分（可以是空）放在数组的后面，然后再这个数组这中找一个给出的值，数组中不存在重复的元素。 这个题目也是《剑指offer》二分查找的一道例题class Solution {public: int search(vector<int>& nums, int target) { int l = 0, r = nums.size()-1;
2017-08-15 10:43:55
400
原创 MySQL 报 Unknown or incorrect time zone: 'Asia/Shanghai' 错
一般是因为mysql中缺少了关于timezone的表 可以到http://dev.mysql.com/downloads/timezones.html下载对应版本的sql语句 一般是下载posix标准的那张表 解压之后， 再终端 登陆mysql 查看mysql的版本在终端直接 输入mysql -V //未登录进mysql的时候mysql -u root -p密码use m...
2017-07-12 15:08:11
8192
1
原创 Laravel mysql 添加外键失败
在是用laravel 数据库模型的时候， 添加外键 遇到了错误， 提示不能添加外键。解决这个问题需要知道mysql 关于外键的要求。 1) 外键在来源的表中必须是主键 2) 添加外键的表，字段的类型必须和外键来源表的字段类型一样。 比如 users表主键是id, infos表 外键user_id, 那么user_id 必须和 id 的类型一样在lara
2017-04-18 23:55:36
1674
1
原创 Laravel 5.4 Eloquent 定义 复合主键(报Illegal offset type错)
Elopuent 默认是定义整数id 自增为表的主键，但是如果我需要2个段或者更多的时候。需要在对应的model里面定义protected $primaryKey = ['字段 1'，'字段2', '字段..']; public $incrementing = false;如果自定义第一个，那么会到的 一个 错误为：Illegal offset type
2017-04-08 16:29:21
5247
原创 Xml 文件解析 & 等特殊字符报错
工作小计在xml文件中，有一些符号是具有特殊意义的，如果直接使用会导致，xml解析报错，例如<,xml解析器会把小于号当做标签的开始，因此会导致错误，为了避免错误，我们需要将特殊的字符使用其对应的转义实体进行操作。这些字符如下表 特殊的字符 对应的转换实体 < < > > & & ‘ ' “ "可以看出&会用来进
2017-03-15 17:01:02
5959
原创 LeetCode #3. Longest Substring Without Repeating Characters
题意： 计算一个字符串的中的最长的不含有重复字母的长度 解法： 尺取法的裸体了，维护2个指针l,r, 不断移动r指针，同时检查[l,r]是不是存在重复的了，如果存在就移动l指针了class Solution {public: int lengthOfLongestSubstring(string s) { int n = s.size(); int l=0
2017-02-16 23:07:24
280
原创 C/C++ 内存对齐规则
记录学习c++中遇见的一些常见的易错的知识点等最近在牛客网刷题的时候经常会遇到关于内存对齐的问题有以下的代码， 结果会输出什么呢，我们知道int是4个字节，short是2个字节，char是1个字节，那么二者是不是都是一样的，都是7呢？ 其实都不是，我的编译器默认是4字节对齐，所以第一个是12，第二个是8#include <stdio.h>struct A{ char a; int
2017-02-10 12:48:53
383
原创 BZOJ 3732: Network（最小生成树+倍增）
题目链接 题意：给出一个图，每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少很明显最终查询的边一定是在最小生成树里面的，先跑出最小生成树，然后，可以树链剖分，也可以使用倍增来计算#include<bits/stdc++.h>using namespace std;#define cl(a,b) memset(a,b,sizeof(a))#define sz(x
2016-12-01 11:47:43
418
原创 poj 1986 Distance Queries (LCA 倍增)
题目链接 题意：给出一颗带权树，询问点对(u,v)路径上的取值和 可以使用 树链剖分做，是没有更新的查询很简单，今天学下倍增计算lca，使用倍增做一下，先dfs跑出树的每个节点的深度，以及每个节点的2的次幂的父亲节点，然后就暴力跑一跑，题目给出的树可能是不连通的#include<stdio.h>#include<cstring>#include<vector>using namespac
2016-12-01 11:30:32
378
原创 TYVJ P1463 智商问题(二分)
题目链接 先按照智商大小排序然后，写一个类似于lower_bound二分函数去找 这里有以前写的二分#include<bits/stdc++.h>using namespace std;#define rep(a,b) for(int i=(a);i<(b);i++)const int maxn = 1e6+6;struct node{ int x,id; bool oper
2016-11-30 15:45:58
315
原创 HDU 1421 搬寝室 (dp)
题目链接 题意：给出n个数，每次选择出来k对(x,y)，代价是(x-y)的平方，然后问代价最小的取法。 首先肯定的是，选择排序之后再一起的代价应该是比较小的，但是会有1 2 34 35 36 这样的情况，1-2间距小，但是2-34很大。用dp[i][j]:{\rm{dp}}[i][j]:表示前i个数据中选择j的最小代价,考虑第i个要么选择要么不选择，不选择就是dp[i−1][j]dp[i - 1
2016-11-29 18:25:17
282
原创 SPOJ 7001 Visible Lattice Points(莫比乌斯反演)
题目链接 题意：三维空间，从原点能看到哪些点，也就是gcd(x,y,z)==1 莫比乌斯反演计算即可 定义：f(x):gcd(x,y,z)==kf(x):\gcd (x,y,z) = = k的个数，F(k):gcd(x,y,z)=kF(k):\gcd (x,y,z) = k的倍数的个数，那么 F(n)=∑n|df(d)F(n) = \sum\limits_{n|d} {f(d)} f(
2016-11-02 14:47:45
279
原创 POJ 3090 Visible Lattice Points(莫比乌斯反演)
题目链接 题意：给出一个n*n的格点，从原点发射出的光线，能够照到的点的个数。 其实就是计算gcd==1 和gcd==0(2个坐标轴)gcd==1直接莫比乌斯反演做好了，小数据不用分块优化也可以#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;#define cl
2016-11-02 14:03:46
349
原创 BZOJ 2818: Gcd (莫比乌斯反演)
题目链接 题意：给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的 数对(x,y)有多少对.会了上一道题，那么这道题就是枚举[1,N]的素数，然后每个素数跑一遍就好了#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;#define cl(a,b) mem
2016-11-02 12:47:35
306
原创 BZOJ 2301: [HAOI2011]Problem b（莫比乌斯反演，分块，容斥）
题目链接 题意：对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。和HDU1695基本是类似的，这道题如果还是使用之前的方法计算f(k)=∑k|du(dk)F(d)=∑k|du(dk)⌊Bd⌋⌊Dd⌋f(k) = \sum\limits_{k|d} {u({d \over k})F(d) = \sum
2016-11-02 11:28:01
297
原创 HDU 1695 GCD（莫比乌斯反演，入门）
题目链接 题意：从区间[a,b]选择一个x,从区间[c,d]选择一个数y，使得gcd(x,y)==k 的方案数。 莫比乌斯反演学习资料 1，文库2，百科莫比乌斯反演学习 纯属个人理解，错误之处还望指正。莫比乌斯反演就是两个函数之间的关系，感觉类似函数中的反函数，莫比乌斯反演是数论中一个比较重要的公式，用于简化加速计算。 公式是： F(n)=∑d|nf(d)⇔f(n
2016-11-01 23:28:43
1632
原创 Manthan, Codefest 16 H. Fibonacci-ish II (暴力)
题目链接 题意：给出n个数，一个m， q个询问区间[l,r] ，问区间里面的数排序去重后 f[1]* a[1]+f[2] *a[2]+… %m的结果暴力#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;#define cl(a,b) memset(a,b,size
2016-11-01 13:46:20
351
原创 Kattis A+B Problem（FFT，计数）
题目链接题意：给出n个数，(i,j,k)i,j,k互不相同，使得a[i]+a[j]=a[k],问这样的三元组有几个。（HK网赛的第一题，当时xjb写的一直wa，今天学FFT，突然遇见他） 其实就是计算数组的a+b的值的个数，这个就是卷积了，FFT搞一下。 题目的数据是有负数的，加上一个偏移，全部变为非负的，一开始的时候把0单独分开，最后在统计0的贡献。#include<cstdio>#inc
2016-10-31 23:20:50
527
原创 CDOJ 1314 Hash Perfectly（FFT，计数）
题目链接 题意：给出一个数组，和一个上限limit，问在1到limit之间找一个k使得数组对k哈希后的，ASL 最小。想使ASL最小，那么就是冲突最小，冲突的产生是a%k==b%k,也就是(a-b)%k==0,问题就变为了计算a-b的值的个数，a-b可以看成a+(-b)我们加上一个偏移使得-b变为正数，然后FFT计算下。#include<cstdio>#include<cstring>#in
2016-10-31 20:23:24
325
原创 Educational Codeforces Round 9 E. Thief in a Shop (FFT,计数)
题目链接 题意：给出n个数字，从中选出k个的，这个k个数的和能够组成哪些数这个题目和HDU4609差不多，不过这道题是选择k个，所以做k次卷积，使用类似快速幂，中间用FFT计算卷积。#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;#define cl(a,b)
2016-10-31 16:25:18
306
原创 HDU 4609 3-idiots（FFT,计数）
题目链接 题意：给出n个长度，问任意选择出来3个能形成三角形的概率FFT学习中，由卷积的定义,设一个多项式A(x)，其中x^k的系数ak 就是表示长度是k的个数，那么B(x)=A(x)*A(x)，B(x)的x^k系数bk就是A(x)系数对应的集合中，可以重复选择组合为k的种类数。利用这个 ，然后再去重处理。 详解HERE#include<cstdio>#include<cstring>#i
2016-10-31 11:34:31
287
原创 HDU 1402 A * B Problem Plus (FFT入门，高精度乘法)
题目链接 题意：计算高精度的A*BFFT 来搞一下，学习的链接 1）http://www.gatevin.moe/acm/fft%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/2）http://www.cnblogs.com/kuangbin/p/3210389.html#include<cstdio>#include<cstri
2016-10-30 23:17:54
457
原创 CF 343D D. Water Tree(树链剖分，简单题)
题目链接 题意：给出一个树；三种操作 1 v 表示把v及其子树全部变为1 2 v 表示把v及其祖先全部变为0 3 v 查询v的值 数组尽管开吧，，， 然后，祖先就是1到该点，不要想太多- - 子树的编号在剖分的编号中是连续的，[p[x],p[x]+size[x]-1]#pragma comment(linker, "/STACK:102400000,102400000")//#inc
2016-10-29 14:55:55
603
原创 poj 3237 Tree(树链剖分，点权，线段树)
题目链接 题意：一棵树3个操作 1.chang i,v 把第i条边权值修改为v 2.negative a,b 把a到b权值取反 3.query a,b 查询a到b的边上的最大值 树链剖分就不说了，线段树，由于取反操作，所以我们同时记录下最小值，这样取反操作，就是最大的变最小了，最小的变最大了，附加一个懒惰标记。偶次反转是没变的。//#pragma comment(linker, "/STA
2016-10-29 12:21:28
289
原创 BZOJ 4034: [HAOI2015]T2（树链剖分，点权，线段树）
题目链接 题意： 有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个 操作，分为三种： 操作 1 ：把某个节点 x 的点权增加 a 。 操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。 操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。直接跑树链剖分，我们知道剖分的第二个dfs，我的代码是getpos 中，某一个节点的子树节点编号是连续的，所
2016-10-29 10:49:29
328
原创 BZOJ 2243: [SDOI2011]染色 (树链剖分，点权，线段树)
题目链接树链剖分，然后直接跑一遍，线段树//#pragma comment(linker, "/STACK:102400000,102400000")#include<bits/stdc++.h>using namespace std;#define cl(a,b) memset(a,b,sizeof(a))#define fastIO ios::sync_with_stdio(false)
2016-10-28 16:56:39
244
原创 poj 2763 Housewife Wind(树链剖分，边权)
题目链接 题意：给出一颗树，初始在s点，有2个操作0操作，表示求s到u路径和 1操作表示把第i条边权重变为w。树链剖分，然后用线段树维护就可以了//#include<bits/stdc++.h>#include<iostream>#include<cstdio>#include<algorithm>#include<vector>#include<queue>#include<sta
2016-10-27 22:29:40
261
原创 树状数组小记
原理就不说了 1）单点更新，区间查询，这个是基本的用法 2）反过来，区间更新，单点查询，也可以使用树状数组实现。 具体的过程是更新区间[l,r]的时候，更新add(l,x), add(r+1,-x) 这样sum(x)就是x点的值了。
2016-10-26 23:28:54
192
原创 线段树小记
关于线段树的叶子节点，连续与离散的2种情况A）连续的，比如[3,7]:就表示数轴上3到7这么一段。B）离散的，比如[3,7]:就是表示集合{3,4,5,6,7}二者在线段树上的区别是 1. A在线段树中的叶子节点是[l,l]，区间分开是[l,m],[m+1,r] 2. B在线段树中的叶子节点是[l,l+1],区间分开是[l,m],[m,r]等
2016-10-26 23:22:05
180
原创 HDU 3966 Aragorn's Story(树链剖分 点权，树状数组)
题目链接 题意：给出一棵树，每次把路径(u,v)上的点权都加上或者减去一个值，然后问某一点的值。 树链剖分，后面可以使用线段树，也可以使用树状数组。使用树状数组的话，因为是点权，要移到边权上，所以pos初始为1。树状数组，使用了区间的更新，单点查询。 具体的过程是初始化 add(i,x),add(i+1,-x) 这样sum(x)就是x点的值了。而不会是x的前缀和了//#include<bits
2016-10-26 18:35:09
300
原创 BZOJ 1036: [ZJOI2008]树的统计Count（树链剖分 点权）
题目链接 题意：给出一个树，告诉每个点的权值，然后有修改操作，还有询问(u,v)路径上的最大值，(u,v)路径的和树链剖分啦，一般分为点权和边权，剖分部分不变，只是用其他数据结构处理的时候注意一下，点权可以可以转换为该点与父边的权值，就变为了边权，这样就相于给根节点来了一个虚拟的父亲(代码中不用体现),对于剖分的学习，动手自己剖分一遍，就明白了，第二个dfs就是把重边连城链，其实就是给边编号，使得
2016-10-26 16:17:10
278
原创 HDU 4622 Reincarnation（字符串hash，hashMap，区间dp）
题目链接 题意：给出一个字符串，问区间的不同子串有几个 首先可以直接预处理出所有长度的字串的hash值，然后用区间dp维护。 区间dp的时候需要记录同一长度下的上一个相同hash值出现的位置，使用STL 的map会超时，所以需要手动写个hashMap，也就是hash加冲突处理。记录相同的hash上一次的位置//#include<bits/stdc++.h>#include<iostream>
2016-10-25 17:18:26
468
原创 UVALive 6893 The Big Painting（二维hash，暴力）
题目链接 题意：问第二个矩阵中有几个第一个矩阵 hash，这次是二维，单独看每一维进行hash即可，暴力的时候还是使用技巧的暴力，类似滑动窗口的原理，枚举每一个宽度，然后向下滑动即可，有前缀和的意思。//#include<bits/stdc++.h>#include<iostream>#include<cstdio>#include<algorithm>#include<vector>
2016-10-25 11:08:53
349
原创 CF D. DZY Loves Strings(字符串hash 暴力)
题目链接 题意：给出一个字符串，然后有q次询问，在字符串中找出最短的字串使其包涵询问的2个串。询问的串长度不大于4，暴力预处理一下，每个长度的子串在原串中的位置。然后在暴力计算，这里暴力计算也是有技巧的，因为预处理的数组是有序的所以这里暴力要使用线性的方法，具体是正着先找小于的，逆着找大于的。每次不要从头开始，因为有序，直接继续。//#include<bits/stdc++.h>#include
2016-10-25 00:05:28
394
原创 HDU 4821 String （字符串hash，技巧暴力）
题目链接题目：是说给出一个字符串有几个不同的长度是M*L的子串,他们是由m个不同的长度是l的子串构成。 字符串hash，把字符串转化为一个整数，同时对于字串可以O(1)计算出他的hash值，类似前缀和的性质，本题要保证相同的字串hash值是一样 的，所以hash函数 sum[i] = sum[i-1]*p+str[i];这样倒着来。 暴力的时候，枚举开头的L个位置，以他们为起点找，然后找够了m个
2016-10-24 19:18:50
310
原创 HDU 4287 Intelligent IME(字符串)
题目链接 题意：给出手机键盘每个数字能打出的字母，然后给出一个词的字典，同时，给出给出一个输入序列，问有多少个匹配的//#include<bits/stdc++.h>#include<iostream>#include<cstdio>#include<algorithm>#include<vector>#include<queue>#include<stack>#include<cs
2016-10-23 11:12:39
289
原创 CF C. Registration system (字符串)
题目链接 题意：一个字符串第一次出现就是ok，否则输出时第几次//#include<bits/stdc++.h>#include<iostream>#include<cstdio>#include<algorithm>#include<vector>#include<queue>#include<stack>#include<cstring>#include<set>#inclu
2016-10-23 10:44:08
333
原创 HDU 5904 LCIS（dp）
题目链接 题意：给出2个序列找出2个序列的最长的上升子序列，要求元素是连续的 使用dp[i]:表示数字i结尾的最长的连续的上升子序列长度。 dp[i] = max(dp[i], dp[i-1]+1)//#include<bits/stdc++.h>#include<iostream>#include<cstdio>#include<algorithm>#include<vector>
2016-10-22 00:10:35
257
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人