大意：给定一棵无根树，进行 k 次操作，每次操作可以删除所有的叶子节点，问最终剩多少个节点。
思路：首先叶子节点的度数是为 1 的，每次删除叶子节点，下次删除的是和叶子节点相连的点，我们直接维护度数，每次把度数为 1 的点入队进行bfs 就行了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=4e5+10;
typedef pair<int,int> PII;
int gcd(int a,int b)
{
return b ? gcd(b,a%b) : a;
}
int de[N],n,k;
vector<int> G[N];
int d[N];
bool st[N];
int bfs()
{
queue<int> q;
for(int i=1;i<=n;i++)
{
if(de[i]<=1)
{
q.push(i);
st[i]=1;
d[i]=1;
}
}
int ans=0;
while(q.size())
{
int u=q.front();
q.pop();
if(d[u]<=k)ans++;
for(auto v:G[u])
{
if(st[v])continue;
de[v]--;
if(de[v]<=1)
{
d[v]=d[u]+1;
q.push(v);
st[v]=1;
}
}
}
return n-ans;
}
void solve()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
de[i]=0,st[i]=0,d[i]=1e9;
G[i].clear();
}
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
de[x]++,de[y]++;
}
if(n==1)
{
cout<<0<<"\n";
return ;
}
int t=bfs();
cout<<t<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int _=1;
cin>>_;
while(_--)solve();
return 0;
}
总结:对于图论问题，大部分情况下搜索都是 O(n)的，不要怕超时。
Half of Same 思维、数学
大意:给定一个长度不超多40的序列a，每次选择一个数，减 k.
简单版：求经过若干次操作，使得序列 a 全部相等的最大 k ,若 k 无穷大输出-1
困难版：求经过若干次操作，使得序列 a 至少有一半全部相等最大的 k ,若 k 无穷大输出 -1
思路：首先看简单版的,对于每次减 k 实际上就是减去 k 的若干倍，所以就可以转化成在%k 相等。对于输出-1的情况，显然就是序列本身全部相等。对于两个数 x,y 同余k。那么可以转化成 (x-y)%k=0。所以我们将序列两两做差求最大公约数就行了，（其实不用两两作差，只需要可以确保能限制所有的数就行了）。
代码：略
对于困难版：与上面类似，对于有 >=n/2 个数相等输出-1.然后就是我们可以两两做差，我们知道 k 必定是他们的几个数中的约数，我们可以把所有的约数处理出来，枚举约数然后去判定就行了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=4e5+10;
typedef pair<int,int> PII;
int gcd(int a,int b)
{
return b ? gcd(b,a%b) : a;
}
int a[50],n;
bool check()
{
map<int,int> cnt;
for(int i=1;i<=n;i++)
{
cnt[a[i]]++;
if(cnt[a[i]]>=n/2)return 1;
}
return 0;
}
bool judge(int x)
{
map<int,int> cnt;
for(int i=1;i<=n;i++)
{
int y=(a[i]%x+x)%x;
cnt[y]++;
if(cnt[y]>=n/2)return 1;
}
return 0;
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
if(check())
{
cout<<-1<<"\n";
return ;
}
vector<int> val;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
val.push_back(abs(a[i]-a[j]));
sort(val.begin(),val.end());
val.erase(unique(val.begin(),val.end()),val.end());
vector<int> p;
for(auto x:val)
{
for(int i=1;i*i<=x;i++)
{
if(x%i==0)
{
p.push_back(i);
p.push_back(x/i);
}
}
}
sort(p.begin(),p.end());
p.erase(unique(p.begin(),p.end()),p.end());
//for(auto x:p)cout<<x<<" "<<" ";
int mx=0;
for(auto x:p)
{
if(judge(x))
{
mx=max(mx,x);
}
}
cout<<mx<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int _=1;
cin>>_;
while(_--)solve();
return 0;
}
总结：对于若干倍的操作，一个重要的思考方向就是先取模。