4.29 华为笔试
第一题：长度不大于8的字符串，求排列组合个数。next_permutation枚举，set去重。输入为空太坑人...
#include <bits/stdc++.h>
using namespace std;
int main()
{
char s[10];
if(!cin.getline(s,10)){
printf("0\n");
return 0;
}
int l = strlen(s);
if(l <= 0){
printf("0\n");
return 0;
}
sort(s, s+l);
set<string> st;
do{
string t = "";
for(int i = 0 ; i < l ; i++){
t += s[i];
}
st.insert(t);
}while(next_permutation(s, s+l));
int ans = st.size();
printf("%d\n",ans);
return 0;
} 第二题：字符串删n个字符，求字典序最小。删掉前面比后面大的字符。如果没有，删掉最后的。用链表好删一点。
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100500
struct node{
char c;
node *next;
node(char cc):c(cc),next(NULL){}
};
char s[MAXN];
int n;
int main()
{
scanf("%s", s);
scanf("%d",&n);
int l = strlen(s);
node *head = new node(' ');
node *p = head;
for(int i = 0 ; i < l ; i++){
node * q = new node(s[i]);
p->next = q;
p = p->next;
}
for(int k = 0 ; k < n ; k++){
p = head;
while(p->next && p->next->next && (p->next->c <= p->next->next->c)){
p = p->next;
}
node *q = p->next->next;
p->next = q;
}
p = head->next;
while(p){
printf("%c", p->c);
p = p->next;
}
printf("\n");
return 0;
} 第三题：带限制条件的最短路。bfs搜索。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define MAXN 1005
struct node{
int x,l,t;
node(){}
node(int xx,int ll,int tt):x(xx),l(ll),t(tt){}
bool operator < (const node a) const{
if(l == a.l) return t < a.t;
return l > a.l;
}
};
vector<node> a[MAXN];
int k,n,m;
int ans;
int main()
{
int s,d,l,t;
scanf("%d",&k);
scanf("%d",&n);
scanf("%d",&m);
for(int i = 0 ; i < m ; i++){
scanf("%d %d %d %d", &s, &d, &l, &t);
s--;
d--;
a[s].push_back(node(d,l,t));
}
priority_queue<node> que;
que.push(node(0,0,0));
ans = -1;
while(!que.empty()){
node now = que.top();
que.pop();
if(now.x == n-1){
ans = now.l;
break;
}
for(int i = 0 ; i < a[now.x].size() ; i++){
if(now.t + a[now.x][i].t > k)
continue;
que.push(node(a[now.x][i].x, now.l + a[now.x][i].l, now.t+a[now.x][i].t));
}
}
printf("%d\n",ans);
return 0;
} 