题目 题目意思很简单，方法很多，就做个解法集合。 1.分块： 分块也是挺好写的。（写的少，出了好多细节问题） 刚开始想每块用个map维护的，然后超内存了，还是老老实实用vector。 坑点，l,r的大小不一定。 顺便分享一个stl函数，equal_range()，返回有序容器中valu对应的区间，返回的是一个pair(好东西!) #include<bits/stdc++.h> using namespace std; int blo = 1000; const int N = 1e5+5; int a[N], l[N], r[N], bl[N]; int n, m; vector...

原题地址 第一眼看过去线段树，然后不会。看了题解，好简单。。一时间还真的没有看出那个公式。 补题的时侯也wa了好多次，以为是精度问题。嗯。。是我太蠢了 ，主要就是维护一个区间和与平方区间和。 #include<bits/stdc++.h> using namespace std; typedef long long LL; #define lson rt<<1, l, mid #define rson rt<<1|1, mid+1,r const int N = 1e5+5; LL sum[N<<2], sum1[N<<2], a[...

HDU-4417：http://acm.hdu.edu.cn/showproblem.php?pid=4417 主席树裸题 #include<bits/stdc++.h> using namespace std; const int N = 1e5+5; int a[N], cnt, root[N], n, m, x, y, k; struct node{int l, r, sum; }T[N*20]; vector<int>v; int getid(int x) {return lower_bound(v.begin(), v.end(), x) - v.begin...

原题地址 主席树是可持久化的线段树，每加入一个节点都建一棵线段树，但是不需要建立一棵完整的树，因为更新一个点只会影响log（n）个节点。不变的节点建立一个联系就可以。先来个经典题存个板子。以后再来填坑。。 #include<algorithm> #include<iostream> #include<cstdio> #include<vector> using namespace std; const int N = 1e5+5; int a[N], cnt, root[N], n, m, x, y, k; struct node{int l,...

题目 前几天学了下大名鼎鼎的莫队算法，精辟，也是挺暴力的一种算法，这题就当留个板子吧 #include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 5e4+5; LL a[N], Ans, ans[N], cnt[N], k; int pos[N], n, m, L, R; struct node{ int l, r, id; bool operator < (const node &a) const { if(pos[l] == pos[a.l] )...

题目 线性基是学线性代数上出现的概念，没想到那么有用。把一个集合弄成一个极大线性无关子集，就能把他所能表示的数都能存起来。求第k小我也不会证。。就当先存个板子吧 #include<bits/stdc++.h> using namespace std; typedef long long LL; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define _for(n,m,i) for (int i = (n); i < (m); i++) #define _rep(n,m,i) for (i...

原题地址：点击 一道简单的dp题，求最长的递减子序列，不过得先排个序，先给出运算符重载的代码 struct node { int x,y,z; bool operator < (const node & a)const { if(x != a.x) return x > a.x; return y > a.y; }//排序方式，长度相同则看宽度 bool operator >(const node & a)const { return x > a.x && y > a.y;//方便后面做比较 }...

原题地址：http://nyoj.top/problem/52 这几天无意中看到的Floyd判圈法实在是好用，用于判断在于给定规则下是否会出现循环，这题是判断是否是按周期出现的，如果还不了解差别看下面的例子 10 3 分别是 10 100 0 0 0~~ 这种就不是周期出现的。 再来说说这种算法吧，在时间复杂度上是差不多的，但是亮点在于空间复杂度O（1）；怎么实现的呢？ 我们先想像一个圆形的跑道，有两个人从同一起点开始跑，但是第二个人的速度是第一个人的两倍。那么如果有环会出现什么结果呢？第一个人跑完一圈的时侯第二个人恰好和它在同一水平线上，简单是说就是相遇（速度是两倍呀） 那具体怎么实现呢，首...

一道思维题，要使区间内每个数都是连续的，即这个区间的最大值与最小值之差等于区间的长度。 #include<iostream> using namespace std; const int N = 1e5+1; int a[N], b[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, s, t; cin >> n >> s >> t; for(int i = 1; i <= n; i++) { cin >> a[i]; ...

原题地址点击 来自于牛客的寒假算法训练营，发现题目还挺好的，先把一些能做的补掉！ 思路： 先简单的判断下能不能到达，如果不能直接输出-1就可以，若可以的话先记录下可以经过哪些地方。 然后使用dp转移所能到达的值，最大的值其实就是（1 << 12）-1， (p最大是3000)。看了下别人的代码，使用了或，确实巧妙。dp[j] |= dp[j^c[i]], 代表若之前jXORc[i] 可达，则j也可达，若j本身就可达，那么就和后面的没啥关系，合并起来就是一个或运算；Orz。 ac代码： #include<iostream> using namespace std; co...

链接：https://ac.nowcoder.com/acm/problem/13224 来源：牛客网 题目描述 n 个小区排成一列，编号为从 0 到 n-1 。一开始，美团外卖员在第0号小区，目标为位于第 n-1 个小区的配送站。 给定两个整数数列 a[0]~a[n-1] 和 b[0]~b[n-1] ，在每个小区 i 里你有两种选择： 选择a：向前 a[i] 个小区。 选择b：向前 b[i] 个小区。 把每步的选择写成一个关于字符 ‘a’ 和 ‘b’ 的字符串。求到达小区n-1的方案中，字典序最小的字符串。如果做出某个选择时，你跳出了这n个小区的范围，则这个选择不合法。 ...

链接：https://ac.nowcoder.com/acm/problem/21561 来源：牛客网 题目描述 小乐乐觉得学习太简单了，剩下那么多的时间好无聊，于是便想打游戏。 最近新出了一个特别火的游戏，叫吃猪，小乐乐准备玩一玩。 吃猪游戏很简单，给定一个地图，大小为n*m，在地图中会随机出现一个火山口，只要小乐乐能逃离这个地图，他便能吃猪！ 但吃鸡远没有那么简单： 1.小乐乐每走一次只能上下左右四个方向中走一步。 2.小乐乐每走一步，火山喷发的岩浆就会向四周蔓延一个格子，所有岩浆走过的地方都视为被岩浆覆盖。 3.小乐乐碰到岩浆就会死。 4.地图中还有很多障碍，使得小乐乐不能到达，但是岩...

链接：https://ac.nowcoder.com/acm/problem/14548 来源：牛客网 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 这是mengxiang000和Tabris来到幼儿园的第四天，幼儿园老师在值班的时候突然发现幼儿园某处发生火灾，而且火势蔓延极快，老师在第一时间就发出了警报，位于幼儿园某处的mengxiang000和Tabris听到了火灾警报声的同时拔腿就跑，不知道两人是否能够逃脱险境？ 幼儿园可以看成是一个N*M的图，在图中一共包含以下几种元素： ...

1001：赶火车 问题描述 小伙伴们愉快地结束了暑假wannafly训练营的生活，决定返回学校，早上小伙伴们要赶到高铁站，高铁将在y分钟后停止检票，但他们发现了一件尴尬的事情——他们不认路。 这个城市的道路是非常诡异的，在他们面前有n+m条路，其中n条路是正确的，如果走正确的路，将会在ai分钟后走到高铁站，另外m条路是不正确的，如果走不正确的路，将会在bi分钟后回到起点。 小伙伴们只能随机选择一条路走，但他们记性很差，即使走过一条不正确的路，他们也可能会再次选择这条路。 小伙伴们是非常谨慎的人，他们想要计算到达高铁站所需时间的期望EX，如果EX≤y，那么就出发，否则就退票。...