[SZKOpuł sol][POI2009]Elephants

aji波兰题！（直球）

这个题显然就是对那个排列乘上一个置换，然后置换的每一个循环事独立的，于是分别考虑每一个循环。

然后每一个循环有一种显然的构造方法就是从一个点开始，逆着边不停的交换两个点。这样的话有一个点会对答案做\(s - 1\)次贡献（\(s\)为循环大小），其他点都会只做一次循环。显然那个点选权值最小的点事坠吼的。

还有一种构造就是把全局最小值和循环最小值换一下，然后用上面的手段构造，最后再把全局最小值和循环最小值换回来。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
const int maxn = 1000005;
int next[maxn];

using ll = long long;
ll m[maxn];
int A[maxn], B[maxn], ma[maxn];
bool vis[maxn];

int main() {
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &m[i]);
  }
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &A[i]); ma[A[i]] = i;
  }
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &B[i]);
    next[ma[B[i]]] = i;
  }
  ll ans = 0LL; ll tv = *std::min_element(m + 1, m + 1 + n);
  for(int i = 1; i <= n; i ++) {
    if(next[i] != i && !vis[i]) {
      int p = i; ll sumv = 0LL, minv = 0x7fffffffLL;
      ll cnt = 0;
      do {
        vis[p] = true; cnt ++;
        sumv += m[A[p]]; minv = std::min(minv, m[A[p]]);
        p = next[p];
      } while(p != i);
      ll delta = sumv + std::min(minv * (cnt - 2LL), minv + tv * (cnt + 1LL));
      ans += delta;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

题解 SZKOpuł POI 置换 贪心 Comments(0) 2018年6月25日 17:45

[BZOJ 3252]攻略

近期心情不顺，坑了一堆没写的题解……（嗯我反演等回来再填坑吧（逃

好了还是说说这题吧，私以为鄙人的做法还是蛮妙的：

定义\(d(x)\)表示\(x\)到根上所有点的权值和，\(d_{max}(x)\)为\(x\)所在的子树中所有点的\(d(x)\)的最大值。对一个结点，他的所有儿子中\(d_{max}(x)\)最大的称为重儿子，其他作为轻儿子，然后做一遍树剖。然后将所有重链的权值和扔到一个数组里，降序排序，选前\(k\)大求和即可（不够的话全选）。

为什么？

显然，尽可能选叶子是划算的。然后，任意一条重链链顶的父亲所在的重链的权值和必定大于该重链，所以说不必担心某个重链选了而他的祖先却没有被记到答案里的情况。而若干这种重链的并，恰好对应了若干条到叶子路径的并。由于我们还是从大到小选的，所以答案是最优的。

继续阅读

题解 贪心 bzoj 树链剖分 Comments(1) 2017年11月27日 13:24

[COGS 396]魔术球问题（简化版）

这简化的真彻底……变成一个贪心水体了……

枚举柱子数，然后每次尽可能放球，放不了球了增加柱子，增加不了了就是最优解：

代码：

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int maxn=61;
vector<int> V[maxn];
inline bool isSqr(int x){
    register int temp=floor(sqrt(x));
    return temp*temp==x;
}
int main(){
    int n,temp;
    bool flag;
    register int i,j,ans=1;
    freopen("balla.in","r",stdin);
    freopen("balla.out","w+",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        while(true){
            flag=false;
            for(j=0;j<i;j++){
                if(V[j].empty() || isSqr(V[j].back()+ans)){
                    V[j].push_back(ans++);
                    flag=true;
                    break;
                }
            }
            if(!flag)
                break;
        }
    }
    printf("%d\n",ans-1);
    return 0;
}

题解 COGS 贪心 Comments(0) 2016年8月27日 22:55

[BZOJ 4326]运输计划

很容易想到树剖直接搞一发的玩法。估计复杂度是[tex]O(nlog^2n)[/tex]的，有点吃不消，再加上会被卡常，咔嚓掉。

考虑二分答案。我们可以直接二分最终答案，那么如何验证？

假设验证谓词为[tex]C(t)[/tex]，表示通过把一条边清零可以使得用时为[tex]t[/tex]。那么所有用时大于[tex]t[/tex]的计划都要被清掉一条边。可见我们需要清零的边是所有用时大于[tex]t[/tex]的计划的边的交集中的最大边。

那么如何求交集呢？可以考虑树上差分，对于每次计划[tex](u,v)[/tex]，我们求出其最近公共祖先[tex]L[/tex]，然后对[tex]d[u][/tex]和[tex]d[v][/tex]分别加一，对[tex]d[L][/tex]则减二。随后将d上标记上推，可以求出每个点连向父亲的边被几个计划经过。易求交集。

至此方向已明确：二分答案，树上差分验证，同时我们还要用到LCA。LCA建议使用总计[tex]O(n)[/tex]的TarjanLCA离线算法，倍增也可。

代码：

/**************************************************************
    Problem: 4326
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4756 ms
    Memory:62188 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=300001,maxm=300001*2;
const int BUFSIZE=10000001;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
 
int n;
namespace FastIO{
    char buf[BUFSIZE];
    int IO_tot=0;
    inline void InitFastIO(){
        fread(buf,sizeof(char),BUFSIZE-1,stdin);
    }
    inline char GetC(){
        return buf[IO_tot++];
    }
    inline int readint(){
        register int x=0;
        register char c=GetC();
        while(!isdigit(c))
            c=GetC();
        while(isdigit(c)){
            x=10*x+c-'0';
            c=GetC();
        }
        return x;
    }
    int bf[10];
    inline void putint(int x){
        register int siz=0,i;
        if(!x){
            bf[siz++]=0;
        }else{
            while(x){
                bf[siz++]=x%10;
                x/=10;
            }
        }
        for(i=siz-1;i>=0;i--)
            putchar(bf[i]+'0');
        putchar('\n');
    }
};
namespace Tree{
    int first[maxn];
    int next[maxm],to[maxm],dist[maxm];
    int tot=0;
    inline void Add_Edge(int u,int v,int d){
        tot++;
        next[tot]=first[u];
        first[u]=tot;
        to[tot]=v;
        dist[tot]=d;
    }
    int d[maxn],father[maxn];
    vector<int> hx;
    void dfs_1(int x,int fa,int dis){
        d[x]=dis;
        father[x]=fa;
        int i;
        GRAPH_REP(i,x){
            if(to[i]!=fa)
                dfs_1(to[i],x,dis+dist[i]);
        }
        hx.push_back(x);
    }
    int lazy[maxn];
    inline void ClearLazy(){
        memset(lazy,0,sizeof(lazy));
    }
    inline int DealCheck(int x){
        register int i,v,ans=0;
        REP_B(i,n){
            v=hx[i-1];
            lazy[father[v]]+=lazy[v];
        }
        REP_B(i,n){
            if(lazy[i]==x){
                ans=max(ans,d[i]-d[father[i]]);
            }
        }
        return ans;
    }
     
    // Djoin Set
    int p[maxn];
    int find_set(int x){
        if(p[x]==x)
            return x;
        else
            return p[x]=find_set(p[x]);
    }
    inline void union_set(int x,int y){
        p[find_set(y)]=find_set(x);
    }
    inline void make_set(int x){
        p[x]=x;
    }
     
    // LCA
    struct Query{
        int u,v,b;
    };
    bool vis[maxn];
    vector<Query> qs;
    vector<int> querys[maxn];
    inline void Add_Query(int x,int y,int b){
        querys[x].push_back(qs.size());
        qs.push_back((Query){x,y,b});
    }
    int res[maxn][3];
    int n;
    void LCA(int u){
        make_set(u);
        vis[u]=true;
        int i,temp;
        REP(i,querys[u].size()){
            Query& tep=qs[querys[u][i]];
            if(vis[tep.v])
                res[tep.b][2]=find_set(tep.v);
        }
        for(i=first[u];i;i=next[i]){
            temp=to[i];
            if(!vis[temp]){
                LCA(temp);
                union_set(u,temp);
            }
        }
    }
};
 
using namespace FastIO;
struct Deal{
    int u,v,lca,d;
    bool operator <(const Deal& x) const{
        return d<x.d;
    }
};
vector<Deal> V;
int m;
inline bool Check(int x){
    register int i,ideal=0,yh=V[m-1].d;
    Tree::ClearLazy();
    for(i=m-1;i>=0;i--){
        int& u=V[i].u,v=V[i].v,lca=V[i].lca,d=V[i].d;
        if(d>x){
            ideal++;
            Tree::lazy[u]++;
            Tree::lazy[v]++;
            Tree::lazy[lca]-=2;
        }else{
            break;
        }
    }
    yh-=Tree::DealCheck(ideal);
    return yh<=x;
}
int main(){
    register int i,u,v,lca,d;
    FastIO::InitFastIO();
    n=readint();
    m=readint();
    REP(i,n-1){
        u=readint();
        v=readint();
        d=readint();
        Tree::Add_Edge(u,v,d);
        Tree::Add_Edge(v,u,d);
    }
    REP(i,m){
        u=readint();
        v=readint();
        Tree::Add_Query(u,v,i);
        Tree::Add_Query(v,u,i);
        Tree::res[i][0]=u;
        Tree::res[i][1]=v;
    }
    Tree::dfs_1(1,0,0);
    Tree::LCA(1);
    REP(i,m){
        u=Tree::res[i][0];
        v=Tree::res[i][1];
        lca=Tree::res[i][2];
        d=Tree::d[u]+Tree::d[v]-2*Tree::d[lca];
        V.push_back((Deal){u,v,lca,d});
    }
    sort(V.begin(),V.end());
    u=0;
    v=V[m-1].d+1;
    while(u<v){
        d=u+(v-u)/2;
        if(Check(d))
            v=d;
        else
            u=d+1;
    }
    putint(u);
    return 0;
}

题解 二分 贪心 NOIP bzoj 树上差分 二分答案 TarjanLCA算法 Comments(0) 2016年8月26日 15:49

[BZOJ 1029]建筑抢修

废了。

我彻底废了。

就一个贪心水体。按截止时间排序然后遍历，当前花时间能干完就干，不能的话看能不能把更劣的选择换。仅此而已。

代码：

/**************************************************************
    Problem: 1029
    User: danihao123
    Language: C++
    Result: Accepted
    Time:396 ms
    Memory:2764 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
const int maxn=150001;
struct Node{
    int a,b;
    bool operator <(const Node& x) const{
        return b<x.b;
    }
    bool operator >(const Node& x) const{
        return b>x.b;
    }
};
Node T[maxn];
priority_queue<ll> Q;
int main(){
    int n;
    register int i,ans=0;
    register ll cur=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&T[i].a,&T[i].b);
    sort(T+1,T+1+n);
    for(i=1;i<=n;i++){
        if(cur+T[i].a<=T[i].b){
            cur+=T[i].a;
            Q.push(T[i].a);
        }else{
            if(Q.size() && Q.top()>T[i].a){
                cur-=Q.top();
                Q.pop();
                cur+=T[i].a;
                Q.push(T[i].a);
            }
        }
    }
    printf("%d\n",Q.size());
    return 0;
}

题解 BZOJ JSOI 省选 贪心 堆 排序 Comments(1) 2016年8月25日 09:54

[BZOJ 1034]泡泡堂

这题其实就是一个田忌赛马类问题。贪心即可。

如果你不知道田忌赛马怎么贪，可以看《骗分导论》相关介绍（然而那个贪心不是骗分算法哦）。

代码：

/**************************************************************
    Problem: 1034
    User: danihao123
    Language: C++
    Result: Accepted
    Time:256 ms
    Memory:1604 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=100001;
int a[maxn],b[maxn];
int n;
inline int solve(int *A,int *B){
    register int L1=1,R1=n,L2=1,R2=n,ans=0;
    while(L1<=R1 && L2<=R2){
        if(A[L1]>B[L2]){
            ans+=2;
            L1++;
            L2++;
        }else{
            if(A[R1]>B[R2]){
                ans+=2;
                R1--;
                R2--;
            }else{
                if(A[L1]==B[R2])
                    ans++;
                L1++;
                R2--;
            }
        }
    }
    return ans;
}
int main(){
    register int i,ans;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
        scanf("%d",&b[i]);
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    printf("%d %d\n",solve(a,b),2*n-solve(b,a));
    return 0;
}

题解 BZOJ ZJOI 省选 贪心 Comments(1) 2016年8月24日 20:38

[CodeVS 3289]花匠

这破题吃枣药丸……

这题略加思索，就能发现最优策略是找转折点。但需要注意相等连块中也会存在转折点……并且，n<3时不要搬走花！

代码：

#include <cstdio>
const int maxn=100001;
int A[maxn];
int main(){
    int n;
    bool flag=false,tal;
    register int i,ans=0;
    scanf("%d",&n);
    if(n<3){
        printf("%d\n",n);
        return 0;
    }
    for(i=1;i<=n;i++){
        scanf("%d",&A[i]);
    }
    for(i=1;i<=n;i++){
        if(i==1){
            ans++;
            continue;
        }
        if(A[i]!=A[i-1])
            flag=true;
        if(i==n){
            if(flag)
                ans++;
            break;
        }
        if(A[i]==A[i-1] && i>=2)
            A[i-1]=A[i-2];
        if((A[i]>A[i-1] && A[i]>A[i+1]) ||
           (A[i]<A[i-1] && A[i]<A[i+1]))
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}

题解 codevs 贪心 Comments(2) 2016年7月15日 20:15