寒假总结

2024-02-05 09:52:40

文章目录

寒假总结笔记
- DFS/BFS/二分
- - BFS
  - DFS
  - 二分
  - 相关例题
- 数论
- 动态规划(DP)
- 数据结构
- - 栈
  - 队列
  - 链表
  - 树
  - - 有根树
    - - 二叉树
  - 例题
  - - Minimum path
    - Largest Rectangle in a Histogram
- 图论

寒假总结笔记

DFS/BFS/二分

BFS

用数据结构中的队列(queue)来实现：把第一个状态放入队列中，随后将这一状态取出，搜索这个状态所能到达的状态，并把这些状态再放入队列中，以此类推。

代码基本格式：

#include<bits/stdc++.h>
using namespace std;

int a[450][450] = {0},n,m;
int v[450][450] = {0};
int dx[k] = {};
int dy[k] = {};//这两个数储存可走到的方向

struct node{
	int x,y;
}q,p;

queue<struct node> s;

int bfs(int x,int y){
	int xx,yy,i;
	a[x][y] = 0;
	q.x = x;q.y = y;
	s.push(q);
	while(s.size()){
		q = s.front();s.pop();
		for(i = 0;i<=k;i++){
			xx = q.x+dx[i];
			yy = q.y+dy[i];
			if(xx<1||yy<1||xx>n||yy>m){//越界则跳过
				continue;
			}
			if(v[xx][yy]!=0){//若已经被访问过则跳过
				continue;
			}
			p.x = xx;p.y = yy;
			a[p.x][p.y] = a[q.x][q.y] + 1;
			s.push(p);
		}
	}
}

DFS

DFS与BFS算是关联比较大，有许多题是dfs和bfs都可以做出来，这两个算法最大的别则是，dfs是一条路走到底，若走不通则返回上一层走另外一条路，找到答案，而bfs则是同一层的先遍历完，再遍历下一层。

代码基本格式

int dfs(状态){//dfs当前状态
	int i,j = 0;
	if(终止条件) return 1;
	//剪枝代码.....
	for(i = 0;i<n;i++){
		
		if(vis[i]) continue;//访问过则跳过
		
		if(符合条件){
			vis[i] = 1;//标记为以访问
			j = dfs(新的状态);//dfs新的状态
			if(j == 1) return 1;
			vis[i] = 0;//回溯时取消访问标记
		}
		//剪枝代码....
		
	}
	return 0;
}

二分

二分是一个比较实用的算法，有些题目当中二分的使用可以大大降低时间复杂度，具体思路便是每一步将划分两个区块，做判断筛掉一个半区。有时候在进行二分时先要将数组进行排序

代码基本格式

int l = 下界-1，r = 上界+1;
while(l+1<r){
    int mid = (l+r)>>1;
    if(check(mid))l = mid;
    else r = mid;
}
//l为满足check的最大值，r为不满足check的最小值

数论

取模

有关取模的几个重要式子:

1.(ab)%c = ( (a%c)(b%c) )%c

2.(b/a)%c = b*(a)^(c-2)%c

快速幂

快速幂这个算法是个死算法，理解代码后把他记下来。

快速幂

int POW(int a,int b){
    int ans = 1;
    int base = a;
    while(b){
        if(b & 1) ans *= base;
        base *= base;
        b >>= 1;
    }
    return ans;
}

快速幂取模

int pow_mod(int a,int b,int c){
    int ans = 1;
    int base = a%c;
    while(b){
        if(b & 1) ans = (ans*base)%c;
        base = (base*base)%c;
        b >>= 1;
    }
    return ans;
}

GCD/欧几里德算法

gcd即最大公因数，求最大公因数，较为简单的方法辗转相除法，又名欧几里德算法。用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。long long gcd(long long a,long long b){

long long gcd(long long a,long long b){
	if(b == 0) return a;
	else return gcd(b,a%b);
}

扩展欧几里德

讲的很好的一篇文章

对于两个不全为0的整数a、b，必存在一组解x,y，使得ax+by==gcd(a,b);---------1式

代码实现

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;y=0;
        return a;
    }
    int r=exgcd(b,a%b,x,y);
    int temp=y;
    y=x-(a/b)*y;
    x=temp;
    return r;
}

由此拓展开ax+by==c，它的解应该是什么呢？x1=x(c/gcd(a,b)),y1=y(c/gcd(a,b))。(其中x,y为1式中解得的x与y)

这个式子的通解x = x1+t*b/d,

y = y1- t*a/d。(t为任意实数)

素数筛

参考

埃氏筛

做法其实很简单，首先将2到n范围内的整数写下来，其中2是最小的素数。将表中所有的2的倍数划去，表中剩下的最小的数字就是3，他不能被更小的数整除，所以3是素数。再将表中所有的3的倍数划去……以此类推，如果表中剩余的最小的数是m，那么m就是素数。然后将表中所有m的倍数划去，像这样反复操作，就能依次枚举n以内的素数，这样的时间复杂度是O(nloglogn)。

代码实现:

bool vis[maxn] = {0};//数值为0时代表是素数
int prime[maxn] = {0},x = 0;
void isprime(int n) 
{
    
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) prime[x++]=i;
        for(int j=2;j*i<=n;j++)
        {
            vis[i*j]=true;
        }
    }
}

欧拉筛

在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。其他复杂度（O(n)）.

代码实现

bool vis[maxn] = {0};//数值为0时代表是素数
int prime[maxn] = {0},x = 0;
void oulasai(int n)  //欧拉筛
{
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) prime[x++]=i;
        for(int j=0;j<x;j++)
        {
            if(i*prime[j]>n) break;
            vis[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}

容斥原理

long long a[max];
void div(long long n) //分解质因子
{
    long long i;
    num=0;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            a[num++]=i;
            while(n%i==0)
                n=n/i;
        }
    }
    if(n>1)
        a[num++]=n;
}

long long rongchi(long long m)//计算1~m与n不互素的个数
{
    long long que[10000],i,j,k,sum=0;
    int t=0;
    que[t++]=-1;
    for(i=0;i<num;i++)
    {
        k=t;
        for(j=0;j<k;j++)
           que[t++]=que[j]*a[i]*(-1);
    }
    for(i=1;i<t;i++)
        sum=sum+m/que[i];
    return sum;
}

动态规划(DP)

动态规划通过将原问题分解成与原问题性质相同的子问题，当求出子问题时，原问题的解也出来了。

动态规划一般有递归和递推两种写法，但是我们一般采用递推而不用递归，因为递归需要调用函数，当数据比较大时是相当耗费时间和空间的，所以我们也是只采用递推的方法来讲

背包问题

01背包

有一个容量为V的背包，还有n个物体。现在忽略物体实际几何形状，我们认为只要背包的剩余容量大于等于物体体积，那就可以装进背包里。每个物体都有两个属性，即体积w和价值v。
问：如何向背包装物体才能使背包中物体的总价值最大?

假设f[i] [j] 表示前i个物品中背包大小为j时所能装下的最大价值；

此时我们可以得到转移方程f [i] [j] = max(f[i-1] [j],f[i-1] [j - w[i] ] + v[i] );

for(i = 1;i<=n;i++){//va[i]表示第i个物品的价值，wei[i]则表示第i个物品的重量。
			for(j = 0;j<=v;j++){
				if(j<wei[i]){
					f[i][j] = f[i-1][j];
					continue;
				}
				f[i][j] = max(f[i-1][j],f[i-1][j-wei[i]]+va[i]);
			}
		}

一位数组优化：

for(i = 1;i<=n;i++){//va[i]表示第i个物品的价值，wei[i]则表示第i个物品的重量。
			for(j = v;j<=0;j++){//一定是从v->0
				if(j<wei[i]){
					f[j] = f[j];
					continue;
				}
				f[j] = max(f[j],f[j-wei[i]]+va[i]);
			}
		}

完全背包

题意:01背包条件加上每个物品有无限个。

for(i = 1;i<=n;i++){//va[i]表示第i个物品的价值，wei[i]则表示第i个物品的重量。
			for(j = 0;j<=v;j++){
				if(j<wei[i]){
					f[i][j] = f[i-1][j];
					continue;
				}
				f[i][j] = max(f[i][j],f[i][j-wei[i]]+va[i]);
			}
		}

用一位数组优化:

for(i = 1;i<=n;i++){//va[i]表示第i个物品的价值，wei[i]则表示第i个物品的重量。
			for(j = 0;j<=v;j++){
				if(j<wei[i]){
					f[j] = f[j];
					continue;
				}
				f[j] = max(f[j],f[j-wei[i]]+va[i]);
			}
		}

多重背包

题意:01背包条件加上每个物品有个数限制

memset(f,-1,sizeof(f));
f[0] = 0;
for(i = 1;i<=n;i++){//a[i]表示第i个物品的数量
			for(j = 0;j<=m;j++){
				if(f[j]>=0) f[j] = a[i];
				else f[j] = -1;
			}
			for(j = 0;j<=m-p[i];j++){
				f[j+p[i]] = max(f[j+p[i]],f[j]-1);
			}
		}

概率DP

参考

概述
一般来说，概率DP找到正确的状态定义后，转移是比较容易想到的。但状态一定是“可数”的，把有范围的整数作为数组下标。事实上，将问题直接作为状态是最好的。如问“n人做XX事的期望次数”，则设计状态为f[i]表示i个人做完事的期望。转移一般是递推，即从上一个状态转移得（填表）或转移向下一个状态（刷表）。

有时期望DP需以最终状态为初始状态转移，即逆推。如f[i]表示期望还要走f[i]步到达终点。这种状态的转移是刷表法，形如f [ i ] = ∑ p [ i → j ] f [ j ] + w [ i → j ] f[i]=\sum p[i\rightarrow j]f[j]+w[i\rightarrow j]f[i]=∑p[i→j]f[j]+w[i→j]，其中p [ ] p[]p[]表示转移的概率，w [ ] w[]w[]表示转移对答案的贡献。一般来说，初始状态确定时可用顺推，终止状态确定时可用逆推。

数据结构

栈

遵循后入先出的原则，在许多题中利用栈可以高效解题，应用场景有dfs等。在c++中用stack来实现栈的操作

队列

遵循先进先出的原则，在bfs算法中有重要作用。在c++中用queue来实现队列的操作

链表

解释略。。。。可以解决约瑟夫环等问题。在c++中用list来实现双向链表的操作

树

有根树

有一个根的特殊节点的数成为有根树。树的储存一般利用”左子有兄弟“的表示方法来表达（二叉树除外），即有结构体数组{int l,r}，其中l表示的是此节点的子节点，r表示的则是此结点的兄弟结点。

二叉树

每个结点最多只有两个子节点的树。

例题

Minimum path

题目链接

You are given a matrix of size n×nn×n filled with lowercase English letters. You can change no more than kk letters in this matrix.

Consider all paths from the upper left corner to the lower right corner that move from a cell to its neighboring cell to the right or down. Each path is associated with the string that is formed by all the letters in the cells the path visits. Thus, the length of each string is 2n−12n−1.

Find the lexicographically smallest string that can be associated with a path after changing letters in at most kk cells of the matrix.

A string aa is lexicographically smaller than a string bb, if the first different letter in aa and bb is smaller in aa.

Input

The first line contains two integers nn and kk (1≤n≤20001≤n≤2000, 0≤k≤n20≤k≤n2) — the size of the matrix and the number of letters you can change.

Each of the next nn lines contains a string of nn lowercase English letters denoting one row of the matrix.

Output

Output the lexicographically smallest string that can be associated with some valid path after changing no more than kk letters in the matrix.

Examples

Input

4 2
abcd
bcde
bcad
bcde

Output

aaabcde

Input

5 3
bwwwz
hrhdh
sepsp
sqfaf
ajbvw

Output

aaaepfafw

Input

7 6
ypnxnnp
pnxonpm
nxanpou
xnnpmud
nhtdudu
npmuduh
pmutsnz

Output

aaaaaaadudsnz

题解:

我们可以知道我们只能往右边或下边走，并且想要使字典序最小那么就一定是把不是a的字符改成a，并且我们还知道在前k个中尽可能的要走到有a的地方，所以首先我们可以先用dp，记录走到这个地方并且前面全变成a（本来就是a除外）所用到的最少次数，并把>0的地方全部变成a，使用队列解决往哪走的问题。

ac代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct node{
	int x,y,num;
}q,p;
int n,k;
char a[2009][2009] = {'\0'};//记录图
int d[2009][2009] = {0};//记录走到这个地方并且前面全变成a（本来就是a除外）所用到的最少次数
bool v[2009][2009] = {0};//记录是否走过这里
char ans[5000] = {'\0'};//记录答案
int dx[] = {1,0};
int dy[] = {0,1};//两个数组记录方向
queue<struct node> s;
int main(){
	int i,j,xx,yy,nu;
	scanf("%d %d",&n,&k);
	for(i = 1;i<=n;i++){
		for(j = 1;j<=n;j++){
			scanf(" %c",&a[i][j]);
		}
	}
	for(i = 1;i<=n;i++){//使用dp记录走到i,j这个地方并且前面全变成a（本来就是a除外）所用到的最少次数
		for(j = 1;j<=n;j++){
			if(i == 1||j == 1){
				if(a[i][j] == 'a'){
					d[i][j] = max(d[i-1][j],d[i][j-1]);
				}else{
					d[i][j] = max(d[i-1][j],d[i][j-1]) + 1;
				}
				continue;
			}
			if(a[i][j] == 'a'){
				d[i][j] = min(d[i-1][j],d[i][j-1]);
			}else{
				d[i][j] = min(d[i-1][j],d[i][j-1]) + 1;
			}
		}
	}
	for(i = 1;i<=n;i++){
		for(j = 1;j<=n;j++){
			if(d[i][j]<=k) a[i][j] = 'a';
		}
	}
	q.x = 1;q.y = 1,q.num = 1;
	s.push(q);
	v[1][1] = 1;
	ans[q.num] = a[q.x][q.y];
	while(s.size()){
		q = s.front();
		s.pop();
		if(ans[q.num] == a[q.x][q.y])//如果不是最小字母则可以不用存到队列中
		for(i = 0;i<=1;i++){
			xx = q.x + dx[i];
			yy = q.y + dy[i];
			if(xx>n||yy>n||(v[xx][yy])) continue;
			v[xx][yy] = 1;
			p.x = xx;p.y = yy;p.num = q.num + 1;
			s.push(p);
			if(!('a'<=ans[p.num]&&ans[p.num]<='z')){
				ans[p.num] = a[p.x][p.y];
			}else{
				ans[p.num] = a[p.x][p.y]<ans[p.num]?a[p.x][p.y]:ans[p.num]; //ans[i]记录第i步所走的最小字母
			}
		}
	}
	for(i = 1;i<=2*n-1;i++){//输出答案
		printf("%c",ans[i]);
	}
	return 0;
}

Largest Rectangle in a Histogram

题目链接

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1 <= n <= 100000. Then follow n integers h1, …, hn, where 0 <= hi <= 1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

Sample Output

8
4000

题解：

这题需要使用到数据结构栈来解决，记答案为mx，首先当栈内没有元素时将元素入栈，当入栈的元素高度大于栈顶元素则入栈，当入栈元素小于等于栈顶元素时则栈顶元素出栈并计算该元素的面积，更新mx，并把出栈元素的宽度累计到准备入栈的元素。最后当输入停止时，若栈内还有元素则按照上面的规则依次出栈。

ac代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
struct tan{
	long long w,h;
}q,p,z;
stack<struct tan> t;
int main(){
	long long mx = 0,i,n,w,tt;
	while(scanf("%lld",&n)&&n){//当输入n = 0时停止
		mx = 0;w = 0;
		for(i = 1;i<=n;i++){
			w = 0;
			scanf("%lld",&q.h);
			q.w = 1;
			if(t.empty()){//如果是空栈则元素直接入栈
				t.push(q);
				continue;
			}
			p = t.top();
			while(t.size()&&p.h>=q.h){//当入栈元素小于等于栈顶元素时则栈顶元素出栈并计算该元素的面积，更新mx。
				t.pop();
				mx = max(mx,p.h*(p.w+w));//更新mx
				w += p.w;//累计入栈元素的宽度
				if(t.size())p = t.top();
			}
			q.w+=w;//入栈元素宽度加上累计宽度
			t.push(q);
		}
		while(t.size()){//当输入停止时若栈内还有元素，则按照上面规则让元素一个个出栈
			p = t.top();
			t.pop();
			mx = max(mx,p.h*p.w);
			if(t.empty()) break;
			q = t.top();
			t.pop();
			q.w+=p.w;
			t.push(q);
		}
		printf("%lld\n",mx);
	}
	return 0;
}

图论

图的储存

图的储存一般使用邻接表或者邻接矩阵，两种方法各有好坏。邻接表一般使用vector来储存，这种方法节省空间，但是当查询某两个点是否有连接时会比较耗费时间。邻接矩阵一般使用二维数组来储存，这种方法花费比较大的空间，但是查询某两个点是否有连接时非常高效，复杂度仅为o（1）。

最短路问题

最短路问题可以使用dfs，bfs算法来求，但是由于使用这两个算法时容易超时需要不断剪枝比较繁琐，所以这里介绍几个算法可以较为简单的求最短路径问题。

弗洛伊德

弗洛伊德算法可以用于基本所有的图（有向图，无向图，树）,并且可以快速知道任意两个点之间的最短路程。但是这个算法的复杂度比较大。需要看题目数据使用。

#define inf 1000000000
int a[N][N] = {0};
int i,j,k;
for(i = 1;i<=n;i++){
    for(j = 1;j<=n;j++){
        a[i][j] = i==j?0:inf;
    }
}
for(k = 1;k<=n;k++){
    for(i = 1;i<=n;i++){
        for(j = 1;j<=n;j++){
            if(a[i][j]>a[i][k]+a[k][j]){//以k为跳板，看看i到j之间经过k是否可以缩短路程
                a[i][j] = a[i][k]+a[k][j];
            }
        }
    }
}

迪克斯特拉

迪克斯特拉用于求单元最短路径问题，即求起点到任意点之间最短的路程，复杂度为o（n^2）。

int d[n][n],ans[n] = {0};//ans[i]表示起点到i的最短距离
void dij(){
	int minv,i,j,u;
	int v[n];
	for(i = 1;i<=n;i++){
		ans[i] = inf;v[i] = 0;
	}
	ans[x] = 0;//x表示起点
	while(1){
		minv = inf;
		u = -1;
		for(i = 1;i<=n;i++){
			if(minv>ans[i]&&!v[i]){
				minv = ans[i];
				u = i;
			}
		}
		if(u == -1) break;
		v[u] = 1;
		for(i = 1;i<=n;i++){
			if(!v[i]&&d[u][i]!=inf){
				if(ans[i]>ans[u]+d[u][i]){
					ans[i] = ans[u]+d[u][i];
				}
			}
		} 
	}
	
}

用优先队列优化

#include<queue>
#define inf 1000000000
int n;
vector<pair<int,int> >adj[MAX];//加权有向图邻接表 ,adj[i][].second表示边的权值，i表示起点，adj[i][].first表示起点 
void dij(){
	int i,j,k;
	priority_queue<pair<int,int> > PQ;//注意：这个表示跟adj不同，i表示起点,second表示边的终点，first表示边的权值 
	int vis[MAX];
	int d[MAX];
	for(i = 0;i<n;i++){
		d[i] = inf;
		vis[i] = 0;
	}
	d[x] = 0;//起点为x
	PQ.push(make_pair(0,x));
	while(!PQ.empty){
		pair<int,int> f = PQ.top();PQ.pop();
		int u = f.second;
		vis[u] = 1;
		if(d[u]<f.first*-1) continue;//取出最小值，如果不是最短路径就忽略，为何乘-1往后看便知 
		
		for(j = 0;j<adj[u].size();j++){
			int v = a[u][j].first;//v为终点 
			if(vis[v] == 1) continue;
			if(d[v]>d[u]+adj[u][j].second){
				d[v] = d[u]+adj[u][j].second;
				PQ.push(make_pair(d[v]*-1,v));//因为优先队列是取出最大值，所以乘以-1则可以达到取出最小值的效果，只需在取出时*-1即可。 
			}
		}
	} 
}

最小生成树

有n个点，求出将所有点连起来所需最短的边长（可以间接相连）。

使用普里姆算法

#define inf 1000000000
int n,M[MAX][MAX];
int prim(){
    int u,minv,i,j;
    int vis[MAX],d[MAX],p[MAX];
    for(i = 0;i<n;i++){
        vis[i] = 0;
        d[i] = inf;
        p[i] = -1;
    }
    d[x] = 0;//x为起点，也可以说是树的根。
    while(1){
        minv = inf;
        u = -1;
        for(i =  0;i<n;i++){
        	if(minv>d[i]&&!vis[i]){
        		minv = d[i];
        		u = i;
			}
		}
		if(u == -1) break;
		vis[u] = 1;
		for(i = 0;i<n;i++){
			if(!vis[i]&&M[u][i]!=inf){
				if(d[i]>M[u][i]){
					d[i] = M[u][i];
					p[i] = u;//记录父节点 
				}
			}
		}
    }
}

例题

还是畅通工程

题目链接

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省*“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。

Output

对每个测试用例，在1行里输出最小的公路总长度。

Sample Input

Sample Output

3
5

题解：显然这是一个最小生成树问题，直接使用prim算法来实现。

ac代码:

#include<cstdio>
#include<iostream>
#include<cstring> 
#define inf 100000000
using namespace std;
int r[109][109] = {0},n;
int d[109] = {0},p[109] = {0};
int mst(){
	int i,j,u,minv,sum = 0;
	for(i = 1;i<=n;i++){
		d[i] = inf;
		p[i] = 0;
	}
	d[1] = 0;
	while(1){
		//printf("***\n");
		minv = inf;
		u = -1;
		for(i = 1;i<=n;i++){
			if(minv>d[i]&&!p[i]){
				u = i;
				minv = d[i];
			}
		}
		p[u] = 1;
		if(u == -1) break;
		for(i = 1;i<=n;i++){
			if(r[u][i]!=inf&&p[i] == 0){
				if(d[i]>r[u][i]){
					d[i] = r[u][i];
				}
			}
		}
		
	}
	for(i = 1;i<=n;i++){
		sum+=d[i];
	}
	return sum;
}
int main(){
	int i,j,a,b,c,ans;
	while(scanf("%d",&n)&&n){
		memset(r,0,sizeof(r));
		for(i = 1;i<=(n*(n-1))/2;i++){
			scanf("%d %d %d",&a,&b,&c);
			r[a][b] = r[b][a] = c;
		}
		ans = mst();
		printf("%d\n",ans);
	}
}

Shortest Cycle

题目链接

You are given nn integer numbers a1,a2,…,ana1,a2,…,an. Consider graph on nn nodes, in which nodes ii, jj (i≠ji≠j) are connected if and only if, aiai AND aj≠0aj≠0, where AND denotes the bitwise AND operation.

Find the length of the shortest cycle in this graph or determine that it doesn’t have cycles at all.

Input

The first line contains one integer nn (1≤n≤105)(1≤n≤105) — number of numbers.

The second line contains nn integer numbers a1,a2,…,ana1,a2,…,an (0≤ai≤10180≤ai≤1018).

Output

If the graph doesn’t have any cycles, output −1−1. Else output the length of the shortest cycle.

Examples

Input

4
3 6 28 9

Output

Input

5
5 12 9 16 48

Output

Input

4
1 2 4 8

Output

-1

题解:弗洛伊德算法+思维。首先我们可以知道ai不超过10^18,所以我们可以知道这个数最多有60位，自己可以草稿纸上模拟一下，发现当个数大于120时就肯定有一个个数为3的环。所以当小于120时我们就可以使用弗洛伊德并不会超时。

ac代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#define inf 1e18
using namespace std;
long long cnt = 0,a[100009] = {0},b[100009] = {0};
long long d[200][200] = {0},w[200][200] = {0},ans = inf;//这两个数组都用来记录两个点之间的大小，但各有用处。
void floyd(){
	long long i,j,k;//简单的数学小知识，三点可以确定一个圆，所以我们可以取三个点看他们是否符合情况。
	for(k = 1;k<=cnt;k++){
		for(i = 1;i<k;i++){
			for(j = i+1;j<k;j++){
				ans = min(ans,d[i][j]+w[j][k]+w[k][i]);/*"d[i][j]+w[j][k]+w[k][i]"这个式子可以表示从i出发又回到
                i的步数。必须要使用一个更新过的和两个没更新过得才可行，否则组成的并不是环*/
			}
		}
		for(i = 1;i<=cnt;i++){
			if(d[i][k]!=inf)
			for(j = 1;j <= cnt;j++){
				d[i][j] = min(d[i][j],d[i][k]+d[k][j]);//只更新d，让w保持原状。
			}
		}
	}
}
int main(){
	long long n,i,j,k;
	scanf("%lld",&n);
	for(i = 1;i <= n;i++){//0与任何数取&都等于0，所以不放入计算中
		scanf("%lld",&a[i]);
		if(a[i]!=0) b[++cnt] = a[i];
	}
	
	if(cnt>128){
		printf("3\n");
	}else{
		for(i = 1;i <= cnt;i++){
			for(j = i;j <= cnt;j++){
				if(i!=j) d[i][j] = d[j][i] = w[i][j] = w[j][i] = (b[i]&b[j])?1:inf;//距离为1。 
			}
		}
		floyd();
		if(ans == inf){
			printf("-1\n");
		}else{
			printf("%lld\n",ans);
		}
	}
	return 0;
}

码农公寓

文章目录

寒假总结笔记

DFS/BFS/二分

BFS

DFS

二分

相关例题

马的遍历

Sticks

Obtain Two Zeroes

数论

取模

快速幂

快速幂

快速幂取模

GCD/欧几里德算法

扩展欧几里德

素数筛

埃氏筛

欧拉筛

容斥原理

相关例题

A/B

青蛙的约会

美素数

动态规划(DP)

背包问题

01背包

完全背包

多重背包

概率DP

相关例题

送快弟

划分

Unidirectional TSP

Flipping Coins

数据结构

栈

队列

链表

树

有根树

二叉树

例题

Minimum path

Largest Rectangle in a Histogram

图论

图的储存

最短路问题

弗洛伊德

迪克斯特拉

用优先队列优化

最小生成树

例题

还是畅通工程

Shortest Cycle

相关文章