B站算法第二次笔试
第一题，排序
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>
#include <string>
#include <set>
#include <queue>
#include <climits>
#include <unordered_set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <map>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
using namespace std;
const int inf = 0x7f7f7f7f;
#define _for(i,l,r) for(int i=(l);i<(r);i++)
int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
vector<string>data;
bool cmp(string a,string b){
int a_len = (int)a.length(),b_len = (int)b.length();
int i = 0,j =0;
while(i < a_len && j < b_len){
if(a[i] > b[j]) return true;
else if(a[i] < b[j]){
return false;
}
i++,j++;
if(i == a_len && j != b_len) i =0;
if(i != a_len && j == b_len) j =0;
}
return true;
}
int main() {
int n,m;
string s;
cin >> s;
int s_len = (int)s.length();
int i = 0;
while(i < s_len){
int pre = i;
while(i < s_len && s[i] != ',')i++;
data.push_back(s.substr(pre,i - pre));
if(i == s_len) break;
i++;
}
sort(data.begin(),data.end(),cmp);
string ans = "";
for(int j=0;j<(int)data.size();j++){
ans += data[j];
}
int j = 0,a_len = (int)ans.length();
while(j < a_len && ans[j]=='0') j++;
if(j == a_len){
cout << "0"<< endl;
}else{
cout << ans.substr(j)<< endl;
}
return 0;
} 第二题，建树,小dp一下，排序 #include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>
#include <string>
#include <set>
#include <queue>
#include <climits>
#include <unordered_set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <map>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
using namespace std;
const int inf = 0x7f7f7f7f;
#define _for(i,l,r) for(int i=(l);i<(r);i++)
int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
vector<int> graph[100005];
int cnt[100005];
int vis[100005];
int in[100005];
vector<pair<int,int>> ans;
void dfs(int u){
vis[u] = 1;
for(int i=0;i<graph[u].size();i++){
int v = graph[u][i];
if(!vis[v]){
dfs(v);
cnt[u] += cnt[v];
}
}
cnt[u] += 1;
}
bool cmp(pair<int,int> a,pair<int,int> b){
if(a.first !=b.first){
return a.first > b.first;
}
else{
return a.second > b.second;
}
}
int main() {
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
in[y] ++;
graph[x].push_back(y);
}
for(int i=0;i<100005;i++){
if(!vis[i] && in[i] == 0 && graph[i].size() > 0){
dfs(i);
}
}
for(int i=0;i<100005;i++){
if(cnt[i] >0){
ans.push_back(make_pair(cnt[i],i));
}
}
sort(ans.begin(),ans.end(),cmp);
cout << ans[0].second << endl;
return 0;
} 第三题，暴力 #include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>
#include <string>
#include <set>
#include <queue>
#include <climits>
#include <unordered_set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <map>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
using namespace std;
const int inf = 0x7f7f7f7f;
#define _for(i,l,r) for(int i=(l);i<(r);i++)
int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
vector<int> data;
int pre_sum[10000];
int main() {
int n,m;
int sum =0;
scanf("%d%d",&n,&m);
_for(i,0,n){
int x;
scanf("%d",&x);
data.push_back(x);
sum += x;
}
if(m > sum){
cout << -1 << endl;
}
else{
int ans = INT_MAX;
for(int i=1;i<=n;i++){
pre_sum[i] = pre_sum[i - 1] + data[i - 1];
}
for(int i=1;i<=n;i++){
for(int j =1;j<=i;j++){
if(pre_sum[i] - pre_sum[j - 1] >= m){
ans = min(ans, i - j + 1);
}
}
}
cout << ans << endl;
}
return 0;
}