机试1-2题代码实现.md

1-2题的代码实现：

20届考生个人编写，仅供参考。如果错误希望大佬指出 解题思路与 你好 大佬基本一致

1

#include<stdio.h>

int dfs(int num, int N) {
        int res = (num<10) ? 0 : 1;
        int low_ = num%10;

//      if(num>=10) printf("%d\n", num);

        if(low_ - 1 >= 0) {
                int new_num = num*10 + low_-1;
                if(new_num<=N) res += dfs(new_num, N);
        }
        if(low_ + 1 <= 9) {
                int new_num = num*10 + low_+1;
                if(new_num<=N) res += dfs(new_num, N);
        }

        return res;
}


int main() {
        int n, m;
        scanf("%d%d", &n, &m);
        n--;
        int ans1=0, ans2=0;

        for(int i=1; i<10; i++) {
                ans1+=dfs(i, n);
                ans2+=dfs(i, m);
        }

        printf("%d\n",ans2-ans1);
        return 0;
}

2

#include <cstdio>
#include <vector>
#include <cstring>

using std::vector;

const int N = 20000 + 10;

struct edge{
	int u, v, w;
};

vector<int> s[N];
vector<edge> edges;

int vis[N];
int n, y;

int dfs(int x, int lim) {
	int res = 1;
	for(auto i : s[x]) {
		edge &e = edges[i];
		if(e.w < lim || vis[e.v]) continue;
		vis[e.v] = true;
		res += dfs(e.v, lim);
	}
	return res;	
}

bool check(int x) {
	memset(vis, 0, sizeof(vis));
	vis[0] = true;
	int res = dfs(0, x);
//	printf("ss: %d\n", res);
       	if(res <= y) return true;
	return false;	
}

int main() {
	scanf("%d %d", &n, &y);
	int l = 0, r = 0;
	for(int i=1; i<n; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		s[x].push_back(edges.size());
		edges.push_back((edge){x, y, z});
		s[y].push_back(edges.size());
		edges.push_back((edge){y, x, z});
		if(r<z) r=z;
	}r++;

	while(l<r) {
		int mid = l + (r-l)/2;
		if(!check(mid)) l = mid+1;
		else r = mid;
	}

	printf("%d\n", l);
	return 0;
}