免费送气球

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 566 Accepted Submission(s): 129

Problem Description

又到了GDUT一年一度的程序设计竞赛校赛的时间啦。同学们只要参加校赛，并且每解出一道题目就可以免费获得由ACM协会和集训队送出的气球一个。听到这个消息，JMC也想参加免费拿气球。可是，由于JMC太菜了而被禁止参赛，于是他找到你想让你帮忙参加比赛，可以通过执行下面的C++程序解决问题后获得气球并送给他。JMC保证了下面的程序一定能获得正确的结果。

void solve(int Q, int type[], long long first[], long long second[]) {
    vector<long long> vec;
    for (int i = 0; i < Q; ++i) {
        if (type[i] == 1) {
            long long k = first[i], val = second[i];
            while (k--) {
                vec.push_back(val);
            }
        }
        else if (type[i] == 2) {
            sort(vec.begin(), vec.end());
            long long l = first[i] - 1, r = second[i], res = 0;
            while (l < r) {
                res = (res + vec[l++]) % 1000000007;
            }
            printf("%lld\n", res);
        }
    }
}

为防止你被JMC的代码搞到头晕目眩，JMC特意给出了问题的文字描述。已知一开始有一个空序列，接下来有Q次操作，每次操作给出type、first和second三个值。当type为1时，意味着该操作属于第一种操作：往序列尾部添加first个second数。当type为2时，意味着该操作属于第二种操作：查询序列中第first小至第second小的数值之和（一共有(second - first + 1)个数被累加），并将结果对1000000007取模后输出。

Input

单组数据
第一行一个Q（1 <= Q <= 1e5），代表Q次操作。
接下来有Q行，每行包含三个整数type、first和second；其中1 <= type <= 2。当type等于1时，0 <= first,second < 1e9。当type等于2时，1 <= first <= second，且first和second均不大于目前已添加进序列的数的数量。

Output

对于每次操作二，将结果对1000000007取模后输出。

Sample Input

1 5 1

1 6 3

2 2 5

2 4 8

1 2 2

2 4 8

Sample Output

题意：中文题。

解析：离散化之后，建立权值线段树。维护一个ans数组用于区间权值求和，维护一个sum数组用于区间个数求和和查询出第first大和second大离散化之后得下标x，y

answer = queryans(1,y-1) - queryans(1,x-1) + (second-querysum(1,y-1))*v[ y-1 ] - (first-querysum(1,x-1))*v[ x-1 ]

AC代码

#include <bits/stdc++.h>

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define all(a) (a).begin(), (a).end()

#define fillchar(a, x) memset(a, x, sizeof(a))

#define huan printf("\n")

#define debug(a,b) cout<<a<<" "<<b<<" "<<endl

#define ffread(a) fastIO::read(a)

using namespace std;

typedef long long ll;

const int maxn = 1e5+;

const int inf = 0x3f3f3f3f;

const ll mod = ;

const double epx = 1e-;

const double pi = acos(-1.0);

//head-----------------------------------------------------------------

ll sum[maxn*],ans[maxn*];

void PushUp(int rt)

{

    sum[rt]=sum[rt<<]+sum[rt<<|];

    ans[rt]=(ans[rt<<]+ans[rt<<|])%mod;

}

void update(int x,ll val,ll vall,int l,int r,int rt)

{

    if(l==x&&r==x)

    {

       sum[rt]+=vall;

       ans[rt]=(ans[rt]+val)%mod;

       return;

    }

    int mid=(l+r)>>;

    if(x<=mid)

        update(x,val,vall,l,mid,rt<<);

    else

        update(x,val,vall,mid+,r,rt<<|);

    PushUp(rt);

}

ll query1(int L,int R,int l,int r,int rt)

{

    if(R<L)

        return ;

    if(L<=l&&R>=r)

    {

        return sum[rt];

    }

    int mid=(l+r)>>;

    ll anss=;

    if(L<=mid)

        anss+=query1(L,R,l,mid,rt<<);

    if(R>mid)

        anss+=query1(L,R,mid+,r,rt<<|);

    return anss;

}

int query2(ll x,int l,int r,int rt)

{

    if(l==r)

    {

        return l;

    }

    int mid=(l+r)>>;

    if(sum[rt<<]>=x)

        return query2(x,l,mid,rt<<);

    else

        return query2(x-sum[rt<<],mid+,r,rt<<|);

}

ll query3(int L,int R,int l,int r,int rt)

{

    if(R<L)

        return ;

    if(L<=l&&R>=r)

    {

        return ans[rt];

    }

    int mid=(l+r)>>;

    ll anss=;

    if(L<=mid)

        anss=(anss+query3(L,R,l,mid,rt<<))%mod;

    if(R>mid)

        anss=(anss+query3(L,R,mid+,r,rt<<|))%mod;

    return anss;

}

struct query

{

    ll op,x,y;

}q[maxn];

vector<ll> v;

int getid(ll x)

{

    return lower_bound(all(v),x)-v.begin()+;

}

int main()

{

    int n;

    scanf("%d",&n);

    {

        for(int i=;i<n;i++)

        {

            scanf("%lld%lld%lld",&q[i].op,&q[i].x,&q[i].y);

            v.pb(q[i].y);

        }

        sort(all(v));

        v.erase(unique(all(v)),v.end());

        int sizen=v.size();

        for(int i=;i<n;i++)

        {

            if(q[i].op==)

            {

                update(getid(q[i].y),(q[i].y*q[i].x)%mod,q[i].x,,sizen,);

            }

            else

            {

                int valx=query2(q[i].x,,sizen,);

                int valy=query2(q[i].y,,sizen,);

                if(valx==valy)

                {

                    ll ret = ((q[i].y-q[i].x+)%mod*v[valx-])%mod;

                    printf("%lld\n",ret);

                }

                else

                {

                    ll numx=query1(,valx-,,sizen,);

                    ll numy=query1(,valy-,,sizen,);

                    ll ret=(query3(,valy-,,sizen,)-query3(,valx-,,sizen,)+mod)%mod;

                    ret=(ret-((q[i].x-numx-)%mod*v[valx-])%mod+mod)%mod;

                    ret=(ret+((q[i].y-numy)%mod)*v[valy-]%mod)%mod;

                    printf("%lld\n",ret);

                }

            }

        }

    }

}

zyb的面试

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 509 Accepted Submission(s): 199

Problem Description

今天zyb参加一场面试,面试官听说zyb是ACMer之后立马抛出了一道算法题给zyb:
有一个序列,是1到n的一种排列,排列的顺序是字典序小的在前,那么第k个数字是什么?
例如n=15,k=7, 排列顺序为1, 10, 11, 12, 13, 14, 15, 2, 3, 4, 5, 6, 7, 8, 9;那么第7个数字就是15.
那么,如果你处在zyb的场景下,你能解决这个问题吗?

Input

T组样例(T<=100)
两个整数n和k(1<=n<=1e6,1<=k<=n),n和k代表的含义如上文

Output

输出1-n之中字典序第k小的数字

Sample Input

15 7

Sample Output

题意：序列1-n 字典序排序之后第k个数是多少。

解析：肯定不能字符串排序，铁超时。。。容易想到先计算出 1-9开头的数分别有多少判断k在哪个区间从而确定了第一位数在确定的数字基础上在进行同样的操作 0-9...

所以写一个函数进行计算直到k=0。

AC代码

#include <bits/stdc++.h>

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define all(a) (a).begin(), (a).end()

#define fillchar(a, x) memset(a, x, sizeof(a))

#define huan printf("\n")

#define debug(a,b) cout<<a<<" "<<b<<" "<<endl

#define ffread(a) fastIO::read(a)

using namespace std;

typedef long long ll;

const int maxn = 1e2+;

const int inf = 0x3f3f3f3f;

const int mod = ;

const double epx = 1e-;

const double pi = acos(-1.0);

//head-----------------------------------------------------------------

vector<int> ans;  //已确定的数字

int getnum(int x,int y)

{

    int res=,ji=,now=;

    for(int i=ans.size()-;i>=;i--)

    {

        now+=ans[i]*ji;

        ji*=;

    }

    for(int i=;i<=1e6;i*=) //位数

    {

        int temp=min((x++now)*i,y+);

        if(temp>=(now+x)*i)

            res+=temp-(now+x)*i;

        if(temp==y+)

            break;

    }

    return res;

}

int main()

{

    int t,n,m;

    scanf("%d",&t);

    while(t--)

    {

        ans.clear();

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

        while(m!=)

        {

            int sum=;

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

            {

                if(ans.size()==&&i==)

                    continue;

                int temp=getnum(i,n);

                if(sum+temp>=m)

                {

                    m-=sum;

                    ans.pb(i);

                    m--;

                    break;

                }

                sum+=temp;

            }

        }

        for(int i=;i<ans.size();i++)

            cout<<ans[i];

        cout<<endl;

    }

}

巴特西

HDU 6464 权值线段树 && HDU 6468 思维题

免费送气球

zyb的面试

最新文章

热门文章