A
题意：O(-1)
思路：排个序搞定。
B
题意：O（-1）
思路：坑了我好久，这个框框水平垂直比例固定，分两种情况即可，不能旋转，我想多了，分了四种情况。
C
题意：一列n个位置，让你填m个数，当连续数达到k时，分数乘以2，计数清零，当不连续时，计数也清零，没到达k之前分数+1.
思路：很显然的问题是让我们处理填m个位置，并且使连续的k个数次数最少。我们先让m个数k-1每次填，填一次空一位，直到不够填了就往前面的空位填。设连续k个次数为mm，那么就是（（（2*k）+k）*2……+k）*2，等比数列求和之后为k*（2^mm-2），不连续k的值为m-mm*k。注意要注意了细节很多，WA了两次。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std; typedef long long lld;
const lld mod=; lld Pow(lld a, int b)
{
lld ans=;
while(b)
{
if(b&) ans=(ans*a)%mod;
b>>=;
a=(a*a)%mod;
}
return ans%mod;
} int main()
{
lld n, m, k;
while(cin >> n >> m >> k)
{
lld c1, c2, s1, num, mm, ans=;
c1=n/k, s1=n%k;
c2=m/(k-);
num=min(c1,c2);
if(c1>c2) s1+=k*(c1-c2);
mm=m-num*(k-);
mm-=min(mm,s1);
if(mm) ans=(k*((Pow(,mm+)-+mod)%mod))%mod;
ans=(ans+m-k*mm%mod+mod)%mod;
cout << ans <<endl;
}
}
/*
23888888 508125 3
*/
D
题意：有一颗n个节点的树，树中有m个恶魔，然后给你一个控制距离d，问你树中哪些节点能控制住所有恶魔（离最远恶魔距离小于等于d）。
思路：很显然的树形dp，开始没考虑清楚一点，把所有节点的最长半径以及次长半径都初始化为0，这样会存在一个小bug，因为当有一个恶魔节点存在树中（此时此节点最长半径为0），父亲节点的最长半径为此节点更新上去的，传递下来的时候此节点只能利用父亲节点的次长半径，当次长半径初始化为0时，此时更新此节点的话次长半径就要大于最长半径，所以节点最长半径和次长半径初始化为-oo，有恶魔的节点最长半径改为0即可，开始没考虑到这点。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std; const int maxn=;
const int oo=0x3fffffff;
int fmax[maxn], smax[maxn], color[maxn], f[maxn];
vector<int>vt[maxn];
int n, m, d; void init()
{
for(int i=; i<=n; i++)
{
vt[i].clear();
fmax[i]=smax[i]=-oo;
color[i]=f[i]=;
}
} void dfs(int u, int fa)
{
for(int i=; i<vt[u].size(); i++)
{
int v=vt[u][i];
if(v==fa) continue;
dfs(v,u);
if(color[v])
{
color[u]++;
if(fmax[v]+>fmax[u]) smax[u]=fmax[u], fmax[u]=fmax[v]+;
else if(fmax[v]+>smax[u]) smax[u]=fmax[v]+;
}
}
} void DFS(int u, int fa)
{
if(u==) ;
else
{
if(fmax[fa]-==fmax[u])
{
if(smax[fa]+>fmax[u]) smax[u]=fmax[u], fmax[u]=smax[fa]+;
else if(smax[fa]+>smax[u]) smax[u]=smax[fa]+;
}
else
{
if(fmax[fa]+>fmax[u]) smax[u]=fmax[u], fmax[u]=fmax[fa]+;
else if(fmax[fa]+>smax[u]) smax[u]=fmax[fa]+;
}
}
for(int i=; i<vt[u].size(); i++)
if(vt[u][i]!=fa)DFS(vt[u][i],u);
} int bfs(int st)
{
int ans=;
queue<int>q;
q.push(st);
while(!q.empty())
{
int u=q.front();
q.pop();
if(fmax[u]<=d) ans++;
for(int i=; i<vt[u].size(); i++)
{
int v=vt[u][i];
if(v==f[u]) continue;
f[v]=u;
q.push(v);
}
}
return ans;
} int main()
{
while(cin >> n >> m >> d)
{
init();
int u, v;
for(int i=; i<=m; i++)
{
scanf("%d",&u);
color[u]=;
fmax[u]=;
}
for(int i=; i<n; i++)
{
scanf("%d%d",&u,&v);
vt[u].push_back(v);
vt[v].push_back(u);
}
dfs(,);
DFS(,);
int ans=bfs();
cout << ans <<endl;
}
return ;
}
/*
10 1 0
3
10 1
9 4
4 5
6 4
2 4
7 5
8 3
5 3
1 3 1
*/