问题：给定一张有n个点，m条有向边的图。一个整数k。（n<=1e5,m<=2e5,k<=10）。你有k次机会使得图中的某一条边权值变为0。求1号点到n号点的最短距离。保证至少存在一条路径从1到n。 思路：dijkstra算法+dp转移   这其实就是一道分层最短路的模板题。普通的dijkstra算法，dis数组记录的是起点到该点的最短距离，这里的话多开一维就好了。dis[i][j]，代表起点到i点并且使用了j次机会的最短距离。转移时候分情况使用或不使用这次机会讨论来进行转移。因为k不超过10,所以空间复杂度和时间复杂度都是合理的。然后其他操作就和普通的dijkstra算法是一...

问题：给定一个长度为n的序列（1<=n<=1e6）,一个整数k(1<=k<=1e9),让你求出这个序列里有几个不同的区间满足区间内的数异或和大于等于k。 思路：转化前缀异或和。然后利用二进制和字典树解决。   一段区间的异或和x[l,r]=x[1,l-1]^x[1,r]。所以问题转化为找这个序列里 有几对序列前缀异或和异或起来的值是大于等于k的。记s[i]为前i个数的异或和。我们可以对于每一个i在[1,i-1]的范围里找有几个j,满足s[j]^s[i]>=k。  然后我们就可以用字典树来解决这个问题了。对于每一个i，先将s[i-1]按高位到低位存入字典树。每个结点...

问题：给定n个整数，如何用最快的方法求出第k大的数？   我们当然可以对这n个整数排序然后直接输出第k大的数，时间复杂度为O(nlog n)。  但是实际上我们可以用基于快速排序所用到的思想，在每一层递归中，随机选取一个数为基准值，把比它大的数交换到左半段，把其余的数和基准值自身一起作为右半段。在这个过程中假设统计出比基准值大的数有cnt个，若k<=cnt，就在左半段中递归寻找第k大;若k>cnt，就在右半段中递归寻找第k-cnt大的数。递归边界为这一段区间长度为1。就返回这个数即为最初所找区间第k大的数。  因为是随机选取基准值，所以找第k大的数平均时间复杂度为n + n/2 +...

题目大意：给你一个长度为n的序列a（1<=n<=27000,1<=a[i]<=1e9）,m(1<=m<=27000)个查询，k（1<=k<=1e9）,每次查询给出li,ri。需要回答在[li,ri]这个区间内有多少对（i，j）满足i<j并且a[i]-a[j]<=k。 思路：题目没有要求在线做，并且又是这么多的区间询问，再看数据范围，显然可以用莫队做。因为莫队算法本身就是每次维护区间的边缘+1或者-1。所以对于一个区间，往最左边或最右边新加入一个数x，那么答案就会多出原来区间里数值大小在[x-k,x+k]范围的个数个。减少一个数同理。然...

问题：给出一个长度为n(1<=n<=1e5)的序列，接下来有q(1<=q<=1e5)个查询，每次查询给出一个区间[l,r],你需要输出在区间[l,r]里有几个不同的数。  解决这个问题的方法，目前就我所知道的有三种。 一、树状数组+离线   首先我们把所有查询一次性读入，然后按照每个查询的r值升序排序（为什么要这样后面会讲到），然后还需要开一个vis数组，vis[i]代表i这个数字上一次出现的位置（如果序列里的数很大的话，可以先离散化一下，我这里先假设序列里的数都不超过1e5），vis初值都为0。  接下来说一下树状数组的作用，众所周知，树状数组可以方便的动态维护一个序...

理解完题意后，能容易想到答案就是1 - 未知身份人数 / 总人数。所以我们就把问题转换成求一共有几个人是身份是未知的（即他的身份是无法从他人那里获取的）。因为其他人我们可以通过这些人来安全的推导出他的身份。所谓的递推吧...   于是我们把n个人看成图上的n个点，认识关系看成点与点之间的有向边。容易发现未知身份的人数就是图中入度为0的点的个数。但是又考虑到可能会出现环，所以我们需要用 tarjan 缩点，即把一个环（强连通分量）缩成一个点，因为一个强连通分量内，我们只要知道一个人的身份我们就可以安全的去确定其他人的身份，所以一个环就等价与一个点。   所以未知身份人数就是用tarjan对原图缩...

题目链接：http://codeforces.com/contest/1283/problem/D 题意：给你n棵树在数轴上的坐标。有m个人，要你把这m个人放在数轴上，一个点只能放一个人（树所在的点不能放）。要使得这m个人每个人到离他最近的树的距离（以下统称距离）的总和最小，输出这个最小值以及m个人在数轴上的坐标。 解法一：BFS        我看过网上大部分人思路是跑BFS，因为假设树坐标是x，那我肯定是放 x+1,x-1,x+2,x-2,...这样最优的，所以我用map记录这个点有没有被放过，然后广搜的去放人就ok了。 AC代码    1 //#include<bits/stdc+...

#include<cstring> #include<cstdio> #include<iostream> using namespace std; typedef struct treepoint* tNode; typedef struct queue* qNode; typedef struct stack* sNode; struct treepoint { char date; tNode lson, rson; }; char s[110]; int pos; tNode build() {//建立二叉树 tNode bt = (tNode)ma...