[CF 676B]Pyramid of Glasses

这题可以直接模拟,貌似也可过。但复杂度很高。

我们可以直接把t个单位的酒放入第一个杯,然后向下溢出,以此类推,这样复杂度就很优秀了。

代码:

#include <iostream>
using namespace std;
const int maxn=12;
int n;
long double k[maxn][maxn];
int call(int x){
	int i,ans=0;
	long double temp;
	if(x>n)
		return 0;
	for(i=1;i<=n;i++){
		if(k[x][i]>=1.0){
			ans++;
			if(k[x][i]>1.0 && x<n){
				temp=(k[x][i]-1.0)/2;
				k[x][i]=1.0;
				k[x+1][i]+=temp;
				k[x+1][i+1]+=temp;
			}
		}
	}
	return ans+call(x+1);
}
int main(){
	cin>>n>>k[1][1];
	cout<<call(1)<<endl;
	return 0;
}

[BZOJ 4152]The Captain

这题初看有些棘手。但是毕竟是最短路,[tex]min(abs(x_{1}-x_{2}),abs(y_{1}-y_{2}))[/tex]这样的边,大可以分成两条边来建,于是乎min就形同虚设了。并且我们可以看到这样建图有一个好处:跨越若干点的方案可以一定可以分成图上的若干边。问题大为简化,迎刃而解。

但这提有个丧病的地方:卡SPFA。加了一些优化照样挂。所以我一气之下写了可并堆优化的Dijkstra :)当然可并堆用的是pb_ds辣。

代码:

/**************************************************************
    Problem: 4152
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4888 ms
    Memory:17412 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <utility>
#include <ext/pb_ds/priority_queue.hpp>
#include <cctype>
#include <bitset>
#ifdef DEBUG
#include <cassert>
#endif
using namespace std;
const int maxn=200001;
int n;
inline int abs(int x){
    return x<0?-x:x;
}
  
int first[maxn];
int next[maxn*4],to[maxn*4],dist[maxn*4];
int graph_cnt=0;
inline void Add_Edge(int x,int y,int d){
    graph_cnt++;
    next[graph_cnt]=first[x];
    first[x]=graph_cnt;
    to[graph_cnt]=y;
    dist[graph_cnt]=d;
}
  
int d[maxn];
bitset<maxn> vis;
typedef pair<int,int> my_pair;
typedef __gnu_pbds::priority_queue<my_pair,greater<my_pair> > Heap;
Heap::point_iterator ite[maxn];
Heap Q;
int dij(){
    register int i,u;
    memset(d,0x7f,sizeof(d));
    d[1]=0;
    ite[1]=Q.push(make_pair(0,1));
    while(!Q.empty()){
        u=Q.top().second;
        Q.pop();
        if(vis[u])
            continue;
        vis[u]=true;
        for(i=first[u];i;i=next[i]){
            if(d[to[i]]>(dist[i]+d[u])){
                d[to[i]]=dist[i]+d[u];
                if(ite[to[i]]!=0)
                    Q.modify(ite[to[i]],make_pair(d[to[i]],to[i]));
                else
                    ite[to[i]]=Q.push(make_pair(d[to[i]],to[i]));
            }
        }
    }
    return d[n];
}
  
int pr[maxn][2];
int order1[maxn],order2[maxn];
int cmp1(const int i,const int j){
    return pr[i][0]<pr[j][0];
}
int cmp2(const int i,const int j){
    return pr[i][1]<pr[j][1];
}
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int main(){
    register int i;
    n=readint();
    for(i=1;i<=n;i++){
        pr[i][0]=readint();
        pr[i][1]=readint();
        order1[i]=i;
        order2[i]=i;
    }
    sort(order1+1,order1+1+n,cmp1);
    sort(order2+1,order2+1+n,cmp2);
    for(i=1;i<=n;i++){
        if(i!=1){
            Add_Edge(order1[i],order1[i-1],pr[order1[i]][0]-pr[order1[i-1]][0]);
            Add_Edge(order2[i],order2[i-1],pr[order2[i]][1]-pr[order2[i-1]][1]);
        }
        if(i!=n){
            Add_Edge(order1[i],order1[i+1],pr[order1[i+1]][0]-pr[order1[i]][0]);
            Add_Edge(order2[i],order2[i+1],pr[order2[i+1]][1]-pr[order2[i]][1]);
        }
    }
    printf("%d\n",dij());
    return 0;
}

[BZOJ 1756]小白逛公园

这题是很经典的线段树题。

我们可以发现最长子序列或跨越中点,或不跨越中点。若不跨越则肯定在左子或右子中,跨越则是左子最大后缀和和右子最大前缀和之和。问题便迎刃而解。(当然,求区间最大前缀/后缀和要用上区间和)

需注意此题可能会出现a>b!

代码:

/**************************************************************
    Problem: 1756
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2604 ms
    Memory:49648 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=500001;
struct Node{
    int L,R;
    int maxP,maxS,ans,sum;
};
Node Tree[maxn*4];
int A[maxn];
void merge(Node& O,Node& LC,Node& RC){
    O.sum=LC.sum+RC.sum;
    O.maxP=max(LC.maxP,LC.sum+RC.maxP);
    O.maxS=max(RC.maxS,RC.sum+LC.maxS);
    O.ans=max(max(LC.ans,RC.ans),LC.maxS+RC.maxP);
}
void maintain(int o){
    Node& O=Tree[o],LC=Tree[o<<1],RC=Tree[o<<1|1];
    merge(O,LC,RC);
}
void build_tree(int o,int L,int R){
    Node& O=Tree[o];
    O.L=L;
    O.R=R;
    if(L==R){
        O.maxP=O.maxS=O.ans=O.sum=A[L];
    }else{
        int M=L+(R-L)/2;
        build_tree(o<<1,L,M);
        build_tree(o<<1|1,M+1,R);
        maintain(o);
    }
}
void update(int o,int p,int v){
    Node& O=Tree[o];
    int& L=O.L,R=O.R;
    if(L==R){
        O.maxP=O.maxS=O.ans=O.sum=v;
    }else{
        int M=L+(R-L)/2;
        if(p<=M)
            update(o<<1,p,v);
        else
            update(o<<1|1,p,v);
        maintain(o);
    }
}
int ql,qr;
Node query(int o){
    Node& O=Tree[o];
    int& L=O.L,R=O.R;
    if(ql<=L && R<=qr){
        return Tree[o];
    }
    int M=L+(R-L)/2;
    Node ANS,LC,RC;
    if(ql<=M){
        LC=query(o<<1);
        if(qr>M){
            RC=query(o<<1|1);
            merge(ANS,LC,RC);
            return ANS;
        }else{
            return LC;
        }
    }else{
        RC=query(o<<1|1);
        return RC;
    }
}
int main(){
    int n,m;
    register int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%d",&A[i]);
    build_tree(1,1,n);
    int k,a,b;
    Node ans;
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&k,&a,&b);
        if(k&1){
            if(a>b)
                swap(a,b);
            ql=a;
            qr=b;
            ans=query(1);
            printf("%d\n",ans.ans);
        }else{
            update(1,a,b);
        }
    }
    return 0;
}

[BZOJ 2429]聪明的猴子

图论填坑中……

这题不难,直接造图搞MST(严格讲是最小瓶颈生成树)即可。比较感人的是,Kruskal竟然也能过……

代码:

/**************************************************************
    Problem: 2429
    User: danihao123
    Language: C++
    Result: Accepted
    Time:320 ms
    Memory:12592 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=1001,maxm=501;
int n;
struct Edge{
    int u,v,d;
    bool operator < (const Edge& x) const{
        return d<x.d;
    }
};
 
// DJoinst 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(){
    for(register int i=1;i<=n;i++)
        p[i]=i;
    // memset(rank,0,sizeof(rank));
}
 
// Kruskal
int m=0;
Edge E[maxn*maxn];
int MST(){
    register int i,ans,count=0;
    init_set();
    sort(E,E+m);
    for(i=0;i<m && count<=(n-1);i++){
        if(!is_same(E[i].u,E[i].v)){
            union_set(E[i].u,E[i].v);
            ans=E[i].d;
            count++;
        }
    }
    return ans;
}
 
int MK[maxm],Tree[maxn][2];
int main(){
    int monkey;
    register int i,j,sd,ans=0;
    scanf("%d",&monkey);
    for(i=1;i<=monkey;i++)
        scanf("%d",&MK[i]);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&Tree[i][0],&Tree[i][1]);
    for(i=1;i<=n;i++){
        for(j=i+1;j<=n;j++){
            E[m].u=i;
            E[m].v=j;
            E[m].d=hypot(abs(Tree[i][0]-Tree[j][0]),abs(Tree[i][1]-Tree[j][1]));
            m++;
        }
    }
    sd=MST();
    for(i=1;i<=monkey;i++)
        if(MK[i]>=sd)
            ans++;
    printf("%d\n",ans);
    return 0;
}

[BZOJ 3713]Iloczyn

这题应该注意到,斐波纳契函数增长速度很快,[tex]10^9[/tex]以下的斐波纳契函数值很少,所以可以打表。这样,问题就迎刃而解了。

代码:

/**************************************************************
    Problem: 3713
    User: danihao123
    Language: C++
    Result: Accepted
    Time:20 ms
    Memory:828 kb
****************************************************************/
 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int fib[46]={0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170};
bool check(int n){
    int m=sqrt(0.5+n);
    if(binary_search(fib,fib+46,n))
        return true;
    register int i;
    for(i=2;i<=m;i++){
        if(!(n%i) && binary_search(fib,fib+46,i)){
            if(binary_search(fib,fib+46,n/i))
                return true;
        }
    }
    return false;
}
int main(){
    int T,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        if(check(n))
            puts("TAK");
        else
            puts("NIE");
    }
    return 0;
}

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