\(NOIP\) 模拟赛

考差了。

T1签到题。注意存在字符串长度为0，不能直接模。\(100\rightarrow0\)

代码：

#include<bits/stdc++.h>
using namespace std;
int k1,k2,k3,len;
string s,t;
int s1[85],s2[85],s3[85];
char c1[85],c2[85],c3[85];
signed main(){
    freopen("a.in","r",stdin);
    freopen("a.in","w",stdout);
    cin>>k1>>k2>>k3>>s;
    t=s;len=s.length();
    for(int i=0;i<len;i++){
        if(s[i]>='a'&&s[i]<='i')s1[++s1[0]]=i,c1[s1[0]]=s[i];
        else if(s[i]>='j'&&s[i]<='r')s2[++s2[0]]=i,c2[s2[0]]=s[i];
        else s3[++s3[0]]=i,c3[s3[0]]=s[i];
    }
    k1%=s1[0],k2%=s2[0],k3%=s3[0];
    for(int i=1;i<=s1[0];i++){
        int v=i+k1;if(v>s1[0])v%=s1[0];
        t[s1[v]]=c1[i];
    }
    for(int i=1;i<=s2[0];i++){
        int v=i+k2;if(v>s2[0])v%=s2[0];
        t[s2[v]]=c2[i];
    }
    for(int i=1;i<=s3[0];i++){
        int v=i+k3;if(v>s3[0])v%=s3[0];
        t[s3[v]]=c3[i];
    }
    cout<<t;
    return 0;
}

---

T2

可以看出是平面最近点对，之前看到过但没做。。。\(100\rightarrow40\)

经典\(O(n\log n)\) 分治做法。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in read()
inline int read(){
    int p=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
    return p*f;
}
const int N=100005;
struct node{
    int x,y;
}t[N],A[N],B[N];
int n;
inline bool cmp1(node a,node b){return a.x<b.x;}
inline bool cmp2(node a,node b){return a.y<b.y;}
inline int dis(node a,node b){
    int tx=a.x-b.x,ty=a.y-b.y;
    return tx*tx+ty*ty;
}
inline int binl(int key,int bn){
    int l=1,r=bn,mid;
    while(l<r){
        mid=(l+r)>>1;
        if(A[mid].y>key)r=mid;
        else l=mid+1;
    }
    return l;
}
inline int binr(int key,int bn){
    int l=1,r=bn,mid;
    while(l<r){
        mid=(l+r+1)>>1;
        if(A[mid].y<key)l=mid;
        else r=mid-1;
    }
    return l;
}
inline int solve(int l,int r){
    if(l==r)return 0x7fffffffffffffff;
    int mid=(l+r)>>1;
    int d1=solve(l,mid),d2=solve(mid+1,r),d=min(d1,d2),an=0,bn=0;
    for(int i=mid;t[mid].x-t[i].x<d&&i>=l;i--)
        A[++an]=t[i];
    for(int i=mid+1;t[i].x-t[mid].x<d&&i<=r;i++)
        B[++bn]=t[i];
    sort(B+1,B+1+bn,cmp2);
    sort(A+1,A+1+an,cmp2);
    int tl=binl(B[1].y-d,an),tr=binr(B[1].y+d,an);
    for(int i=1;i<=bn;i++){
        while(A[tl].y<=B[i].y-sqrt(d)&&tl<an)tl++;
        while(A[tr+1].y<B[i].y+sqrt(d)&&tr<bn)tr++;
        for(int j=tl;j<=tr;j++)
            d=min(d,dis(B[i],A[j]));
    }
    return d;
}
signed main(){
    n=in;
    for(int i=1;i<=n;i++){
        t[i].y=t[i-1].y+in;
        t[i].x=i;
    }
    sort(t+1,t+1+n,cmp1);
    printf("%lld",solve(1,n));
    return 0;
}

---

T3

需要对两个函数进行分析。正解链剖线段树。但暴力dfs加小优化也能A。我有想过优化但认为其能被卡，所以\(100\rightarrow40\)

代码：

#include<bits/stdc++.h>
using namespace std;
#define in read()
inline int read(){
    int p=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
    return p*f;
}
const int N=200005;
struct edge{
    int v,next;
}e[N*2];
int head[N],en;
void insert(int u,int v){
    e[++en].v=v;
    e[en].next=head[u];
    head[u]=en;
}
int n,q,a[N],fa[N],f1[N],f2[N];
void dfs(int u){
    int t1=f1[u],t2=f2[u];
    if(f1[fa[u]]+1<a[u])f1[u]=a[u],f2[u]=1;
    else if(f1[fa[u]]+1>a[u])f1[u]=f1[fa[u]]+1,f2[u]=f2[fa[u]];
    else f1[u]=f1[fa[u]]+1,f2[u]=f2[fa[u]]+1;
    if(t1==f1[u]&&t2==f2[u])return ;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].v;
        if(v==fa[u])continue;
        fa[v]=u;
        dfs(v);
    }
}
signed main(){
    //freopen("c.in","r",stdin);
    //freopen("c.out","w",stdout);
    n=in;
    for(int i=1;i<=n;i++)
        a[i]=in;
    for(int i=1;i<n;i++){
        int u=in,v=in;
        insert(u,v);
        insert(v,u);
    }
    f1[1]=a[1],f2[1]=1;
    for(int i=head[1];i;i=e[i].next){
        int v=e[i].v;
        fa[v]=1;
        dfs(v);
    }
    q=in;
    for(int i=1;i<=q;i++){
        int opt=in;
        if(opt==0){
            int u=in,val=in;
            a[u]=val;
            dfs(u);
        }
        if(opt==1){
            int u=in;
            cout<<f1[u]<<" "<<f2[u]<<'\n';
        }
    }
    return 0;
}

---

T4

在用权值线段树求LIS时做些修改即可，但我写挂了。\(100\rightarrow0\)

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=50005;
const int mod=1000000007;
int n;
int a[N];
int qn,q[N];
int bin(int key){
    int l=1,r=qn;
    int mid;
    while(l<r){
        mid=(l+r)>>1;
        if(q[mid]>key)r=mid-1;
        else if(q[mid]<key)l=mid+1;
        else{l=mid;break;}
    }
    return l;
}

int len[N],fro[N];
//seg_tree----------------
#define m(x) tree[x].m
#define sum(x) tree[x].sum
struct node{
    int sum,m;
}tree[4*N];
void built(int l,int r,int p){
    m(p)=sum(p)=0;
    if(l==r)return ;
    int mid=(l+r)>>1;
    built(l,mid,p<<1);
    built(mid+1,r,p<<1|1);
    return ;
}
struct temp{int maxn,many;};
temp query(int l,int r,int p,int ql,int qr){
    temp ans;
    ans.many=ans.maxn=0;
    if(ql>qr)return ans;
    if(l>=ql&&r<=qr){
        ans.maxn=m(p);
        ans.many=sum(p);
        return ans;
    }
    int mid=(l+r)>>1;
    if(ql<=mid)ans=query(l,mid,p<<1,ql,qr);
    if(qr>mid){
        if(!ans.maxn)ans=query(mid+1,r,p<<1|1,ql,qr);
        else{
            temp ans1=query(mid+1,r,p<<1|1,ql,qr);
            if(ans.maxn==ans1.maxn) ans.many+=ans1.many;
            else if(ans.maxn<ans1.maxn)ans.maxn=ans1.maxn,ans.many=ans1.many;
        }
    }
    return ans;
}
void update(int l,int r,int p,int u,int d){
    if(l==r){
        if(d==m(p))sum(p)++;
        if(d>m(p)){m(p)=d;sum(p)=1;}
        return ;
    }
    int mid=(l+r)>>1;
    if(u<=mid)update(l,mid,p<<1,u,d);
    else update(mid+1,r,p<<1|1,u,d);
    if(m(p<<1)==m(p<<1|1)){
        m(p)=m(p<<1);
        sum(p)=sum(p<<1)+sum(p<<1|1);
    }
    else if(m(p<<1)>m(p<<1|1)){
        m(p)=m(p<<1);
        sum(p)=sum(p<<1);
    }
    else{
        m(p)=m(p<<1|1);
        sum(p)=sum(p<<1|1);
    }
    return ;
}
//------------------------
signed main(){
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        q[i]=a[i];
    }
    sort(q+1,q+1+n);
    qn=unique(q+1,q+1+n)-(q+1);
    for(int i=1;i<=n;i++)
        a[i]=bin(a[i]);
    built(1,qn,1);
    int maxlen=0,tans=0;
    for(int i=1;i<=n;i++){
        temp t=query(1,qn,1,1,a[i]-1);
        len[i]=1+t.maxn;
        fro[i]=t.many;

        update(1,qn,1,a[i],len[i]);
        if(len[i]>maxlen){
            maxlen=len[i];
            tans=fro[i]%mod;
        }
        else if(len[i]==maxlen)
            tans=(tans+fro[i])%mod;
    }
    //for(int i=1;i<=n;i++)
    //  cout<<len[i]<<" ";
    //cout<<endl;
    //for(int i=1;i<=n;i++)
    //  cout<<fro[i]<<" ";
    //cout<<maxlen<<" "<<tans;
    cout<<tans;
    return 0;
}

---

考的不理想.