2017.9.4 NOIP模拟赛

题解 套题

不要急，慢慢来。

目录

• 2017.9.4 NOIP模拟赛
  • 命令序列
    • 思路
    • 代码
  • 找位置
    • 思路
    • 代码
  • 摧毁道路
    • 思路
    • 代码
  • L君找工作
    • 思路
    • 代码

命令序列

思路

• $80$分显然$O(n^2)$暴力模拟，后$20$分只有$L,R$，考虑分类求解；
• 考虑一段序列$l$~$r$，能够回到原点，当且仅当$1$~$l$和$1$~$r$序列到达的位置相同；
• 那么对于每个$r$，我们只需记录之前有多少到达该处的$l$，扫一下就可以了。

代码

#include <cstdio>
#include <utility>
#define x first
#define y second
using std::pair;
typedef pair<int,int> position;
const int MAXN=4e5+5;
int n;
char cmd[MAXN];
namespace solve1
{
inline int operate(int l){
    position pos(0,0);
    int ret=0;
    for(;l<=n;++l){
        switch(cmd[l]){
            case 'U': ++pos.y; break;
            case 'D': --pos.y; break;
            case 'L': --pos.x; break;
            case 'R': ++pos.x; break;
        }
        if(pos.x==0 && pos.y==0) ++ret;
    }
    return ret;
}
inline int solve(){
    int ret=0;
    for(int i=1;i<=n;++i)
        ret+=operate(i);
    return ret;
}
}
namespace solve2
{
int arr[MAXN<<1];
inline long long solve(){
    long long ret=0;
    int *sum=&arr[n+1];
    sum[0]=1;
    for(int i=1,tmp=0;i<=n;++i){
        cmd[i]=='L' ? --tmp:++tmp;
        ret+=sum[tmp];
        ++sum[tmp];
    }
    return ret;
}
}
int main(){
    freopen("command.in","r",stdin);
    freopen("command.out","w",stdout);
    scanf("%d%s",&n,cmd+1);
    if(n<=4000) printf("%d",solve1::solve());
    else printf("%lld",solve2::solve());
    return 0;
}

找位置

思路

• 考虑模拟的话，我们不妨连边建图跑；
• 再思考一下就会发现，图一定会连成若干个不相交的环；
• 那么$O(n)$扫一遍找环存到vector中，对于询问算一下即可。

代码

#include <cstdio>
#include <vector>
using std::vector;
const int MAXN=1e5+5;
int n,q,tot,idx;
int he[MAXN],up_pos[MAXN],dwn_pos[MAXN],pos[MAXN][2];
bool vis[MAXN];
vector<int> cir[MAXN];
struct line{int to,nex;}ed[MAXN<<1];
inline void addE(int u,int v){
    static int cnt=0;
    ed[++cnt]=(line){v,he[u]};
    he[u]=cnt;
}
inline void build(){
    for(int i=1;i<=n;++i)
        addE(dwn_pos[i],up_pos[i]);
}
void find_cir(int u){
    cir[tot].push_back(u);
    pos[u][0]=tot,pos[u][1]=++idx;
    vis[u]=true;
    for(int i=he[u],v;i;i=ed[i].nex){
        v=ed[i].to;
        if(!vis[v]) find_cir(v);
    }
}
int main(){
    freopen("position.in","r",stdin);
    freopen("position.out","w",stdout);
    scanf("%d%d",&n,&q);
    for(int i=1,u,d;i<=n;++i){
        scanf("%d%d",&u,&d);
        up_pos[u]=i;
        dwn_pos[d]=i;
    }
    build();
    for(int i=1;i<=n;++i){
        if(!vis[i]){
            ++tot,idx=0;
            find_cir(i);
        }
    }
    for(int i=1,k,s;i<=q;++i){
        scanf("%d%d",&k,&s);
        printf("%d\n",cir[pos[k][0]][(pos[k][1]+s-1)%cir[pos[k][0]].size()]);
    }
    return 0;
}

摧毁道路

思路

• 显然我们要尽可能使两条路径的交更长；
• 而且可以猜想出只有连续一段的交时更优（很容易反证多次分离、相交一定不优于这个）；
• 由于边权都为$1$，先$n$遍BFS处理出两点间距离；
• 之后$O(n^2)$枚举路径交的端点来更新答案即可。

代码

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using std::max;
using std::queue;
const int MAXN=3005;
int n,m,s1,t1,l1,s2,t2,l2;
int he[MAXN],G[MAXN][MAXN];
struct line{int to,nex;}ed[MAXN<<1];
inline void addE(int u,int v){
    static int cnt=0;
    ed[++cnt]=(line){v,he[u]};
    he[u]=cnt;
}
inline void BFS(int s){
    static bool vis[MAXN];
    static queue<int> que;
    memset(vis,false,sizeof(vis));
    que.push(s);
    vis[s]=true;
    int u;
    int *dis=G[s];
    while(que.size()){
        u=que.front();
        que.pop();
        for(int i=he[u],v;i;i=ed[i].nex){
            v=ed[i].to;
            if(!vis[v]){
                dis[v]=dis[u]+1;
                que.push(v);
                vis[v]=true;
            }
        }
    }
}
inline void cal_APSP(){
    memset(G,30,sizeof(G));
    for(int i=1;i<=n;++i){
        G[i][i]=0;
        BFS(i);
    }
}
inline int solve(){
    if(G[s1][t1]>l1 || G[s2][t2]>l2) return -1;
    int ret=m-G[s1][t1]-G[s2][t2];
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(G[s1][i]+G[i][j]+G[j][t1]<=l1 && G[s2][i]+G[i][j]+G[j][t2]<=l2)
                ret=max(ret,m-G[s1][i]-G[s2][i]-G[i][j]-G[j][t1]-G[j][t2]);
            if(G[s1][i]+G[i][j]+G[j][t1]<=l1 && G[s2][j]+G[j][i]+G[i][t2]<=l2)
                ret=max(ret,m-G[s1][i]-G[s2][j]-G[i][j]-G[j][t1]-G[i][t2]);
        }
    }
    return ret;
}
int main(){
    freopen("destroy.in","r",stdin);
    freopen("destroy.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;++i){
        scanf("%d%d",&u,&v);
        addE(u,v),addE(v,u);
    }
    scanf("%d%d%d",&s1,&t1,&l1);
    scanf("%d%d%d",&s2,&t2,&l2);
    cal_APSP();
    printf("%d",solve());
    return 0;
}

L君找工作

思路

• 直接求不太现实，考虑二分答案后判断；
• 那么问题就变成求连续区间内大于给定值的权值之和，这个我在考试时直接用主席树维护了，其实可以考虑离线做；
• 那么我们将$t_i$和$d_i$排列，将符合要求的$t_i$加到树状数组中即可；
• 复杂度$O((n+m)\log^2 m)$，但主席树常数比树状数组大，所以当时做的时候还卡了半天常数。

代码

#include <cstdio>
#include <algorithm>
using std::sort;
const int MAXN=200005;
int n,m;
struct day{
    int t,id;
    friend bool operator< (const day &a,const day &b){
        return a.t<b.t;
    }
}d[MAXN];
struct work{
    int d,r,time,id;
    static bool cmp_d(const work &a,const work &b){return a.d<b.d;}
    static bool cmp_id(const work &a,const work &b){return a.id<b.id;}
}wk[MAXN];
template<typename type>
class BIT{
    private:
        type c[MAXN];
        int lowbit(int x){return x&-x;}
    public:
        void add(int l,type val){
            for(;l<=m;l+=lowbit(l))
                c[l]+=val;
        }
        type qry(int r){
            type ret=0;
            for(;r;r-=lowbit(r))
                ret+=c[r];
            return ret;
        }
};
BIT<int> cnt;
BIT<long long> ta;
inline void cal_time(work &now,int id){
    static int cur=1;
    for(;d[cur].t<=now.d && cur<=m;++cur){
        ta.add(d[cur].id,-d[cur].t);
        cnt.add(d[cur].id,-1);
    }
    long long sum=ta.qry(m)-(long long)now.d*cnt.qry(m);
    if(now.r>sum){
        now.time=0;
        return;
    }
    int l=1,r=m,mid;
    while(l<=r){
        mid=l+r>>1;
        if(now.r<=ta.qry(mid)-(long long)now.d*cnt.qry(mid))
            r=mid-1;
        else l=mid+1;
    }
    now.time=l;
}
int main(){
    freopen("work.in","r",stdin);
    freopen("work.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d",&d[i].t);
        ta.add(i,d[i].t);
        cnt.add(i,1);
        d[i].id=i;
    }
    sort(d+1,d+m+1);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&wk[i].d,&wk[i].r);
        wk[i].id=i;
    }
    sort(wk+1,wk+n+1,work::cmp_d);
    for(int i=1;i<=n;++i)
        cal_time(wk[i],i);
    sort(wk+1,wk+n+1,work::cmp_id);
    for(int i=1;i<=n;++i)
        printf("%d ",wk[i].time);
    return 0;
}