T1:
给出一个n个点的图，编号依次为1~n。编号为i和j的两点之间边权为c*（i^j）（c为给定常数）
另外还有m条边，边权给定。给出A，B，求出A到B的最短路
题目链接
solution:
考虑异或这种操作。其实不用建出n*n条边，只需要如此建边：
比如5（101）号节点，只用向4（100），7（111），1（001）连边即可
即向每一个二进制位取异或连边
而比如5（101）到6（110）的边，可通过5（101）到4（100）到6（110）如此到达
注意下0号节点也需要连边
code:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef pair<int,int> pii;
int n,m,c,h,st,ed;
struct edge{int to,w;};
vector<edge>v[N];
inline int dijkstra()
{
int d[N];fill(d,d+n+1,1e9);
d[st]=0;
priority_queue<pii,vector<pii>,greater<pii> >pq;
pq.push(make_pair(0,st));
while(!pq.empty())
{
int u=pq.top().second;pq.pop();
for(int i=0;i<v[u].size();++i)
{
int j=v[u][i].to,w=v[u][i].w;
if(d[j]>d[u]+w)
{
d[j]=d[u]+w;
pq.push(make_pair(d[j],j));
}
}
}
return d[ed];
}
int main()
{
scanf("%d%d%d",&n,&m,&c);
for(h=0;(1<<h)<=n;++h);
for(int i=1;i<=m;++i)
{
int f,t,vv;scanf("%d%d%d",&f,&t,&vv);
v[f].push_back({t,vv});
}
for(int i=0;i<=n;++i)
for(int j=0;j<=h;++j)
{
int k=i^(1<<j);
if(k>n)continue;
v[i].push_back({k,(1<<j)*c});
}
scanf("%d%d",&st,&ed);
cout<<dijkstra();
return 0;
}
T2:
在字节山脉有n座山峰，每座山峰有它的高度。有些山峰之间有双向道路相连，共m条路径，每条路径有一个困难值，这个值越大表示越难走，现在有q组询问，每组询问询问从点开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。
(n<=10^5,m,q<=5*10^5)
山峰高度(hi<=10^9)
题目链接
solution:
首先对整个图用kruskal求出kruskal重构树
而后对于每一个询问，通过在重构树上倍增求出它所对应的区间
问题转化为静态区间第k大，上主席树即可
需要注意：kruskal重构树节点的val要初始化
另外主席树注意空间开够及一些小细节
部分实现可以封装简化
code:
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5,maxm=6e5+5;
int N,M,Q,T,cnt,H[maxn],B[maxn];
int Fa[maxn];
int Nd,ch[maxn<<1][2],val[maxn<<1],nH[maxn],st[maxn<<1],ed[maxn<<1];
int pr[maxn<<1][20];
int rt[maxn],o,l[maxn*40],r[maxn*40],s[maxn*40];
vector<int>new_H;
struct Smer{int num,id;}_H[maxn];
struct edge{int fr,to,w;}e[maxm];
inline int read()
{
int s=0,w=1; char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
for(;isdigit(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
return s*w;
}
inline bool cmp1(Smer x,Smer y){return x.num<y.num;}
inline bool cmp2(Smer x,Smer y){return x.id<y.id;}
inline bool cmp(edge x,edge y){return x.w<y.w;}
int fd(int x){return Fa[x]==x?x:Fa[x]=fd(Fa[x]);}
inline void smer()
{
Smer cpyH[maxn];cnt=0;
for(int i=1;i<=N;++i)
cpyH[i].num=H[i],cpyH[i].id=i;
sort(cpyH+1,cpyH+N+1,cmp1);
for(int i=1;i<=N;++i)
{
if(i==1||cpyH[i].num!=cpyH[i-1].num)_H[i].num=++cnt;
else _H[i].num=cnt;
_H[i].id=cpyH[i].id;
}
sort(_H+1,_H+N+1,cmp2);
for(int i=1;i<=N;++i)B[_H[i].num]=H[i];
}
inline void kruskal()
{
memset(val,127,sizeof(val));
fill(val+1,val+N+1,0);
for(int i=1;i<=N*2;++i)Fa[i]=i;
sort(e+1,e+M+1,cmp);
Nd=N;
int ct=0;
for(int i=1;i<=M;++i)
{
int aa=e[i].fr,bb=e[i].to;
int faa=fd(aa),fbb=fd(bb);
if(faa==fbb)continue;
++ct;
val[++Nd]=e[i].w;
ch[Nd][0]=faa;ch[Nd][1]=fbb;
Fa[faa]=Fa[fbb]=Nd;
if(ct==N-1)break;
}
}
void dfs(int pos,int depth,int Pr)
{
pr[pos][0]=Pr;
for(int i=1;(1<<i)<=depth;++i)
pr[pos][i]=pr[pr[pos][i-1]][i-1];
if(!val[pos])
{
st[pos]=ed[pos]=new_H.size();
new_H.push_back(pos);
return;
}
dfs(ch[pos][0],depth+1,pos);dfs(ch[pos][1],depth+1,pos);
st[pos]=st[ch[pos][0]];ed[pos]=ed[ch[pos][1]];
}
inline void get_interval(int pos,int _val,int &ll,int &rr)
{
for(int i=19;i>=0;--i)
if(val[pr[pos][i]]<=_val)
pos=pr[pos][i];
ll=st[pos];rr=ed[pos];
}
void update(int &_rt,int pre_rt,int p,int ll,int rr)
{
_rt=++o;
if(ll==rr){s[_rt]=s[pre_rt]+1;return;}
int mid=ll+rr>>1;
l[_rt]=l[pre_rt];r[_rt]=r[pre_rt];
if(p<=mid)update(l[_rt],l[pre_rt],p,ll,mid);
else update(r[_rt],r[pre_rt],p,mid+1,rr);
s[_rt]=s[l[_rt]]+s[r[_rt]];
}
int query(int rt1,int rt2,int ll,int rr,int kk)
{
if(s[rt2]-s[rt1]<kk)return -1;
if(ll==rr)return ll;
int rcnt=s[r[rt2]]-s[r[rt1]],mid=ll+rr>>1;
if(kk>rcnt)return query(l[rt1],l[rt2],ll,mid,kk-rcnt);
else return query(r[rt1],r[rt2],mid+1,rr,kk);
}
int main()
{
N=read();M=read();Q=read();T=read();
for(int i=1;i<=N;++i)H[i]=read();
smer();
for(int i=1;i<=M;++i)
{
int aa=read(),bb=read(),cc=read();
e[i].fr=aa;e[i].to=bb;e[i].w=cc;
}
kruskal();
new_H.push_back(0);
for(int i=1;i<=N*2-1;++i)
if(fd(i)==i)dfs(i,1,0);
for(int i=1;i<new_H.size();++i)nH[i]=_H[new_H[i]].num;
for(int i=1;i<=N;++i)
update(rt[i],rt[i-1],nH[i],1,N);
int lastans=0;
while(Q--)
{
int vv=read(),xx=read(),kk=read(),ll=0,rr=0;
if(T)vv^=lastans,xx^=lastans,kk^=lastans;
get_interval(vv,xx,ll,rr);
int ans=query(rt[ll-1],rt[rr],1,N,kk);
if(ans==-1)puts("-1"),lastans=0;
else printf("%d
",B[ans]),lastans=B[ans];
}
return 0;
}
T3:
平面直角坐标系内给出n个点，求一个纵坐标已给出的点使得它到那n个点的距离之和最小
(n<=10^5)
题目链接
solution:
设出距离之和函数f(x)，而后对其求导得到g(x)，易知g(x)单调递增（其实是不会证明）
然后二分求得其零点，带入原函数即可
注意：精度问题以及求导不要求错了
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
double k,x[N],y[N],z[N],w[N];
inline bool ck(double p)
{
double num=0.0;
for(int i=1;i<=n;++i)
num+=100*(p*2-z[i])/sqrt(p*p-z[i]*p+w[i]);
return num>0;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%lf%lf",&x[i],&y[i]);
scanf("%lf",&k);
for(int i=1;i<=n;++i)
{
z[i]=x[i]*2.0;
w[i]=(y[i]-k)*(y[i]-k)+x[i]*x[i];
}
double l=-1.0e9,r=1.0e9;
for(int i=1;i<=150;++i)
{
double mid=(l+r)/2.0;
if(ck(mid)) r=mid;
else l=mid;
}
long double ans=0.0;
for(int i=1;i<=n;++i)
ans+=sqrt((x[i]-r)*(x[i]-r)+(y[i]-k)*(y[i]-k));
cout<<fixed<<setprecision(0)<<ans;
return 0;
}