- 博客(541)
- 收藏
- 关注
RSS订阅原创 3238: [Ahoi2013]差异
题目链接题目大意：一个长度为 n 的字符串 S，令TiTiT_i表示它从第 i 个字符开始的后缀，求 ∑1≤i<j≤nlen(Ti)+len(Tj)−2lcp(Ti,Tj)∑1≤i<j≤nlen(Ti)+len(Tj)−2lcp(Ti,Tj)\sum\limits_{1 \leq i ...
2018-03-28 20:38:14
359
原创 4552: [Tjoi2016&Heoi2016]排序
题目链接题目大意：维护一个1到n的排列，进行m次局部排序，最后求第 q 位置的数字题解：二分答案x，把序列变成a[i]≥xa[i] \geq x?1:0 区间排序变成区间置0/1，维护区间0的个数就好了……我的收获：233#include <cstdio>#define init int l = t[k].l, r = t[k].r, mid = (l + r) >> 1const int m
2018-03-28 20:29:59
347
原创 2005: [Noi2010]能量采集
题目链接题目大意：求∑x=1n∑y=1mgcd(x,y)∑x=1n∑y=1mgcd(x,y)\sum\limits_{x=1}^{n} \sum\limits_{y=1}^{m} gcd(x,y)题解：点(x,y)与(0,0)所连线段上不包含原点有的点为gcd(x,y) 反演或简单容斥都可以我的收获：2333#include <iostream> #include...
2018-03-28 20:23:47
323
原创 2428: [HAOI2006]均分数据
题目链接题目大意：把 n 个正整数分成 m 组，最小化各组的均方差题解：模拟退火2333我的收获：2333#include <cstdio>#include <cmath>#include <algorithm>using namespace std;typedef double lf;const int N = 25;int n, m;lf mid, ans;int a[N], p[N
2018-03-28 20:19:20
296
原创 1502: [NOI2005]月下柠檬树
题目链接题目大意：有一个由圆锥和圆台组成的柠檬树，在月亮发出的平行光下，可以形成一个影子，求这个影子的面积题解：自适应辛普森积分……我的收获：2333#include<cmath>#include<cstdio>#include<string>#include<cstring>#include<algorithm>using namespace std;const double eps=
2018-03-28 20:17:11
386
原创 3163: [Heoi2013]Eden的新背包问题
题目链接题目大意：现在有n个物品，第i个物品有c[i]个，每购买第i个物品一个需要a[i]元，可获b[i]代价。 有m个询问，每次询问形如：第x个物品禁止购买，你有y元的话，你能获得的最大价值是多少？询问之间互相独立。 题解：CDQ分治 Solve(l,r)表示，当前维护的dp数组，记录的答案是除去[l,r]外的物品的答案 Solve(l,mid)时，用[mid+1,r]内的物品转移dp数组
2018-03-28 20:14:57
361
原创 4565: [Haoi2016]字符合并
题目链接题目大意：有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。得到的新字 符和分数由这 k 个字符确定。你需要求出你能获得的最大分数题解：区间+状压dp 细节见此我的收获：#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>#include
2018-03-27 12:18:32
359
原创 3706: 反色刷
题目链接题目大意：给出一个n个点m条边的无向图，每一条边有一个颜色0/1，每一次可以选择一个环（不一定是简单环）使环上的所有边都反色。问最少选择多少次使所有的边都变成白色。这个图的边的颜色会发生变化，每一次操作有可能使一条边反色题解：性质1：性质2：我的收获：#include #include #include #include #include using
2018-03-27 07:55:20
355
原创 1500: [NOI2005]维修数列
题目链接题目大意：维护一个数列，支持一堆操作（懒得写了）题解：上fhq treap……我的收获：2333#include <cstdio>#include <queue>#include <cstdlib>using namespace std;#define N 500010#define INF 0x3f3f3f3fint n,m,root,cnt;int ch[N][2],siz[N
2018-03-26 20:09:24
233
原创 3817: Sum
题目链接题目大意：给定正整数N，R；求∑d=1n(−1)⌊d×r×d⌋\sum\limits_{d=1}^{n}(-1)^{\lfloor d \times r \times d \rfloor }题解：膜CA我的收获：经典套路#include <bits/stdc++.h>using namespace std;typedef long long ll;int T;ll n,r;double
2018-03-26 19:43:56
224
原创 2795: [Poi2012]A Horrible Poem
题目链接题目大意：给出一个长度为N的字符串，有Q次询问； 每次询问给出一个区间，求区间最短循环节长度题解：膜一发GXZ大爷我的收获：循环节……e#include<bits/stdc++.h>using namespace std;typedef unsigned long long ull;const int N=500009;const ull B=1000173169;int n,q;i
2018-03-26 19:19:28
231
原创 1901: Zju2112 Dynamic Rankings
题目链接题目大意：区间k大，支持单点修改题解：带修主席树模板我的收获：233#include <bits/stdc++.h>using namespace std;#define N 10005int n,m,top,cnt,tot;int v[N],num[N<<1];int A[N],B[N],K[N],flag[N];int root[N],L[55],R[55];inline int
2018-03-26 19:07:33
167
原创 3124: [Sdoi2013]直径
题目链接题目大意：给定一棵树，求直径的长度以及有多少条边满足所有的直径都经过该边题解：丢题解跑……我的收获：分析性质……emmmmm#include<cmath>#include<queue>#include<vector>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define FOR(
2018-03-26 12:11:20
244
原创 4530: [Bjoi2014]大融合
题目链接题目大意：一棵树，动态加边，询问经过一条边的路径条数题解：LCT 维护子树信息我的收获：2333#include <bits/stdc++.h>using namespace std;#define ls c[x][0]#define rs c[x][1]const int N=1e5+10;int n,q;int c[N][2],fa[N],size[N],sum[N],stk[N]
2018-03-26 11:51:18
258
原创 3944: Sum
题目链接题目大意：求∑φ\sum \varphi 和∑μ\sum \mu题解：杜教筛模板我的收获：2333#include<iostream>#include<cstdio>#include<cstring>#define ll long longusing namespace std;int cas,n,m,cnt,c[1000005]; ll phi[2000005],mu[200000
2018-03-26 11:43:22
220
原创 3143: [Hnoi2013]游走
题目链接题目大意：在一个无向连通图上随机游走，初始在1，每一步等概率选择某条出边走到下一个顶点，获得等于这条边的编号的分数；到达 n 结束 对边进行编号，最小化期望总分题解：详细的题解……我的收获：各种转化……妙啊#include<cstdio>#include<algorithm>#define N 502#define M 202222int n,m,i,x,y,du[N],n1[M]
2018-03-25 21:52:42
203
原创 2115: [Wc2011] Xor
题目链接题目大意：给定一幅边权非负的无向连通图,求一条从1到n的路径,使得路径上边权的异或和最大(不需要是简单路径)题解：dfs处理出1到每个点的任意一条路径的边权的异或和,同时处理出图中所有环的边权异或和发现把1到n的任意一条路径的异或值与任意个环的异或值求异或就可以得到所有1到n的路径的异或和……然后是经典线性基了我的收获：2333#include <cstdio>#include <cstr
2018-03-25 21:38:05
229
原创 2844: albus就是要第一个出场
题目链接题目大意：给定一个 n 个数的集合 S 和一个数 x ,求 x 在 S 的2n2^n个子集从小到大的异或和序列中最早出现的位置题解：考虑一个结论：对于一个n个数构成的大小为 k 的线性基 可以得到的2k2^k个异或和每个会重复2n−k2^{n-k}次从高到低枚举二进制位，异或这一位后小于 k 就加上我的收获：2333#include <iostream>#include <cstdio>
2018-03-25 09:29:55
260
原创 2821: 作诗(Poetize)
题目链接题目大意：N个数，M组询问，每次问[l,r]中有多少个数出现正偶数次，强制在线题解：经典分块 预处理ans[i][j]ans[i][j]表示第 i 块到第 j 块的答案 sum[i][j]sum[i][j]表示前 j 块中元素 i 出现的次数我的收获：2333#include <cstdio>#include <vector>#include <map>#include <cmat
2018-03-25 08:42:19
238
原创 1875: [SDOI2009]HH去散步
题目链接题目大意：给定一张无向图，每条路的长度都是1，没有自环，可能有重边，给定起点与终点，求从起点走t步到达终点的方案数。 每一步走的时候要求不能走上一条刚刚走的路题解：为了处理要求，需要用边构造矩阵我的收获：emmm#include<cstdio> #include<cstring> #include<iostream> using namespace std; #define
2018-03-24 20:50:00
141
原创 3028: 食物
题目链接题目大意：有一些食物，存在一些限制……计算携带N件物品的方案数题解：求出每种食物的一般生成函数，把闭形式相乘 用一下广义二项式定理或麦克劳林展开求出第 n 项系数详见popoqqq我的收获：2333#include <cstdio>#include <cstring>#include <iostream>#include &l...
2018-03-24 20:44:17
251
原创 1975: [Sdoi2010]魔法猪学院
题目链接题目大意：找出1~k短路题解：x的估价函数f(x)f(x)取x到结束节点的最短路，这个是准确值，因此复杂度有保证 按广搜的方式扩展节点，每次优先扩展估价+实际最小的节点 第i次扩展到目标节点，代表找到了第i短路我的收获：org#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #incl
2018-03-24 20:38:09
164
原创 1856: [Scoi2010]字符串
题目链接题目大意：给定n个1和m个0，能组成多少种序列，满足对于任意前缀1的个数>=0的个数题解：膜有图的题解我的收获：卡特兰数强啊#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define mod 20100403#define N 2001000using namespace st
2018-03-24 20:31:42
212
原创 2395: [Balkan 2011]Timeismoney
题目链接题目大意：n个点m条边的无向图，每条边有权值c和v，选出一个生成树，最小化∑c∗∑v\sum c * \sum v题解：膜题解我的收获：数形结合套路#include <iostream>#include <algorithm>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#define L
2018-03-22 21:50:54
189
原创 1297: [SCOI2009]迷路
题目链接题目大意：n 个节点的有向图，求从1到n的长度为T的路径条数题解：拆点+矩阵乘法我的收获：2333#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 100 #define MOD 2009 #define P(i,j) (((j)-1)*m+(
2018-03-22 12:21:07
223
原创 4916: 神犇和蒟蒻
题目链接题目大意：求∑Ni=1μ(i2)\sum_{i=1}^N{\mu (i^2)}和∑Ni=1φ(i2)\sum_{i=1}^N{\varphi (i^2)}题解：第一问呵呵 第二问求∑Ni=1φ(i)∗i\sum_{i=1}^N{\varphi (i)*i} 可以杜教筛 丢推导跑我的收获：23333#include <cstdio>#include <map>#define N 10
2018-03-22 12:08:33
230
原创 3534: [Sdoi2014]重建
题目链接题目大意：求生成树概率，边权为实数题解：emmm 膜xehoth我的收获：强啊#include<cstdio>#include<cmath>#include<algorithm>#define N 52using namespace std;namespace runzhe2000{ const double eps = 1e-7; int n; dou
2018-03-21 17:33:43
323
原创 3551: [ONTAK2010]Peaks加强版
题目链接题目大意：同3545，强制在线题解：kruskal重构树 板子来自hzwer 讲解可以看popoqqq我的收获：模版++#include <bits/stdc++.h>using namespace std;const int L=20;const int N=200005;int n,m,Q;int ext,top;int lastans;int h[N>>1],z[N>>1
2018-03-20 22:08:51
234
原创 3156: 防御准备
题目链接题目大意：一条线上N个（检查）点，编号1~N，一个点j上可以建一个守卫塔花费为a[j]，也可以选择放个木偶（为什么会是木偶= =），花费是这个点右边建的第一个守卫塔i到这个点的距离，即i-j。问最小花费题解：斜率优化，随便推推式子我的收获：233333#include <bits/stdc++.h>using namespace std;#define N 1000005#define
2018-02-27 14:51:23
242
原创 3874/2832: [Ahoi2014&Jsoi2014]宅男计划
题目链接题目大意：外卖店有N种食物，第i种食物有固定的价钱Pi和保质期Si。第i种食物会在Si天后过期。JYY是不会吃过期食物的。 比如JYY如果今天点了一份保质期为1天的食物，那么JYY必须在今天或者明天把这个食物吃掉，否则这个食物就再也不能吃了。保质期可以为0天，这样这份食物就必须在购买当天吃掉。 JYY现在有M块钱，每一次叫外卖需要额外付给送外卖小哥外送费F元。送外卖的小哥身强力壮，可以瞬
2018-02-27 13:22:15
429
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人