10.7总结
前言
今，天，的，内容，怎么，那么，难？！
P1852 跳跳棋
嗯，怼。紫题？！
题目意思：在一个数轴内有三个数，使其中一颗棋子以相邻的一颗棋子为对称轴翻到那颗棋子的另一边使距离相等
我们首先画出这样一个数轴
于是我们可以分出两种情况：从两边向中间跳，从中间向两边跳
对于从两边向中间跳的可以参考图二，我们可以发现，这个跳的过程有点像gcd？！！于是根据那个跳转的点确认三个点的位置
对于从中间向两边跳的，我们可以根据图一看出他可以向左边的点跳，可以向右边的点跳，于是我们可以根据此来构造一棵树
这样就可以求出这个区间的所有情况
根据上述原理，我们可以初步的写一个跳转函数，求出这几个数最后会跳转到的地方，如果不能跳到一个地方说明这两个区间不会重合输出NO
否则让他们先跑到同一层，再用二分答案二分需要跳转的步数再使他们跳同样的步数来求解答案
#include<bits/stdc++.h>
using namespace std;
int a,b,c,x,y,z;
int dep1,dep2,ans=0;
void init() {
if(a>b) {
swap(a,b);
}
if(a>c) {
swap(a,c);
}
if(b>c) {
swap(b,c);
}
if(x>y) {
swap(x,y);
}
if(x>z) {
swap(x,z);
}
if(y>z) {
swap(y,z);
}
return;
}
int get_space(int a,int b,int c,int &dep,int &l) {
int d1=b-a;
int d2=c-b;//两个数之间的基础距离
while(d1!=d2) {// a b c可以变成b a c然后再变成a b c，a可以一直向c接近
if(d2>d1) {
int s=d2/d1;
int dis=d2%d1;
if(!dis) {//找到了gcd，可以直接返回了
dep+=s-1;//跳的次数 ，在这里面调的次数等同于深度
l=d1;
return a+(s-1)*d1;//找到了跳一次的距离就可以推出来能跳到的地方
}
dep+=s;
a+=s*d1;
b+=s*d1;
d2=dis;//剩余的距离
} else {
int s=d1/d2;
int dis=d1%d2;
if(!dis) {
dep+=s-1;
l=d2;
return a;//向左边翻转最后就是此处的答案
}
dep+=s;
b-=s*d2;
c-=s*d2;
d1=dis;
}
}
dep=0;//说明不需要翻转
l=d1;
return a;
}
void skip_up(int &a,int &b,int &c,int step) {//得到答案后开始优化步数
while(step) {
int d1=b-a,d2=c-b;
if(d2>d1) {
int s=d2/d1;//可以跳的次数
int dis=d2%d1;//调完之后剩余的步数
if(s>=step) {
a+=step*d1;
b+=step*d1;
return;
}
a+=s*d1;
b+=s*d1;
step-=s;
} else {
int s=d1/d2;
int dis=d1%d2;
if(s>=step) {
b-=step*d2;
c-=step*d2;
return;
}
b-=s*d2;
c-=s*d2;
step-=s;
}
}
return;
}
void solve() {
int l=0-1,r=min(dep2,dep1)+1;
while(l+1<r) {
int mid=(l+r)/2;
int aa=a,bb=b,cc=c;
int xx=x,yy=y,zz=z;
skip_up(aa,bb,cc,mid);
skip_up(xx,yy,zz,mid);
if(aa==xx&&bb==yy&&cc==zz) {
r=mid;
} else {
l=mid;
}
}
cout<<ans+r*2<<endl;
return;
}
signed main() {
cin>>a>>b>>c>>x>>y>>z;
init();
int space1,space2;
int pos1=get_space(a,b,c,dep1,space1);//dep1得到深度，space1得到
int pos2=get_space(x,y,z,dep2,space2);
if(space1!=space2||pos1!=pos2) {//如果(n,m,k)不同说明不会跳到那里
cout<<"NO"<<'\n';
return 0;
}
cout<<"YES"<<'\n';
if(dep1>dep2) {//调整到同一深度
ans+=dep1-dep2;
skip_up(a,b,c,dep1-dep2);//向上跳
} else if(dep2>dep1) {
ans+=dep2-dep1;
skip_up(x,y,z,dep2-dep1);
}
solve();
return 0;
}T2
依旧陈老师秘制拼好题
对于n<=1000的数据由于所有的询问的起点相同，直接开始暴力bfs开搜把所有答案搜出来
剩下的数据保证边比点多200个，利用这个性质，我们可以首先考虑所有点上的边构成树的情况，所以我们可以树上lca求出任意两点的距离，然后多出来的边一定会组成环，所以我们考虑从多出来的边上的点作为起点跑bfs
然后在每次询问的时候枚举i到u到v的距离，判断三角形法则哪个更近就行
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+7;
vector<int>g[maxn];
int dp[maxn][25];
int f[maxn],dep[maxn],dis[240][maxn];
int num;
int n,m;
vector<pair<int,int> >vec;
int Dis[1005][1005];
void BFS(int s) {
queue<int>q;
Dis[s][s]=0;
q.push(s);
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=0;i<g[u].size();i++) {
int v=g[u][i];
if(Dis[s][u]+1<Dis[s][v]) {
Dis[s][v]=Dis[s][u]+1;
q.push(v);
}
}
}
return ;
}
void solve() {
for(int i=1;i<=m;i++) {
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
memset(Dis,0x3f,sizeof(Dis));
for(int i=1;i<=n;i++) {
BFS(i);
}
int q;
cin>>q;
while(q--) {
int a,b;
cin>>a>>b;
cout<<Dis[a][b]<<'\n';
}
return ;
}
void addline(int u,int v) {
g[u].push_back(v);
g[v].push_back(u);
}
int find(int x) {
if(f[x]==x) {
return x;
}
return f[x]=find(f[x]);
}
void dfs(int u,int fa) {
dep[u]=dep[fa]+1;
dp[u][0]=fa;
for(int i=1;(1<<i)<=dep[u];i++) {
dp[u][i]=dp[dp[u][i-1]][i-1];
}
for(int i=0;i<g[u].size();i++) {
int v=g[u][i];
if(v!=fa) {
dfs(v,u);
}
}
return ;
}
int lca(int x,int y) {
if(dep[x]<dep[y]) {
swap(x,y);
}
for(int i=21;i>=0;i--) {
if(dep[dp[x][i]]>=dep[y]) {
x=dp[x][i];
}
}
if(x==y) {
return x;
}
for(int i=20;i>=0;i--) {
if(dp[x][i]!=dp[y][i]) {
x=dp[x][i],y=dp[y][i];
}
}
return dp[x][0];
}
void bfs(int u) {
num++;
dis[num][u]=0;
queue<int>q;
q.push(u);
while(!q.empty()) {
int x=q.front();
q.pop();
for(int i=0;i<g[x].size();i++) {
int v=g[x][i];
if(dis[num][v]>dis[num][x]+1) {
dis[num][v]=dis[num][x]+1;
q.push(v);
}
}
}
return;
}
int main() {
cin>>n>>m;
if (n <= 1000){
solve();
return 0;
}
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=n;i++) {
f[i]=i;
}
for(int i=1;i<=m;i++) {
int u,v;
cin>>u>>v;
int x=find(u),y=find(v);
if(x==y) {
vec.push_back({u,v});
} else {
f[x]=y;
addline(u,v);
}
}
dfs(1,0);
for(int i=0;i<vec.size();i++) {
addline(vec[i].first,vec[i].second);
}
for(int i=0;i<vec.size();i++) {
bfs(vec[i].first);
}
int q;
cin>>q;
while(q--) {
int u,v;
cin>>u>>v;
int ans=dep[u]+dep[v]-2*dep[lca(u,v)];
for(int i=1;i<=num;i++) {
ans=min(ans,dis[i][u]+dis[i][v]);
}
cout<<ans<<'\n';
}
return 0;
}T3
首先longlong范围只有1e19开多了肯定会炸
然后我们思考后缀0的性质，只有一个2和一个5相乘的时候才会有后缀0，所以目的是要找因子2和5的个数
然后考虑对于某个节点x如何求解，将所有答案分为两个区域,一个是x的子树，一个是x的子树之外的部分，区域1所能产生的贡献值是x×cnt2[i],xcnt5[i];
考虑直接计算一个答案的时间太长，换根的方式可以加速离线操作
换根的步骤主要就是先找到根节点的答案然后找到子树根x和son（x）的关系，然后继续以x为根继续划分区域
开始将f(x)转为f(son(x))
对于区域1而言,lca(x,x)依旧是lca(son(x),x)没有影响
对于区域2直接把lca(i,x)转成lca(i,son(x))，此时区域2只有son（x）的子树受到了影响，其他点的祖先仍然是x，贡献值为$siz[son(x)](cnt[x]-cnt[son(x)])$
对于区域3而言,说明x的祖先不是自身,那么son(x)也是它的儿子，他们有一个共同的祖先，所以最终的答案不变
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
struct Edge{
int u,to;
int w;
int nxt;
}edge[maxn*2];
int head[maxn];
int cnt=0;
void addline(int u,int v,int w) {
edge[++cnt].u=u;
edge[cnt].to=v;
edge[cnt].nxt=head[u];
head[u]=cnt;
return ;
}
int ans[maxn];
int cnt2[maxn];
int cnt5[maxn];
int siz[maxn];
int n;
void init() {
for(int i=1;i<=n;i++) {
int x=i;
while(x%2==0) {
cnt2[i]++;
x/=2;
}
x=i;
while(x%5==0) {
cnt5[i]++;
x/=5;
}
}
return ;
}
void dfs1(int u,int fa){
siz[u]=1;
for(int i=head[u];i;i=edge[i].nxt) {
int v=edge[i].to;
if(v!=fa) {
dfs1(v,u);
siz[u]+=siz[v];
}
}
return ;
}
void dfs2(int u,int fa,int t,int f) {
ans[u]=min(t,f);
for(int i=head[u];i;i=edge[i].nxt) {
int v=edge[i].to;
if(v!=fa) {
dfs2(v,u,t-siz[v]*(cnt2[u]-cnt2[v]),f-siz[v]*(cnt5[u]-cnt5[v]));
}
}
return ;
}
int main() {
cin>>n;
init();
int q;
cin>>q;
for(int i=1;i<n;i++) {
int u,v;
cin>>u>>v;
addline(u,v,0);
addline(v,u,0);
}
dfs1(1,1);
dfs2(1,1,0,0);
for(int i=1;i<=q;i++) {
int x;
cin>>x;
cout<<ans[x]<<'\n';
}
return 0;
}