nn020701-CSDN博客

原创 P3157 [CQOI2011]动态逆序对

P3157 [CQOI2011]动态逆序对原题地址此处写的是cdq分治板子题（三维偏序）#include<bits/stdc++.h>using namespace std;#define ll long long#define For(i,x,y) for(ll i=(x);i<=(y);++i)#define FOr(i,x,y) for(ll i=(x);i>=(y);--i)#define rep(i,x,y) for(ll i=(x);i<(y);++

2020-10-26 21:26:02 112

原创洛谷P3805 【模板】manacher算法

P3805 【模板】manacher算法原题地址板子题#include<bits/stdc++.h>using namespace std;#define ll long long#define For(i,x,y) for(ll i = (x);(i) <= (y);++(i))#define FOr(i,x,y) for(ll i = (x);(i) < (y);++(i))inline ll read(){ ll x = 0,f = 1;char ch = g

2020-10-12 22:22:25 99

原创 Codeforces Round #465 (Div. 2)E. Fafa and Ancient Mathematics(CF935E)(树形动规)

树形DP。将数字看做叶子节点，？（操作符）看做中间节点。一开始没有看出来，还傻傻地想用背包将所有可能凑出的数字存下，其实只用知道最大值和最小值就行了。比较有的时候要用最大值减最小值来更新最大值。看了这篇题解才知道;#include<bits/stdc++.h>using namespace std;inline int read(){ int k=0,...

2018-02-27 09:30:28 263

原创 [BZOJ]1226 [SDOI2009]学校食堂Dining

题目地址：[BZOJ]1226 [SDOI2009]学校食堂Dining;题面：1226: [SDOI2009]学校食堂DiningTime Limit: 10 Sec Memory Limit: 259 MBDescription小FF 的学校在城市的一个偏僻角落，所有学生都只好在学校吃饭。学校有一个食堂，虽然简陋，但食堂大厨总能做出让同学们满意的菜肴。当然，不同的人口味也不一定相同，但每个人的

2017-10-02 11:25:38 252

原创 Codeforces Round #436 (Div. 2) 864E. Fire

那天晚上发现有场cf时间比较早就跑去打了一下，只写出ABCDE的我（一次都没被hack，也一次都没去hack）……地址：Codeforces Round #436 (Div. 2) 864E. Fire题目：E. Firetime limit per test : 2 seconds memory limit per test : 256 megabytes input : standard i

2017-09-28 20:37:23 298

原创 Codeforces Round #436 (Div. 2) 864D.Make a Permutation!

那天晚上发现有场cf时间比较早就跑去打了一下，只写出ABCDE的我（一次都没被hack，也一次都没去hack）……地址：Codeforces Round #436 (Div. 2) D.Make a Permutation!题面:D. Make a Permutation!time limit per test : 2 seconds memory limit per test : 256 meg

2017-09-28 19:42:22 201

原创 [Vijos1864]NOIP2013提高Day2华容道

题目地址：华容道Vijos1864题解:这道题的正解是bfs+spfa 这道题的n和m最大只有30，也就是说所有的点最多只有900个。对于一个状态来说我们只需要知道：起始格和空白格的位置。对于空白格来说，它的位置是很容易改变的，如果把空白格和有的格子反过来看，空白格子是可以上下左右除了固定格随便移动的。因为起始格的位置改变是需要和上下左右的空白格来交换位置。所以我们在存贮状态的时候只需要存

2017-09-20 21:48:15 365

原创 NOIP2016提高组D1T2天天爱跑步（lca+树上差分）

D1T2 天天爱跑步地址：天天爱跑步Vijos 题解：这道题我觉得应该与T3换一个位置，难度显然有问题的说。在树上一个点跑到另一个点的位置显然通过路程为，s->lca(s,t)->t.我们因此就可以拆路径，拆成向上的s->lca(s,t)与向下的lca(s,t)->t.然后我们将向上和向下的两段路径分开来讨论。向上的时候，每个点观察到的点的深度实际就是观察点的深度加上观察时间（即走这么

2017-09-03 21:49:02 310

原创 NOIP2016提高组D1T1玩具谜题

D1T1 玩具谜题地址：玩具谜题Vijos 题解：这道题因为是个圈，所以我们可以直接用取模O（1）模拟每次的位置变化，总时间就只用O（n），n最大只有100000可以轻松解决。但要注意编号变化的方向和每个人的朝向还有传递的方向。因为朝内人的左边和朝外人的右边是相同的方向，我们可以用异或来确定方向，不过每次都分类讨论也是可以的。代码：#include <iostream>#include

2017-09-03 20:36:33 674

原创有关矩阵乘法的学习

原先对矩阵不是很熟悉，用法也不清楚。有神犇给我推荐了这么一个网址十个利用矩阵乘法解决的经典题目.自己对着里面的题目写了一遍深有感触他在里面的题解已经很详细了，我主要是写在博客上保存这么一个网址和我自己题解的代码。T3:#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace st

2017-08-28 10:36:04 272

原创洛谷[3879] [TJOI2010]阅读理解(trie树模板)

题目链接：luogu3879P3879 [TJOI2010]阅读理解时空限制 2s / 128MB题目描述英语老师留了N篇阅读理解作业，但是每篇英文短文都有很多生词需要查字典，为了节约时间，现在要做个统计，算一算某些生词都在哪几篇短文中出现过。输入输出格式输入格式：第一行为整数N，表示短文篇数，其中每篇短文只含空格和小写字母。按下来的N行，每行描述一篇短文。每行的开头是一个整数L，表示这篇短文由

2017-08-27 19:13:14 817

原创 [BZOJ] 3674 可持久化并查集加强版(主席树广泛运用)

链接：BZOJ 36743674: 可持久化并查集加强版Time Limit: 15 Sec Memory Limit: 256 MBDescription：自从zkysb出了可持久化并查集后……hzwer:乱写能AC，暴力踩标程KuribohG：我不路径压缩就过了！ndsf：暴力就可以轻松虐！zky:……n个集合 m个操作操作：1 a b 合并a,b所在集合2 k 回到第k次操作

2017-08-18 20:32:18 241

原创 [Hdu] 2665 Kth number(主席树模板题)

题目链接：Hdu 2665这道题也放上来，同样是主席树模板，不过是求区间第K大的，基本和上个链接的是一样的，就是怕有人不明白（比如自己）。如果想看主席树模版有解释的可以去[Hdu] 4417 Super Mario (主席树模板题)看看。同样此题数据的原因要离散（好像这类权值线段树之类的都要离散）。代码：#include<iostream>#include<cstdio>#include<cst

2017-08-18 19:08:56 320

原创 [Hdu] 4417 Super Mario (主席树模板题)

地址链接：Hdu 4417这道题应该是显然的模板题，区间求比K小的数的个数。当然由于数据的关系离散是必要的（虽然我对二分操作一直都很迷）。就借这道题稍微给自己的主席树模版介绍一下顺便贮存一下板子。主席树只要理解了，写起来应该是挺容易的。它关键在于每个点更新的时候“新建”一个树，但新建的这个树，只有在发生改变的那logn个点新建，其它的点可以直接引用上一次的。这样每次新建只多出logn的空间，在有限的

2017-08-18 18:49:07 245

原创 2017.3.15模拟赛题解

# 3.11小题解–by cym## T1 前缀？(a.cpp/c/pas)本题是一道非常水的DP由于n只有400；O(n^3^)轻松水过 (而且只是渐进意义，远远达不到n^3^)。30%分数直接开n个for枚举，强行判断。50%分数dfs的方式枚举，会比强行暴力快。80%分数80%的作法已经是DP了。我们开个数组f[i][a1][a2]记录到第i位时，有a1个2 与 a2个1；0不用存

2017-03-18 17:17:20 683

原创 [BZOJ]1006 [HNOI2008]神奇的国度

本题所给出的图显然满足弦图的定义，其主要性质与有关算法可以参考cdq的论文《弦图与区间图》。这里以人为节点，人之间的认识关系就是边，而分组不能将互相认识的人分在一起，将一个组看成一种颜色的话，这就是一道最小染色的题目，但是朴素的染色方法会超时，我们可以使用弦图的性质来完成染色。而求弦图的最小染色，我们可以先求出弦图的完美消除序列，再将序列中的点顺序倒着用来贪心染色，所用到的颜色数就是答案。其实到这里

2017-03-13 17:53:13 299

原创 2017.3.11模拟赛题解

2017.3.11小题解

2017-03-11 16:45:59 355

原创 [BZOJ]1304 [CQOI2009]叶子的染色

1304: [CQOI2009]叶子的染色Description给一棵m个结点的无根树，你可以选择一个度数大于1的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点（哪怕是这个叶子本身）。对于每个叶结点u，定义c[u]为从根结点从U的简单路径上最后一个有色结点的颜色。给出每个c[u]的值，设计着色方案

2017-03-11 15:29:58 583

原创 [BZOJ]1003 物流运输题解

BZOJ1003 物流运输Description　　物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情，会

2017-01-18 20:05:02 1498

永无止境