滴滴 9.17笔试 凉经
第一题：
一个标书证书的字符串，其中有几位是问号，知道这个数字满足
1，可被3整除；2，相邻数字不同；3，首位不为0
问这个数字最小是多少
直接贪心+回溯 ac
bool f(string& str, int index, int pre){
if(index==str.size()){
return pre==0;
}
if(str[index]=='?'){
char before=(index==0)?'0':str[index-1];
char after=(index+1==str.size())?'*':str[index+1];
for(int i=0;i<9;i++){
char c='0'+i;
if(c!=before && c!=after){
str[index]=c;
int left=(pre*10+i)%3;
if(f(str,index+1,left)) return true;
//str[index]='?';
}
}
str[index]='?';
}else{
int left=(pre*10+str[index]-'0')%3;
return f(str, index+1,left);
}
return false;
}
int main(){
string str;
cin>>str;
f(str, 0, 0);
cout<<str<<endl;
return 0;
} 第二题：
n个栅栏，每个栅栏被涂上两种漆，每次在【l，r】区间上（左闭右闭）涂一种漆，当第一种漆涂至少p次，第二种漆涂之撒后q次时这个栅栏才是正常。问给定一系列区间，有多少个栅栏是正常的。
经典的排序+贪婪。但是问题是要考虑端点，因为全是比区间，我就是栽在这上面了。。。。后来刚改完就交卷了，服了
int main(){
int n,p,q;
cin>>n>>p>>q;
vector<vector<int>> points(2*n, vector<int>(3,0));//[index, type, add/delete]
for(int i=0;i<n;i++) {
cin>>points[i][0];
points[i][2]=1;
}
for(int i=n;i<2*n;i++) {
cin>>points[i][0];
points[i][2]=-1;
}
for(int i=0;i<n;i++){
int type;
cin>>type;
points[i][1]=type;
points[i+n][1]=type;
}
//for(auto& v:points) cout<<v[0]<<", "<<v[1]<<", "<<v[2]<<endl;
sort(points.begin(), points.end());
//cout<<"====="<<endl;
//for(auto& v:points) cout<<v[0]<<", "<<v[1]<<", "<<v[2]<<endl;
int type1=0,type2=0;
int pre=points[0][0];
if(points[0][1]==1){
type1=points[0][2];
}else{
type2=points[0][2];
}
int result=0;
for(int i=1;i<points.size();){
cout<<i<<endl;
int index=points[i][0],type=points[i][1];
int type1_add=0,type1_minux=0,type2_add=0,type2_minux=0;
if(type1>=p && type2>=q){
result+=index-pre;
}
cout<<index<<type1<<", "<<type2<<endl;
while(i<points.size() && points[i][0]==index){
if(points[i][1]==1){
if(points[i][2]>0){
type1_add++;
}else{
type1_minux++;
}
}else{
if(points[i][2]>0){
type2_add++;
}else{
type2_minux++;
}
}
i++;
}
type1+=type1_add;
type2+=type2_add;
if(type1>=p && type2>=q) result++;
type1-=type1_minux;
type2-=type2_minux;
pre=index+1;
}
cout<<result;
return 0;
} 感觉出这种类型的题应该滴滴可能也不太想招人。但是我还是没ac。。最近一直是在上机的时候考虑问题不仔细，临要弄完了就才想明白。。。心态崩了
