Lvat_s Blog

贪心的做

因为只做一次特技显然没用

我们要把价值最大的特技安排在两端

然后贪心的做特技就好了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
int n,k,c[1005],ans;
 
int main(){
freopen("2697.in","r",stdin);
freopen("2697.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1;i<=k;i++)scanf("%d",&c[i]);
sort(c+1,c+k+1);
for(int i=k;i>=1 && n>1;i--,n-=2){ans+=c[i]*(n-1);}
printf("%d\n",ans);
return 0;
}

KD-Tree直接上

维护一个关于点对距离的数组

每次询问直接在KD-Tree里面贪心的找就可以了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int Sort_Tag,n,m,root,Ask_k,id[25];
long long Ask_x,Ask_y,ans[25];
 
struct KDTree{
long long d[2],mx[2],mn[2];
int l,r,id;
friend bool operator<(KDTree A,KDTree B){
return (A.d[Sort_Tag]<B.d[Sort_Tag])||(A.d[Sort_Tag]==B.d[Sort_Tag] && A.d[!Sort_Tag]<B.d[!Sort_Tag]);
}
}tree[N],Tp;
 
void Pushup(int rt){
if(tree[rt].l){
    if(tree[rt].mn[0]>tree[tree[rt].l].mn[0])tree[rt].mn[0]=tree[tree[rt].l].mn[0];
    if(tree[rt].mn[1]>tree[tree[rt].l].mn[1])tree[rt].mn[1]=tree[tree[rt].l].mn[1];
    if(tree[rt].mx[0]<tree[tree[rt].l].mx[0])tree[rt].mx[0]=tree[tree[rt].l].mx[0];
    if(tree[rt].mx[1]<tree[tree[rt].l].mx[1])tree[rt].mx[1]=tree[tree[rt].l].mx[1];
}
if(tree[rt].r){
    if(tree[rt].mn[0]>tree[tree[rt].r].mn[0])tree[rt].mn[0]=tree[tree[rt].r].mn[0];
    if(tree[rt].mn[1]>tree[tree[rt].r].mn[1])tree[rt].mn[1]=tree[tree[rt].r].mn[1];
    if(tree[rt].mx[0]<tree[tree[rt].r].mx[0])tree[rt].mx[0]=tree[tree[rt].r].mx[0];
    if(tree[rt].mx[1]<tree[tree[rt].r].mx[1])tree[rt].mx[1]=tree[tree[rt].r].mx[1];
}
}
 
int Build(int l,int r,int D){
int mid=l+r>>1;
Sort_Tag=D;
nth_element(tree+l+1,tree+mid+1,tree+r+1);
tree[mid].mx[0]=tree[mid].mn[0]=tree[mid].d[0];
tree[mid].mx[1]=tree[mid].mn[1]=tree[mid].d[1];
if(l<mid)tree[mid].l=Build(l,mid-1,!D);
if(r>mid)tree[mid].r=Build(mid+1,r,!D);
Pushup(mid);
return mid;
}
 
long long Sqr(long long x){return x*x;}
 
long long MxDist(int p,long long x,long long y){
return max(Sqr(tree[p].mx[0]-x),Sqr(tree[p].mn[0]-x))+max(Sqr(tree[p].mx[1]-y),Sqr(tree[p].mn[1]-y));
}
 
void Query(int rt){
long long Dl,Dr,Dm=Sqr(tree[rt].d[0]-Ask_x)+Sqr(tree[rt].d[1]-Ask_y);
int Kt=Ask_k;
while(Kt && ((ans[Kt]<Dm)||(ans[Kt]==Dm && id[Kt]>tree[rt].id)))Kt--;
if(Kt!=Ask_k){
    for(int i=Ask_k;i>=Kt+2;i--){
        ans[i]=ans[i-1];
        id[i]=id[i-1];
    }
    ans[Kt+1]=Dm;id[Kt+1]=tree[rt].id;
}
if(tree[rt].l)Dl=MxDist(tree[rt].l,Ask_x,Ask_y);else Dl=-1;
if(tree[rt].r)Dr=MxDist(tree[rt].r,Ask_x,Ask_y);else Dr=-1;
if(Dl<Dr){
    if(Dr>=ans[Ask_k])Query(tree[rt].r);
    if(Dl>=ans[Ask_k])Query(tree[rt].l);
}
else {
    if(Dl>=ans[Ask_k])Query(tree[rt].l);
    if(Dr>=ans[Ask_k])Query(tree[rt].r);
}
}
 
int main(){
freopen("2626.in","r",stdin);
freopen("2626.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%lld %lld",&tree[i].d[0],&tree[i].d[1]);tree[i].id=i;}
root=Build(1,n,0);
scanf("%d",&m);
for(int i=1;i<=m;i++){
    scanf("%lld %lld %lld",&Ask_x,&Ask_y,&Ask_k);
    memset(ans,0,sizeof(ans));
    memset(id,127,sizeof(id));
    Query(root);
    printf("%d\n",id[Ask_k]);
}
return 0;
}

首先我们可以离线做

考虑每次把一条链上的权值全部加上1，然后询问z到根的值就是这个LCA的和

然后离线排序树剖一下直接做就好了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const int N=50005,Mod=201314;
 
int n,q,en,fa[N],h[N],cnt,dep[N],top[N],segn,siz[N],son[N],id[N];
 
struct Ask{
int z,ans1,ans2;
}Qu[N];
 
struct Option{
int id,p,flag;
friend bool operator<(Option A,Option B){return A.p<B.p;}
}Opt[2*N];
 
struct Edge{
int b,next;
}e[N];
 
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
 
struct SegTree{
int l,r,sum,tag;
}tree[4*N];
 
void Pushup(int rt){tree[rt].sum=(tree[rt<<1].sum+tree[rt<<1|1].sum)%Mod;}
 
void Pushdown(int rt){
if(tree[rt].tag){
    tree[rt<<1].tag=(tree[rt<<1].tag+tree[rt].tag)%Mod;
    tree[rt<<1|1].tag=(tree[rt<<1|1].tag+tree[rt].tag)%Mod;
    tree[rt<<1].sum=(tree[rt<<1].sum+tree[rt].tag*(tree[rt<<1].r-tree[rt<<1].l+1))%Mod;
    tree[rt<<1|1].sum=(tree[rt<<1|1].sum+tree[rt].tag*(tree[rt<<1|1].r-tree[rt<<1|1].l+1))%Mod;
    tree[rt].tag=0;
}
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
if(l==r){tree[rt].sum=0;tree[rt].tag=0;return;}
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
}
 
void Modify(int rt,int l,int r,int val){
if(l<=tree[rt].l && tree[rt].r<=r){
    tree[rt].tag=(tree[rt].tag+val)%Mod;
    tree[rt].sum=(tree[rt].sum+val*(tree[rt].r-tree[rt].l+1))%Mod;
    return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Modify(rt<<1,l,r,val);
if(r>mid)Modify(rt<<1|1,l,r,val);
Pushup(rt);
}
 
int Query(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r)return tree[rt].sum;
int mid=tree[rt].l+tree[rt].r>>1,ans=0;
Pushdown(rt);
if(l<=mid)ans=(ans+Query(rt<<1,l,r))%Mod;
if(r>mid)ans=(ans+Query(rt<<1|1,l,r))%Mod;
return ans;
}
 
void dfs1(int u){
dep[u]=dep[fa[u]]+1;
siz[u]=1;
son[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fa[u])continue;
    dfs1(v);
    siz[u]+=siz[v];
    if(siz[son[u]]<siz[v])son[u]=v;
}
}
 
void dfs2(int u,int ux){
top[u]=ux;
id[u]=++segn;
if(!son[u])return;
dfs2(son[u],ux);
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(son[u]==v || fa[u]==v)continue;
    dfs2(v,v);
}
}
 
void Update(int x){
while(top[x]!=top[1]){
    Modify(1,id[top[x]],id[x],1);
    x=fa[top[x]];
}
Modify(1,id[1],id[x],1);
}
 
int Solve(int x){
int ans=0;
while(top[x]!=top[1]){
    ans=(ans+Query(1,id[top[x]],id[x]))%Mod;
    x=fa[top[x]];
}
return (ans+Query(1,id[1],id[x]))%Mod;
}
 
int main(){
freopen("3626.in","r",stdin);
freopen("3626.out","w",stdout);
scanf("%d %d",&n,&q);
for(int i=2;i<=n;i++){scanf("%d",&fa[i]);fa[i]++;AddEdge(fa[i],i);}
dfs1(1);
dfs2(1,1);
Build(1,1,n);
for(int i=1;i<=q;i++){
    int x,y,z;
    scanf("%d %d %d",&x,&y,&z);
    x++;y++;z++;
    Qu[i].z=z;
    Opt[++cnt].id=i;
    Opt[cnt].p=x-1;
    Opt[cnt].flag=0;
    Opt[++cnt].id=i;
    Opt[cnt].p=y;
    Opt[cnt].flag=1;
}
sort(Opt+1,Opt+cnt+1);
int Now=1;
for(int i=1;i<=cnt;i++){
    while(Now<=Opt[i].p){Update(Now);Now++;}
    if(Opt[i].flag)Qu[Opt[i].id].ans2=Solve(Qu[Opt[i].id].z);
    else Qu[Opt[i].id].ans1=Solve(Qu[Opt[i].id].z);
}
for(int i=1;i<=q;i++){
    printf("%d\n",(Qu[i].ans2-Qu[i].ans1+Mod)%Mod);
}
return 0;
}

直接Splay上

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int n,m,a[N];
 
struct Node{
int v,rev,siz;
Node *ch[2],*fa;
Node(){}
Node(int vx);
void Pushdown();
void Pushup();
}*root,*Null;
 
Node::Node(int vx){
v=vx;
siz=1;
rev=0;
ch[0]=ch[1]=fa=Null;
}
 
Node *GetNull(){
Node *p=new Node(0);
p->siz=0;
p->ch[0]=p->ch[1]=p->fa=p;
return p;
}
 
void Node::Pushdown(){
if(rev){
    rev=0;
    if(ch[0]!=Null)ch[0]->rev^=1;
    if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0]->ch[0],ch[0]->ch[1]);
    swap(ch[1]->ch[0],ch[1]->ch[1]);
}
}
 
void Node::Pushup(){
siz=ch[0]->siz+ch[1]->siz+1;
}
 
void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(z!=Null)z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}
 
void Splay(Node *x,Node *place){
while(x->fa!=place){
    Node *y=x->fa,*z=y->fa;
    if(z==place)Rotate(x,y->ch[0]==x);
    else {
        if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
        else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
        else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
        else {Rotate(y,0);Rotate(x,0);}
    }
}
if(place==Null)root=x;
}
 
Node *Find(Node *splay,int k){
splay->Pushdown();
if(splay->ch[0]->siz+1==k)return splay;
if(splay->ch[0]->siz>=k)return Find(splay->ch[0],k);
return Find(splay->ch[1],k-1-splay->ch[0]->siz);
}
 
Node *GetSeq(int l,int r){
Node *Tp1=Find(root,l);
Splay(Tp1,Null);
Node *Tp2=Find(root,r+2);
Splay(Tp2,root);
return Tp2->ch[0];
}
 
Node *Build(int l,int r){
if(l>r)return Null;
int mid=l+r>>1;
Node *splay=new Node(a[mid]);
splay->ch[0]=Build(l,mid-1);
if(splay->ch[0]!=Null)splay->ch[0]->fa=splay;
splay->ch[1]=Build(mid+1,r);
if(splay->ch[1]!=Null)splay->ch[1]->fa=splay;
splay->Pushup();
return splay;
}
 
void PrintTree(Node *rt){
if(rt==Null)return;
rt->Pushdown();
if(rt->ch[0]!=Null)PrintTree(rt->ch[0]);
if(rt->v)printf("%d ",rt->v);
if(rt->ch[1]!=Null)PrintTree(rt->ch[1]);
}
 
void Reverse(int l,int r){
Node *seq=GetSeq(l,r),*fat=seq->fa;
seq->rev^=1;
swap(seq->ch[0],seq->ch[1]);
fat->Pushup();
fat->fa->Pushup();
}
 
int main(){
freopen("3223.in","r",stdin);
freopen("3223.out","w",stdout);
scanf("%d %d",&n,&m);
Null=GetNull();
for(int i=1;i<=n;i++)a[i+1]=i;
root=Build(1,n+2);
for(int i=1;i<=m;i++){
    int l,r;
    scanf("%d %d",&l,&r);
    Reverse(l,r);
}
PrintTree(root);
return 0;
}

四边形不等式优化

我一开始直接写了一个旋转卡壳然后WA了

搜了一下题解，发现这样不对(有可能点会靠后一些)

需要优化

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=500005;
int n,T,ans[N];
 
struct Point{
long long x,y,id;
Point(){}
Point(long long sa,long long sb){x=sa;y=sb;}
friend Point operator+(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
friend Point operator-(Point A,Point B){return Point(A.x-B.x,A.y+B.y);}
friend Point operator*(Point A,long long B){return Point(A.x*B,A.y*B);}
friend long long operator*(Point A,Point B){return A.x*B.y-A.y*B.x;}
}poi[2*N];
 
long long Dist(Point A,Point B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}
 
bool cmp(int i,int j,int k){
long long x=Dist(poi[i],poi[j]),y=Dist(poi[i],poi[k]);
if(j<i || j>i+n)x=-x;
if(k<i || k>i+n)y=-y;
return x==y?poi[j].id>poi[k].id:x<y;
}
 
void Find(int l,int r,int L,int R){
if(l>r)return;
int mid=l+r>>1,M=L;
for(int i=L+1;i<=R;i++)if(cmp(mid,M,i))M=i;
ans[mid]=poi[M].id;
Find(l,mid-1,L,M);Find(mid+1,r,M,R);
}
 
int main(){
freopen("2739.in","r",stdin);
freopen("2739.out","w",stdout);
scanf("%d",&T);
while(T--){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld %lld",&poi[i].x,&poi[i].y),poi[i].id=i;
    if(n==1){puts("1");continue;}
    if(n==2){puts("2\n1");continue;}
    for(int i=n+1;i<=2*n;i++)poi[i]=poi[i-n];
    Find(1,n,1,n<<1);
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
}
return 0;
}

模版题

每个点只向每个象限里最近的点连边

离散化后树状数组维护就好了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const long long N=50005,LIMIT=1000000000,INF=210000000000000ll;
 
long long n,f[N],Fir[10*N],Sec[10*N],cnt,Line[10*N],Num[10*N],tot,ans;
 
struct Point{
long long x,y,id;
friend bool operator<(Point A,Point B){return (A.x<B.x)|(A.x==B.x && A.y<B.y);}
}poi[N];
 
struct Edge{
long long x,y,len;
Edge(){}
Edge(long long sa,long long sb,long long sc){x=sa;y=sb;len=sc;}
friend bool operator<(Edge A,Edge B){return A.len<B.len;}
}e[20*N];
 
long long Find(long long x){return f[x]==x?x:f[x]=Find(f[x]);}
void Union(long long x,long long y){if(x>y)f[x]=y;else f[y]=x;}
long long lowbit(long long x){return x&(-x);}
void AddBIT(long long x,long long y,long long z){while(x){if(Fir[x]>y){Fir[x]=y;Sec[x]=z;}x-=lowbit(x);}}
long long QueBIT(long long x){long long Mx=LIMIT*2,Ex=0;while(x<=n){if(Mx>Fir[x]){Mx=Fir[x];Ex=Sec[x];}x+=lowbit(x);}return Ex;}
long long Abs(long long x){return x>0?x:-x;}
long long Dist(Point A,Point B){return Abs(A.y-B.y)+Abs(A.x-B.x);}
 
int main(){
freopen("2177.in","r",stdin);
freopen("2177.out","w",stdout);
scanf("%lld",&n);
for(long long i=1;i<=n;i++){scanf("%lld %lld",&poi[i].x,&poi[i].y);poi[i].id=i;}
for(long long i=1;i<=4;i++){
    if(i==3)for(long long i=1;i<=n;i++)poi[i].x=LIMIT-poi[i].x;
    if(i==2 || i==4)for(long long i=1;i<=n;i++)swap(poi[i].x,poi[i].y);
    sort(poi+1,poi+n+1);
    for(long long i=1;i<=n;i++)Line[i]=poi[i].y-poi[i].x;
    sort(Line+1,Line+n+1);
    for(long long i=1;i<=n;i++)Num[i]=lower_bound(Line+1,Line+n+1,poi[i].y-poi[i].x)-Line;
    for(long long i=1;i<=n;i++)Fir[i]=INF;
    for(long long i=n;i>=1;i--){
        long long Set=QueBIT(Num[i]);
        if(Set)e[++cnt]=Edge(poi[i].id,poi[Set].id,Dist(poi[i],poi[Set]));
        AddBIT(Num[i],poi[i].y+poi[i].x,i);
    }
}
sort(e+1,e+cnt+1);
for(long long i=1;i<=n;i++)f[i]=i;
for(long long i=1;i<=cnt && tot<n-1;i++){
    if(Find(e[i].x)!=Find(e[i].y)){
        tot++;
        Union(Find(e[i].x),Find(e[i].y));
        ans+=1ll*e[i].len;
    }
}
printf("%lld\n",ans);
return 0;
}

图上进行概率DP

先BFSn次算出每个点的最优前进点

然后对于每种情况DFS算期望

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
 
const int N=1005;
 
int n,m,en,h[N],deg[N],Cat,Mouse,D[N][N],P[N][N];
double f[N][N];
queue<int> Q;
 
struct Edge{
int b,next;
}e[N*2];
 
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
deg[sa]++;
}
 
void BFS(int S){
Q.push(S);
D[S][S]=0;
while(!Q.empty()){
    int u=Q.front(),tmp=P[S][u];
    Q.pop();
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(D[S][v]==-1 || (D[S][u]+1==D[S][v] && tmp<P[S][v])){
            D[S][v]=D[S][u]+1;
            if(!tmp)P[S][v]=v;
            else P[S][v]=tmp;
            Q.push(v);
        }
    }
}
}
 
double DP(int Cat,int Mouse){
if(f[Cat][Mouse])return f[Cat][Mouse];
if(Cat==Mouse)return f[Cat][Mouse]=0;
if(P[Cat][Mouse]==Mouse || P[P[Cat][Mouse]][Mouse]==Mouse)return f[Cat][Mouse]=1;
double Sum=DP(P[P[Cat][Mouse]][Mouse],Mouse);
for(int i=h[Mouse];i;i=e[i].next)Sum+=DP(P[P[Cat][Mouse]][Mouse],e[i].b);
return f[Cat][Mouse]=Sum/(deg[Mouse]+1)+1;
}
 
int main(){
freopen("1415.in","r",stdin);
freopen("1415.out","w",stdout);
memset(D,-1,sizeof(D));
scanf("%d %d %d %d",&n,&m,&Cat,&Mouse);
for(int i=1;i<=m;i++){
    int sa,sb;
    scanf("%d %d",&sa,&sb);
    AddEdge(sa,sb);
    AddEdge(sb,sa);
}
for(int i=1;i<=n;i++)BFS(i);
printf("%.3lf\n",DP(Cat,Mouse));
return 0;
}

使用n!近似公式算一下就可以了

注意特判

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
 
const long double Pi=acos(-1),e=exp(1),eps=1e-10;
long long n,k;
 
long double log(long double a,long double b){return log(a)/log(b);}
 
int main(){
freopen("3000.in","r",stdin);
freopen("3000.out","w",stdout);
while(scanf("%lld %lld",&n,&k)!=EOF){
    double ans=0;
    if(n<=10000){
        for(int i=1;i<=n;i++)ans+=log(i);
        ans/=log(k);
        ans=ceil(ans+eps);
        printf("%.0lf\n",ans);
    }
    else printf("%lld\n",(long long)(0.5*log(2*Pi*n,k)+n*log(n,k)-n*log(e,k)+1));
}
return 0;
}