无    2017-11-21 20:46:45    170    1    1

这次考试不好怎么说,只是该拿到的分拿到了,可惜的是民间数据能上400,而NOIP的机器却卡掉40分,在洛谷过了也没有办法,在全省考的水平并不理想,真的很无奈.
我们班是一个优秀的班级,别人暂时竞赛虽然比较落后,但文化成绩却都非常好.但他们都停课以后,都能考出好的竞赛水平.我的这种浪费了两个月却只能如此成绩的人是非常糟糕的.
必须要提高自己的知识水平,竞赛不能放弃,但文化确实要恢复一个很好的水平,雅礼中学的fuboat在联赛不理想和省选未能翻盘的情况下能凭借强劲的水平考上pkusc的rank1,但我水平差,我不是大神,在本部培训期间,也只能在某些考试才能比较理想,其余考试只能GG,和我水平差一点,差不多好一些,好很多只不过没考好的人,这些伙伴们都比比皆是,我只不过是菜到彻底而已,本校下一届已经学会莫队算法的人,而且联赛成绩和我已经差不多了,希望他能考出好的水平,走好下一年,而不要想今年的我一样.
我终究是菜的不行,对于大家有时秒杀的题目,我也需要有时看上半天.天下父母都希望儿子成功,我望望自己的竞赛和文化,只有感叹之声,没有什么好说的,文化要下一笔大功夫,竞赛就没必要再执着的从一月份停下去了.我在南雅中学是如此拥有好的机会,可是饱满的干瘪了,竞赛不是重点了,我在班上是如此惨淡,望着班级的成绩,那要花许多精力才能赶上,但也必须赶上,从今天开始,必须要珍惜一分一秒.
总是走失败的道路,那个原来初中成绩班上前十的人怎么样了?那个高一省一的人怎么样了?现在一揭开,我的丑陋的面容表现别人眼前,不剩什么了,去年今日的我,还在为美丽的星空而感慨,还在为下一年的奋斗而奇思妙想,在去年的雅礼集训与同学们欢乐着,越来越虚幻,越来越低迷.
人人都能有好的出路,而我在高中猛士一样关闭一扇窗,而另一扇窗却也模糊了.

无    2017-08-26 22:21:37    137    0    0

最近很久没发博客了,主要是因为在集训期间有常规的改题任务,但在集训中还是学到了很多.最近一些烦心的事也多,不过也并无大碍,倒是在51nod和Codeforce有不少好题,主席树倒是一类好的思想,于是也不难构造出可持久化Trie.

于是就用一个sz差分来记一下这段区间有没有新的子节点,一下贴出51Nod1295的代码

  1. #include<bits/stdc++.h>
  2. #define l(x) ch[x][0]
  3. #define r(x) ch[x][1]
  4. const int MAXN = 1551000;
  5. const int MAXM = 50000+10;
  6. const int DIT = 30;
  7. using namespace std;
  8. int n, m, ch[MAXN][2], d[MAXM], sz[MAXN], rt[MAXM], tot;
  9. namespace prisident_trie
  10. {
  11. void insert(int l,int &x,int y)
  12. {
  13. int o=!d[l-1];
  14. x=++tot; l(x)=l(y); r(x)=r(y);
  15. sz[x]=1+sz[y]; if(!l) return;
  16. insert(l-1,ch[x][o],ch[y][o]);
  17. }
  18. int find(int l,int x,int y)
  19. {
  20. if(!l) return 0;
  21. int o=d[l-1];
  22. if(sz[ch[x][o]]>sz[ch[y][o]]) return find(l-1,ch[x][o],ch[y][o])+(1<<(l-1));
  23. return find(l-1,ch[x][!o],ch[y][!o]);
  24. }
  25. void solve()
  26. {
  27. scanf("%d%d",&n,&m);
  28. int l=0,L=0,R=0,x;
  29. for(int i=1; i<=n; ++i)
  30. {
  31. scanf("%d",&x); l=0;
  32. for(int j=0; j<DIT; ++j) d[j]=(x&1), x>>=1;
  33. insert(DI
无    2017-07-20 19:35:50    220    0    0

膜拜ljs,这篇博客讲的很好,把下面两个符号改去就行了.对于1D/1D
能够一个找到单调的斜率,那么如果分母为正,那么就使用斜率优化就是一个好的选择.
我就随便发了个BZOJ1911

  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #define LL long long
  5. const int N = 1e6 + 10;
  6. const double INF = 1e60;
  7. LL a, b, c;
  8. int n;
  9. LL dp[N], s[N], g[N], q[N+10];
  10. using namespace std;
  11. LL spr(LL x) {return x * x;}
  12. inline double slope(LL j,LL k)
  13. {
  14. return 1.0*(dp[j]-dp[k]+a*(spr(s[j])-spr(s[k]))-b*(s[j]-s[k])) / ((s[j]-s[k]));
  15. }
  16. inline LL f(LL x)
  17. {
  18. return a*x*x + b*x + c;
  19. }
  20. namespace ljsun
  21. {
  22. void go()
  23. {
  24. scanf("%d%lld%lld%lld",&n,&a,&b,&c);
  25. for(int i=1; i<=n; ++i)
  26. {
  27. scanf("%lld",&g[i]);
  28. s[i]=s[i-1]+g[i];
  29. }
  30. int l=0, r=0;
  31. for(int i=1; i<=n; ++i)
  32. {
  33. while(l<r && slope(q[l+1],q[l])>2*a*s[i]) l++;
  34. int j = q[l];
  35. dp[i] = dp[j] + f(s[i]-s[j]);
  36. while(l<r && slope(q[r],q[r-1])<slope(i,q[r])) r--;
  37. q[++r] = i;
  38. }
  39. printf("%lld\n",dp[n]);
  40. }
  41. }
  42. int main() {ljsun :: go();}
上下界网络流    2017-07-17 11:51:09    132    0    1
  • 无源无汇可行流
  • 对于可行流,我们有经典的做法
    记录每个点入流量与出流量的差值, 对于一条网络中的,
    我们记录一个入流量出流量的差值为p,
  • 两点之间连上限与下限的差值即可行流
  • 如果差值p>0,则说明要多流,即从S流过来
  • p<0的情况是对称的
    显然每条边的流量由下限流反向弧流构成
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<iostream>
  6. #define NODES(i,h) for(int i=bgn[h]; i!=-1; i=nxt[i])
  7. #define CURS(i,h) for(int &i=cur[h]; i!=-1; i=nxt[i])
  8. using namespace std;
  9. const int N = 80000;
  10. const int P = 300;
  11. const int INF = 0x3f3f3f3f;
  12. int bgn[N],nxt[N<<1],m,n,d,to[N<<1],upper[N<<1],gap[N<<1],e,cur[N<<1], pre[N<<1], w[N<<1],lvl[N<<1],S,T;
  13. int exin[N],G[P][P];
  14. namespace lNet
  15. {
  16. inline void add(int x,int y,int z) {to[e]=y; nxt[e]=bgn[x]; w[e]=z; bgn[x]=e++;}
  17. inline void add_net(int x,int y,int z) {add(x,y,z); add(y,x,0);}
  18. inline int ckmn(int x,int y) {return x<y?x:y;}
  19. int mxflow(int N)
  20. {
  21. int u; u=pre[S]=S; int flag=0,ans=0,ang=-1;
  22. while(lvl[S]<N)
  23. {
  24. flag=0;
  25. CURS(i,u)
  26. {
  27. int v=to[i];
  28. if(lvl[u]==lvl[
RMQ 卡常数    2017-07-17 11:50:51    162    0    0

显然这道题目的解决方案是分块加RMQ,当BL_SZIE4000+的时候是跑的非常快的,显然inline,register解决问题

  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<iostream>
  4. #include<ctime>
  5. #include<algorithm>
  6. #define R register
  7. #include<cmath>
  8. const long long INF = 1e50;
  9. const int N = 20000000 + 10;
  10. const int P = 4472; //472 ;///10000 10000 10000
  11. using namespace std;
  12. int n, m, s; int a[N], f[P+10][14];
  13. inline long long ckmn(int a,int b) {return a<b?a:b;}
  14. inline long long ckmx(int a,int b) {return a>b?a:b;}
  15. struct block
  16. {
  17. int sz;
  18. int prf[P+10],suf[P+10],k[P+10];
  19. void init()
  20. {
  21. for(R int i=1; i<=sz; ++i) prf[i]=ckmx(prf[i-1],k[i]);
  22. for(R int i=sz; i>=1; --i) suf[i]=ckmx(suf[i+1],k[i]);
  23. }
  24. } B[N/P+10];
  25. int nu, ct;
  26. namespace GenHelper
  27. {
  28. unsigned z1,z2,z3,z4,b;
  29. inline unsigned rand_()
  30. {
  31. b=((z1<<6)^z1)>>13;
  32. z1=((z1&4294967294U)<<18)^b;
  33. b=((z2<<2)^z2)>>27;
  34. z2=((z2&4294967288U)<<2)^b;
  35. b=((z3<<13)^z3)>>21;
  36. z3=((z3&4294967280U)<<7)^b;
  37. b=((z4<<3
CDQ    2017-07-17 11:44:54    137    0    0

我们平时在线回答,实际上是修改对下一次询问有影响,所以我们通过二分时间,合理安排顺序,破除限制,用前一半的东西卷在一起去回答后一半,然后继续按时间分治,这样就成为了CDQ的原理,十分简单.
以下是BZOJ1176,二维单点修改,区间查询,显然先给它差分充斥一下,再按x排序,这样在考虑时间的时候,前面的修改不光在它前面而且我们使时间在它前面,但这样完了吗?没有,子区间也是这样的问题,分治下去,因为开始按x轴排序,所以类似归并一下就可以AC.
注意:如果认为memset BIT数组很快, 那就O(n*n)再见

  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<iostream>
  5. #include<algorithm>
  6. #define q Q
  7. #define REP(i,a,b) for(int i=(int)a; i<=(int)b; ++i)
  8. const int N = 6e5 + 10;
  9. const int M = 2e6 + 10;
  10. using namespace std;
  11. struct Query {int type, id, l, r, v, t;} Q[M], T[M];
  12. int cnt, s, tot;
  13. int ans[N], c[N];
  14. bool cmp(Query &a, Query &b)
  15. {
  16. if(a.l == b.l)
  17. {
  18. if(a.r != b.r) return a.r < b.r; else return a.type < b.type;
  19. }
  20. return a.l < b.l;
  21. }
  22. namespace BIT
  23. {
  24. int lowbit(int x) {return x & -x;}
  25. int sum(int x) {int s = 0; while(x) { s += c[x]; x -= lowbit(x);} return s;}
  26. void add(int x,int v) {while(x <= s) {c[x] += v; x += lowbit(x);}}
  27. }
  28. using namespace BIT;
  29. namespace CDQ
  30. {
  31. void
上下界网络流 red    2017-06-10 12:09:02    80    0    0

显然要求最小流,但有源汇上下界可行流的流量要在T-S的反向边
里面找, 注意求T->S最大流要删掉SS,TT

  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<iostream>
  5. #include<algorithm>
  6. #define CURS(i,u) for(int &i=cur[u]; i!=-1; i=nxt[i])
  7. #define NODES(i,u) for(int i=bgn[u]; i!=-1; i=nxt[i])
  8. const int N = 1120 + 10;
  9. const int INF = 0x7f7f7f7f;
  10. const int E = 1120 * 120 + 10;
  11. int pre[N],cur[N],bgn[N],lvl[N],nxt[E],w[E],to[E],gap[N];
  12. int exin[N],e,n;
  13. using namespace std;
  14. namespace A
  15. {
  16. inline void add(int x,int y,int z) {to[e]=y; w[e]=z; nxt[e]=bgn[x]; bgn[x]=e++;}
  17. inline void add_net(int x,int y,int z) {add(x,y,z); add(y,x,0);}
  18. inline int ckmn(int x,int y) {return x<y?x:y;}
  19. void del(int x) {NODES(i,x) w[i]=w[i^1]=0;}
  20. int mxflow(int N,int S,int T)
  21. {
  22. int u; u=pre[S]=S; int flag=0,ans=0,ang=-1;
  23. while(lvl[S]<N)
  24. {
  25. flag=0;
  26. CURS(i,u)
  27. {
  28. int v=to[i];
  29. if(lvl[u]==lvl[v]+1&&w[i])
  30. {
  31. if(ang==-1)ang=w[i];else ang=ckmn(ang,w[i])
red FNT    2017-07-17 08:52:51    144    0    0

为了纪念一直想写的代码, 就此发一篇博客

  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<iostream>
  5. #include<algorithm>
  6. #define LL long long
  7. const int N = 4e5 + 10;
  8. const int E = 19;
  9. const LL MOD = 998244353;
  10. LL g0 = 3, g[N][E], a[N], b[N], c[N];
  11. int n, rev[N];
  12. using namespace std;
  13. namespace Poly
  14. {
  15. inline LL fpm(LL x,LL y) {LL s=1; while (y) {if(y&1LL) s=s*x%MOD; x=x*x%MOD; y>>=1LL;} return s;}
  16. inline LL Rev(LL x) {return fpm(x, MOD-2);}
  17. inline LL read()
  18. {
  19. LL x = 0;
  20. char ch = getchar();
  21. while (ch > '9' || ch < '0') ch = getchar();
  22. while (ch >= '0' && ch <= '9') x = x = x * 10 + ch - '0', ch = getchar();
  23. return x;
  24. }
  25. void init()
  26. {
  27. int t = 0;
  28. for(int i=1; i<=n; i<<=1,++t)
  29. {
  30. g[t][0] = fpm(g0,(MOD-1)/(i*1LL));
  31. g[t][1] = Rev(g[t][0]);
  32. }
  33. for(int i=0; i<n; ++i) rev[i] = (rev[i>>1]>>1) + (i&1)*(n>>1);
  34. }
  35. void Mod(LL &x)
  36. {
  37. if(x < 0) x += MOD;
  38. if(x >= MOD) x %= MO
无    2017-07-14 12:11:08    208    0    0

若有g(x)=i|xg(i),且可以o(1)算出g(x)
则有F(i)=i=1nf(i)=i=1n(g(i)d|i,dif(d)))=i=1ng(i)i=2nF([ni])
根据定义或证明:
n=d|nφ(d)
d|nμ(d)=[n=1]
μφ的前缀和容易这样表示
显然预处理23项,再hash记忆化(显然我只会map)根据求导得

线段树合并    2017-07-01 13:01:40    155    0    0

在一些神奇的问题中,我们常常用到splay启发式合并(whats)统计,但我们转换成(权值)线段树合并,能够很快找到题目的思路,这里给出例子:

  1. #define l(x) ch[x][0]
  2. #define r(x) ch[x][1]
  3. int Merge(int x,int y)
  4. {
  5. if(!x) return y; if(!y) return x;
  6. The Fucnion of calc();
  7. l(x)=merge(l(x),l(y));
  8. r(x)=merge(r(x),r(y));
  9. sz[x]=sz[l(x)]+sz[r(x)]; //maintain
  10. }

显然线段树的结构相同合并也就这样
Ex1: POITree Rotations(LOJ2163)
给你一棵树可以任意交换子树,询问怎样做最小化中序遍历逆序数
分析:本是一道难题,但我们发现在合并过程中也就两边的权值线段树合并的时候乘一下,反正中间那个节点是空的,不影响答案,左子树和右子树,代码比普通线段树还要短.

  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #define LL long long
  6. #define l(h) ch[h][0]
  7. #define r(h) ch[h][1]
  8. using namespace std;
  9. const int N = 4e5 + 10;
  10. const int D = 30;
  11. int v[N], ch[N*D][2], n, rr[N], sz[N*D], ll[N], rt[N], ct, nu;
  12. long long ans0, ans1, ans;
  13. namespace POI
  14. {
  15. inline LL ckmn(LL a,LL b) {return a < b ? a : b;}
  16. void RT(int x)
  17. {
  18. scanf("%d",&v[x]);
  19. if(!v[x])
  20. {
  21. ll[x]=++ct; rr[x]=++ct;
  22. RT(ll[x]); RT(rr[x]);
  23. }
  24. }
  25. int merge(int x
1/9