hdu 4602
思路: 数学
分析:
我们可以特判出 n <= k 的情况。
对于 1 <= k < n,我们可以等效为 n 个点排成一列,并取出其中的连续 k 个点。下面分两种
情况考虑:
第一种情况,被选出的不包含端点,那么有(n – k − 1)种情况完成上述操作,剩下未被圈的点
之间还有(n – k − 2)个位置,可以在每个位置断开,所以共 2^(n−k−2) ∗ (n−k−1)种方法。
第二种情况,即被选出的包含端点,那么有 2 种情况,并且剩余共(n – k − 1)个位置,所以共
2 ∗ 2^(n – k − 1)种方法。
总计 2 ∗ 2^(n – k − 1) + 2^(n – k − 2) ∗ (n – k − 1) = (n – k + 3) * 2^(n – k − 2)。
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int mod = 1e9+7;
typedef long long ll;
ll k , n;
ll quicklyPow(ll m , ll x){
ll ans = 1;
while(x){
if(x&1)
ans = (ans*m)%mod;
x >>= 1;
m = (m*m)%mod;
}
return ans%mod;
}
ll getAns(){
if(k == n-1)
return 2;
if(k == n)
return 1;
if(k >= n)
return 0;
// 求ans
ll ans = 0;
ans += (2*quicklyPow(2 , n-k-1))%mod;
ans += (n-k-1)*quicklyPow(2 , n-k-2)%mod;
return ans%mod;
}
int main(){
int Case;
scanf("%d" , &Case);
while(Case--){
scanf("%lld%lld" , &n , &k);
cout<<getAns()<<endl;
}
return 0;
}
hdu 4607
思路: 搜索
分析:
1 题目只要找到最长链，然后去判断k和最长链上面的点的关系即可，找最长链利用两次的bfs
2 首先如果 k 小于等于直径长度,那么答案为k − 1。如果 k 大于直径长度,设直径长度为 r,那么答案为r − 1 + (k − r) ∗ 2。
代码:
#include<vector>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100010;
struct Node{
int num;
int step;
};
int n , m , len;
int start;
bool vis[MAXN];
queue<Node>q;
vector<int>v[MAXN];
void bfs(){
while(!q.empty()){
Node tmp = q.front();
q.pop();
int size = v[tmp.num].size();
for(int i = 0 ; i < size ; i++){
if(!vis[v[tmp.num][i]]){
q.push((Node){v[tmp.num][i] , tmp.step+1});
vis[v[tmp.num][i]] = true;
}
}
if(q.empty()){
start = tmp.num;
len = tmp.step;
}
}
}
void solve(){
// first bfs
memset(vis , false , sizeof(vis));
q.push((Node){1,1});
vis[1] = true;
bfs();
// second bfs
memset(vis , false , sizeof(vis));
q.push((Node){start,1});
vis[start] = true;
bfs();
}
int main(){
int Case;
int x , y , k;
scanf("%d" , &Case);
while(Case--){
scanf("%d%d" , &n , &m);
for(int i = 1 ; i < MAXN ; i++)
v[i].clear();
// n-1
for(int i = 1 ; i < n ; i++){
scanf("%d%d" , &x , &y);
v[x].push_back(y);
v[y].push_back(x);
}
// get ans
solve();
while(m--){
scanf("%d" , &k);
if(k <= len)
printf("%d\n" , k-1);
else
printf("%d\n" , len-1+(k-len)*2);
}
}
return 0;
}
hdu 4608
思路: 高精度模拟
分析:
1 很明显y < x+20
2 证明: 假设x的各个位数之和为sum，那么明显sum%10的结果为0～9，所以我们最多通过两次的增加使得x->y，那么两次的增加的总和最多为18，所以我们通过暴力枚举即可得出ans
3 注意题目的数据是有前导0的
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100010;
int num[MAXN];
char str[MAXN];
int len , pos;
int getSum(){
int sum = 0;
for(int i = 0 ; i <= pos ; i++)
sum += num[i];
return sum;
}
void output(){
if(num[pos])
printf("%d" , num[pos]);
for(int i = pos-1 ; i >= 0 ; i--)
printf("%d" , num[i]);
printf("\n");
}
void solve(){
len = strlen(str);
pos = 0;
memset(num , 0 , sizeof(num));
for(int i = len-1 ; i >= 0 ; i--)
num[pos++] = str[i]-'0';
// 最多加20
for(int i = 1 ; i <= 20 ; i++){
num[0]++;
for(int j = 0 ; j < pos ; j++){
num[j+1] += num[j]/10;
num[j] %= 10;
}
if(getSum()%10 == 0){
output();
return;
}
}
}
int main(){
int Case;
scanf("%d%*c" , &Case);
while(Case--){
gets(str);
solve();
}
return 0;
}
