4 Mmh2000

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 1w+

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

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

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 &amp;lt;iostream&amp;gt; #include...

2018-03-28 20:23:47

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

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

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

4565: [Haoi2016]字符合并

题目链接题目大意:有一个长度为 n 的 01 串,你可以每次将相邻的 k 个字符合并,得到一个新的字符并获得一定分数。得到的新字 符和分数由这 k 个字符确定。你需要求出你能获得的最大分数题解:区间+状压dp 细节见此我的收获:#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>#include

2018-03-27 12:18:32

3706: 反色刷

题目链接题目大意:给出一个n个点m条边的无向图,每一条边有一个颜色0/1,每一次可以选择一个环(不一定是简单环)使环上的所有边都反色。问最少选择多少次使所有的边都变成白色。这个图的边的颜色会发生变化,每一次操作有可能使一条边反色题解:性质1:性质2:我的收获:#include #include #include #include #include using

2018-03-27 07:55:20

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

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

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

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

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

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

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

3209: 花神的数论题

35

2018-03-25 21:54:53

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

2115: [Wc2011] Xor

题目链接题目大意:给定一幅边权非负的无向连通图,求一条从1到n的路径,使得路径上边权的异或和最大(不需要是简单路径)题解:dfs处理出1到每个点的任意一条路径的边权的异或和,同时处理出图中所有环的边权异或和发现把1到n的任意一条路径的异或值与任意个环的异或值求异或就可以得到所有1到n的路径的异或和……然后是经典线性基了我的收获:2333#include <cstdio>#include <cstr

2018-03-25 21:38:05

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

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

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!