codeforces#326(div2)

codeforces#326(div2)

A题：水题。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn=1000100;
const int INF=(1<<29);

int n,a,p;

int main()
{
    while(cin>>n){
        int m=INF,ans=0;
        while(n--){
            scanf("%d%d",&a,&p);
            m=min(p,m);
            ans+=m*a;
        }
        cout<<ans<<endl;
    }
    return 0;
}

B题：水题。

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

typedef long long ll;
const int maxn=10001000;
const int INF=(1<<29);

ll n;
vector<int> prime;
bool isprime[maxn];

void getPrime()
{
    memset(isprime,1,sizeof(isprime));
    isprime[1]=0;
    REP(i,2,maxn-1){
        if(!isprime[i]) continue;
        for(int j=i+i;j<maxn;j+=i) isprime[j]=0;
    }
    REP(i,2,maxn-1) if(isprime[i]) prime.push_back(i);
    //REP(i,1,10) cout<<prime[i]<<" ";cout<<endl;
}

ll jud(ll n)
{
    for(int i=0;i<prime.size();i++){
        ll t=prime[i];
        if(t*t>n) break;
        while(n%(t*t)==0) n/=t;
    }
    return n;
}

int main()
{
    getPrime();
    while(cin>>n){
        cout<<jud(n)<<endl;
    }
}

C题：水题。

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))
using namespace std;

typedef long long ll;
const int maxn=2000100;
const int INF=(1<<29);

int n;
int a[maxn];
ll cnt[maxn];

int main()
{
    while(cin>>n){
        REP(i,1,n) scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        MS0(cnt);
        REP(i,1,n) cnt[a[i]]++;
        REP(i,0,maxn-2){
            while(cnt[i]/2){
                cnt[i+1]+=cnt[i]/2;
                cnt[i]%=2;
            }
        }
        ll ans=0;
        REP(i,0,maxn-2) ans+=cnt[i];
        printf("%I64d
",ans);
    }
    return 0;
}

E题：

求一颗数路径上最小的k个值，每个结点有多个值，有的结点没有值。

树剖+线段树。由于k<=10,每个结点维护一个长度为10的数组，然后合并的时候按归并排那样合并就行了。

比赛的时候被卡常数FST了。。。还是自己写合并的时候太懒，合并两个数组直接排序就交了，赛后改成按归并排那样的合并就过了。。。本来完全可以打到前50的。。。。居然多了个log20的常数FST了。。。不服不服！

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

using namespace std;

typedef long long ll;
const int maxn=100100;
const int INF=(1<<29);

int n,m,q;
int u,v,a;
int c[maxn];
int k,p[maxn];
struct SegTree
{
    int val[11];
};SegTree T[maxn<<2];
vector<int> G[maxn];
int dep[maxn],son[maxn],fa[maxn],siz[maxn];
int top[maxn];
int id[maxn];
int num;

void dfs1(int u,int f,int d)
{
    fa[u]=f;
    dep[u]=d;
    son[u]=0;
    siz[u]=1;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==f) continue;
        dfs1(v,u,d+1);
        if(siz[v]>siz[son[u]]) son[u]=v;
        siz[u]+=siz[v];
    }
}

void dfs2(int u,int tp)
{
    top[u]=tp;
    id[u]=++num;
    if(son[u]) dfs2(son[u],tp);
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}

SegTree Min(SegTree A,SegTree B)
{
    SegTree res;
    REP(i,0,10) res.val[i]=INF;
    int i=0,j=0,k=0;
    while(k<11){
        if(A.val[i]<B.val[j]) res.val[k++]=A.val[i++];
        else res.val[k++]=B.val[j++];
    }
    return res;
}

void push_up(int rt)
{
    T[rt]=Min(T[rt<<1],T[rt<<1|1]);
}

void build(int l,int r,int rt)
{
    REP(i,0,10) T[rt].val[i]=INF;
    if(l==r) return;
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    push_up(rt);
}

void update(int p,int x,int l,int r,int rt)
{
    if(l==r){
        REP(i,0,10){
            if(T[rt].val[i]>x){
                T[rt].val[i]=x;
                return;
            }
        }
        return;
    }
    int m=(l+r)>>1;
    if(p<=m) update(p,x,lson);
    else update(p,x,rson);
    push_up(rt);
}

void change(int u,int x)
{
    update(id[u],x,1,num,1);
}

SegTree Seg_INF;

SegTree query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R) return T[rt];
    int m=(l+r)>>1;
    SegTree res=Seg_INF;
    if(L<=m) res=Min(res,query(L,R,lson));
    if(R>m) res=Min(res,query(L,R,rson));
    return res;
}

SegTree cha(int u,int v)
{
    SegTree res=Seg_INF;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        res=Min(res,query(id[top[u]],id[u],1,num,1));
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    res=Min(res,query(id[u],id[v],1,num,1));
    return res;
}

int main()
{
    freopen("in.txt","r",stdin);
    REP(i,0,10) Seg_INF.val[i]=INF;
    while(cin>>n>>m>>q){
        REP(i,0,n) G[i].clear();
        REP(i,1,n-1){
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        num=0;
        dfs1(1,0,1);
        dfs2(1,1);
        build(1,num,1);
        REP(i,1,m){
            scanf("%d",&c[i]);
            change(c[i],i);
        }
        while(q--){
            scanf("%d%d%d",&u,&v,&a);
            SegTree ans=cha(u,v);
            k=0;
            REP(i,0,a-1){
                if(ans.val[i]==INF) break;
                else k++;
            }
            printf("%d ",k);
            REP(i,0,k-1){
                if(i!=k-1) printf("%d ",ans.val[i]);
                else printf("%d",ans.val[i]);
            }
            puts("");
        }
    }
    return 0;
}

D题题意看了半天没看懂，待补充。。。

E题太可惜了，看来以后写树剖一定要注意常数，主要在结点的维护和合并上优化。