滴滴笔试（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时满足小昱记忆中数据的特征，且是可能出现的最小值。
#滴滴笔试#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
栅栏被按顺序编号为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;
} 
