十一黄(xun)金(lian)周感想

实际上并没有训整整一周-_-||

只训了三天

听说纪中全员没过节(ΩДΩ)好可怕

这三天考了5场模拟赛，一场初赛模拟

让我感觉我和开学时比起来还是有很大的提升的

最主要就是在dp方面。

经过整个九月疯狂的刷Vjudge和usaco月赛题目，我现在有种满脑子都是dp的感觉

然而因为在打牌的时候用dp所以输的很惨

十一期间的题目，我感觉质量略有参差，但是总体还是很棒(nan)的。

在这里放几道比较好（我没做出来）的

还教室

题意：给一段区间，每个数有一个值，每次可能有三种操作：更改一段值，询问一个区间的平均数和方差

题解：线段树显然，但是要构建两棵，而且要推导一下方差的公式

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

using namespace std;

const int N=1e5+;

#define m (l+r)/2

#define lson o<<1,l,m

#define rson o<<1|1,m+1,r

#define lc o<<1

#define rc o<<1|1

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,q,flag,l,r; ll d;

struct node{

    ll s,s2,mark;

}t[N<<];

inline void paint(int o,int l,int r,ll d){

    t[o].mark+=d;t[o].s2+=d*d*(r-l+)+*d*t[o].s;

    t[o].s+=d*(r-l+);

}

inline void merge(int o){

    t[o].s=t[lc].s+t[rc].s;

    t[o].s2=t[lc].s2+t[rc].s2;

}

inline void pushDown(int o,int l,int r){

    if(t[o].mark){

        ll d=t[o].mark;

        paint(lson,d);

        paint(rson,d);

        t[o].mark=;

    }

}

void build(int o,int l,int r){

    if(l==r) {ll a=read();t[o].s=a;t[o].s2=a*a;}

    else{

        build(lson);

        build(rson);

        merge(o);

    }

}

void add(int o,int l,int r,int ql,int qr,ll d){

    if(ql<=l&&r<=qr) paint(o,l,r,d);

    else{

        pushDown(o,l,r);

        if(ql<=m) add(lson,ql,qr,d);

        if(m<qr) add(rson,ql,qr,d);

        merge(o);

    }

}

ll query1(int o,int l,int r,int ql,int qr){

    if(ql<=l&&r<=qr) return t[o].s;

    else{

        pushDown(o,l,r);

        ll ans=;

        if(ql<=m) ans+=query1(lson,ql,qr);

        if(m<qr) ans+=query1(rson,ql,qr);

        return ans;

    }

}

ll query2(int o,int l,int r,int ql,int qr){

    if(ql<=l&&r<=qr) return t[o].s2;

    else{

        pushDown(o,l,r);

        ll ans=;

        if(ql<=m) ans+=query2(lson,ql,qr);

        if(m<qr) ans+=query2(rson,ql,qr);

        return ans;

    }

}

ll gcd(ll a,ll b){return b==?a:gcd(b,a%b);}////

void print(ll x,ll y){

    ll g=gcd(x,y);

    printf("%lld/%lld\n",x/g,y/g);

}

int main(){

    freopen("classroom.in","r",stdin);

    freopen("classroom.out","w",stdout);

    n=read();q=read();

    build(,,n);

    for(int i=;i<=q;i++){

        flag=read();l=read();r=read();

        if(flag==){d=read();add(,,n,l,r,d);}

        else if(flag==){

            ll x=query1(,,n,l,r),len=r-l+;

            print(x,len);

        }else{

            ll x1=query1(,,n,l,r),x2=query2(,,n,l,r),len=r-l+;//printf("hi %lld %lld\n",x1,x2);

            print(len*x2-x1*x1,len*len);

        }

    }

}

来自erickin的爱（-_-||）

题意：求一个图的最小生成树长度和个数，这个图中没有三个以上相等权值的边

题解：第一问kruskal

　　第二问，显然不同的最小生成树中每一种长度的边数量是一定的。所以我们只需要求得每个阶段的方案总数，累乘起来即可。对于每一条树边进行dfs，同时在第一问时记录每对点用了tot条边联通，dfs处理这个阶段的等价方案（即为联通所需的tot相等）

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const ll mod=1e9+;

struct ed{

    int k,w,next;

}e[];

struct edge{

    int x,y,w;

}E[];

bool cmp(edge a,edge b){

    return a.w<b.w;

}

int n,m,fa[];

int find(int *fa,int k){

    if(fa[k]!=k) fa[k]=find(fa,fa[k]);

    return fa[k];

}

int find1(int *fa,int k){

    while(fa[k]!=k) k=fa[k];

    return k;

}

int R,cnt,pos[],val;

void dfs(int k,int w){

    if(k==R){

        if(w==val)cnt++;

        return;

    }

    dfs(k+,w);

    int x=find(pos,E[k].x);

    int y=find(pos,E[k].y);

    if(find(pos,x)!=find(pos,y)){

        pos[x]=y;

        dfs(k+,w+);

        pos[x]=x;

    }

}

int main(){

    freopen("love.in","r",stdin);

    freopen("love.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++) scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].w);

    sort(E+,E+m+,cmp);

    ll ans=,sum=;

    for(int i=;i<=n;i++) fa[i]=i;

    for(int i=,p;i<=m;i=p){

        val=;

        for(p=i;p<=m&&E[p].w==E[i].w;p++){

            E[p].x=find(fa,E[p].x),E[p].y=find(fa,E[p].y);

            pos[E[p].x]=find(fa,E[p].x);

            pos[E[p].y]=find(fa,E[p].y);

        }

        for(int j=i;j<p;j++){

            int x=find(fa,E[j].x),y=find(fa,E[j].y);

            if(x!=y){

                ans+=E[j].w;

                val++;

                fa[x]=y;

            }

        }

        R=p;cnt=;

        dfs(i,);

        sum=sum*ll(cnt)%mod;

    }

    printf("%lld %lld",ans,sum);

    return ;

}

最后：曾老师的月饼真好吃\(^o^)/~

巴特西

十一黄(xun)金(lian)周感想

最新文章

热门文章