hiho1097 Prim和Dijkstra很像，这里也是用邻接矩阵存的，应该也能改成堆优化的吧，然后就是松弛条件那里和dijk不一样 #include <bits/stdc++.h> using namespace std; const int N=1e3+50; const int INF=0x3f3f3f3f; int n; int cost[N][N]; int dis[N]; bool vis[N]; int Prim(){  int ans=0; memset(vis,false,sizeof(vis)); vis[0]=true; for(int i=1;i<n...

B君和G君聊天的时候想到了如下的问题。 给定自然数l和r ,选取2个整数x,y满足l <= x <= y <= r ,使得x|y最大。 其中|表示按位或，即C、 C++、 Java中的|运算。 Input 包含至多10001组测试数据。 第一行有一个正整数，表示数据的组数。 接下来每一行表示一组数据，包含两个整数l,r。 保证 0 <= l <= r <= 1018。 Output 对于每组数据输出一行，表示最大的位或。 Sample Input 5 1 10 0 1 1023 1024 233 322 1000000000000000000 1000000...

Gardon和小希每天晚上都喜欢到屋外的森林里散步，设森林里有N块空地，任意两块空地之间都有一条小径相通。他们每次从任意一块空地出发，经过所有的空地后回到原来的空地。 由于他们都喜欢新鲜的旅行，所以他们不希望对任何一条小径经过两次。那么请问，他们最多能保证多少次这种新鲜的旅行呢？ 例如（图），当N=5时，他们只能保持两次这样新鲜的旅行。  Input 输入包含多组数据，每组数据占一行，是一个数字 N。(0<N<=1000000000) 文件以一个0结束。 Output 对于每个输入的N，输出最多能保证新鲜旅行的次数。 Sample Input 5 0 Sample Output 2...

gym100712F import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Scanner; public class Main{  static class Edge implements Comparable<Edge>{  int u,v,w; Edge(int u,int v,int w){  this.u=u; this.v=v; this.w=w; } @Override public int compareTo(Edge o...

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后 [1] 结果+1即为原问题的解。  有递推公式 f n = ( f n − 1 + k ) % n f_n=(f_{n-1}+k)\%n fn​=(fn−1​+k)%n， f n f_n fn​表示n个人按k的取法最后一个人的编号，这个公式的证明： 首先我们是在知道 f n − 1 f_{n-1} fn−1...

给一个数组，求出区间最大异或和 01字典树的典型应用，不过这个不是求和某个数x异或的最大值，而是要求出区间，区间的问题我们可以转成前缀和，比如查询与pre[2]异或最大的值，然后用这个求出的异或pre[2]就是3-k这一段的异或和了，然后为了保持查询的索引一定是再右边，所以一边扫查询一边插入新的（再后面的前缀和） 有一个坑点，不能从32位开始，要从31开始，32就会wa… #include <bits/stdc++.h> using namespace std; const int N=1e5+50; int tree[33*N][2]; int a[33*N]; int pre[...

递推式 要用矩阵快速幂加速，但是构造出来的矩阵里面有一个不确定的遍历 p/i 所以没办法从第一项直接用矩阵快速幂推到最后一项 不过可以看出p/i是可以分块的，就是从1递推到n中间的这些矩阵里，可以分成几个块这样子来递推，每一个块里面的构造矩阵就是一样了，直接用矩阵快速幂 注意p/(p/i)这个就可以快速找到这个块的最右边界 还要注意开long long 代码： #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD=1e9+7; struct Mat{  ll m[3][3];...

判断x^y 和 y^x的大小关系 很简单的题，取个log就行，比较坑的地方是取完log是一个浮点数，会出现精度误差，这样判断大小还行，判断相等就出问题了，虽然在本地a-b<0.0000001能过，提交上去就不行了，所以直接在输入两个数的时候判断就行了 代码： #include <bits/stdc++.h> using namespace std; typedef long long ll; ll x,y; int main(void){  scanf("%lld%lld",&x,&y); if(x==y){  printf("=...

Some company is going to hold a fair in Byteland. There are n towns in Byteland and m two-way roads between towns. Of course, you can reach any town from any other town using roads. There are k types of goods produced in Byteland and every town produces only one type. To hold a fair you have to brin...

Petr likes to come up with problems about randomly generated data. This time problem is about random permutation. He decided to generate a random permutation this way: he takes identity permutation of numbers from 1 to n and then 3n times takes a random pair of different elements and swaps them. Ale...

求出每个子区间的最大值减最小值的和 可以化成求出每个子区间的最大值的和减去每个子区间最小值的和 又可以看成求每个数作为最大值能左右延伸多远，就直接用这个数乘以这个区间能组成多少个子区间（分区间是否跨过这个数来计数） 然后这个问题就可以用单调栈来解决了 #include <bits/stdc++.h> using namespace std; const int N=1e5+50; typedef long long ll; ll le[N],ri[N]; ll a[N]; int t,n; ll solve(){  memset(le,0,sizeof(le)); memset(r...

读题看懂样例就花了好久… 给一棵树，树上任意两个点的距离表示为距离%2，那这样任意两个点之间距离要不就是0要不就是1了，这样就能把树上的点分成两个集合，相同集合内点相距0，不同集合点相距1，然后推出公式就是 n + 6 ∗ ( C k 2 + C n − k 2 + C k 3 + C n − k 3 ) n+6*(C_k^2+C_{n-k}^2+C_k^3+C_{n-k}^3) n+6∗(Ck2​+Cn−k2​+Ck3​+Cn−k3​)，所以问题就变成怎么把节点分开了，一开始就这个问题想了很多假算法，并查集用了一半发现不对，最后发现不就dfs就好了 代码： #include <bits...

hdu1257 d[i]就是保存到i的最大上升子序列长度 g[i]保存长度为i的最大上升子序列的的最小编号（因为编号越小越有机会有上升子序列的机会） import java.util.Scanner; public class Main{  static int n; static final int N=10050; static final int INF=0x3f3f3f3f; static int[] a=new int[N]; static int[] g=new int[N]; static int[] d=new int[N]; public static void main(S...

单调栈是一个很神奇的东西… 比如可以用来算出数组中每个数作为最大/最小值能向左向右延伸到那里，从而可以来算出区间的一些问题 单调栈的思想感觉有点像尺取法，就是在一个新的数要入栈的时候就判断然后不断地出栈（如果需要的话），然后通过出栈完的状态（空栈或者还有栈顶元素）来记录当前数的状态。 hdu1506 求最大的矩形面积，其实也就相当于求每个高度作为区间的最小值能延伸到哪里，那对应的矩形面积就是这个高度乘以这个延伸到的区间长度 以这题来看，具体就是当一个数要入栈时，先判断栈是否为空，如果非空而且当前高度小于等于栈顶高度，那这个栈顶元素就要出栈，只要栈顶元素大于要加入的元素，即保持这个栈的单调性（栈...