滴滴9.17笔试
第一题，寻找第一个满足解即可
#include<bits/stdc++.h>
using namespace std;
// 3整除，全部加起来能够整除3
string res;
bool flag = false;
bool check(string str) {
int cnt = 0;
for (char c : str) {
cnt += (c - '0');
}
if (cnt % 3 == 0) {
return true;
}
return false;
}
void dfs(string &s, int k) {
// cout<<s<<endl;
if (flag) {
return;
}
if (k >= s.length()) {
// cout<<s<<endl;
if (check(s)) {
res = s;
flag = true;
}
return;
}
// for (int j = k; j < s.length(); ++j) {
//
// }
int j = k;
if (s[j] != '?') {
dfs(s, k + 1);
} else {
if (j == 0) {
if (s.length() == 1) {
for (int i = 1; i <= 9; ++i) {
s[j] = '0' + i;
dfs(s, k + 1);
s[j] = '?';
}
} else {
for (int i = 1; i <= 9; ++i) {
if (s[j + 1] == '0' + i) {
continue;
}
s[j] = '0' + i;
dfs(s, k + 1);
s[j] = '?';
}
}
} else {
for (int i = 0; i <= 9; ++i) {
if (s[j - 1] == '0' + i) {
continue;
}
if (j != s.length() - 1 && s[j + 1] == '0' + i) {
continue;
}
s[j] = '0' + i;
dfs(s, k + 1);
s[j] = '?';
}
}
}
}
int main () {
string str;
cin>>str;
dfs(str, 0);
cout<<res<<endl;
return 0;
} 第二题，用了两个差分数组，只过了91，有大佬帮忙看看么
// 维护两个差分数组即可！！
#include<bits/stdc++.h>
using namespace std;
long long MAX_NUM = 0;
int main () {
long long n, p, q;
cin>>n>>p>>q;
// cout<<n<<" "<<p<<" "<<q<<endl;
vector<long long> l(n, 0);
vector<long long> r(n, 0);
vector<long long> t(n, 0);
// int l, r, t;
for (long long i = 0; i < n; ++i) {
cin>>l[i];
MAX_NUM = max(MAX_NUM, r[i]);
}
for (long long i = 0; i < n; ++i) {
cin>>r[i];
MAX_NUM = max(MAX_NUM, r[i]);
}
for (long long i = 0; i < n; ++i) {
cin>>t[i];
}
MAX_NUM += 5;
// cout<<"over"<<endl;
vector<long long>cf1(MAX_NUM, 0);
vector<long long>cf2(MAX_NUM, 0);
for (long long i = 0; i < n; ++i) {
if (t[i] == 1) {
cf1[l[i]]++;
cf1[r[i] + 1]--;
} else {
cf2[l[i]]++;
cf2[r[i] + 1]--;
}
}
long long sum1 = 0;
long long sum2 = 0;
long long res = 0;
for (long long i = 1; i < MAX_NUM; ++i) {
sum1 += cf1[i];
sum2 += cf2[i];
if (sum1 >= p && sum2 >= q) {
res++;
}
}
cout<<res<<endl;
return 0;
} 
