题解 - danihao123's Blog - 大蒟蒻zzs的博客

[BZOJ3043]IncDec Sequence

这题并不很好下手，但注意差分序列的前缀和为原值这个性质。

由此可见，所求数列的差分序列除了第一项以外都应该是0，求出满足条件的最小操作次数就轻松多了。

求满足条件的数列个数似乎也不是难事。通过差分序列易推数列第一项差分值的范围，突破口就在于此。

看起来，满足条件数列个数为[tex]max(S1,S2)-min(S1,S2)[/tex]（S1，S2分别为正、负差分绝对值的和）。但是请注意，存在第一项没被操作的特殊情况。并且精度也是个问题！

/**************************************************************
    Problem: 3043
    User: danihao123
    Language: C++
    Result: Accepted
    Time:292 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    int n;
    long long last=0,temp;
    register long long S1=0,S2=0,i,cf,ans2;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%llu",&temp);
        cf=temp-last;
        if(i!=1){
            if(cf>0)
                S1+=cf;
            else
                S2-=cf;
        }
        last=temp;
    }
    ans2=max(S1,S2)-min(S1,S2)+1;
    printf("%llu\n%llu\n",max(S1,S2),ans2);
    return 0;
}

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

[BZOJ 1682]干草危机

这道题就是求最小瓶颈生成树中边的最大值。

然而图的MST就是图的一个最小瓶颈生成树……这下问题就迎刃而解了。

代码：

/**************************************************************
    Problem: 1682
    User: danihao123
    Language: C++
    Result: Accepted
    Time:44 ms
    Memory:940 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<n;i++)
#define REPB(i,n) for(i=1;i<=n;i++)
#define FROMG_TO E[i].u,E[i].v
const int maxn=2001,maxm=10001;
int n,m;
// Djoint set
int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
void link_set(int x,int y){
    if(rank[x]>rank[y]){
        p[y]=x;
    }else{
        p[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}
inline void union_set(int x,int y){
    link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
inline void init_set(){
    register int i;
    for(i=1;i<=n;i++)
        p[i]=i;
    // memset(rank,0,sizeof(rank));
}
// Graph
struct Edge{
    int u,v,d;
};
int cmp(const Edge& a,const Edge& b){
    return a.d<b.d;
}
Edge E[maxm];
int mst(){
    register int i,cnt=0,ans=0;
    init_set();
    sort(E,E+m,cmp);
    for(i=0;cnt<(n-1) && i<m;i++){
        if(!is_same(FROMG_TO)){
            union_set(FROMG_TO);
            ans=max(ans,E[i].d);
            cnt++;
        }
    }
    return ans;
}
int main(){
    register int i;
    scanf("%d%d",&n,&m);
    REP(i,m){
        scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
    }
    printf("%d\n",mst());
    return 0;
}

[BZOJ 1232]安慰奶牛

这题要用到DFS欧拉遍历树（胡编词汇）的一个特征：每一条边都经过2遍。这样似乎每个边度数就可以确定了，然后……

但是，起点也要算啊……

代码：

/**************************************************************
    Problem: 1232
    User: danihao123
    Language: C++
    Result: Accepted
    Time:248 ms
    Memory:2056 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10001,maxm=100001;
// Djoin set
int p[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
void union_set(int x,int y){
    p[find_set(x)]=find_set(y);
}
bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
// Graph
struct Edge{
    int u,v,d;
};
int cmp(const Edge& a,const Edge& b){
    return a.d<b.d;
}
int n,m;
int c[maxn];
Edge E[maxm];
int mst(){
    register int i,cnt=0,ans=0;
    for(i=1;i<=n;i++)
        p[i]=i;
    sort(E,E+m,cmp);
    for(i=0;cnt<(n-1) && i<m;i++){
        if(!is_same(E[i].u,E[i].v)){
            union_set(E[i].u,E[i].v);
            ans+=E[i].d;
            cnt++;
        }
    }
    return ans;
}
int main(){
    register int i,kkk=0x5fffffff;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&c[i]);
        kkk=min(kkk,c[i]);
    }
    for(i=0;i<m;i++){
        scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
        E[i].d+=E[i].d+c[E[i].u]+c[E[i].v];
    }
    printf("%d\n",kkk+mst());
    return 0;
}

[BZOJ 1603]打谷机

啊啊啊啊我又活过来了……

然而这也就是一道脑残题……

代码：

/**************************************************************
    Problem: 1603
    User: danihao123
    Language: C++
    Result: Accepted
    Time:20 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1001;
struct Edge{
    int u,v;
    bool type;
};
vector<Edge> edges;
vector<int> G[maxn];
void Add_Edge(int u,int v,bool type){
    edges.push_back((Edge){u,v,type});
    G[u].push_back(edges.size()-1);
}
bool ans[maxn],vis[maxn];
void dfs(int x){
    vis[x]=true;
    int i;
    for(i=0;i<G[x].size();i++){
        Edge& e=edges[G[x][i]];
        if(!vis[e.v]){
            ans[e.v]=e.type?(!ans[x]):ans[x];
            dfs(e.v);
        }
    }
}
int main(){
    register int i;
    int n,u,v,d;
    scanf("%d",&n);
    for(i=0;i<(n-1);i++){
        scanf("%d%d%d",&u,&v,&d);
        Add_Edge(u,v,(bool)d);
        Add_Edge(v,u,(bool)d);
    }
    dfs(1);
    printf("%d\n",ans[n]?1:0);
    return 0;
}