- 博客(71)
- 收藏
- 关注
RSS订阅原创 Python 文件操作
利用os模块编写一个能实现dir -l输出的程序。from datetime import datetimeimport ospwd = os.path.abspath('.')print(' Size Last Modified Name')print('------------------------------------')for f in os.lis...
2019-05-03 15:53:42
158
原创 [字符串专项] Manacher算法
Manacher算法算法过程分析参考资料 https://subetter.com/algorithm/manacher-algorithm.html由于回文分为偶回文（比如 bccb）和奇回文（比如 bcacb），而在处理奇偶问题上会比较繁琐，所以这里我们使用一个技巧，具体做法是：在字符串首尾，及各字符间各插入一个字符（前提这个字符未出现在串里）。举个例子：s=“abbahopxpo”，...
2019-03-29 22:22:59
139
原创 [字符串专项] 字符串Hash
单哈希 洛谷 3370#include <algorithm>#include <cstdio>#include <cstring>#include <iostream>using namespace std;typedef unsigned long long ULL;const int MAXM = 1511;const int...
2019-03-27 20:29:40
167
原创 [字符串专项] 基本IO及函数
基础IOcin & scanf读入以’\n’或’ '作为分割符.getlinegetline(cin, str);具体情境读入带空格字符串用gets().读入不带空格字符串用scanf, cin.C语言字符串处理函数strchr 字符查找原型 char * strrchr ( char * str, int character);在str中查...
2019-03-27 19:30:28
181
原创 [Data Structure] List 链表
1 指针实现链表#include<stdio.h>#include<stdlib.h>struct node{ int data; struct node *nxt;};void listInsert(int a, node *head, node *p, node *t){//注意指针类型 t = head; while(t != NULL){...
2019-03-10 16:57:50
137
原创 1.3 神奇的其他图论算法
1.3.1 拓扑排序用于有向无环图，做一些跟点层数有关的事情。Eg1.神经网络 先把u[i]预处理好，重点要好好读题#include<bits/stdc++.h>using namespace std;const int maxn = 110;int n, p, c[maxn], u[maxn], tot, st[maxn], ind[maxn], out[maxn];bool vi
2017-11-07 11:02:49
249
原创 1.2 最短路算法的多用
1.2.1 分算法之Dijkstra算法本质是贪心，一些不像图论的可贪心的让求关于单源的解的题也能用哦。不能解决负权边。Eg1.佳佳的魔法药水 一道看起来和最短路没啥关系的题，但是可以贪心啊，每次找一个值最小但却没有确定最小值的药水，将其标记为最小值，然后枚举能与此药水合成药水的药水，用找到的药水与配对的药水更新合成药水的最小值，和Dij相似。#include<bits/stdc++.h
2017-11-06 18:31:46
310
原创 1.1 并查集 & 最小生成树
1.1.1 并查集用以表示某些关系，包括在同一集合，在对立集合等。**Eg1.洛谷1196 银河英雄传说** 加权并查集。不仅要知道两点有没有关系，还要具体知道两点之间的点数量。因此需要siz[]维护祖先旗下的点的数量，dis[]维护到队头的数量。询问时输出abs(dis[x]-dis[y])-1即可。#include<bits/stdc++.h>using namespace std
2017-11-06 08:19:47
261
原创 模板大集结！
好久不碰OI了，最近决定把各种基础算法的模板和用法整理下。·SPFA -求瓶颈路 洛谷 1396 -求最短路 好多。。 -路上最值 洛谷 1073 -边的特殊处理 eg. 加入点出点 暑末Day2 T1 -判负环 可结合分数规划食用#include<bits/stdc++.h>using namespace std;const int maxn =
2017-09-09 21:52:57
302
原创 暑末 Day3 T1 Sum
//设n的逆元为k，x/n%moder == x%moder*k%moder%moder//运用等比数列求和公式 #include<iostream>using namespace std;typedef long long ll;const ll P=1e9+7;void open_file(){ freopen("sum.in","r",stdin); freopen
2017-08-29 17:51:03
306
原创 暑末 Day2 T3
//maxd表示根到叶子的最大距离//预处理maxd，即知需修改的长度 //to != fa #include<bits/stdc++.h>using namespace std;const int maxn = 500000;////const int inf = 0x3f3f3f3f;int n, tot, ans;int st[maxn], out[maxn], dep[max
2017-08-29 17:28:24
302
原创 暑末 Day2 T1 Azuki has to work
//考试的时候把终点当成了n...//如果需要在城市群 a 与城市群 b 之间连一条长度为 c 的无向边,则我们连长度为 c 的有向边 outa → inb 和 outb → ina.容易发现这样建出的图和原图中城市互相可达的情况是等价的 //#include <bits/stdc++.h>#define debug(x) std::cerr << #x" = " << (x) << std
2017-08-29 17:11:16
347
原创 SDOI 2013 直径
可以去洛谷看我的题解#include<bits/stdc++.h>using namespace std;const int maxn = 200010;int n, tot, far;long long maxd;int st[maxn], fa[maxn];long long dis[maxn];bool isol[maxn];struct node{ int v, w,
2017-08-28 22:17:24
293
原创 洛谷 2014 选课
//dp[i][j]是以i为根不算i的子树选j门课的学分 #include<bits/stdc++.h>using namespace std;const int maxn = 3030;int n, m, tot = 0;int dp[maxn][maxn], st[maxn], a[maxn];struct node{ int v, w, nxt;} edge[maxn];
2017-08-28 17:49:03
476
原创 暑末 Day1 Face
//伪概率DP#include<bits/stdc++.h>using namespace std;int hm, high, low, n, m, c, a, b, t;int delta;double dp[810][16001], sum[16001];inline int read(){ int num = 0; char c; while((c = get
2017-08-28 11:23:23
220
原创 HAOI 2008 木棍分割
//需要优化很多的DP，包括预处理前缀和，滚动数组，预处理可转移状态 #include<bits/stdc++.h>using namespace std;const int moder = 10007;const int maxn = 50010;const int inf = 0x3f3f3f3f;int n, m, tmp;int f[maxn], a[maxn], last[m
2017-08-28 10:59:18
333
原创 CodeVS 3012 & 3037 线段覆盖4 & 5
//dp[i]表示到枚举完i时的最优解//二分找前面的线段进行转移//!!!二分时将符合的答案先记下来以备作为结果，以l为答案会错 #include<bits/stdc++.h>using namespace std;const int maxn = 1000010;int n;long long dp[maxn];struct node{ long long l, r;
2017-08-26 22:04:34
258
原创 SDSC 2017 Day 5 T3
//dp1[i]是以i结尾的最长下降子序列的长度 //dp2[i]是以i结尾的...的方案数 #include<bits/stdc++.h>using namespace std;const int maxn = 5010;int n, ans, tot;int dp1[maxn], dp2[maxn], a[maxn];int main(){ scanf("%d", &n);
2017-08-25 12:06:09
267
原创 SDSC 2017 Day5 T2
//f[i]表示以i为根子树归零累加值，g{i]表示累减值//肯定是先搞定底部再搞上面 #include<bits/stdc++.h>using namespace std;const int maxn = 300010;int n, a[maxn], st[maxn], tot = 0;long long f[maxn], g[maxn];struct node{ int v,
2017-08-25 11:28:51
306
原创 SDSC 2017 Day 4 T3 Lift
//dp[i][j]表示从i层出发还剩j次坐电梯的方案数 #include<bits/stdc++.h>using namespace std;const int moder = 1e9 + 7;int n, a, b, k;long long sum[5010], start, end;int dp[5012][2];inline int read(){ int num = 0
2017-08-25 09:31:09
245
原创 洛谷 2680 运输计划
//二分+倍增LCA+树上前缀和//尽力缩小二分范围，能多拿分就多拿分//掌握树上前缀和的初始化和区间修改 //读入优化//二分答案，然后找出超出mid的计划，记录他们的公共重边，这里用树上前缀和找前缀和exc==超出计划数 的最大的边，删掉后再判断是否<=mid。 #include<bits/stdc++.h>using namespace std;const int inf = 0
2017-08-24 17:12:41
348
原创 CodeVS 1242 布局
//差分约束系统//以x-y <= k为例，等价于x <= k+y，相当于x和y之间的连边最大权值为k，然后跑最短路即知最大解。 //好久不做CodeVS了，洛谷大法好！#include<bits/stdc++.h>using namespace std;const int inf = 0x3f3f3f3f;queue<int> q;int n, m1, m2, tot;bool f
2017-08-24 10:46:16
259
原创 洛谷 2024 食物链
//对于某种特定的动物，世界上只有三种动物，同类、他吃的和吃他的，按三类的关系维护并查集即可，注意要三类转移，而不仅转移当前动物的 。 //i+n吃i，i+2*n吃i+n, i吃i+2*n #include<bits/stdc++.h>using namespace std;const int maxn = 50010;int n, k, ans;int f[3*maxn];inline
2017-08-23 21:57:44
261
原创 BZOJ 3831 Little Bird
//要熟练手写队列 //单调队列优化DP筛选转移点 #include<bits/stdc++.h>using namespace std;const int maxn = 1000010;int n, qut;int q[maxn], f[maxn], h[maxn];inline void getInit(){ memset(f, 0, sizeof(f)); mems
2017-08-22 22:02:22
225
原创 SDSC 2017 Day1 T2 && 洛谷 2652 同花顺
#include<bits/stdc++.h>using namespace std;int ans, tot, n;struct node{ int c, r;} a[100010], b[100010];inline bool cmp(node p, node q){//按花色排序 if(p.c == q.c) return p.r < q.r; return
2017-08-22 20:28:06
333
原创 NOI 2015 程序自动分析
//要先处理=再判断!= //离散化后并的是地址而非数值 //low_bound可查询特定数值所在的地址，和map差不多？//思考查找其他离散化的方法 #include<bits/stdc++.h>using namespace std;const int maxn = 100010;int n, t, tot;int f[2*maxn], e[2*maxn];struct nod
2017-08-22 20:24:28
264
原创 NOIP 2016 Day2 T3 愤怒的小鸟
//状压DP，(1<<n)-1相当于全集。 #include<bits/stdc++.h>using namespace std;const int inf = 0x3f3f3f3f;const double lit = 1e-6;int t, n, m;double a, b;int f[1048576], c[22][22];struct node{ double x, y
2017-08-22 11:58:16
362
原创 HOJ 2662 Pieces Assignment
新学状态压缩DP。 http://www.cnblogs.com/avril/p/3282295.html#include<bits/stdc++.h>#define LL long longusing namespace std;const int maxl = (1<<9) + 5;int n, m, k, mark[maxl], len;LL dp[88][22][maxl];inl
2017-08-21 21:31:37
217
原创 洛谷 1875 佳佳的魔法药水
//此题像游戏里的装备合成树。类似于树形结构，但又存在环。所以不能用树形DP，考虑贪心的思想，每次用一个当前最小代价得到药水(一定是当前最优价格)+已经确定药水价格的药水来合成另一个药水,更新他的价格，这就是Dijkstra的思想。 #include<bits/stdc++.h>using namespace std;const int inf = 0x3f3f3f3f;const int
2017-08-17 16:16:47
340
原创 洛谷 1396 营救
//最小瓶颈路，用SPFA。 #include<bits/stdc++.h>using namespace std;const int maxn = 100010; int n, m, s, t, tot;int d[maxn], st[maxn];//d[]表示到该点路上最大值的最小值。 bool vis[maxn];queue<int> q;struct node{ in
2017-08-16 17:21:48
364
原创 洛谷 1073 最优贸易
//反BFS找能到终点的点，正BFS找到此点及以前最小代价。正BFS实际上是SPFA，要熟练掌握重复更新的思想。#include<bits/stdc++.h>using namespace std;const int maxn = 100010;const int maxm = 500010;int n, m, tot, tot1, ans;int st[maxn], rst[maxn]
2017-08-16 16:32:29
264
原创 洛谷 1908 逆序对
//树状数组 #include<bits/stdc++.h>using namespace std;const int maxn = 100010;int n, s, haoyu[maxn], c[maxn];struct node{ int x, site;} a[maxn];bool cmp(node p, node q){ return p.x < q.x;}voi
2017-08-10 16:49:02
436
原创 洛谷 1168 中位数
#include<bits/stdc++.h>using namespace std;int n, sum1, sum2;priority_queue<int, vector<int>, greater<int> > q2;priority_queue<int> q1;int main(){ scanf("%d", &n); for(int i = 1, x; i <= n
2017-08-10 15:42:50
242
原创 洛谷 1196 银河英雄传说
#include<bits/stdc++.h>using namespace std;const int maxn = 30030;int t, fa[maxn], siz[maxn], dis[maxn];inline void init(){ for(int i = 0; i <= maxn; i++){ fa[i] = i; siz[i] = 1;
2017-08-10 15:40:08
381
原创 洛谷3372 线段树1
//注意求和要*区间个数#include<bits/stdc++.h>using namespace std;const int maxn = 100010;int n, m;long long a[maxn];struct node{ long long val, mark;} segtree[4*maxn];inline void make_tree(int root, in
2017-08-07 21:02:26
479
原创 洛谷3374 树状数组1&2
#include<bits/stdc++.h>using namespace std;const int maxn = 500010;int n, m;int a[maxn], c[maxn];inline void update(int x, int k){ while(x <= n){ c[x] += k; x += x & (-x); }
2017-08-07 20:59:28
245
原创 3375 KMP字符串匹配
http://blog.csdn.net/qq_30974369/article/details/74276186#include<bits/stdc++.h>using namespace std;const int maxc = 1000010;char a[maxc], b[10010];int fail[10010];//勿用next！！！那是保留字。fail[i]表示1-i这个子串
2017-08-07 10:25:12
225
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人