2017.10.27 NOIP模拟赛

题解 套题

目录

• 2017.10.27 NOIP模拟赛
  • Graph
    • 思路
    • 代码
  • Permutation
    • 思路
    • 代码
  • Tree
    • 思路
    • 代码

Graph

思路

• 这是竟然是一个贪心。。。不过经过尝试后发现确实像；
• 我们考虑一个$n$个点的连通块的贡献最多是$\lfloor\frac{n}{2}\rfloor$，我们只需要考虑怎么构造出来就好了；
• 不妨使用DFS处理，对于每一个点$u$，我们都只处理DFS树上它子树里的；
• 也就是如果有边$(u,v)$且$deep(u)<deep(v)$，那么我们将$v$放入$u$的一个答案集合；
• 如果$u$答案集合$S$大小是偶数，那么很好办，$u$的贡献就是$\forall v \in S,u,\forall w \in S$，这样两两配对；
• 如果是奇数怎么办呢？我们把DFS树上的边$(fa,u)$分给$u$补上就好了（偶数情况就分给$fa$了，这样的正确性在于尽可能将这个有用的补偿向上传递直至被用上，反证可知没有更优方案）。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <vector>
using std::vector;
const int MAXN=100005,MAXM=200005;
int n,cnt;
int he[MAXN],deg[MAXN],de[MAXN];
bool vis[MAXN];
vector<int> ans[MAXN];
struct line{int to,nex;}ed[MAXM<<1];
inline void addE(int u,int v){
    static int cnt;
    ed[++cnt]=(line){v,he[u]};
    he[u]=cnt;
}
void DFS(int u,int fa){
    vis[u]=true;
    for(int i=he[u],v;i;i=ed[i].nex){
        v=ed[i].to;
        if(v==fa) continue;
        if(!vis[v]){
            de[v]=de[u]+1;
            DFS(v,u);
        }
        else if(de[v]>de[u]){
            ++deg[u];
            ans[u].push_back(v);
        }
    }
    if(fa){
        if(deg[u]&1) ans[u].push_back(fa);
        else{
            ++deg[fa];
            ans[fa].push_back(u);
        }
    }
}
inline void solve(){
    for(int i=1;i<=n;++i){
        if(!vis[i]) DFS(i,0);
    }
    for(int i=1;i<=n;++i)
        cnt+=ans[i].size()>>1;
}
int main(){
    setIO("graph");
    int m;
    read(n),read(m);
    for(int i=1,u,v;i<=m;++i){
        read(u),read(v);
        addE(u,v),addE(v,u);
    }
    solve();
    write(cnt,'\n');
    for(int i=1;i<=n;++i){
        for(int j=0;j+1<ans[i].size();j+=2){
            write(ans[i][j],' ');
            write(i,' ');
            write(ans[i][j+1],'\n');
        }
    }
    return 0;
}

Permutation

思路

• 这种题目我是第一次遇到，也加深了对拓扑序的理解；
• 题目给的条件对直接根据$P$求解没有很大的帮助，我们考虑转化；
• 设$id_{P_i}=i$，那么就是求序列$id$的映射最小字典序；
• 至于题目中的条件，转化为了：$id_i,id_j$可交换$\iff \mid i-j \mid=1$且$\mid id_i-id_j \mid\geq k$；
• 这样$id$序列只能将相邻的两个元素交换，那么$\mid id_i-id_j \mid<k$的$id_i,id_j$相对位置永远不可能改变；
• 相对位置这个可以转化为DAG上的连边，即如果原来$id_i$在$id_j$前面，那么连一条边$id_i \to id_j$；
• 我们确定了这些相对关系，求一下这个DAG的字典序最小的拓扑序，就是字典序最小的$id$序列了，那么也就可以反推回$P$了；
• 但是，如果暴力连边，每个点要连$2k$条边，这显然会T；
• 考虑其实每一个点$id_i$，我们只需确定其和最左、右边界的点的相对关系即可，也就是在区间$[id_i-k+1,id_i),(id_i,id_i+k-1]$里的最小值，用线段树就可以解决了；
• 至于求映射字典序最小的拓扑序，就是反向建边，将队列换成priority_queue即可，我也不知道为啥。。。

代码

#include <cstdio>
#include <algorithm>
#include <climits>
#include <queue>
#include <cstring>
using std::min;
using std::priority_queue;
const int MAXN=500005;
int n,k;
int p[MAXN],id[MAXN];
int he[MAXN],inD[MAXN];
struct line{int to,nex;}ed[MAXN<<1];
class segT{
#define ls (u<<1)
#define rs (ls|1)
    private:
        int minw[MAXN<<2];
        void upd(int u){
            minw[u]=min(minw[ls],minw[rs]);
        }
        void ist(int u,int l,int r,int pos,int x){
            if(l==r){
                minw[u]=min(minw[u],x);
                return;
            }
            int mid=l+r>>1;
            if(pos<=mid) ist(ls,l,mid,pos,x);
            else ist(rs,mid+1,r,pos,x);
            upd(u);
        }
        int qry(int u,int l,int r,int lp,int rp){
            if(lp<=l && r<=rp) return minw[u];
            int mid=l+r>>1,ret=INT_MAX;
            if(lp<=mid) ret=qry(ls,l,mid,lp,rp);
            if(rp>mid) ret=min(ret,qry(rs,mid+1,r,lp,rp));
            return ret;
        }
    public:
        segT(){memset(minw,0x7f,sizeof(minw));}
        void ist(int pos,int x){ist(1,1,n,pos,x);}
        int qry(int lp,int rp){return qry(1,1,n,lp,rp);}
#undef ls
#undef rs
}T;
inline void addE(int u,int v){
    static int cnt;
    ed[++cnt]=(line){v,he[u]};
    he[u]=cnt;
}
inline void build(){
    for(int i=n,v;i;--i){
        v=T.qry(id[i]-k+1,id[i]);
        if(v<=n){
            addE(id[v],id[i]);
            ++inD[id[i]];
        }
        v=T.qry(id[i],id[i]+k-1);
        if(v<=n){
            addE(id[v],id[i]);
            ++inD[id[i]];
        }
        T.ist(id[i],i);
    }
}
inline void topo_sort(){
    static priority_queue<int> pq;
    for(int i=1;i<=n;++i){
        if(!inD[i]) pq.push(i);
    }
    for(int i=n,u;i;--i){
        u=id[i]=pq.top();
        pq.pop();
        for(int j=he[u],v;j;j=ed[j].nex){
            v=ed[j].to;
            if(--inD[v]==0) pq.push(v);
        }
    }
}
int main(){
    freopen("permutation.in","r",stdin);
    freopen("permutation.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)
        scanf("%d",&p[i]);
    for(int i=1;i<=n;++i)
        id[p[i]]=i;
    build();
    topo_sort();
    for(int i=1;i<=n;++i)
        p[id[i]]=i;
    for(int i=1;i<=n;++i)
        printf("%d\n",p[i]);
    return 0;
}

Tree

思路

• 这题很有意思。。。
• 依旧是个贪心，对于一条边，经过它对答案的贡献不大于它的边权；
• 那么对于一个点$u$，如果往上（往下一样）走，贡献最多是上面那条边的边权，那么我们就贪心的让它是好了；
• 也就是每个边的边权只在答案中贡献一次是最优的，因为如果有条边的边权贡献了不止一次，那一定是某个更大边权的边没有贡献上（可以反证）；
• 所以答案就是边权之和，这个说不太清，但是就是那个意思...

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
int main(){
    setIO("tree");
    int n;
    read(n);
    long long ans=0;
    for(int i=1,w;i<n;++i){
        scanf("%*d%*d%d",&w);
        ans+=w;
    }
    write(ans);
    return 0;
}