头像

DreamChaser


访客:868

离线:7小时前



题目:

给你一棵 $N$ 个节点的树以及 $Q$ 组询问,每组询问给定三个点 $(a, b, c)$ ,请你求出 $(a,b,c)$ 的某个排列 $(s, f, t)$ ,使得从 $s$ 到 $f$ 的链与从 $t$ 到 $f$ 的链的交的长度最大(这里计链的长度为链上点的个数),输出这个最大值。

$n,q\le 100000$


目前思路大概是LCA,但不太清楚具体怎么搞,求助各位大佬们

(其实之前发过一个帖子,只是大家似乎都没有回答…)




求助如何优化下面这个代码:

#include <iostream>
#include <algorithm>

using namespace std;
const int N=3000000;

int n,q,a[N];
int l,r;

int main() {
    cin>>n>>q;
    for(int i=1; i<=n; i++) cin>>a[i];
    while(q--) {
        cin>>l>>r;
        bool ok=true;
        for(int i=l; i<r; i++) if(abs(a[i+1]-a[i])>1) ok=false;
        if(ok) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

数据范围:$1\le n,m\le 3000000,1\le l\le r\le n,1\le a_i\le 10^9$



活动打卡代码 AcWing 104. 货仓选址

#include<bits/stdc++.h>
#define ll long long
#define landingyu work();
#define AK return
#define IOI 0;
#define inf 0x3f3f3f3f
#define eps 0.00001
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int F[1000];
void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
using namespace std;
int a[100010],ans;
void work(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) ans+=abs(a[i]-a[n+1>>1]);
    cout<<ans;
}
int main(){landingyu AK IOI}



活动打卡代码 AcWing 103. 电影

#include<bits/stdc++.h>
using namespace std;
int n,m,ans0=1,ans1,ans2,tot,k;
int a[200010],x[200010],y[200010],cinema[600010],ans[600010];
int find(int f){
    return lower_bound(cinema+1,cinema+k+1,f)-cinema;
}
int main(){
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        cinema[++tot]=a[i];
    }
    cin>>m;
    for(int i=1; i<=m; i++) {
        cin>>x[i];
        cinema[++tot]=x[i];
    }
    for (int i=1; i<=m; i++) {
        cin>>y[i];
        cinema[++tot]=y[i];
    }
    sort(cinema+1,cinema+tot+1);
    k=unique(cinema+1,cinema+tot+1)-(cinema+1);
    for(int i=1; i<=n; i++) ans[find(a[i])]++;
    for(int i=1; i<=m; i++) {
        int ansx=ans[find(x[i])],ansy=ans[find(y[i])];
        if(ansx>ans1 || (ansx==ans1 && ansy>ans2)) {
            ans0=i;
            ans1=ansx;
            ans2=ansy;
        }
    }
    cout<<ans0;
    return 0;
}


活动打卡代码 AcWing 113. 特殊排序

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> specialSort(int n) {
        vector<int> res;
        res.push_back(1);
        for(int i=2;i<=n;i++){
            int l=0,r=res.size()-1;
            while(l<r){
                int mid=(l+r+1)>>1;
                if(compare(res[mid],i)) l=mid;
                else r=mid-1;
            }
            res.push_back(i);
            for(int j=res.size()-2;j>=r+1;j--) swap(res[j],res[j+1]);
            if(compare(i,res[r])) swap(res[r],res[r+1]);
        }
        return res;
    }
};


活动打卡代码 AcWing 102. 最佳牛围栏

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
double a[100001],b[100001],sum[100001];
int main(){
    int N,L;
    cin>>N>>L;
    for(int i=1;i<=N;i++) scanf("%lf",&a[i]);
    double eps=1e-5;
    double l=-1e6,r=1e6;
    while(r-l>eps){
        double mid=(l+r)/2;
        for(int i=1;i<=N;i++) b[i]=a[i]-mid;
        for(int i=1;i<=N;i++) sum[i]=(sum[i-1]+b[i]);
        double ans=-1e10;
        double min_val=1e10;
        for(int i=L;i<=N;i++){
            min_val=min(min_val,sum[i-L]);
            ans=max(ans,sum[i]-min_val);
        }
        if(ans>=0) l=mid;
        else r=mid;
    }
    cout<<int(r*1000)<<endl;
    return 0;
}



活动打卡代码 AcWing 101. 最高的牛

#include<bits/stdc++.h>
#define ll long long
#define landingyu work();
#define AK return
#define IOI 0;
#define inf 0x3f3f3f3f
#define eps 0.00001
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int F[1000];
void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
using namespace std;
map<pair<int,int>,bool> existed;
int c[10010],d[10010];
void work(){
    int n=read(),p=read(),h=read(),m=read();
    for(int i=1;i<=m;i++){
        int a=read(),b=read();
        if(a>b) swap(a,b);
        if(existed[make_pair(a,b)]) continue;
        d[a+1]--,d[b]++;
        existed[make_pair(a,b)]=true;
    } 
    for(int i=1;i<=n;i++){
        c[i]=c[i-1]+d[i];
        cout<<c[i]+h<<endl;
    } 
}
int main(){landingyu AK IOI}



活动打卡代码 AcWing 100. IncDec序列

#include<bits/stdc++.h>
#define ll long long
#define landingyu work();
#define AK return
#define IOI 0;
#define inf 0x3f3f3f3f
#define eps 0.00001
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int F[1000];
void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
using namespace std;
int a[100010],b[100010];
void work(){
    int n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];
    b[n+1]=0;
    long long p=0,q=0;
    for(int i=2;i<=n;i++) {
        if(b[i]>0) p+=b[i];
        if(b[i]<0) q-=b[i];
    }
    cout<<max(p,q)<<endl<<abs(p-q)+1;
}
int main(){landingyu AK IOI}


活动打卡代码 AcWing 99. 激光炸弹

#include<bits/stdc++.h>
using namespace std;
int a[5010][5010];
int x,y,w;
int ans;
int main(){
    int n,r;
    cin>>n>>r;
    for(int i=1; i<=n; i++) {
        cin>>x>>y>>w;
        a[x+1][y+1]=w;
    }
    for(int i=1; i<=5001; i++)
        for(int j=1; j<=5001; j++)
            a[i][j]=a[i-1][j]+a[i][j-1]+a[i][j]-a[i-1][j-1];
    for(int i=0; i<5001-r; i++)
        for(int j=0; j<5001-r; j++)
            ans=max(ans,a[i+r][j+r]-a[i+r][j]-a[i][j+r]+a[i][j]);
    cout<<ans;
    return 0;
}



活动打卡代码 AcWing 98. 分形之城

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
#define landingyu work();
#define AK return
#define IOI 0;
#define inf 0x3f3f3f3f
#define eps 0.00001
inline long long read(){
    long long x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int F[1000];
void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
using namespace std;
int N;
long long S,D;
pair<long long,long long> calc(int n,long long m){
    if(n==0) return make_pair(0,0);
    long long len=1ll<<(n-1),cnt=1ll<<(2*n-2);
    auto pos=calc(n-1,m%cnt);
    auto x=pos.first,y=pos.second;
    auto z=m/cnt;
    if(z==0) return make_pair(y,x);
    if(z==1) return make_pair(x,y+len);
    if(z==2) return make_pair(x+len,y+len);
    if(z==3) return make_pair(2*len-y-1,len-x-1);
} 
void work(){
    int T=read();
    while(T--){
        N=read(),S=read(),D=read();
        double x1=calc(N,S-1).first ,x2=calc(N,D-1).first;
        double y1=calc(N,S-1).second,y2=calc(N,D-1).second;
        printf("%.0lf\n",sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))*10);
    }

}
int main(){landingyu AK IOI}