A. 卡尔的连招
待更
B. 聪明的班主任
题目大意：有$n$ 个人每人有$a_i$ 本书，每次可以使任意$m$ 个人将他的书送给相邻的一个人，问最少几次能使所有人有相同本书。
贪心
具体思路见代码。
代码如下：
#include <iostream>
#include <cstdio>
using namespace std;
int T,n,a[10005];
int main(void){
scanf("%d",&T);
while(T--){
int sum=0,temp=0,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
sum+=a[i];
}
if(sum%n!=0){
printf("-1\n");
continue;
}
sum/=n;
for(int i=1;i<=n;++i){
temp+=sum-a[i];
ans=max(ans,temp>0?temp:-temp);
ans=max(ans,a[i]-sum>0?a[i]-sum:sum-a[i]);
}
printf("%d\n",ans);
}
}C. 一道简单题
待更
D. 又是一道简单题
题目大意：询问以树上两结点$u,v$ 的最近公共祖先为根的子树中，不在这$u,v$ 的简单路径中的最小编号。若无则输出$-1$ 。
LCA+DFS序
首先预处理LCA，复杂度$O(nlgn)$ 。
DFS整棵树，并记录各个结点$x$ 的进入时间$in[x]$ ，出去时间$out[x]$ 以及以$x$ 为根的子树中最小的结点编号$minnode[x]$ 。
当且仅当，$in[x] \leqslant in[y]$ 且$out[y] \leqslant out[x]$ 时，结点$y$ 在以结点$x$ 为根的子树中。
如此一来，对每个询问，只需要遍历以$LCA(u,v)$ 为根的子树，$O(1)$ 的复杂度判定当前结点$x$ 是否位于$u$ 和$v$ 的简单路径中，若不在则直接返回$minnode[x]$ ，单次查询复杂度$O(deep)$ ，其中$deep$ 表示整颗树的深度。
代码如下：
#include <cstdio>
#include <vector>
#include <cmath>
#define N 50010
using namespace std;
int T,minnode[N];
int n,m,u,v,tot,in[N],out[N],ans,father[N];
vector<int>e[N];
struct LCA{
int k,ver[2*N],dep[2*N],dp[2*N][20],f[N];
void init(){
k=0;
}
void prepare(int root){
dfs(root,0,-1);
rmq(k);
}
void dfs(int x,int d,int fa){
f[x]=k;
dep[k]=d;
ver[k++]=x;
for(int i=0;i<(int)e[x].size();++i)if(e[x][i]!=fa){
dfs(e[x][i],d+1,x);
dep[k]=d;
ver[k++]=x;
}
}
void rmq(int k){
for(int i=0;i<k;++i)dp[i][0]=i;
for(int j=1;(1<<j)<=k;++j){
for(int i=0;i+(1<<j)<=k;++i){
int x=dp[i][j-1],y=dp[i+(1<<(j-1))][j-1];
dp[i][j]=dep[x]<dep[y]?x:y;
}
}
}
int lca(int i,int j){
int u=f[i],v=f[j];
if(u>v)swap(u,v);
int len=log(v-u+1.0)/log(2.0);
int x=dp[u][len],y=dp[v+1-(1<<len)][len];
return ver[dep[x]<dep[y]?x:y];
}
}gao;
void pdfs(int u,int fa){
in[u]=++tot;
father[u]=fa;
minnode[u]=u;
for(int i=0;i<(int)e[u].size();++i)if(e[u][i]!=fa){
pdfs(e[u][i],u);
minnode[u]=min(minnode[u],minnode[e[u][i]]);
}
out[u]=tot;
}
void dfs(int x,int u,int v,int fa){
if((in[x]<=in[u]&&out[u]<=out[x])
||(in[x]<=in[v]&&out[v]<=out[x])){
for(int i=0;i<(int)e[x].size();++i)if(e[x][i]!=fa)
dfs(e[x][i],u,v,x);
}else{
ans=min(ans,minnode[x]);
}
}
int main(void){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
gao.init();
for(int i=1;i<n;++i){
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
gao.prepare(1);
tot=0;
pdfs(1,-1);
while(m--){
scanf("%d%d",&u,&v);
int lca=gao.lca(u,v);
ans=N;
dfs(lca,u,v,father[lca]);
if(ans!=N)printf("%d\n",ans);
else printf("-1\n");
}
for(int i=1;i<=n;++i)
e[i].clear();
}
}E. 车轮轴迹
待更
F. Easy Number
题目大意：给出$n$ 个数，定义能被$n$ 个数中任意一个整除的数为Easy Number，问第$k$ 大的Easy Number是什么。
二分+容斥原理
$[0,x]$ 中能被$p$ 整除的数的个数有$\lfloor \frac{x}{p} \rfloor$ 。
由此我们可以利用容斥原理求出$x$ 以内能被任意一个$n$ 个数整除的数的个数，即Easy Number的个数，复杂度为$O(n \times 2^n)$ 。
二分这个界，则可找出第$k$ 大的数。
总复杂度为$O(log_2k \times n \times 2^n)$ 。
代码如下：
#include <cstdio>
using namespace std;
typedef long long ll;
ll T,n,k,a[15];
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
bool check(ll x){
ll ans=0;
for(ll i=0;i<(1<<n);++i){
ll cnt=0,temp=1;
for(ll j=0;j<n;++j)if(i&(1<<j)){
temp=lcm(temp,a[j]);
cnt++;
}
if(cnt)ans+=(cnt&1)?x/temp:-x/temp;
}
return ans>=k;
}
int main(void){
scanf("%lld",&T);
while(T--){
scanf("%lld%lld",&n,&k);
for(int i=0;i<n;++i)scanf("%lld",&a[i]);
ll l=1,r=1000000000;
while(l<r){
ll mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%lld\n",r);
}
}