滴滴笔试（9.17）

算法卷，两道题

第一题

小昱做了很久的实验得到了一个用正整数表示的实验数据，并记录在了纸上。但是由于做完实验太过激动，他一不小心把墨水打翻溅在了纸上，导致数据中一些位置上的数字看不清楚。他仍记得这个数据有以下三个特征：
1. 这个数是正整数，且没有前导零（即数的最高位不是0）
2. 这个数任意两个相邻数位的数字不同
3. 这个数可以被3整除
他现在很关心在满足以上特征的条件下，这个数字最小为多少。

输入描述
输入一个由数字0-9和‘?’构成的字符串。若输入的第i个字符为问号，则表示数据从高位往低位数的第i位被墨水遮盖，不能确定是哪个数字；否则，表示这一位未被墨水遮盖，是一个确定的数。
输出描述
输出一个正整数，表示实验数据最小可能是多少。

样例输入
?12?0?9??
样例输出
212101902

提示
输入的字符串长度不超过100000，且至少为1。
所有数据均保证合法，保证存在合法解，且至少含有1个‘?’。
最高位为‘?’表示最高位被遮挡无法确定。因为第一条特征限制，最高位不能为0。因为第二位为1，根据第二条限制，最高位不能为1。所以最高位只能是2到9中的任意一个数字，当最高位为2时，实验数据会最小。第4、6、8、9位数字也被墨水遮挡，当第4、6位为数字1，第8位为数字为0，第9位为数字2时满足小昱记忆中数据的特征，且是可能出现的最小值。

int main()
{
	string s;
	cin >> s;
	int pre = -1, post = -1;
	int last_idx = -1;
	int now_sum = 0;
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] != '?')
		{
			now_sum = (now_sum + (s[i] - '0')) % 3;
			continue;
		}

		last_idx = i;
		if (i >= 1)
			pre = s[i - 1] - '0';
		else
			pre = 10;

		if (i < s.length() - 1)
		{
			if (s[i + 1] == '?')
				post = 10;
			else
				post = s[i + 1] - '0';
		}
		else
			post = 10;

		for (int k = 0; k <= 9; k++)
		{
			if (i == 0 && k == 0)
				continue;
			if (k != pre && k != post)
			{
				s[i] = '0' + k;
				break;
			}
		}
		now_sum = (now_sum + (s[i] - '0')) % 3;
	}

	if (now_sum % 3 !=0)
	{
		if (last_idx >= 1)
			pre = s[last_idx - 1] - '0';
		else
			pre = 10;

		if (last_idx < s.length() - 1)
		{
			if (s[last_idx + 1] == '?')
				post = 10;
			else
				post = s[last_idx + 1] - '0';
		}
		else
			post = 10;

		for (int k = s[last_idx] - '0' + (3- now_sum); k <= 9; k = k + 3)
		{
			if (k != pre && k != post)
			{
				s[last_idx] = '0' + k;
				break;
			}
		}
	}
	cout << s;
	return 0;
}

第二题

小明正在刷栅栏。为了使得栅栏在经过风吹雨打后依然不掉色，需要用两种不同的油漆刷栅栏。
栅栏被按顺序编号为1到1000000000。每一段栅栏需要至少刷 p 遍的1号油漆和 q 遍的2号油漆后才能保证长时间不掉色。
每次刷漆都会使用某种类型的油漆，并将编号属于某个区间内的栅栏都刷上这种油漆。
现在给出每次刷漆的栅栏编号范围和油漆种类，请你求出有多少段栅栏能够长时间不掉色。

输入描述
第一行有三个正整数n,p,q(1<=n<=100000,1<=p,q<=n)，代表刷漆的次数，以及两个参数 p 和 q。
第二到四行给出了一个大小为3*n的矩阵，第 i 列的三个数从上到下记为l,r,t(1<=l,r<=1000000000,1<=t<=2)，代表第i次刷漆将编号在 l 到 r 之间的栅栏刷了一遍 t号油漆。

输出描述
输出一个正整数，代表有多少栅栏可以长时间不掉色。

样例输入
5 2 2
1 1 2 3 2
3 5 4 5 4
1 2 1 1 2
样例输出
3

--需要离散化处理一下，直接差分内存炸了

int main()
{
	int n = 0, p = 0, q = 0;
	cin >> n >> p >> q;

	int mini = 1000000002, maxi = 1;
	vector<vector<int>> matrix(3, vector<int>(n, 0));
	for (int i = 0; i < n; i++)
	{
		cin >> matrix[0][i];
		if (matrix[0][i] < mini)
			mini = matrix[0][i];
	}

	for (int i = 0; i < n; i++)
	{
		cin >> matrix[1][i];
		if (matrix[1][i] > maxi)
			maxi = matrix[1][i];
	}
	for (int i = 0; i < n; i++)
	{
		cin >> matrix[2][i];
	}

	vector<int> dp1(maxi - mini + 3, 0);
	vector<int> dp2(maxi - mini + 3, 0);


	for (int i = 0; i < n; i++)
	{
		if (matrix[2][i] == 1)
		{
			dp1[matrix[0][i] - mini + 1]++;
			dp1[matrix[1][i] + 1 - mini + 1]--;
		}
		else
		{
			dp2[matrix[0][i] - mini + 1]++;
			dp2[matrix[1][i] + 1 - mini + 1]--;
		}
	}
	int pre = 0;
	vector<int> res1(maxi - mini + 3, 0);
	vector<int> res2(maxi - mini + 3, 0);
	for (int i = 1; i <= maxi - mini; i++)
	{
		res1[i] = pre + dp1[i];
		pre = res1[i];
		if (res1[i] >=p)
			res1[i] = 1;
		else
			res1[i] = 0;
	}
	pre = 0;
	for (int i = 1; i <= maxi - mini; i++)
	{
		res2[i] = pre + dp2[i];
		pre = res2[i];
		if (res2[i] >=q)
			res2[i] = 1;
		else
			res2[i] = 0;
	}

	int result = 0;
	for (int i = 1; i <= maxi - mini; i++)
	{
		if (res1[i] == 1 && res2[i] == 1)
			result++;
	}
	cout << result;
	return 0;
}

#滴滴笔试#