danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

26244

[CodeVS 1098]均分纸牌

2016年9月11日 10:44 | Comments(0) | Category:题解 | Tags:

很妙的一个贪心啊……

根据题意,易求平均值。然后每个数减去平均值表示这个数和平均数的“差异”。然后呢?如果每个数的差异值不为0,就直接摊给下一堆。

这种做法最大的精髓在于,即使差异值为负,也能摊给下一堆,从而避免了各种复杂操作。

代码:

#include <iostream>
using namespace std;
const int maxn=105;
int A[maxn];
int main(){
	register int i,sum=0,ans=0;
	int n;
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>A[i];
		sum+=A[i];
	}
	sum/=n;
	for(i=1;i<=n;i++){
		A[i]-=sum;
	}
	for(i=1;i<=n;i++){
		if(A[i]!=0){
			ans++;
			A[i+1]+=A[i];
			A[i]=0;
		}
	}
	cout<<ans<<endl;
	return 0;
}

[BZOJ 1217]消防局的设立

2016年9月10日 19:36 | Comments(0) | Category:题解 | Tags:

很明显可以看出消防局距离为5的话最划算……然后贪心就行了,顺便注意下根节点处理

代码:

/**************************************************************
    Problem: 1217
    User: danihao123
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:844 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1010;
#define GRAPH_REP(i,u) for(i=first[u];i;i=next[i])
int first[maxn];
int next[maxn*2],to[maxn*2];
int graph_cnt=0;
inline void AddEdge(int u,int v){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
}
 
int ans=0;
int d[maxn];
void dfs(int x,int fa=-1){
    int maxq=-maxn,minq=maxn;
    int i;
    GRAPH_REP(i,x)
        if(to[i]!=fa){
            dfs(to[i],x);
            maxq=max(maxq,d[to[i]]);
            minq=min(minq,d[to[i]]);
        }
    if(minq+maxq<=3)
        d[x]=minq+1;
    else
        d[x]=maxq+1;
    if(minq==maxn)
        d[x]=3;
    if(d[x]==5){
        ans++;
        d[x]=0;
    }else{
        if(fa==-1 && d[x]>2)
            ans++;
    }
}
 
int main(){
    int n,v;
    register int i;
    scanf("%d",&n);
    for(i=1;i<=(n-1);i++){
        scanf("%d",&v);
        AddEdge(i+1,v);
        AddEdge(v,i+1);
    }
    dfs(1);
    printf("%d\n",ans);
    return 0;
}

[COGS 396]魔术球问题(简化版)

2016年8月27日 22:55 | Comments(0) | Category:题解 | Tags:

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

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

代码:

#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;
}

[BZOJ 4326]运输计划

2016年8月26日 15:49 | Comments(0) | Category:题解 | Tags:

很容易想到树剖直接搞一发的玩法。估计复杂度是[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;
}

[BZOJ 1029]建筑抢修

2016年8月25日 09:54 | Comments(0) | Category:题解 | Tags:

废了。

我彻底废了。

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

代码:

/**************************************************************
    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 1034]泡泡堂

2016年8月24日 20:38 | Comments(0) | Category:题解 | Tags:

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

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

代码:

/**************************************************************
    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;
}

[CodeVS 1214]线段覆盖

2016年8月11日 17:02 | Comments(0) | Category:题解 | Tags:

此题是朴素的线段覆盖问题,直接按照右端点排序并贪心即可。

需注意可能会有l>r的情况!

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=101;
struct Line{
	int l,r;
	bool operator <(const Line& x) const{
		return r<x.r;
	}
};
Line LP[maxn];
int main(){
	register int i,last=-1001,ans=0;
	int n;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d",&LP[i].l,&LP[i].r);
		if(LP[i].l>LP[i].r)
			swap(LP[i].l,LP[i].r);
	}
	sort(LP+1,LP+1+n);
	for(i=1;i<=n;i++){
		if(LP[i].l>=last){
			ans++;
			last=LP[i].r;
		}
	}
	printf("%d\n",ans);
	return 0;
}

[CodeVS 3168]抄书问题 3

2016年8月06日 17:40 | Comments(0) | Category:题解 | Tags:

二分答案处女作,嗯……

这题没啥好说的……二分答案+贪心判定。注意最后输出的时候不能一味贪心,否则区间数可能小于k!

代码:

#include <cstdio>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1000001;
int n;
ll A[maxn];
bool hf(int k,int x){
    register int i,d=1;
    register ll ans=0;
    for(i=1;i<=n;i++){
        if(ans+A[i]>x){
            d++;
            ans=A[i];
        }else{
            ans+=A[i];
        }
    }
    return d<=k;
}
vector<pii> as;
void print(int k,int x){
    register int i,kr=k,l=n,r=n;
    register ll cnt=0;
    for(i=n;i>=1;i--){
        if(cnt+A[i]>x || i<kr){
            l=i+1;
            kr--;
            as.push_back(make_pair(l,r));
            cnt=A[i];
            l=i;
            r=i;
        }else{
            l=i;
            cnt+=A[i];
        }
    }
    as.push_back(make_pair(l,r));
    for(i=as.size()-1;i>=0;i--)
        printf("%d %d\n",as[i].first,as[i].second);
}
int main(){
    register int i,k;
    register ll L=-1,R=0,M;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++){
        scanf("%lld",&A[i]);
        R+=A[i];
        L=max(L,A[i]);
    }
    if(R<=1)
        R=2;
    while(R>L){
        M=L+(R-L)/2;
        if(hf(k,M))
            R=M;
        else
            L=M+1;
    }
    print(k,L);
    return 0;
}

[CodeVS 3289]花匠

2016年7月15日 20:15 | Comments(0) | Category:题解 | Tags:

这破题吃枣药丸……

这题略加思索,就能发现最优策略是找转折点。但需要注意相等连块中也会存在转折点……并且,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;
}