UESTC 2019 Summer Training #2 Div.2

比赛地址: https://vjudge.net/contest/309894

A – HihoCoder 1636

题目大意:给你若干堆石子,每次能把几堆石子合成一堆,这个几限定在L-R的范围内。问合成一堆的最小花费,如果合不成就输出-1

分析:这道题可以用DP来做。首先做前缀和sum表示合并l到r的代价。dp[i][j][k]表示第i堆到第j堆合成了k堆的代价。然后状态转移即可

代码:

#include <bits/stdc++.h>
using namespace std;
/////////////////////////
int dp[110][110][110];
int sum[110][110];
int a[110];
int n,l,r;
/////////////////////////
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    while(cin>>n>>l>>r)
    {
        memset(dp,0x3f,sizeof(dp));
        for(int i=1;i<=n;++i)
        {
            cin>>a[i];
        }
        for(int i=1;i<=n;++i)
        {
            sum[i][i-1]=0;
            for(int j=i;j<=n;++j)
            {
                sum[i][j]=sum[i][j-1]+a[j];
            }
        }
        for(int i=1;i<=n;++i)
        {
            for(int j=i;j<=n;++j)
            {
                dp[i][j][j-i+1]=0;
            }
        }
        for(int len=2;len<=n;++len)
        {
            for(int i=1,j=i+len-1;j<=n;++i,++j)
            {
                for(int p=i;p<j;++p)
                {
                    for(int k=1;k<=len;++k)
                    {
                        dp[i][j][k]=min(dp[i][j][k],dp[i][p][k-1]+dp[p+1][j][1]);
                        if(l<=k && k<=r)
                        {
                            dp[i][j][1]=min(dp[i][j][1],dp[i][j][k]+sum[i][j]);
                        }
                    }
                }
            }
        }
        if(dp[1][n][1]==INF)
        {
            cout<<0<<endl;
        }
        else
        {
            cout<<dp[1][n][1]<<endl;
        }
    }
    return 0;
}

F – HDU 6191

分析:这道题我用了树合并的方法。异或树的合并难度并不高。可以看出某个结点的结果,肯定包含他的子树,所以自然而然想到合并。

代码:

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <set>
#include <map>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INF64 = 3e18;
const unsigned long long HASHBASE=1222827239ull;
/////////////////////////
struct tree
{
    tree *next[2];
    tree(){next[1]=NULL;next[0]=NULL;}
};
struct node
{
    int id,u,x;
};
vector<int> g[200010];
int val[200010];
vector<node> qs[200010];
int ans[200010];
tree *root[200010];
int n,q;
void insert(int x,tree *rt)
{
    tree *myroot=rt;
    for(int i=30;i>=0;--i)
    {
        int p=(x>>i)&1;
        if(myroot->next[p]==NULL)
        {
            myroot->next[p]=new tree;
        }
        myroot=myroot->next[p];
    }
}
int query(int x,tree *rt)
{
    tree *myroot=rt;
    int ans=0;
    for(int i=30;i>=0;--i)
    {
        int p=(x>>i)&1;
        if(myroot->next[p^1]==NULL)
        {
            myroot=myroot->next[p];
        }
        else
        {
            ans+=(1<<i);
            myroot=myroot->next[p^1];
        }
    }
    return ans;
}
void deltree(tree *rt)
{
    if(rt->next[0]!=NULL) deltree(rt->next[0]);
    if(rt->next[1]!=NULL) deltree(rt->next[1]);
    delete rt;
}
tree *merge(tree *t1,tree *t2)
{
    if(t1==NULL) return t2;
    if(t2==NULL) return t1;
    t1->next[0]=merge(t1->next[0],t2->next[0]);
    t1->next[1]=merge(t1->next[1],t2->next[1]);
    delete t2;
    return t1;
}
void dfs(int u,int fa)
{
    root[u]=new tree;
    for(int i=0;i<g[u].size();++i)
    {
        int son=g[u][i];
        dfs(son,u);
        merge(root[u],root[son]);
    }
    insert(val[u],root[u]);
    for(int i=0;i<qs[u].size();++i)
    {
        ans[qs[u][i].id]=query(qs[u][i].x,root[u]);
    }
}
/////////////////////////
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    while(cin>>n>>q)
    {
        for(int i=1;i<=n;++i)
        {
            g[i].clear();
            qs[i].clear();
        }
        for(int i=1;i<=n;++i)
        {
            cin>>val[i];
        }
        int qwe,ewq;
        for(int i=2;i<=n;++i)
        {
            cin>>qwe;
            g[qwe].push_back(i);
        }
        for(int i=0;i<q;++i)
        {
            cin>>qwe>>ewq;
            qs[qwe].push_back(node{i,qwe,ewq});
        }
        dfs(1,-1);
        for(int i=0;i<q;++i)
        {
            cout<<ans[i]<<endl;
        }
        deltree(root[1]);
    }
    return 0;
}

G – ZOJ 4008

分析:这个是后面看了题解。就相当于求l到r中有多少个完整的线段。

代码:

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <set>
#include <map>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INF64 = 3e18;
const unsigned long long HASHBASE=1222827239ull;
/////////////////////////
int bit[200010],n,q,t,u,v,ans[200010];
inline int lowbit(int x)
{
    return x&-x;
}
void add(int x,int val)
{
    for(int i=x;i<=n;i+=lowbit(i))
        bit[i]+=val;
}
int sum(int x)
{
    int res=0;
    for(int i=x;i>0;i-=lowbit(i))
        res+=bit[i];
    return res;
}
struct seg
{
    int l,r,kind,id;
}segs[400010];
bool cmp(const seg &a,const seg &b)
{
    if(a.r==b.r)
        return a.kind<b.kind;
    else
        return a.r<b.r;
}
/////////////////////////
int main()
{
    //ios::sync_with_stdio(false); cin.tie(0);
    scanf("%d",&t);
    while(t--)
    {
        cin>>n>>q;
        for(int i=0;i<n-1;++i)
        {
            scanf("%d%d",&segs[i].l,&segs[i].r);
            if(segs[i].l>segs[i].r)
                swap(segs[i].l,segs[i].r);
            segs[i].kind=0;
        }
        for(int i=0;i<q;++i)
        {
            scanf("%d%d",&segs[i+n-1].l,&segs[i+n-1].r);
            if(segs[i+n-1].l>segs[i+n-1].r)
                swap(segs[i+n-1].l,segs[i+n-1].r);
            segs[i+n-1].kind=1;
            segs[i+n-1].id=i;
        }
        sort(segs,segs+n+q-1,cmp);
        memset(bit,0,sizeof(bit));
        u=0;
        for(int i=0;i<n+q-1;++i)
        {
            if(!segs[i].kind)
            {
                ++u;
                add(segs[i].l,1);
            }
            else
            {
                ans[segs[i].id]=(segs[i].r-segs[i].l+1) - (u - sum(segs[i].l-1));
            }
        }
        for(int i=0;i<q;++i)
        {
            printf("%d\n",ans[i]);
        }
    }
    return 0;
}

H – ZOJ 4009

分析:比赛时不懂写。后来才知道,模小数的情况,会有循环节。这道题的循环节是48,也就是立方48次就回到原来。所以只需要记住立方多少次就行了。后来和舍友讨论时,发现其实懒标记甚至不用清零(说不清楚),反正就是还能跑得更快。

代码:

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <set>
#include <map>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INF64 = 3e18;
const unsigned long long HASHBASE=1222827239ull;
/////////////////////////
long long sum[4*100010][50];
long long lazy[4*100010],status[4*100010];
long long a[100010],pre[100010];
void init()
{
    for(long long i=0;i<99971ll;++i)
    {
        pre[i]=i*i*i%99971ll;
    }
}
void pushup(long long v)
{
    for(long long i=0;i<48;++i)
    {
        sum[v][i]=(sum[2*v][(status[2*v]+i)%48]+sum[2*v+1][(status[2*v+1]+i)%48]) % 99971;
    }
    status[v]=0;
}
void pushdown(long long v)
{
    if(!lazy[v])return;
    lazy[2*v]+=lazy[v];
    lazy[2*v+1]+=lazy[v];
    status[2*v]=(status[2*v]+lazy[v])%48;
    status[2*v+1]=(status[2*v+1]+lazy[v])%48;
    lazy[v]=0;
}
void build(long long l,long long r,long long v)
{
    lazy[v]=status[v]=0;
    if(l==r)
    {
        sum[v][0]=a[l] % 99971;
        for(long long i=1;i<48;++i)
        {
            sum[v][i]=pre[ sum[v][i-1] ];
        }
        return;
    }
    long long m=(l+r)/2;
    build(l,m,2*v);
    build(m+1,r,2*v+1);
    pushup(v);
}
void update(long long l,long long r,long long lt,long long rt,long long v)
{
    if(lt<=l && r<=rt)
    {
        status[v] = (status[v]+1) % 48;
        ++lazy[v];
        return;
    }
    pushdown(v);
    long long m=(l+r)/2;
    if(lt<=m) update(l,m,lt,rt,2*v);
    if(rt>m) update(m+1,r,lt,rt,2*v+1);
    pushup(v);
}
long long query(long long l,long long r,long long lt,long long rt,long long v)
{
    if(lt<=l && r<=rt)
    {
        return sum[v][status[v]];
    }
    long long ans=0;
    pushdown(v);
    long long m=(l+r)/2;
    if(lt<=m) ans+=query(l,m,lt,rt,2*v);
    if(rt>m) ans+=query(m+1,r,lt,rt,2*v+1);
    pushup(v);
    return ans%99971;
}
long long t,n,q;
/////////////////////////
int main()
{
    //ios::sync_with_stdio(false); cin.tie(0);
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&q);
        for(long long i=1;i<=n;++i)
        {
            scanf("%d",a+i);
        }
        long long d1,d2,d3;
        build(1,n,1);
        for(long long i=0;i<q;++i)
        {
            scanf("%d%d%d",&d1,&d2,&d3);
            if(d1==1)
            {
                update(1,n,d2,d3,1);
            }
            else if(d1==2)
            {
                printf("%d\n",query(1,n,d2,d3,1));
            }
        }
    }
    return 0;
}

I – ZOJ 4006

分析:概率题,看题解才会写。反正就,数学公式推一推

代码:

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <set>
#include <map>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INF64 = 3e18;
const unsigned long long HASHBASE=1222827239ull;
const long long MODNUM=1000000007ll;
/////////////////////////
long long f[600010],p[600010];
long long extgcd(long long a, long long b, long long& x, long long& y)
{
    long long d = a;
    if (b != 0)
    {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }
    else
    {
        x = 1;y = 0;
    }
    return d;
}
long long mod_reverse(long long a,long long n)
{
    long long x,y;
    long long d=extgcd(a,n,x,y);
    if(d==1) return (x%n+n)%n;
    else return -1;
}
long long C(long long a,long long b)
{
    long long up=f[a];
    long long down=f[a-b]*f[b]%MODNUM;
    return up*mod_reverse(down,MODNUM)%MODNUM;
}
/////////////////////////
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    p[0]=f[0]=1ll;
    for(long long i=1;i<600010ll;++i)
    {
        p[i]=p[i-1]*2ll%MODNUM;
        f[i]=f[i-1]*i%MODNUM;
    }
    long long n,m,t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        long long ans=0;
        for(long long x=0;x<=n;++x)
        {
            long long y=n-x-m-x;
            long long z=m+x;
            if(y<0 || y>n) continue;
            if(z<0 || z>n) continue;
            long long up=C(n,x)*C(n-x,y)%MODNUM;
            long long down=p[2*(x+z)+y];
            ans=(ans+up*mod_reverse(down,MODNUM)%MODNUM)%MODNUM;
        }
        cout<<ans<<endl;
    }
    return 0;
}

J – ZOJ 4004

分析:显然大的乘小的,没了

代码:

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <set>
#include <map>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INF64 = 3e18;
const unsigned long long HASHBASE=1222827239ull;
/////////////////////////

/////////////////////////
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    long long t;
    cin>>t;
    while(t--)
    {
        long long n,m,a;
        cin>>n>>m;
        vector<long long> v;
        for(int i=0;i<n;++i)
        {
            cin>>a;
            v.push_back(a);
        }
        sort(v.begin(),v.end());
        long long sum=0;
        for(int i=0;i<m;++i)
        {
            sum+=v[i]*v[2*m-i-1];
        }
        cout<<sum<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注