林大3.3训练 操作序列、角谷猜想、距离、矩阵线段、子数组【已更新完成】

1、小蓝与操作序列（林大OJ 2347）

一道水题，先热热身

Description

小蓝学会了一种新的数据结构：栈。 
栈是一种仅在表尾进行插入和删除操作的线性表。 
表头被称为栈底，表尾被称为栈尾。
小蓝实现了一个支持四种操作的栈：
push：在栈顶压入一个元素， 
新元素会置于原本的栈顶上方，成为新的栈顶。
pop：弹出现在的栈顶，原本的栈顶将成为新的栈顶。 
如果此时栈中不存在元素，那么程序会出错。
top：返回现在的栈顶元素。 
如果此时栈中不存在元素，那么程序会出错。
clear：清空栈中元素，将栈置空。
但是他在使用这种数据结构时经常出错。 
现在他写出了自己使用栈时的一个操作序列， 
你能判断该操作序列是否合法吗？ 
一个操作序列合法当且仅当 
一个空栈依次执行对应操作时不会出错。

Input

输入第一行包含一个整数N ， 
代表操作序列的操作数目。

接下来包含 N 行，每行包含一个字符串，表示一个操作。 
该字符串一定是上述四个操作中的一个， 
即 "push" ， "pop" ， "top" 和 "clear" 
四种字符串中的一种（不包含引号）。

Output

输出两行。 
如果该操作序列合法，那么输出第一行 "Yes" ，第二行输出一个整数：最后栈中的元素数目； 
否则输出 "No" ，第二行输出一个整数：该操作序列会在执行第几个操作时出错（输出不包含引号）。

Sample Input

输入样例1
5
push
push
top
pop
push

Sample Output

输出样例1
Yes
2

Hint

输入样例 2
5
push
top
push
clear
pop
输出样例 2
No
5

代码：

这里用ele记录模拟栈中的元素个数，cnt来记录步骤数

#include<bits/stdc++.h>
 
using namespace std;
 
int n;
 
int main()
{
	cin>>n;	
		 
	queue<string>q;
	
	for(int i=0;i<n;i++)
	{
		string op;
		cin>>op;
		q.push(op);
	} 
	
	int cnt=0;
	int ele=0;
	bool f=true;
	while(!q.empty())
	{
		string s=q.front();
		q.pop();
		
		if(s=="push")
		{
			cnt++;
			ele++;
		}
		else if(s=="pop")
		{
			cnt++;
			if(ele==0)
			{
				f=false;
				break;
			}
			else
			{
				ele--;
			}
		}
		else if(s=="top")
		{
			cnt++;
			if(ele==0)
			{
				f=false;
				break;
			}
		}
		else
		{
			cnt++;
			ele=0;
		}
	}
	if(f)cout<<"Yes"<<endl<<ele;
	else cout<<"No"<<endl<<cnt;
	return 0;
} 

2、小兰与角谷猜想（林大OJ 2351）

Description

角谷猜想是指对于每一个正整数， 
如果它是奇数，则对它乘 3 再加1  ， 
如果它是偶数，则对它除以2  ， 
如此循环，最终都能够得到1 。

小蓝了解到，对于小于1000000000  的数字，我们总可以在 1000 步以内的得到 。 
现在他想知道， 【l,r】区间的数中哪个数得到 1 的步骤最大。

Input

输入包含一行，共两个整数 l 和r ， 
表示小蓝想查询的区间。

Output

输出一行，包含一个整数， [l,r]区间的数中得到1  的步骤最大的那个数。 
如果存在多个步骤最大的数，那么输出最小的那个。

Sample Input

样例输入1
1 10

Sample Output

样例输出1
9

输入样例 2
999999900 1000000000
输出样例 2
999999906

Hint

这道题让我TLE了很长时间，以下是第一次的代码：TLE

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
 
unordered_map<LL,LL>m,re;
 
LL odd(LL x)
{
	x=x*3;
	x+=1;
	return x;
}
 
LL even(LL x)
{
	x/=2;
	return x;
}
 
int main()
{
	int l,r;
	cin>>l>>r;
	
	int big=0;
	int res;
	for(int i=l;i<=r;i++)
	{
		LL t=i;int cnt=0;
		
		while(t!=1)
		{
			if(re[t])
			{
				re[i]=cnt+re[t];
				cnt=re[i];
				break;
			}
			cnt++;
			if(m[t])t=m[t];
			else if(t%2==0)
			{
				m[t]=even(t);
				t=m[t];
				//cout<<t<<"　";
			}
			else
			{
				m[t]=odd(t);
				t=m[t];
				//cout<<t<<"　"; 
			}
		} 
		
		re[i]=cnt;
		
		if(cnt>big)
		{
			//cout<<i<< " "<<cnt<<endl;
			big=cnt;
			res=i;
		}
		
	}
	cout<<res<<endl;//<<" "<<re[res];
}

有一点并查集的感觉，但是两个表速度太慢了

实际上用深搜，加上记忆搜索，一个表就能解决

代码：

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL; 
 
unordered_map <LL, LL> m;
 
LL dfs(LL x)
{
    if(m.count(x)) return m[x];
    if(x == 1) return 0;
    if(x & 1)
        return m[x] = 1 + dfs(3 * x + 1);
    else
        return m[x] = 1 + dfs(x / 2);
}
 
int main()
{
    LL n, m;
    cin >> n >> m;
    
    LL maxn = 0, res = 0;
    for(int i = n; i <= m; ++ i)
	{
        LL ans = dfs(i);
        if(ans > maxn)
		{
            maxn = ans;
            res = i;
        }
    }
    cout << res << endl;
    return 0;
}

3、小兰与名氏距离（林大OJ 2352）

Description

Input

输入第一行包含一个整数 N， 
表示二维空间中点的数目。

接下来包含 N 行，第行包含两个整数， 
表示一个点对的 X 坐标和 Y 坐标。

Output

输出一行，包含一个整数， 
表示距离与p  无关的点对数目。

Sample Input

3
0 1
1 0
1 1

Sample Output

2

Hint

**公式推导**：

这题就是求横坐标或者纵坐标相同的对数有多少个

对于相同的横纵坐标：这相当于一个对于n个重复元素，求不重复的组合数

比如：1 1 1 1 1

五个1，第一个1可以选后四个1：4

             第二个1可以选后三个1：3

             ...................

             最后一个1可以选0个

总共有4+3+2+1

可以转化为等差数列求和

求和公式 ：（首项 + 末项） * 项数/2 

转化为这个之后，分别排序横坐标和纵坐标

用sum一直累加重复的对数就行了

代码：

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
 
const int N=1e5+10;
 
int x[N],y[N];//存储x、y坐标 
 
int n;
//相当于 n 个相同的数求前缀和 
// 1 1 1 1 2 相当于 三项  （i-stx-1）*（i-stx-1+1）就是这么来的 
// 3+2+1
 
int main()
{
	cin>>n;
	
	for(int i=0;i<n;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
	} 
	
	sort(x,x+n);
	sort(y,y+n);
	
	int stx=0,sty=0;
	
	LL sum=0;
	
	for(int i=1;i<n;i++)
	{
		if(x[stx]!=x[i])
		{
			sum+=(LL)(i-stx)*(i-stx-1)/2;//（首项 + 末项） * 项数/2 
			stx=i;
		}
		
		if(y[sty]!=y[i])
		{
			sum+=(LL)(i-sty)*(i-sty-1)/2;
			sty=i;
		}
	}
	//最后可能到n-1的时候还没算完 比如说 9 9 9 9 一直到n-1最后一个
	//x【i】没有不等于 x【stx】 
	//就算是 9 9 9 9 10形式的，用以下方式算也不会错 
	//因为第n个不存在，到第n个也相当于一定不等于前面的，大不了sum+=0 
	
	sum+=(LL)(n-stx)*(n-stx-1)/2;
	sum+=(LL)(n-sty)*(n-sty-1)/2;
	
	cout<<sum<<endl;
	return 0;
}

4、小兰与线段（林大OJ 2353）

Description

给定一个仅包含 0和1，大小为N*M的矩阵。
小蓝想找到其中最长线段的长度。

Input

输入第一行包含两个整数 N 和M ， 
表示矩阵的行和列数目。
接下来包含  N行，第i  行包含M  个整数， 
表示矩阵的第  i行。

Output

输出一行，包含一个整数，表示矩阵中最长线段的长度。

Sample Input

3 3
0 1 1
1 1 0
0 1 0

Sample Output

3

Hint

1<=N,M<=1000,数字仅包含0和1

代码：

选择两个方向进行深度优先搜索：dfsx（）、dfsy（）

#include<bits/stdc++.h>
 
using namespace std;
 
const int N=1005;
 
int n,m;
int t=max(n,m);
int g[N][N];
int vis[N][N],visx[N][N],visy[N][N];
int dx[4]={1,-1};
int dy[4]={1,-1};
 
 
int dfsx(int x,int y)
{
	int res=0;
	res+=1;
	//cout<<"+"<<endl;
	visx[x][y]=1;
	if(res==t)return res;
	for(int i=0;i<2;i++)
	{
		int nx=x+dx[i];
		if(!visx[nx][y] && nx>=1 && nx<=n && y>=1 && y<=m && g[x][y]==g[nx][y])
		{
			res+=dfsx(nx,y);//cout<<"yes"<<res<<endl;
		}
	}
	//cout<<"res=="<<res<<endl;
	return res;
}
 
int dfsy(int x,int y)
{
	int res=0;
	res+=1;
	//cout<<"+"<<endl;
	visy[x][y]=1;
	if(res==t)return res;
	for(int i=0;i<2;i++)
	{
		int ny=y+dy[i];
		if(!visy[x][ny] && x>=1 && x<=n && ny>=1 && ny<=m && g[x][y]==g[x][ny])
		{
			res+=dfsy(x,ny);//cout<<"yes"<<res<<endl;
		}
	}
	//cout<<"res=="<<res<<endl;
	return res;
}
 
int main()
{
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>g[i][j];	
		} 
 
	int res=-1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			int t;
			if(!vis[i][j])
			{
				int x=dfsx(i,j);
				int y=dfsy(i,j);
				t=max(x,y);
				vis[i][j]=1;
			}
			//cout<<t<<endl;
			res=max(res,t);
		}
 
	
	cout<<res;
	return 0;
}

5、小兰与子数组（林大OJ 2354）

Description

数组的范围是数组中最大元素和最小元素的差值。 
对于小蓝而言，求数组的范围是轻而易举的。 
但是现在，他想知道数组的所有子数组中， 
子数组范围的最大值和次大值。
子数组是由数组中的一个或连续多个整数组成一个数列

Input

输入包含两行。 
第一行包含一个整数N ，表示数组的长度。 
第一行包含 N 个整数，表示数组中各个元素的值。

Output

输出一行，包含两个整数，表示子数组范围的最大值和次大值。

Sample Input

5
4 3 2 1 4

Sample Output

3 3

Hint

代码：

用大顶堆、小顶堆维护最大值、次大值、最小值、次小值

#include<bits/stdc++.h>
 
using namespace std;
 
priority_queue<int,vector<int>,greater<int>> qmin;
priority_queue<int,vector<int>> qmax;
 
int main()
{
	int n;
	cin>>n;
	
	for(int i=0;i<n;i++)
	{
		int t;
		cin>>t;
		qmin.push(t);
		qmax.push(t);
	}
	long long ans[2];
	int cnt=0;
	int a,b,c,d;
	//最大减去最小 
	int qma=qmax.top();qmax.pop();
	int qmi=qmin.top();qmin.pop();
	
	int qma1=qmax.top();
	int qmi1=qmin.top();
	
	a=qma-qmi;//最大减最小 
	
	b=qma-qmi1;//最大减次小 
	c=qma1-qmi;//次大减最小 
	
	int t=max(b,c);
	
	cout<<a<<" "<<t;
	return 0;	
}