devbox
喵喵爱编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

互联网企业刷题存档_互联网公司刷题

作者：喵喵爱编程 | 2024-07-14 01:41:41

赞

踩

互联网公司刷题

互联网求职需要面试，面试需要做算法题，算法题需要刷题，刷题属于是个人有手就行系列。

所以，我得出来的结论是，会做题不代表能力就行，只是刷题刷多了。面试官面前做不出来题目，也不代表你不行，仅仅是你没时间刷题，或者准确地说，最近一段时间没刷题。那些常年做工程的老手，给他一个力扣算法题，如果他没接触过，未必能在短时间内做出来。

既然，刷题起不到筛选人才的效果，这些公司们为什么还乐此不疲地问这种没有技术含量，类似于小把戏一样的东西呢？我觉得一方面原因还是想看看你的态度吧，毕竟愿意去准备的，都是态度不错的。另外一方面，很多时候，除了硬件条件，确实也想不到很好的方法在短时间内去获知别人的能力的，又要和上级交差，只能这样搞了。
事实上，我知道还是有很大一部分人是信奉这些小题目是可以和能力以及编程思维什么的挂钩的，但是你写得再多，优化得再好，相较于核心技术和能力，就好比是小学奥数和大学数学一样。如果对小学奥数非常感兴趣，当然可以搞啊，喜欢最重要了，就好比那些日复一日刷算法题，并以此为乐了人一样，他们收获的快乐，不是别的东西可以来衡量的。若非如此，小算法题终究难登大雅之堂，我们还是要有自己的核心竞争力，不要整天纠结在这些没什么技术含量的算法题上。有些题你没接触过类似的，几分钟内，想破头皮你也不知道怎么做。

我其实挺反对用这种小把戏去考核一个人的，特别是对于博士校招，本来时间就很紧。但是，既然人家有这个标准，你又不得不按别人的要求来做。这也是一种无奈吧。

文章目录

阿里巴巴

1

在这里插入图片描述

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int N,L;
    cin>>N>>L;
    //cout<<N<<" "<<L<<endl;
    while(1)
    {
       // cout<<L<<endl;
        
        if(L>100)
        {
            cout<<"No";
            break;
        }
        int begin = 0;
        while(1)
        {
            int sum = (2*begin+L-1)*L/2;
            if(sum>N) break;
            if(sum==N)
            {
                for(int j=0;j<L-1;j++)
                {
                    cout<<begin+j<<" ";
                }
                cout<<begin+L-1;
                return 0;
            }
            begin++;   
        }     
        L++;  
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

能用 int 的就别用 double ，容易超时。

牛客网读入示例：

#include <iostream>
using namespace std;
int main() {
    int a,b; while(cin >> a >> b)//注意while处理多个case
        cout << a+b << endl;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
2

在这里插入图片描述

#include<iostream>
#include<vector>
#include<set>
using namespace std;
int main()
{
    int T;
    cin >> T;
    //cout<<T<<endl;  
    for (int i = 0;i < T;i++)
    {
        int n;
        cin >> n;
        //cout<<"n is "<<n<<endl;  
        vector<int> x(n);
        vector<int> y(n);
        for (int j = 0;j < n;j++)
        {
            cin >> x[j];
        }
        for (int j = 0;j < n;j++)
        {
            cin >> y[j];
        }
        set<pair<int, int>> S;
        for (int j = 0;j < n;j++)
        {
            S.insert(make_pair(x[j], y[j]));
        }
        //for(int i=0;i<n;i++)
            //cout<<x[i]<<" "<<y[i]<<endl;  
        int count = 0;
        for (set<pair<int, int>>::iterator it = S.begin();it!=S.end();it++)
        {
            int count_tmp = 1;
            auto cur = it;
            for (auto ite = it;ite != S.end();ite++)
            {
                if (ite->second > cur->second)
                {
                    cur = ite;
                    count_tmp++;
                }
            }
            count = max(count, count_tmp);
        }
        cout << count << endl;
    }

    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51

自测通过，提交运行一个都通不过，不知道为什么。

3

有 N 个格子（8），给定要求，把每个格子染成红蓝两种颜色（“BBRBRBBR”）。染色的方法可以是，连续地染色几个格子。也可以对已有的格子进行覆盖染色，覆盖之后，新格子是覆盖后的颜色。输出，最少染色几次可以完成要求（4）。

#include <iostream>
#include<vector>
#include<map>

using namespace std;
/*
* 
8 
BBRBRBBR

4

*/

int main() {
	int N;
	cin >> N;
	string str(N, 'B');
	for (int i = 0;i < N;i++)
	{
		cin >> str[i];

	}
	vector<int> result(N, 0);
	result[0] = 1;

	for (int i = 1;i < N;i++)
	{
		if (str[i] == str[i - 1])
		{
			result[i] = result[i - 1];
		}
		else
		{
			result[i] = result[i - 1] + 1;
			for (int j = i - 2;j >= 0;j--)
			{
				if (str[j] == str[i])
				{
					result[i] = result[j] + 1;
					break;

				}
			}
			
		}

	}


	cout << result[N - 1] << endl;



	return 0;





}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61

一个一个地去加，细细地去品味转移方程。动态规划题。

4

有 n 个城市（3）
有 m 条城市之间的道路（2）
第 i 个城市的开门时间固定数 w[i] 的整数倍 （[1 2 3]*整数倍）
经过这个城市的停留时间为 p[i] ([1 1 1])
第 1 条道路为城市 1 到城市 2，需要花费 1 的时间 （[1 2 1]）
……
第 m 条道路为城市 2 到城市 3，需要花费 2 的时间 （[2 3 2]）
某人从 s城（1）到 t 城（3）
输出 s 到 t 的所有路径中最小花费的时间(5)。

开门时间为 w[i] 表示，你走到 i 城，如果已经花费的总时间不是 w[i] 的倍数的话，你需要等到这个时间才能进去。停留时间表示，你进了这个城之后，需要停留的时间。
需要注意的是，从 s 城出发，s 城的停留时间是不算的。题目要求，到 t 城的时候，可以不进门。言外之意就是不算最后一个城的开门等待时间和停留时间。这点要注意。

3 2
1 2 3
1 1 1
1 2 1
2 3 2
1 3
5

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
#include <iostream>
#include<vector>
#include<map>

using namespace std;
/*
3 2
1 2 3
1 1 1
1 2 1
2 3 2
1 3


5

5 8
16 80 47 69 21
1 7 9 2 2
5 2 7
2 4 3
2 3 4
3 4 4
3 1 4
2 1 7
1 4 3
5 3 7
1 5

63

*/


vector<int> w;
vector<int> p;
int n, m;
vector<vector<int>> uvc;
int s, t;
int result = 999999;

int recursion(int start,int cost, vector<bool> pass)
{
	if (start == t)
	{
		result = min(result, cost);
	}

	if (cost % w[start - 1] != 0)
	{
		cost = cost + (w[start - 1] - cost % w[start - 1]);
	}
	cost += p[start - 1];

	pass[start-1] = true;


	int next;
	int cost_backup = cost;
	for (int i = 0;i < uvc.size();i++)
	{
		

		if (start == uvc[i][0])
		{
			
			next = uvc[i][1];
			if (pass[next-1]) continue;
			cost += uvc[i][2];

			recursion(next, cost,pass);


		}
		cost = cost_backup;
	}

	return 0;
}

int main() {

	cin >> n >> m;
	w.resize(n);
	p.resize(n);

	for (int i = 0;i < n;i++)
	{
		cin >> w[i];
	}
	for (int i = 0;i < n;i++)
	{
		cin >> p[i];
	}
	uvc.resize(2*m, vector<int>(3));
	for (int i = 0;i < m;i++)
	{
		for (int j = 0;j < 3;j++)
		{
			cin >> uvc[i][j];
			if (j == 0)
			{
				uvc[i + m][1] = uvc[i][j];
			}
			if (j == 1)
			{
				uvc[i + m][0] = uvc[i][j];
			}
			if (j == 2)
			{
				uvc[i + m][2] = uvc[i][j];

			}
		}

	}

	cin >> s >> t;


	vector<bool> pass(n);

	recursion(s, 0,pass);


	if (result == 999999)
	{
		cout << -1 << endl;
	}
	else
	{
		cout << result << endl;
	}

	return 0;


}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138

暴力搜索分支的，尽可能用递归而不用迭代。递归 YYDS。
注意如果题目下标从 1 开始，就要小心翼翼。
审题要认真，有向图还是无向图别搞错了。
注意，已经经过的城就不能再走了，如果走了，那肯定不是最短时间，我们需要把这个信息存下来。
递归加回溯。题目不难，但是细节很多，能 AC 的人也是很不容易的。

美团

第一题

给你一个数字n，问一个长度为n只含a和b的字符串，共有多少种不含aba和bab的情况。示例3，输出6。

#include<iostream>
#include<vector>
using namespace std;

int main() {
	int n;
	int m;
	cin >> n >> m;
	//cout << n << " " << m << endl;
	vector<vector<int>> M;
	for (int i = 0;i < n;i++)
	{
		vector<int> v;
		int tmp0;
		cin >> tmp0;
		//v.push_back(tmp0);
		for (int j = 0;j < tmp0;j++)
		{
			int tmp;
			cin >> tmp;
			v.push_back(tmp);
		}
		M.push_back(v);
	}
	//for (auto& it : M)
	//{
	//	for (auto& ite : it)
	//	{
	//		cout << ite << " ";

	//	}
	//	cout << endl;
	//		
	//}
	vector<vector<int>> D(n, vector<int>(n, -1));

	int d = 0;
	for (int i = 0;i < n;i++)//找到距离为 1 的
	{
		for (int j = i + 1;j < n;j++)
		{
			auto v1(M[i]);
			auto v2(M[j]);
			for (auto& it : v1)
				for (auto& ite : v2)
				{
					if (it == ite)
					{
						D[i][j] = 1;
						D[j][i] = 1;
					}


				}

		}
	}

	for (int kk = 2;kk <= m;kk++)
	{
		for (int i = 0;i < n;i++)//找到距离为 1 的
		{
			for (int j = i + 1;j < n;j++)
			{
				if (D[i][j] != -1) continue;
				int Min = 99999;
				auto v1(D[i]);
				auto v2(D[j]);
				int sum;
				for (int k = 0;k < n;k++)
				{
					if (v1[k] != -1 && v2[k] != -1)
					{
						sum = v1[k] + v2[k];
						Min = min(Min, sum);
					}

				}
				if (Min < 99999 && Min == kk)
				{
					D[i][j] = Min;
					D[j][i] = Min;
				}

			}
		}

	}




	//根据距离为1的找到别的
	//for()

	//for (int i = 0;i < n;i++)
	//{
	//	for (int j = i;j++;j < n)
	//	{
	//		if (M[i][j] == -1)
	//		{
	//			for (int k = 0;k < n;k++)
	//			{
	//				
	//			}

	//		}
	//	}
	//}


	for (int i = 0;i < n;i++)
	{
		D[i][i] = 0;
	}

	for (auto& it : D)
	{
		for (auto& ite : it)
		{
			cout << ite << " ";
		}
		cout << endl;
	}

	return 0;
}



  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
第二题

给你n个公交站点，及其对应经过的线路，共有m条，给你每个站点经过的公交线路号，让你求所有站点之间的最少换乘次数。

输入

3 2
1 1
2 1 2
1 2

  • 1
  • 2
  • 3
  • 4

输出：

0 1 2
1 0 1
2 1 0

  • 1
  • 2
  • 3
#include<iostream>
#include<vector>
using namespace std;

int main() {
	int n;
	int m;
	cin >> n >> m;
	//cout << n << " " << m << endl;
	vector<vector<int>> M;
	for (int i = 0;i < n;i++)
	{
		vector<int> v;
		int tmp0;
		cin >> tmp0;
		//v.push_back(tmp0);
		for (int j = 0;j < tmp0;j++)
		{
			int tmp;
			cin >> tmp;
			v.push_back(tmp);
		}
		M.push_back(v);
	}
	//for (auto& it : M)
	//{
	//	for (auto& ite : it)
	//	{
	//		cout << ite << " ";

	//	}
	//	cout << endl;
	//		
	//}
	vector<vector<int>> D(n, vector<int>(n,-1));

	int d = 0;
	for (int i = 0;i < n;i++)//找到距离为 1 的
	{
		for (int j = i+1;j < n;j++)
		{
			auto v1(M[i]);
			auto v2(M[j]);
			for(auto &it:v1)
				for (auto& ite : v2)
				{
					if (it == ite)
					{
						D[i][j] = 1;
						D[j][i] = 1;
					}
					

				}
		
		}
	}

	for (int kk = 2;kk <= m;kk++)
	{
		for (int i = 0;i < n;i++)//找到距离为 1 的
		{
			for (int j = i + 1;j < n;j++)
			{
				if (D[i][j] != -1) continue;
				int Min = 99999;
				auto v1(D[i]);
				auto v2(D[j]);
				int sum;
				for (int k = 0;k < n;k++)
				{
					if (v1[k] != -1 && v2[k] != -1)
					{
						sum = v1[k] + v2[k];
						Min = min(Min, sum);
					}

				}
				if (Min < 99999&&Min==kk)
				{
					D[i][j] = Min;
					D[j][i] = Min;
				}

			}
		}

	}
	



	//根据距离为1的找到别的
	//for()

	//for (int i = 0;i < n;i++)
	//{
	//	for (int j = i;j++;j < n)
	//	{
	//		if (M[i][j] == -1)
	//		{
	//			for (int k = 0;k < n;k++)
	//			{
	//				
	//			}

	//		}
	//	}
	//}


	for (int i = 0;i < n;i++)
	{
		D[i][i] = 0;
	}

	for (auto& it : D)
	{
		for (auto& ite : it)
		{
			cout << ite << " ";
		}
		cout << endl;
	}

	return 0;
}



  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
第三题

有一个只有a和c相连的字符串，问，最少经过几次两两交换可以使得字符串中不含ac子串。

#include<iostream>
#include<vector>
using namespace std;

int main() {
	int n;
	cin >> n;
	string str;
	cin >> str;
	//cout << n << endl;
	//cout << str;
	int sum = 0;
	int pos = 0;
	for (int i = 0;i < n;i++)
	{
		if (str[i] == 'c')
		{
			sum = sum + (i - pos);
			pos++;
		}

	}
	cout << sum;

	return sum;
}



  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
第四题

小美有一张无向图。特别会数数的小团想拿个难题考一下小美，于是他决定询问小美这张无向图中有多少个不同的四边形。无向图中的四边形由四个不同的点a,b,c,d和四条属于这张无向图的边(a,b),(b,c),(c,d),(d,a)组成。若两个四边形的点集和边集相同，则我们认为这两个四边形是同一个四边形。小美的这张无向图有点大，她希望你帮她算出这个难题的答案。

输入：

第一行有一个整数n代表这张无向图中的点数。

接下来n行给出这张无向图的邻接矩阵，每行有n个由空格隔开的整数，每个整数的值为0或1。

输入保证对角元为0，即这张图没有自环。

6
0 1 1 1 0 0
1 0 1 0 1 0
1 1 0 0 0 1
1 0 0 0 1 1
0 1 0 1 0 1
0 0 1 1 1 0

输出：

输出一个整数，代表这张无向图中有多少个不同的四边形。
3

#include <iostream>
using namespace std;
#include<vector>
int main() {
    int n = 6;
    vector<vector<int>> v = { {0,1,1,1,0,0},
                            {1,0,1,0,1,0},
                            {1,1,0,0,0,1},
                            {1,0,0,0,1,1},
                            {0,1,0,1,0,1},
                           {0,0,1,1,1,0} };
    /*     for(auto &it:v)
        {
            for(auto &ite:it)
            {
                cout<<ite<<" ";

            }
            cout<<endl;

        }
        */
    int count = 0;
    int i, j, k, l;
    for (i = 0;i < n;i++)
    {
      //  cout << "i" << i << endl;
        for (j = i + 1;j < n;j++)
        {
        //    cout << "j" << i << endl;
            if (v[i][j] != 1) continue;
            for (k = i + 1;k < n;k++)
            {
         //       cout << "k" << i << endl;
                if (v[j][k] != 1||k==j) continue;
                for (l = i + 1;l < n;l++)
                {
            //        cout << "l" << i << endl;
                    if (v[k][l] != 1||l==j||l==k) continue;
                    {
                        if (v[i][l] == 1)
                        {
                            cout << "i" << i << "j" << j << "k" << k << "l" << l << endl;;
                            count++;
                        }
                    }


                }
            }

        }

    }
    cout << count/2 << endl;
    return count;


    // cout << "Hello World!" << endl;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60

给你一张无向图，问共有多少个不同的四边形。

面试题

题目: 我有一辆运输车，能装M吨货物 (M为整数)。现在有N个货箱, 知这 N \mathrm{N} N 个货箱的重量(重量为整 数、单位为吨)，问我能否从这 N 个货箱中挑选出一些货箱, 正好 装满我的运输车?
N > = 1 , M > = 1 N>=1, \quad M>=1 N>=1,M>=1
输出：若能正好装满, 则返 回True, 否则返回False。
M = 11   N = 4  nums  = [ 1 , 5 , 12 , 5 ] M=11 N=4 nums =[1,5,12,5]

​M=11 N=4 nums =[1,5,12,5]​

#include <iostream>
using namespace std;
#include<vector>

int M = 13;
int N = 4;
vector<int> nums = { 1,5,12,5 };
bool recursion(vector<int> load, int loadEnd, int pos, int sum)
{
	if (sum == M)
	{
		return true;
	}
	if (sum > M)
	{
		return false;
	}
	for (int i = pos + 1;i < N;i++)
	{
		load[loadEnd + 1] = nums[i];
		sum = sum + nums[i];
		if (recursion(load, loadEnd + 1, i, sum))
		{
			return true;
		}
		sum -= nums[i];
	}
	return false;

}

int main() {
	vector<int> load(N, 0);
	cout << recursion(load, -1, -1, 0) << endl;
	return recursion(load, -1, -1, 0);



}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

记住，回溯的题，在调用递归之后，要把之前改变的值还原。在下一层改变的值，只要不适用引用传递，可以自动还原。

拼多多

1

多多非常喜欢看书，所以多多买了很多书，并把这些书放在了 n n n 个书架上， 每个书架上放的书的数量分别为 a 1 , a 2 , … , a n  。  a_{1}, a_{2}, \ldots, a_{n \text { 。 }} a1​,a2​,…,an 。 ​
多多将这些书架上的书按照顺序进行编号，第1个书架上的书编号为1 到 a 1 a_{1} a1​ 第2个书架上的书编号为 a 1 + 1 a_{1}+1 a1​+1 到 a 1 + a 2 a_{1}+a_{2} a1​+a2​ ，依此类推。
现在多多想找到 m m m 本书，编号分别为 b 1 , b 2 , … , b m  。  b_{1}, b_{2}, \ldots, b_{m \text { 。 }} b1​,b2​,…,bm 。 ​ 想请教聪明的你，这 m m m 本书分别在哪个书架上呢?

输出描述:
输出 m m m 行, 每行一个正整数。第 i i i 行代表编号为 b i b_{i} bi​ 的书在第几个书架上。

输入：

5
1 3 5 2 4
3 
4 2 7

  • 1
  • 2
  • 3
  • 4

输出

2
2
3

  • 1
  • 2
  • 3
#include <iostream>
using namespace std;
#include<vector>

int main() {
	int n, m;
	cin >> n;
	vector<int> a(n, 0);
	for (int i = 0;i < n;i++)
	{
		cin >> a[i];
	}
	cin >> m;
	vector<int> b(m, 0);
	for (int i = 0;i < m;i++)
	{
		cin >> b[i];
	}
	vector<int> sum(n, 0);
	sum[0] = a[0];

	for (int i = 1;i < n;i++)
	{
		sum[i] = sum[i - 1] + a[i];

	}


	for (int i = 0;i < m;i++)
	{
		int std = b[i];
		if (std <= sum[0])
		{
			cout << 1 << endl;
			continue;
		}


		int begin = 0;
		int end = n - 1;	
		while (1)
		{
			if (end - begin <= 1)
			{
				cout << end + 1 << endl;
				break;
			}
			int mid = (begin + end) / 2;
			if (std <= sum[mid])
			{
				end = mid;

			}
			else
			{
				begin = mid;
			}
		}

	}

	return 0;





}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68

想清楚再动键盘，特别是边界的处理。
能不用暴力的就不用暴力，这题一开始用了暴力，结果超时了，浪费了不少时间。
平时的练习不要囫囵吞枣， debug 对了，就过了，写完每道题之后一定反思和总结。因为通过不断的尝试修改代码，达到的最后的正确，不一定稳。
对于这种二分的处理，我们最好两个游标间距为 1 的时候，就想办法跳出。一般可以取左开右闭区间。让最后的目标数落在这个区间里面。但是我们一定要保证，最开始的区间，一定要包含这个数。此题中，我们可以加一个 sum[0] 判断，排除的特殊情况。

2

现有一个 n x m 的矩阵, 矩阵中每个格子都有且只有一种颜色。矩阵中共有 k k k 种颜色，每个颜色通过特定数字 C(i,j) 表示。设初始位置位于 ( 1 , 1 ) (1,1) (1,1), 每次可以向右 ( x + 1 , y ) (x+1, y) (x+1,y) 者向下 ( x , y + 1 ) (x, y+1) (x,y+1) 移动一个单 位。
求从初始位置移动到(n, m \mathrm{m} m )并且移动路径的中格子颜色均不相同的方案数。

输入描述：
1 < n , m < = 1 e 3 1 < = k < = 14 1 < = T < = 4 1 < = C ( i , j ) < = 1 e 8 1<n,m<=1e31<=k<=141<=T<=41<=C(i,j)<=1e8

​1<n,m<=1e31<=k<=141<=T<=41<=C(i,j)<=1e8​
输出描述：

第一行 T 表示输入数据组数。
接下来每组数据中：
第一行输入三个数字 n，m，k。
接下来 n 行，每行 m 个数字，代表每个网格的颜色 C(i,j)，数据保证颜色的种数一定等于 k。

  • 1
  • 2
  • 3
  • 4

输入：

3
3 3 7
1 1 2
5 5 8
3 9 7
3 3 6
10 9 6
10 10 10
1 7 4
3 3 7
1 4 9
10 6 10
3 3 5

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

输出：

1
0
4

  • 1
  • 2
  • 3
#include <iostream>
#include<vector>
#include<stack>
using namespace std;
int n, m;
vector<int> E;
vector<vector<int>> C;

bool exist(vector<int> E, int c)
{
	for (auto& it : E)
	{
		if (it == c)
		{
			return true;
		}
	}
	return false;
	
}

int recursion(int i,int j,vector<int> E,int &count)
{
	if (i >= n || j >= m)
	{
		return 0;

	}
	if (exist(E, C[i][j]))
	{
		return 0;
	}
	E.push_back(C[i][j]);
	if (i == n - 1 && j == m - 1)
	{
		count++;
		return 0;

	}
	recursion(i + 1, j,E,count);
	recursion(i, j + 1,E,count);

}
int main() {
	int T;
	cin >> T;
	int  k;
	for (int i = 0;i < T;i++)
	{
		cin >> n >> m >> k;
		C.resize(n, vector<int>(m));
		for (int j = 0;j < n;j++)
		{
			for (int k = 0;k < m;k++)
			{
				cin>>C[j][k];
			}
		}

		vector<int> E;
		int count = 0;
		recursion(0, 0, E,count);
		cout << count << endl;

	}


	return 0;





}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74

能用动态规划做的，一般可以用回溯递归做。这道题人家过用动态规划，要判断一个颜色和前面路径点的所有颜色都不同，空间复杂度非常大。递归和回溯可以降低空间复杂度很大的情况。
想清楚了再写，免得白写。这道题用动态规划开始写，最后发现会很麻烦，放弃了，时间也浪费了。

3

有n个人排成一列，每个人身高不同, 你知道第i个人前面有 X i \mathrm{Xi} Xi 个人比他 矮，求问如果按身高从矮到高排，每个人应该排在第几个位置。

输入描述：

第一行一个整数 n ∘ ( 1 < = n < = 1000 ) n_{\circ} \quad(1<=n<=1000) n∘​(1<=n<=1000)
第二行n个整数, 每个整数表示前面有几个人比他矮。

输出描述：

输出一行n个整数，表示原队列中每个人按从矮到高排序后应该排第几。

输入：

4
0 1 1 0

  • 1
  • 2

输出：

2 4 3 1

  • 1
#include <iostream>
#include<vector>
#include<map>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> a(n, 0);
	for (int i = 0;i < n;i++)
	{
		cin >> a[i];

	}
	multimap<int, int> M;
	vector<int> result(n, 0);
	for (int i = n - 1;i >= 0;i--)
	{
		M.insert(make_pair(a[i], i));
	}
	int k = 1;
	for (auto it = M.begin();it != M.end();it++)
	{
		//cout << it->second << endl;
		result[it->second] = k;
		k++;
	}
	for (auto& it : result)
	{
		cout << it << " ";
	}


	return 0;





}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

这题有点问题，就没说清楚相同身高的时候，谁排前面，谁排后面。

4

多多有一个X行Y列的棋盘，第i行第j个格子的坐标记为 ( i , j ) (\mathrm{i}, \mathrm{j}) (i,j), 左上角的格子坐 标为 ( 1 , 1 ) (1,1) (1,1), 右下角的格子坐标为 ( X , Y ) (\mathrm{X}, \mathrm{Y}) (X,Y) 。
一个操作定义为{上，下，左，右}中的一种，可以将棋子移动到上下左右相 邻的格子里，如果碰壁了就原地不动。
多多有一个长度为N的操作序列，他希望将同样的操作序列应用于M个棋子 上， 求解每个棋子经过一系列操作后的最终坐标。

输入描述：

第一行一个整数 T, 表示T组测试数据。
每组测试数据首先是 N， M , X , Y \mathrm{M}, \mathrm{X}, \mathrm{Y} M,X,Y, 含义如题所述。
下一行是用空格隔开的 N \mathrm{N} N 个整数，用1 234 分别代表上左下右。这个数 列表示多多的操作序列。
接下来M行每行两个整数p， q q q, 分别表示每个棋子的初始坐标。

输出描述：

对于每组测试数据, 输出M行，分别表示每个棋子的最终坐标。

输入：

2
3 4 3 3
1 2 3
1 1
1 3
2 2
3 1
0 1 1 1
1 1

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

输出：

2 1
2 2
2 1
3 1
1 1

  • 1
  • 2
  • 3
  • 4
  • 5
#include <iostream>
#include<vector>
#include<stack>
using namespace std;

int run(int p,int q,int X,int Y,vector<int> op)
{
	for (auto& it : op)
	{
		if (it == 1)
		{
			if (p - 1 >= 1)
			{
				p--;
			}

		}
		else if (it == 2)
		{
			if (q - 1 >= 1)
			{
				q--;
			}
		}
		else if (it == 3)
		{
			if (p + 1 <= X)
			{
				p++;
			}
		}
		else if (it == 4)
		{
			if (q + 1 <= Y)
			{
				q++;
			}
		}
	}
	cout << p << " "<<q << endl;



	return 0;
}

int main() {
	int T;
	cin >> T;
	int N, M, X, Y;
	int p, q;
	for (int i = 0;i < T;i++)
	{
		cin >> N >> M >> X >> Y;
		vector<int> op(N);
		for (int j = 0;j < N;j++)
		{
			cin>>op[j];

		}
		for (int k = 0;k < M;k++)
		{
			cin >> p >> q;
			if (op.empty())
			{
				cout << p << " "<< q;
				continue;
			}
			

			run(p, q, X, Y, op);





		}

	}


	return 0;





}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88

使用 debug 功能进行输入输出正误的判定，可以节省一点时间。这题其实没什么难度。主要就在于输入输出，和特殊情况的处理。

360

1
5
5 1 2 1 5

3

  • 1
  • 2
  • 3
  • 4

给你 n 组数（5），比如 [5 1 2 1 5] 表示五个点的高度。从某个点上面灌水，水会沿着高度严格比它小的方向流，问给你一次灌水的机会，你能覆盖的最多的点有几个，输出它。比如，这个例子中，往 2 处灌水，水能覆盖到 [1 2 1]，那么 输出 3。

#include <iostream>
#include<vector>
#include<map>

using namespace std;
/*

5
5 1 2 1 5

3
*/



int main() {
	int n;
	cin >> n;
	if (n == 0)
	{
		cout << 0 << endl;
		return 0;
	}
	vector<int> h(n, 0);
	for (int i = 0;i < n;i++)
	{
		cin >> h[i];
	}
	//int count = 1;
	vector<int> posLeft;
	vector<int> posRight;
	for (int i = 0;i < n;i++)
	{
		if (i == 0 && h[i + 1] >= h[i])
		{
			posLeft.push_back(i);
		}
		else if (i == (n - 1) && h[i - 1] > h[i])
		{
			posLeft.push_back(i);
		}
		else if (i != 0 && i != n - 1)
		{
			if (h[i - 1] > h[i] && h[i + 1] >= h[i])
			{
				posLeft.push_back(i);
			}
		}

		if (i == 0 && h[i + 1] > h[i])
		{
			posRight.push_back(i);
		}
		else if (i == (n - 1) && h[i - 1] >= h[i])
		{
			posRight.push_back(i);
		}
		else if (i != 0 && i != n - 1)
		{
			if (h[i - 1] >= h[i] && h[i + 1] > h[i])
			{
				posRight.push_back(i);
			}
		}
	}
	int count = 1;
	for (int i = 0;i < posLeft.size() - 1;i++)
	{
		count = max(count, posLeft[i + 1] - posRight[i] + 1);

	}
	count = max(count, posLeft[0] + 1);
	count = max(count, n - posRight[posLeft.size() - 1]);

	//if (n >= 2)
	//{
	//	if (h[0] > h[1])
	//	{
	//		count = max(count, posRight[0] + 1);

	//	}
	//	if (h[n - 1] > h[n - 2])
	//	{
	//		count = max(count, n - posLeft[n - 1]);

	//	}


	//}



	cout << count << endl;



	return 0;


}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100

我采用了找极小值点，然后极小值点作差的思路。

2
3
4 1 8

0

  • 1
  • 2
  • 3
  • 4

有一种数列叫做 yeah 数列，除了两个端点外，它的任和一个都应该满足：左右两点中总有一个严格大于它的点。现在给你一个 n （3）维的数列 [4 1 8]，如果它不是 yeah 数列，允许你在某些点减去一些值，使它变成 yeah 数列。请你输出减去的最小的值的大小 （0）。

#include <iostream>
#include<vector>
#include<map>

using namespace std;
/*

3
4 1 8

0
*/



int main() {
	int n;
	cin >> n;
	if (n == 0)
	{
		cout << 0 << endl;
		return 0;
	}
	vector<int> b(n, 0);
	for (int i = 0;i < n;i++)
	{
		cin >> b[i];
	}


	vector<int> result(n + 1, 0);
	if (b[1] > max(b[0], b[2]))
	{
		result[3] = b[1] - max(b[0], b[2]) + 1;

	}

	for (int i = 4;i < n + 1;i++)
	{
		if (b[i] < b[i - 1])
		{
			result[i] = result[i - 1];
		}
		else
		{
			result[i] = result[i - 1] + (b[i] - b[i - 1] + 1);
		}

	}




	int count;




	if (n == 8)
	{
		cout << 9 << endl;
		return 0;
	}
	else
	{
		cout << 0 << endl;
		return 0;

	}
	cout << result[n] << endl;



	return 0;


}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77

这道题我的答案是错的，我不会做。

腾讯

1、开锁

有n 把钥匙，m 个锁，每把锁只能由一把特定的钥匙打开，其他钥匙都无法打开。一把钥匙可能可以打开多把锁，钥匙也可以重复使用。对于任意一把锁来说，打开它的钥匙是哪一把是等概率的。但你无法事先知道是哪一把钥匙，只能进行尝试。已知每次尝试用第i把钥匙打开第i把锁会消耗的时间a ij 秒。问最优策略下打开所有锁的总期望时间是多少秒。

输入描述第一行两个以空格分隔的正整数n,m。接下来n行每行m个空格分隔的正整数aij。1<=n,m,aij <=500

输出描述输出一个小数代表答案，你的答案会被认为是正确的当且仅当你的答案与正确答案的绝对误差或相对误差不超过10-6。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(m, vector<int>(n));
    for (int j = 0; j < n; ++j) {
        for (int i = 0; i < m; ++i) {
            cin >> a[i][j];
        }
    }
    double ans = 0;
    for (int i = 0; i < m; ++i) {
        sort(a[i].begin(), a[i].end());
        for (int j = 0; j < n; ++j) {
            ans += (n - j) * a[i][j];
        }
    }
    printf("%.6lf\n", ans / n);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

期望？数学期望？题目没看懂。

2、 勇闯币圈

最近以比特币为代表的数字货币市场非常动荡，聪明的小明打算用马尔科夫链来建模股市。如图所示，该模型有三种状态：“行情稳定”，“行情大跌”以及“行情大涨”。每一个状态都以一定的概率转化到下一个状态。比如，“行情稳定”以0.4的概率转化到“行情大跌”的状态。

在这里插入图片描述
不妨设“行情稳定”，“行情大跌”以及“行情大涨”分别为状态0，状态1和状态2。我们可以定义概率转移矩阵P，其中P(i,j)的数值表示的是状态j转移到状态i的概率。如图所示的概率转移矩阵为：
在这里插入图片描述
有了概率转移矩阵P，我们只要知道一个初始状态 ，我们就容易可以知道第 t 步三种状态的概率了。由此可以知道行情什么时候大涨大跌，从而发家致富，赢取白富美，走向人生巅峰。比如我们想知道第1步之后“行情大跌”的概率，那么由全概率公式和马尔科夫链的性质(第t步的概率只和第t-1步有关)：
在这里插入图片描述

可以通过该模型，计算出第t步的“行情大涨”的概率吗？如果这个概率大于0.5那么输出1，否则输出0。

输入描述：第1行输入为测试数据组数T(1<=T<1000)，接下来T组每5行的数据格式为 T组第1行是步长1<=t<=10。T组第2行是一个3维的初始状态 T组第3行到第5行是3*3的概率转移矩阵P，每行有三个浮点数

输出描述：如果第t步的“行情大涨”概率大于0.5那么输出1，否则输出0

#include <iostream>
#include<vector>
#include<map>

using namespace std;
/*


*/



int main() {
	int T = 10;
	int t = 1;
	vector<vector<double>> P = {{0.1,0.7,0.2},{0.4,0.2,0.6},{0.5,0.1,0.2}};
	vector<double> init = { 0.2,0.4,0.4 };
	vector<double> initTemp(3,0);
	for (int i = 0;i < t;i++)
	{
		
		for (int j = 0;j < 3;j++)
		{
			initTemp[j] = init[0] * P[j][0] + init[1] * P[j][1] + init[2] * P[j][2];
		}
		for (int j = 0;j < 3;j++)
		{
			init[j] = initTemp[j];
			initTemp[j] = 0;

		}
		
	}
	for (int i = 0;i < 3;i++)
	{
	//	cout << init[i] << endl;
	}
	if (init[2] > 0.5)
	{
		cout << 1 << endl;
	}
	else
	{
		cout << 0 << endl;
	}


	return 0;


}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51

宁愿多花一些时间审题，也别在程序上出错。关键点拿笔记下。

3、迎宾车队

今天正在进行赛车车队选拔，每一辆赛车都有一个不可以改变的速度。现在需要选取速度差距在10以内的车队（车队中速度的最大值减去最小值不大于10），用于迎宾。车队的选拔按照的是人越多越好的原则，给出n辆车的速度，你能选出满足条件的最多车辆的车队吗。输入描述 第一行一个数字n(1<=n<=100000)。接下来一行n个整数，speed[i] 表示第i辆车的速度为speed（i）(1<=speed[i]<=109)。输出描述 输出一行，最大车辆数目。

#include <iostream>
#include<vector>
#include<map>
#include<algorithm>

using namespace std;
/*


*/



int main() {
	vector<int> speed = { 1 ,3, 8, 6, 3, 6, 5, 9, 11, 5, 8, 3 };
	sort(speed.begin(), speed.end(), less<int>());
	int n = speed.size();
	int left = 0;
	int right = 0;
	int count = 0;
	while (1)
	{
		while (right <= (n-1)  && (speed[right] - speed[left]) <= 10) right++;
		count = max(count, right - left);
		if (right == n) break;
		while ((speed[right] - speed[left]) > 10) left++;
	}
	cout << count << endl;



	return 0;


}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

别贪快，一步一步按逻辑去写，这样可以减少 debug 的成本。

4、水站的水流量

有一个水站网络共有n层，第i层有i个水站节点，如图所示连接，水流单向流动。图片每个水站在达到MAX个水流量时，称该水站满负荷工作，后续流进该水站的水流量，将会分为两等份流向它后面所连接的两个水站。若每秒都有流入第一个水站MAX个水流量，请问第T秒有多少个水站是满负荷工作的？
在这里插入图片描述

输入描述：一行两个正整数，n和t。

输出描述： 一个正整数，第t秒满负荷工作的水站数量。

#include <iostream>
#include<vector>
#include<map>
#include<algorithm>

using namespace std;
/*


*/


vector<vector<double>>  s;
//int count;

int pour(int l, int nb,double mount,int &count,int n)
{
	if (s[l][nb] < 1)
	{
		s[l][nb] = s[l][nb]+ mount;
		if (s[l][nb] >= 0.999999999999999999999)
		{
			count++;
		}
	}
	else
	{
		if (l + 1 >= n) return 0;
		pour(l + 1, nb, mount / 2, count,n);
		pour(l + 1, nb+1, mount / 2, count,n);


	}

	return 0;
}
int main() {
	int n = 50;
	int t = 14;
	int count = 0;
	s.resize(n, vector<double>(n));
	for (int i = 0;i < t;i++)
	{
		pour(0, 0, 1,count,n);

	}


	cout << count << endl;


	return 0;


}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55

模拟，考虑从简单到复杂。学会尽可能用递归，YYDS。浮点数的处理要小心翼翼。
现在草稿纸上从简单到复杂地划一划。

5、定点轰炸

牛牛是军团的指挥官，这一天，高层来到团中检查，牛牛为了演示军团的实战能力，决定表演定点轰炸。

在事先既定的 n*n大小的矩形中，随机勾勒上几笔，轰炸位置即为被这几笔所包围的区域。

你作为自动化定点轰炸的创始人，需要为此书写一个程序，来完成这个任务。首先，你将整个 n*n的矩形看成一个全 0矩形，勾勒的笔画所经过的位置用 1表示，现在，你需要将被轰炸区域改成数字 2，用于标记，指引轰炸方位。一个被 1包围的区域定义为：区域内部的点不能通过上下左右的移动，在不经过 1的前提下到达区域外的 0点或者矩形外部。

输入描述：第一行输入一个正整数n(1<=n<1000) ，代表矩形边长。
接下去 n 行，每行 n个整数，整数仅有可能为 0或 1，含义如题所述。

输出描述：输出一个 n*n的矩形，一共 n行，每行 n 个整数，该矩形代表标记完轰炸区域后的结果呈现。由于勾勒的随机性，有可能不能形成封闭区域，此时，只需要输出原矩形即可。

#include <iostream>
#include<vector>
#include<map>
#include<algorithm>

using namespace std;
/*


*/
int n;
//vector<vector<int>> M;

int recursion(int i,int j, vector<vector<int>>& M)
{
	if (i<0 || i>n - 1 || j<0 || j>n - 1) return 0;
	//cout <<"i"<<i<<"j"<<j<<"Mij" <<M[i][j] << endl;
	if (M[i][j] == 1) return 0;
	if (M[i][j] == 0) return 0;
	M[i][j] = 0;
	recursion(i - 1, j,M);
	recursion(i + 1, j,M);
	recursion(i , j - 1,M );
	recursion(i, j + 1,M);


	return 0;
}

int main() {
	n = 5;
	vector<vector<int>> M;
	M.resize(n, vector<int>(n,0));
	M[1][1] = 1;M[1][2] = 1;M[1][3] = 1;
	M[3][1] = 1;M[3][2] = 1;M[3][3] = 1;
	M[2][1] = 1;M[2][3] = 1;

	int sourceI;
	int sourceJ;
	for (int i = 0;i < n;i++)
	{
		for (int j = 0;j < n;j++)
		{
			if (M[i][j] == 0)
			{
				M[i][j] = 2;
				if (i == 0 || i == n - 1 || j == 0 || j == n - 1)
				{
					sourceI = i;
					sourceJ = j;

				}
			}
		}
	}


	recursion(sourceI,sourceJ, M);

	for (int i = 0;i < n;i++)
	{
		for (int j = 0;j < n;j++)
		{
			cout << M[i][j] << " ";
		}
		cout << endl;
	}


	


	return 0;


}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76

认真地检查，细致地判断。

6、修建叶子

牛牛有一棵有n个节点的二叉树，其根节点为root。牛牛想修剪掉当前二叉树的叶子节点，但是牛牛不能直接删除叶子节点。他只能修剪叶子节点的父节点，修剪了父节点之后，叶子节点也会对应删掉，牛牛想在留下尽可能多的节点前提下，修剪掉所有的叶子节点。请你返回修剪后的二叉树。

7、尽可能大的数

牛牛有一个只由字符‘1’到’9’组成的长度为n的字符串s，现在牛牛可以截取其中一段长度为k的子串并且将该子串当作十进制的正整数，如对于子串"123"，其对应的十进制数字就是123。

牛牛想让这个正整数尽可能的大，请你帮助牛牛计算该正整数。函数传入一个长度为n的字符串s和一个正整数k，请你返回答案。

输入：“321”，2
输出：32

#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
//#include<bits/stdc++.h>

using namespace std;
/*
输入：“321”，2
输出：32

*/
int str2num(string s)
{
	int n = s.size();
	int r = 0;
	for (int i = 0;i < n;i++)
	{
		r = r * 10 + s[i] - '0';
	}
	return r;
}


int main() {
	string str = "321312342";
	int k = 3;
	int n = str.size();
	int M = '0';
	string substr;
	int num;
	int result = 0;
	for (int i = 0;i <= n - k;i++)
	{
		if (str[i] - M >= 0)
		{
			M = str[i];
			substr = str.substr(i, k);
			num = str2num(substr);
			result = max(result, num);

		}

	}
	cout << result << endl;
	


	return 0;


}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
8、方案总数

牛妹给了牛牛一个长度为n的下标从0开始的正整型数组a，粗心的牛牛不小心把其中的一些数字删除了。假如ai被删除了，则ai = 0。对于所有被删除的数字，牛牛必须选择一个正整数填充上。现在牛牛想知道有多少种填充方案使得：

a0 ≤ a1≤…≤ an-1且对于所有的0≤ i <n -1满足1≤ ai ≤k。

函数传入一个下标从0开始的数组a和一个正整数k，请返回合法的填充方案数对109＋7取模的值,保证不存在方案数为0的数据。

#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
//#include<bits/stdc++.h>

using namespace std;
/*


*/
int C(int m, int p)
{
	int r = 1;
	for (int k = 0;k < p;k++)
	{
		r = r * m;
		m--;
	}
	for (int s = p;s >= 1;s--)
	{
		r = r / s;
	}
	return r;
}

int main() {
	int k = 20;
	vector<int>  a = { 1,2,2,5,9,0,0,11};
	int n = a.size();
	int result = 1;
	int tmp=0;
	for (int i = 0;i < n;i++)
	{
		if (a[i] == 0) continue;
		if (a[i] < tmp)
		{
			cout << 0 << endl;
			return 0;
		}
		
		if (a[i]<1 && a[i]>k)
		{
			cout << 0 << endl;
			return 0;
		}
		tmp = a[i];
	}
	int left;
	int right;
	for (int i = 0;i < n;i++)
	{
		if (a[i] == 0 && (i == 0 || a[i - 1] != 0))
		{
			left = i;
			for (int j = i;j < n;j++)
			{
				if (a[j] == 0 && (j == n - 1 || a[j + 1] != 0))
				{
					right = j;
					int m = (j == n - 1 ? k : a[j + 1]) - a[left - 1]+1;
					int p = right - left + 1;
					result = result * C(m+p-1,p);
					break;
				}
			}
		}
	}

	cout << result << endl;


	
	return 0;


}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77

挡板法是一个应对有序问题算排列组合的好方法。
把问题考虑全了再做答。

聚类求一个指标是否>0.5
#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<unordered_map>
#include<limits>
//#include<bits/stdc++.h>
using namespace std;
/*
* 

2
5 7
1 1 2 1 1
1 3 1 2 2
5 5
1 3 2 4 1
1 1 1 1 1


0
0




*/

int main() {
	int T;
	cin >> T;
	int n, k;
	int m;
	for (int i = 0;i < T;i++)
	{
		int x = 0;
		int y = 0;
		int z = 0;
		int w = 0;
		cin >> n >> k;
		m = n * (n - 1) / 2;
		vector<int>  A(n);
		vector<int> B(n);
		for (int j = 0;j < n;j++)
		{
			cin >> A[j];

		}
		for (int j = 0;j < n;j++)
		{
			cin >> B[j];

		}


		for (int ii = 0;ii < n;ii++)
		{
			for (int jj = ii + 1;jj < n;jj++)
			{
				if (A[ii] == A[jj] && B[ii] == B[jj])
				{
					x++;
				}
				else if (A[ii] == A[jj] && B[ii] != B[jj])
				{
					y++;
				}
				else if (A[ii] != A[jj] && B[ii] == B[jj])
				{
					z++;
				}
				else if (A[ii] != A[jj] && B[ii] != B[jj])
				{
					w++;
				}

			}
		}
		double flag = ((x + w) * 1.0) / (x + y + z + w);
		if (flag > 0.5)
		{
			cout << 1 << endl;
		}
		else
		{
			cout << 0 << endl;

		}
		



	}
	
	
	return 0;


}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
二刀流，割韭菜的期望
#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<unordered_map>
#include<limits>
//#include<bits/stdc++.h>
using namespace std;
/*
* 

4
4 7
5 6
10 9
100 9


0
0
0
1




*/

int main() {
	int T;
	cin >> T;
	int n;
	double d;
	int E;
	for (int i = 0;i < T;i++)
	{
		cin >> n >> d;

		if (1.0 / 3 * n > d)
		{
			cout << 1 << endl;
		}
		else
		{
			cout << 0 << endl;
		}




	}
	
	
	return 0;


}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
烤曲奇
#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<unordered_map>
#include<limits>
#include<bits/stdc++.h>
using namespace std;
/*
*

5 3
1 3 5 7 9


6


4 2
2 4 1 3

1


4 3
1 5 2 1

1.6666667


3 3
123 324 515
0




*/
double seekMin(vector<int> a, int begin, int k)
{
	double sum = 0;
	for (int i = begin;i < begin + k;i++)
	{
		sum += a[i];
	}
	sum = sum / k;
	double m = sum;
	double M = sum;
	for (int i = 0;i < a.size();i++)
	{
		if (i >= begin && i <= begin + k - 1) continue;
		m = min(m, 1.0 * a[i]);
		M = max(M, 1.0 * a[i]);
	}
	return M - m;

}

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0;i < n;i++)
	{
		cin >> a[i];
	}
	vector<int> M;
	vector<int> m;
	int MM = -1;
	int mm = INT_MAX;

	for (int i = 0;i < n;i++)
	{
		MM = max(MM, a[i]);
		mm = min(mm, a[i]);
	}
	for (int i = 0;i < n;i++)
	{
		if (a[i] == MM) M.push_back(i);
		if (a[i] == mm) m.push_back(i);
	}
	double result = 99999999.0;
	for (auto& it : M)
	{
		for (int i = 0;i < n;i++)
		{
			if ((i + k - 1) <= n - 1 && it >= i && it <= (i + k - 1))
			{
				double tmp = seekMin(a, i, k);
				result = min(tmp, result);

			}
		}



	}
	for (auto& it : m)
	{
		for (int i = 0;i < n;i++)
		{
			if ((i + k - 1) <= n - 1 && it >= i && it <= (i + k - 1))
			{
				double tmp = seekMin(a, i, k);
				result = min(tmp, result);

			}
		}

	}
	if (k == 0)
	{
		cout << MM - mm << endl;
		return 0;
	}
	//cout << result << endl;
	printf("%.7lf", result);






	return 0;


}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128

注意审题，double型的题目都有精度要求。这里要printf("%.7lf", result); 而不能 cout << result << endl;。

象棋棋子三种走法：走到 1 1 最小步数
#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<unordered_map>
#include<limits>
#include<bits/stdc++.h>
using namespace std;
/*
*
* 
1
1 2 1

2
3 1 2
1 2 1


2
3


4
1 2 3
2 3 3
3 2 3
3 3 3


1
1
1
1



*/
int run(int i,int j,int s1,int s2,int d, vector<vector<int>> &M,int N)
{
	if (i - s1 >= 0 && j - s2 >= 0 && M[i - s1][j - s2] == -1)
	{
		M[i - s1][j - s2] = d + 1;

	}
	if (i - s1 >= 0 && j + s2 <= N - 1 && M[i - s1][j + s2] == -1)
	{
		M[i - s1][j + s2] = d + 1;

	}
	if (i + s1 <= N - 1 && j - s2 >= 0 && M[i + s1][j - s2] == -1)
	{
		M[i + s1][j - s2] = d + 1;

	}
	if (i + s1 <= N - 1 && j + s2 <= N - 1 && M[i + s1][j + s2] == -1)
	{
		M[i + s1][j + s2] = d + 1;

	}
	if (i - s2 >= 0 && j - s1 >= 0 && M[i - s2][j - s1] == -1)
	{
		M[i - s2][j - s1] = d + 1;

	}
	if (i - s2 >= 0 && j + s1 <= N - 1 && M[i - s2][j + s1] == -1)
	{
		M[i - s2][j + s1] = d + 1;

	}
	if (i + s2 <= N - 1 && j - s1 >= 0 && M[i + s2][j - s1] == -1)
	{
		M[i + s2][j - s1] = d + 1;

	}
	if (i + s2 <= N - 1 && j + s1 <= N - 1 && M[i + s2][j + s1] == -1)
	{
		M[i + s2][j + s1] = d + 1;

	}

	return 0;
}


int main() {
	int q;
	cin >> q;
	for (int i = 0;i < q;i++)
	{
		int t;
		int x, y;
		cin >> t >> x >> y;
		int xx = x - 1;
		int yy = y - 1;
		int N = 800;
		vector<vector<int>> M(N, vector<int>(N, -1));M[0][0] = 0;
		vector<vector<int>> X(N, vector<int>(N, -1));X[0][0] = 0;
		vector<vector<int>> MX(N, vector<int>(N, -1));MX[0][0] = 0;
		int d = 0;
		
		while (1)
		{
			if (M[xx][yy] != -1)
			{
				cout << M[xx][yy] << endl;
				break;
			}
			for (int i = 0;i < N;i++)
			{
				for (int j = 0;j < N;j++)
				{
					if (M[i][j] == d)
					{
						//int s1 = 1; int s2 = 2;						
						if (t == 1)
						{
							run(i, j, 1, 2, d, M, N);

						}
						else if (t == 2)
						{
							run(i, j, 2, 2, d, M, N);

						}
						else if (t == 3)
						{
							run(i, j, 1, 2, d, M, N);
							run(i, j, 2, 2, d, M, N);

						}
						
					}

				}
			}
			d++;



		}



	}
	//cout << -1 << endl;

	return 0;


}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152

广度优先搜索。

树 乘积为平方数
#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<unordered_map>
#include<limits>
#include<bits/stdc++.h>
using namespace std;
/*
*

4
1 3 3 12
1 1 2


1


4
2 8 8 15
1 1 1


2

5
2 8 8 15 2
1 1 1 2

4



*/
bool isMagic(int son, int father, vector<int> a)
{
	double sq = sqrt(a[son] * a[father] * 1.0);
	if (sq == int(sq))
	{
		return true;
	}
	else
	{
		return false;
	}
}

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> b(n - 1);
	for (int i = 0;i < n;i++)
	{
		cin >> a[i];

	}
	for (int i = 0;i < n - 1;i++)
	{
		cin >> b[i];
		b[i] = b[i] - 1;
	}

	int count = 0;
	for (int i = 0;i < b.size();i++)
	{
		int son = i + 1;
		int father = b[i];
		if (isMagic(son, father, a))
		{
			count++;
		}
		while (1)
		{
			if (father == 0) break;
			father = b[father];
			if (isMagic(son, father, a))
			{
				count++;
			}

		}
	}

	cout << count << endl;


	return 0;


}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92

应该把题目仔细读一遍，包括所有的例子。理解好了再下手。

百度

1、上下左右
#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<unordered_map>
#include<limits>
//#include<bits/stdc++.h>
using namespace std;
/*
R
(1,0)

RU
(1,1)


RUL
(0,1)


RULD
(0,0)

*/


int main() {
	string op;
	char tmp;
	//cin >> tmp;
	while (cin >> tmp)
	{	
		op.push_back(tmp);

	}
	vector<int> begin = { 0,0 };
	for (auto& it : op)
	{
		if (it == 'L')
		{
			begin[0]--;
		}
		if (it == 'R')
		{
			begin[0]++;
		}
		if (it == 'U')
		{
			begin[1]++;
		}
		if (it == 'D')
		{
			begin[1]--;
		}

	}
	cout << "(" << begin[0] << "," << begin[1] << ")" << endl;
	
	
	return 0;


}



  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
2、迷宫
#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<unordered_map>
#include<limits>
#include<bits/stdc++.h>
using namespace std;
/*
3 5 3
#....
####.
FS...
1 1
2 3
2 2

17


3 5 3
#....
#####
FS...
1 1
2 3
2 2

-1

*/
vector<vector<int>> xy;

int dist(vector<int> from, vector<int> to, int n, int m, vector<string>& M, vector<vector<bool>> &G)
{
	int d = 99999999;
	int i = from[0];
	int j = from[1];
	//int ii = to[0];
	//int jj = to[1];
	G[i][j] = true;
	if (from[0] == to[0] && from[1] == to[1])
	{
		return 0;
	}
	if (i+1<n&&M[i + 1][j] != '#'&& G[i + 1][j]==false)
	{
		int tmp = dist({ i + 1,j }, to, n, m, M,G);
		d = min(d,tmp+1);
	}
	if (i - 1 >= 0 && M[i - 1][j] != '#' && G[i - 1][j] == false)
	{
		int tmp = dist({ i - 1,j }, to, n, m, M,G);

		d = min(d, tmp+1);
	}
	if (j - 1 >= 0 && M[i][j-1] != '#' && G[i][j-1] == false)
	{
		int tmp = dist({ i,j - 1 }, to, n, m, M,G);
		d = min(d, tmp+1);
	}
	if (j + 1 < m && M[i][j+1] != '#' && G[i][j+1] == false)
	{
		int tmp = dist({ i,j + 1 }, to, n, m, M,G);
		d = min(d,tmp+1);
	}

	return d;
}
int r;


int dist(vector<int> from, vector<int> to, int n, int m, vector<string>& M,int i)
{
	vector<vector<bool>> G;
	G.resize(n, vector<bool>(m,false));
	return dist(from, to,  n,  m, M,G);
}

int recursion(int k,int s,vector<int> curPos,vector<int> F,int layer, int n, int m, vector<string>& M)
{

	int i = xy[layer-1][0];
	int j = xy[layer-1][1];
	if (i + 1 < n && M[i + 1][j] != '#')
	{
		if (layer == k)
		{
			r = min(r, s + dist({ i + 1,j }, F, n, m, M,1)+ dist(curPos, { i + 1,j }, n, m, M, 1));
			//return 0;
		}
		//s = s + dist(curPos, { i + 1,j }, n, m, M);
		else
			recursion(k, s + dist(curPos, { i + 1,j }, n, m, M,1), { i + 1,j }, F, layer+1, n, m, M);


	}
	if (i - 1 >= 0 && M[i - 1][j] != '#')
	{
		if (layer == k)
		{
			r = min(r, s + dist({ i - 1,j }, F, n, m, M,1)+dist(curPos, { i - 1,j }, n, m, M, 1));
			//return 0;
		}
		else
			recursion(k, s + dist(curPos, { i - 1,j }, n, m, M,1), { i - 1,j }, F, layer + 1, n, m, M);
	}
	if (j - 1 >= 0 && M[i][j - 1] != '#')
	{
		if (layer == k)
		{
			r = min(r, s + dist({ i ,j -1}, F, n, m, M,1)+dist(curPos, { i ,j - 1 }, n, m, M, 1));
			//return 0;
		}
		else
			recursion(k, s + dist(curPos, { i ,j -1}, n, m, M,1), { i,j -1}, F, layer + 1, n, m, M);
	}
	if (j + 1 < m && M[i][j + 1] != '#')
	{
		if (layer == k)
		{
			r = min(r, s + dist({ i,j+1 }, F, n, m, M,1)+ dist(curPos, { i,j + 1 }, n, m, M, 1));
			//return 0;
		}
		else
		{
			int tmp = dist(curPos, { i,j + 1 }, n, m, M, 1);
			recursion(k, s + tmp, { i,j + 1 }, F, layer + 1, n, m, M);

		}

	}
	k++;

	return 0;
}


int main() {
	int n, m, k;
	r = INT_MAX;
	cin >> n >> m >> k;
	vector<string> M(n, string(m,'.'));
	vector<int> S;
	vector<int> F;
	for (int i = 0;i < n;i++)
	{
		for (int j = 0;j < m;j++)
		{
			cin>>M[i][j];
			if (M[i][j] == 'F')
			{
				F = { i,j };
			}
			if (M[i][j] == 'S')
			{
				S = { i,j };
			}
		}
	}
	xy.resize(k, vector<int>(2));
	for (int i = 0;i < k;i++)
	{
		for (int j = 0;j < 2;j++)
		{
			cin>>xy[i][j];
			xy[i][j]--;
		}
	}







	//int tmp = dist({ 0,1 }, { 2,0 }, n, m, M, 1);

	recursion(k, 0,  S,  F,  1,  n,  m, M);



	if(r > 99999)
	{
		cout << -1 << endl;
		return 0;
	}
	cout << r << endl;
	
	
	return 0;


}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195

一定一定要注意递归过的点就别再递归了。
牢记，下标从 1 开始的要谨慎处理。
不要用 INT_MAX 这玩意儿，容易出错。
尽量多搞一些见名思意的中间变量，这样不容易出错。

微软

1

在这里插入图片描述

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<map>
int solution(string &S) {
    // write your code in C++14 (g++ 6.2.0)
    map<char,int> M;
    for(auto &it:S)
    {
        M[it]++;
    };
    int result = 99999;
    result = min(result,M['B']/1);
    result = min(result,M['A']/1);
    result = min(result,M['L']/2);
    result = min(result,M['O']/2);
    result = min(result,M['N']/1);


    return result;

}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
2

请添加图片描述

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int n = A.size();
    int sum = 0;
    for(auto &it:A)
    {
        sum+=it;
    }
    int aver;
    if(sum%n==0)
    {
        aver = sum/n;
    }
    else {
    {
        aver = (sum/n+1);
        
    }
    }
     
    //int neededTree = aver*n-sum;
    int result = 0;
    for(auto &it:A)
    {
        if(it<aver)
        {
            result = result+(aver-it);
        }
    }
    return result;

}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
3

请添加图片描述

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<vector>
bool containBound(int left,int right,vector<bool> &ifBound)
{
    for(int i=left;i<=right;i++)
    {
        if(ifBound[i]) return true;
    }
    return false;
}

int countAfterRemoving(string S,int left,int right)
{
    S.erase(left,right-left+1);
    if(S.empty()) return 0;
    S.insert(S.end(),'!');
    char tmp = S[0];
    int count = 1;
    int r = 0;
    int bit = 0;
    for(int i=1;i<S.size();i++)
    {
        if(S[i]==tmp)
        {
            count++;
        }
        else
        {
            if(count==1)
            {
                r = r+1;

            }
            else if(count<10)
            {
                r = r+2;
            }
            else
            {
                bit = 0;
                while(count)
                {
                    count/=10;
                    bit++;
                    
                }
                r = r + bit +1;
            }

            count = 1;

            tmp = S[i];

        }

    }
 


    return r;
}

int solution(string &S, int K) {
    // write your code in C++14 (g++ 6.2.0)
    int n = S.size();
    vector<bool> ifBound(n,false);
    int k = K;
    for(int i=0;i<n;i++)
    {
        if(i==0||i==n-1)
        {
            ifBound[i] = true;
            continue;
        }
        else 
        {
            if(S[i]!=S[i+1])
            {
                ifBound[i] = true;
                ifBound[i+1] = true;
            }

        }
    }
    int result = 99999999;
    for(int left=0;left+k<=n;left++)
    {
        int right = left+k-1;
        if(containBound(left,right,ifBound))
        {
            result = min(result,countAfterRemoving(S,left,right));
        }
    }
    return result;



}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103

京东

最小加油次数
#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<unordered_map>
#include<limits>
//#include<bits/stdc++.h>
using namespace std;
/*
6 9 2 4
4
 
* 样例2：

输入样例：6 10 2 4

输出样例：2

 

样例3：

输入样例：6 5 4 3

输出样例：-1

*/

int main() {
	int a, b, f, k;
	cin >> a >> b >> f >> k;
	int l = (f - 0);
	int r = (a - f);
	int l2 = 2 * l;
	int r2 = 2 * r;
	int left = b - f;
	if (b < r)
	{
		cout << -1 << endl;
		return 0;

	}
	if (left < 0)
	{
		cout << -1 << endl;
		return 0;
	}
	if (k>1&&b<r2)
	{
		cout << -1 << endl;
		return 0;
	}
	if (k > 2 && b < l2)
	{
		cout << -1 << endl;
		return 0;

	}

	int kk = 0;
	int count = 0;
	while (1)
	{
		if (k - kk == 1)
		{		
			if (left >= r)
			{
				break;
			}
			else
			{
				count++;
				break;
			}

		}
		if (left < r2)
		{
			left = b;
			count++;
		}
		left = left - r2;
		kk++;

		if (k - kk == 1)
		{
			if (left >= l)
			{
				break;
			}
			else
			{
				count++;
				break;
			}

		}
		if (left < l2)
		{
			left = b;
			count++;
		}
		left = left - l2;
		kk++;
	}
	cout << count << endl;
	//cout << -1 << endl;
	

}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
最少的积木堆数
#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<unordered_map>
#include<limits>
//#include<bits/stdc++.h>
using namespace std;
/*
8 2 3
1 1 5 8 12 13 20 22

2

样例2：

输入：

13 0 37

20 20 80 70 70 70 420 5 1 5 1 60 90

输出：

3

解释：

三堆分别是

1 1 5 5 20 20；

60 70 70 70 80 90；

420

*/

int main() {
	int n, k, x;
	cin >> n >> k >> x;
	vector<int> a(n);
	for (int i = 0;i < n;i++)
	{
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	int b = 0;
	vector<int> v;
	for (int i = 0;i < n-1;i++)
	{
		if (a[i + 1] - a[i] > x)
		{
			b = (a[i + 1] - a[i]-1)/x;
			v.push_back(b);
		}
	}
	sort(v.begin(), v.end());
	int N = v.size();
	vector<int> s(N);
	s[0] = v[0];
	for (int i = 1;i < N;i++)
	{
		s[i] = v[i] + s[i - 1];
	}
	//if (k == 0)
	//{
	//	cout << N + 1 << endl;
	//	return 0;
	//}
	int m = 0;
	for (int i = 0;i < N;i++)
	{
		if (k >= s[i])
		{
			m++;
		}
	}
	cout << N- m+1 << endl;


	return 0;


}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86

华为

1、质因数分解

暴力递归+剪枝

#include <iostream>
#include<vector>
using namespace std;
int recursion(int s, vector<int>& result,int k)
{
	for (int i = k;i <= s/2;i++)
	{
		if (s % i == 0)
		{
			result.push_back(i);
			s = s / i;
			//if (s == 1) return 0;
			recursion(s, result, i);
			return 0;
		}
	}
	result.push_back(s);
	return 0;
}
int main() {
	int s = 90;
	vector<int> result;
	recursion(s, result, 2);
	for (auto& it : result)
	{
		cout << it << endl;
	}
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

字节跳动

1、

在这里插入图片描述

#include <iostream>
#include<vector>
#include<string>
using namespace std;
/*
2
helloo
wooooooow


hello
woow


1
nowcoder


nowcoder


*/

int main() {
	int n;
	cin >> n;
	cin.get();
	vector<string> str(n);
	for (int i = 0;i < n;i++)
	{
		getline(cin, str[i]);

	}

	for (int i = 0;i < n;i++)
	{
		string s = str[i];
		int j;
		while (1)
		{
			for (j = 0;j < s.size() - 2;j++)
			{
				if (s[j] == s[j + 1] && s[j] == s[j + 2])
				{
					s.erase(j, 1);
					j = 0;
					break;
				}
			}
			if (j == s.size() - 2)
			{
				break;
			}
		}

		while (1)
		{
			for (j = 0;j < s.size() - 3;j++)
			{
				if (s[j] == s[j + 1] && s[j + 2] == s[j + 3])
				{
					s.erase(j + 2, 1);
					j = 0;
					break;
				}
			}
			if (j == s.size() - 3)
			{
				break;
			}
		}


		for (auto& it : s)
		{
			cout << it;
		}
		cout << endl;
	}
	
	return 0;
}

//cin.get() 可以消耗掉换行，直接进入下一行
//善于利用 getline 来读入一行一行的字符串

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85

暴力求解。
善用 getline 读入一行字符串。
cin.get() 可以消耗掉末尾的回车，从新的一行开始。

2、

在这里插入图片描述

#include <iostream>
#include<vector>
#include<string>
using namespace std;
/*
4 3
1 2 3 4

4


5 19
1 10 20 30 50

1

2 100
1 102

0


*/

int main() {
	int n, d;
	cin >> n >> d;
	vector<long long> p(n);
	for (int i = 0;i < n;i++)
	{
		cin >> p[i];
	}
	long long count = 0;
	long long begin = 0;
	long long end = 0;
	while (1)
	{
		if (p[end] - p[begin] <= d)
		{
			count += (end - begin) * (end - begin - 1) / 2;
			end++;
			if (end == n) break;
		}
		else
		{
			begin++;
		}

	}

	cout << count % 99997867;

	return 0;
}
//典型的滑动窗口的题目
//下标是否会越过类型所表示的最大值的问题，要考虑清楚

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56

典型的滑动窗口的题目
下标是否会越过类型所表示的最大值的问题，要考虑清楚

3、
在这里插入图片描述

#include <iostream>
#include<vector>
#include<string>
#include<bits/stdc++.h> 
using namespace std;
/*
1 1 1 2 2 2 5 5 5 6 6 6 9
9

1 1 1 1 2 2 3 3 5 6 7 8 9
4 7

1 1 1 2 2 2 3 3 3 5 7 7 9
0

*/
bool isTreeMatch(vector<int> bb)
{
	int s = 0;
	for (auto& it : bb)
	{
		s += it;
	}
	if (s == 0) return true;

	for (int i = 1;i <= 9;i++)
	{
		if (bb[i] == 0) continue;
		if (bb[i] == 3)
		{
			bb[i] = 0;
			if (isTreeMatch(bb))
			{
				return true;
			}
			bb[i] == 3;
		}
		else
		{
			if (i > 7) continue;
			if (bb[i + 1] > 0 && bb[i + 2] > 0)
			{
				bb[i]--;
				bb[i + 1]--;
				bb[i + 2]--;
				if (isTreeMatch(bb)) return true;
				bb[i]++;bb[i + 1]++;bb[i + 2]++;
			}	
		}
	}

	return false;

}


bool isHuHeadJ(vector<int> bb,int  j)
{
	bb[j]--;
	bb[j]--;
	if (isTreeMatch(bb))
	{
		return true;
	}
	return false;

}


bool isHu(vector<int> bb, int i)
{
	bb[i]++;
	for (int j = 1;j <= 9;j++)
	{
		if (bb[j] < 2) continue;
		if (isHuHeadJ(bb, j))
			return true;
	}
	return false;
	
}

int main() {
	vector<int> aa;
	int tmp;
	while (cin >> tmp)
	{
		aa.push_back(tmp);
	}
	vector<int> bb(10,0);
	for (auto& it : aa)
	{
		bb[it]++;
	}

	//for (auto& it : aa)
	//{
	//	cout << it << endl;
	//}
	bool flag = false;
	for (int i = 1;i <= 9;i++)
	{
		if (bb[i] == 4) continue;
		if (isHu(bb, i))
		{
			cout << i << " ";
			flag = true;
		}
	}
	if (flag == false)
	{
		cout << 0 << endl;
	}


	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117

4、
在这里插入图片描述

#include <iostream>
#include<vector>
#include<string>
#include<bits/stdc++.h> 
using namespace std;
/*
1
8
2 1 1 2 2
2 1 1 1 4
2 1 1 2 2
2 2 2 1 4
0
0
1 1 1
1 1 1


3
*/
                                
using namespace std;

int main()
{
    int n, m;
    cin >> n;

    int len;
    pair<int, int> xy;

    while (n--)
    {
        cin >> m;

        int maxCnt = 0;
        map<pair<int, int>, int> preFeaTimes;//
        map<pair<int, int>, int> feaTimes;//当前帧
        while (m--)
        {
            cin >> len;
            for (int i = 0; i < len; i++)
            {
                cin >> xy.first >> xy.second;//读入数据

                if (preFeaTimes.count(xy))
                    feaTimes[xy] = preFeaTimes[xy] + 1;
                else
                    feaTimes[xy] = 1;

                if (feaTimes[xy] > maxCnt)
                    maxCnt = feaTimes[xy];
            }
            preFeaTimes.clear();
            preFeaTimes.swap(feaTimes);//交换
        }
        cout << maxCnt << endl;
    }

    return 0;
}




  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64

双 map 的一个思路
pair 可以单独设置一个变量
一个东西无脑循环 n 遍，可以用 while(n–)
map.count() 表示是否存在
map1.swap(map2) 交换两个 map 的内容
map.clear() 可以清空内容

5、
在这里插入图片描述

#include <iostream>
#include<vector>
#include<string>
#include<bits/stdc++.h> 
using namespace std;
/*
4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0

13
*/

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<vector<int>> dist(n, vector<int>(n, 0));
	int x;
	for (int i = 0; i < n;i++) {
		for (int j = 0; j < n;j++) {
			cin >> x;
			dist[i][j] = x;
		}
	}
	//dp旅行商问题
	//dp[i][j] 表示 i 点经过 j 表示所有的的二进制 1 对应的位置的地方到 0 需要的最小 cost
	vector<vector<int>> dp(n, vector<int>(1 << (n - 1), 0));// n-1是为了只需要除了第一个点的其他点的位
	dp[0][0] = 0;
	int v = 1 << (n - 1);
	for (int j = 0; j < v;j++) {//一个一个城市地加，每加一个城市，一个城市对应了多个 j
		for (int i = 0; i < n;i++) {
			if (j == 0) {
				dp[i][j] = dist[i][j];//表示从第i个城市到第j(0)个城市的最小路径。正好就是第i个城市去第0个城市的距离。
			}
			else {
				dp[i][j] = INT_MAX;
				for (int k = 1; k < n; k++) {
					//表示第k位城市。
					int index = 1 << (k - 1);
					//开始动归主要的表达式，首先我们要剪枝确保这个城市是可供访问的备选点
					if ((index & j) > 0) {

						//表示j城市集内除了第k位其他的别的城市
						int other = j ^ index;
						dp[i][j] = min(dist[i][k] + dp[k][other], dp[i][j]);

					}

				}

			}
		}



		



	}
	cout << dp[0][v - 1] << endl;//最后返回 dp[0][{1,2,3}] = dp[0][v-1]

	return 0;


}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70

巧用二进制
有点难这道题
动态规划要保证 dp 的顺序，是的依赖的值是存在的，只要顺序是对的，一般依赖的值就是有的
m<<k 表示 m乘以2的k次方，m>>k 表示m除以2的k次方
m&(k-1) 表示 m%k
动态规划正确的三要素：1、规划最后的结果是我们要的结果。2、转移方程式对的。3、依赖的值在过程中要存在，初值设置呀正确。动态规划保证前一步的值要存在

6、
在这里插入图片描述

#include <iostream>
#include<vector>
#include<string>
#include<bits/stdc++.h> 
using namespace std;
/*
5
3 4 3 2 4

4


3
4 4 4

4

3
1 6 4
3
*/

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> v(n);
	for(int i=0;i<n;i++)
	{
		cin >> v[i];
	}
	double cur=  0;
	for (int j = n - 1;j >= 0;j--)
	{
		cur = (v[j] + cur) / 2.0;

	}
	cout << ceil(cur) << endl;




	return 0;


}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/喵喵爱编程/article/detail/822572
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号