1008. Park Visit
题目大意：给你n个城市，这n个城市之间共有n-1条道路，每条道路的长度均为1，并且这n个城市是相互可达的。再给你一个数k，让你计算：访问这n个城市中的k个城市最少需要走多少距离？
解题思路：这是一道典型的求树的直径的问题。先求出树的直径 r（我建造的树当中，根节点的深度为1 ），然后推出：如果k <= r , 则最短路程 = k - 1 ；否则，最短距离 = k - 1 + （r - k）* 2 。
请看代码：
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std ;
const int MAXN = 1e5 + 5 ;
struct Node
{
int adj ;
Node * next ;
};
Node* vert[MAXN] ;
int vis[MAXN] ;
int dis[MAXN] ; // 记录数中各个节点的深度
int n , m ;
int maxr ; // 记录树的直径
queue<int> q ;
int bfs(int start)
{
memset(vis , 0 , sizeof(vis)) ;
memset(dis , 0 , sizeof(dis)) ;
int ans = start ;
while (!q.empty())
{
q.pop() ;
}
q.push(start) ;
dis[start] = 1 ;
maxr = -1 ;
int tmp ;
Node * p ;
while (!q.empty())
{
tmp = q.front() ;
q.pop() ;
vis[tmp] = 1 ;
p = vert[tmp] ;
while (p != NULL)
{
int tp2 = p -> adj ;
if(!vis[tp2])
{
vis[tp2] = 1 ;
dis[tp2] = dis[tmp] + 1 ;
if(maxr < dis[tp2])
{
maxr= dis[tp2] ;
ans = tp2 ;
}
q.push(tp2) ;
}
p = p -> next ;
}
}
return ans ; // 返回树的直径的端点序号
}
int zj() // 求树的直径，两次bfs
{
int zj1 = bfs(1) ;
int zj2 = bfs(zj1) ;
return maxr ;
}
int main()
{
int t ;
scanf("%d" , &t) ;
while (t --)
{
scanf("%d%d" , &n , &m) ;
memset(vert , 0 , sizeof(vert)) ;
int i ;
for(i = 0 ; i < n - 1 ; i ++)
{
int a , b ;
scanf("%d%d" , &a , &b) ;
Node * p ;
p = new Node ;
p -> adj = b ;
p -> next = vert[a] ;
vert[a] = p ;
p = new Node ;
p -> adj = a ;
p -> next = vert[b] ;
vert[b] = p ;
}
int r = zj() ;
for(i = 1 ; i <= m ; i ++)
{
int k ;
scanf("%d" , &k) ;
if(k <= r)
{
printf("%d\n" , k - 1) ;
}
else
{
printf("%d\n" , r - 1 + (k - r) * 2) ;
}
}
}
return 0 ;
}
1010. I-number
题目大意:给你一个数X， 让你求出满足如下条件的整数Y的最小值 ：1、Y > X 2 、Y的所有数位上的数字之和是10 的整数倍。
解题思路：这个题不能简单地直接用 long long 做 ， 因为题目中说的是Ｘ的 “位数” 不超过 10 ^ 5 。我是用数组直接模拟加暴力A掉的 。
下面请看代码：
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std ;
const int MAXN = 1e6 + 7 ;
char s[MAXN] ;
char s2[MAXN * 10] ;
void print(char A[] , int len) // 输出数组
{
int i ;
for(i = len - 1 ; i >= 0 ; i --)
{
printf("%c" , A[i]) ;
}
printf("\n") ;
}
void tiao(char A[] , int &len) // 调整数组 是 原来的数组代表的数值 + 1
{
int i ;
for(i = 0 ; ; i ++)
{
if(A[i] < '9')
{
A[i] = A[i] + 1 ;
break ;
}
else if(A[i] == '9')
{
A[i] = '0' ;
if(i == len - 1)
{
len ++ ;
A[i + 1] = '0' ;
}
}
}
}
int main()
{
int t ;
scanf("%d" , &t) ;
while (t --)
{
memset(s , 0 ,sizeof(s)) ;
scanf("%s" , s) ;
int i ;
int len = strlen(s) ;
for(i = len - 1 ; i >= 0 ; i -- )
{
s2[len - i - 1] = s[i] ; // 把原数组s逆向存入数组s2中,
// 这样对后面调整数组比较有利
}
int sum ;
tiao(s2 , len) ; // 先调一下数组，因为 Y > X
while (1)
{
sum = 0 ;
int j ;
for(j = 0 ; j < len ; j ++)
{
sum = sum + s2[j] - '0' ;
}
if(sum % 10 == 0)
{
print(s2 , len) ;
break ;
}
else
tiao(s2 , len) ;
}
}
return 0 ;
}