CCPC2018-湖南全国邀请赛 解题报告 Apare

CCPC2018-湖南全国邀请赛 解题报告

by lj zx xzc 2019/5/6

题目链接：

vj链接：CCNUACM Team Contest 2019 Round #5
HDU链接：CCPC2018-湖南全国邀请赛-重现赛（感谢湘潭大学）

A. Easy h-index

题意： 略

我们的代码：

/* Status Accepted Time 46ms Memory 2156kB Length 337 Lang G++ Submitted 2019-05-05 15:16:41 */
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[200005];
int main()
{
	int n,k;
	long long sum;
	while(scanf("%d",&n)!=EOF){
		sum = 0;
		for(int i = 0;i <= n;i++)
		scanf("%d",&a[i]);
		for(int i = n;i >=0;i--){
			sum+=a[i];
			if(sum>=i){
				printf("%d\n",i);
				break;
			} 
		}
	}
	return 0;
}

B. Higher h-index

题意：

我们的代码：

/* Status Accepted Time 15ms Memory 1224kB Length 203 Lang G++ Submitted 2019-05-05 17:02:07 */
#include<stdio.h>
#include<algorithm>
using namespace std;
#define ll long long
ll n,a;
int main()
{
    while(scanf("%lld%lld",&n,&a)!=EOF)
    {
        printf("%lld\n",(n+a)/2);
    }
    return 0;
}

C. Just h-index

题意：
  数组大小1E5,元素1到1E5,询问1E5,每个询问给出一个区间，要找到最大的h，使得这个区间内>=h的数有>=h个

思路：
  二分答案，用主席树求区间第K大(len+1-k小)，然后check xx>=mid 即可
  据说主席树自带二分性质
我们的代码：

/* Status Accepted Time 1357ms Memory 22948kB Length 1889 Lang G++ Submitted 2019-05-05 17:45:53 */
#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
using namespace std;
const int maxn = 1e5+20;
int a[maxn],n,cnt;
struct Node{
    int Lchild,Rchild,sum;
}node[maxn*20];
int root[maxn*20];
int update(int left,int right,int v,int p)
{
    if(v<left||v>right) return p;
    int t = cnt++;
    node[t].Lchild = node[p].Lchild;
    node[t].Rchild = node[p].Rchild;
    node[t].sum = node[p].sum+1;
    int mid = (left+right)>>1;
    if(left==right) return t;
    node[t].Lchild = update(left, mid,  v,node[p].Lchild);
    node[t].Rchild = update(mid+1,right,v,node[p].Rchild);
    return t;
}
void build()
{
    cnt = 0;
    root[0] = cnt++;
    node[0].Lchild = node[0].Rchild = node[0].sum = 0;
    For(i,1,n) root[i] = update(1,n,a[i],root[i-1]);
}
int query(int left,int right,int k,int rx,int ry)
{
    if(left==right) return left;
    int tot = node[node[ry].Lchild].sum - node[node[rx].Lchild].sum;
    int mid = (left+right)>>1;
    if(k<=tot) return query(left,   mid,k,    node[rx].Lchild,node[ry].Lchild);
    else return       query(mid+1,right,k-tot,node[rx].Rchild,node[ry].Rchild);
}

int main()
{
    //freopen("in.txt","r",stdin);
    int q;
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        For(i,1,n) scanf("%d",a+i);
        build();
        int h,l,r;
        while(q--)
        {
            scanf("%d%d",&l,&r);
            int left = 1,right = r-l+2,mid;
            while(right-left>1)
            {
                mid = (left+right)>>1;
                int xx = query(1,n,r-l+2-mid,root[l-1],root[r]);
                //printf("[%d,%d]之间的第%d小是%d\n",l,r,n+1-mid,xx);
                if(xx>=mid) left = mid;
                else right = mid;
            }
            printf("%d\n",left);
        }
    }


    return 0;
}

F. Sorting

题意：
  结构体排序，字典序最小，且a0+b0/a0+b0+c0 < a1+b1/a1+b1+c1
直接乘会爆Long long,可以优化一下，见代码

我们的代码：

/* Status Accepted Time 46ms Memory 1484kB Length 1051 Lang G++ Submitted 2019-05-05 15:35:11 */
#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
using namespace std;
const int maxn = 1e5+20;
struct Node{
    unsigned long long a,b,c;
    int id;
    bool operator < (const Node& r)const{
        if(c*(r.a+r.b+r.c)==r.c*(a+b+c))
            return id < r.id;
        return c*(r.a+r.b+r.c)>r.c*(a+b+c);
    }
    void input(int _id)
    {
        id = _id;
        //scanf("%ull%ull%ull",&a,&b,&c);
        cin>>a>>b>>c;
    }
    void out()
    {
        printf("node[%d] %ull %ull %ull\n",id,a,b,c);
    }
}node[maxn];
int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        For(i,1,n)
        {
            node[i].input(i);
           // node[i].out();
        }
        sort(node+1,node+1+n);
        printf("%d",node[1].id);
        For(i,2,n)
        {
            printf(" %d",node[i].id);
        }
        printf("\n");
    }


    return 0;
}

G. String Transformation

题意：
  有两个字符串仅仅由’a’,‘b’,'c’组成，我们对每个字符串都可以插入或者删除"aa",“bb”,“abab”，问给定的两个字符串是否可以变为一样的

样例：
Sample Input
ab
ba
ac
ca
a
ab
Sample Output
Yes
No
No
分析：

  由样例我们可以知道ab和ba可以相互转换，就是说相邻的ab可以交换：

  • ab->aababb->ba
  • ba->aababb->ab
    而c是不可以变的，所以我们以c为坐标即可
    我们可以知道，插入和删除的字符串长度为2和4，所以不改变原串长度的奇偶性。
  • 如果两个串长度奇偶性不同，直接输入no
  • 然后我们对两个串分别遍历，记录下来每个串c的位置，如果c的个数不同，直接输出no
  • 我们可以把字符串开头结尾都插入一个’c’，然后两个串比较任意连个相邻的c之间a和b的个数的奇偶性是否相同即可(见代码)

我们的代码：

/* Status Accepted Time 15ms Memory 1412kB Length 1561 Lang G++ Submitted 2019-05-05 16:57:45 */
#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
using namespace std;
const int maxn = 1e5+20;
char s[maxn],t[maxn];
int lens,lent;
int ps[maxn],cnts;
int pt[maxn],cntt;
bool ok(int sL,int sR,int tL,int tR)
{
    int nb=0,na=0;
    For(i,sL,sR)
    {
        if(s[i]=='a') ++na;
        else if(s[i]=='b') ++nb;
    }
    For(i,tL,tR)
    {
        if(t[i]=='a') --na;
        else if(t[i]=='b') --nb;
    }
    na = abs(na);
    nb = abs(nb);
    return (na%2==0&&nb%2==0);
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%s%s",s,t)!=EOF)
    {
        lens = strlen(s);
        lent = strlen(t);
        cnts = cntt = 0;
        ps[cnts++] = -1;
        pt[cntt++] = -1;
        if((max(lent,lens)-min(lent,lens))%2)
        {
            printf("No\n");continue;
        }
        for(int i=0;i<lens;++i)
        {
            if(s[i]=='c') ps[cnts++] = i;
        }
        for(int i=0;i<lent;++i)
        {
            if(t[i]=='c') pt[cntt++] = i;
        }
        if(cnts!=cntt)
        {
            printf("No\n");continue;
        }
        ps[cnts++] = lens;
        pt[cntt++] = lent;
        bool flag = true;
        For(i,1,cntt-1)
        {
            if(!ok(ps[i-1]+1,ps[i]-1,pt[i-1]+1,pt[i]-1))
            {
                printf("No\n");
                flag = false;
                break;
            }
        }
        if(flag) printf("Yes\n");
    }
    return 0;
}

K. 2018

题意：
  给两个区间， [a,b]和[c,d]， 从第一个区间里挑一个数x,从第二个区间里挑一个数y，使得x*y是2018的倍数，问有多少种取法

分析：
  分解一下质因数，我们知道2018 = 2 * 1009,两个质数，我们可以简单容斥一下
  一个区间[a,b]内k的倍数的个数为：b/k-(a-1)/k
我们令f(a,b,k) = b/k-(a-1)/k
  设A,B为集合，则A - B = A - AB

我们就先分析[a,b]这个区间选出的数x:

  1. x只是2的倍数： y2n9 = f(a,b,2) - f(a,b,2018)
  2. x只是1009的倍数：n2y9 = f(a,b,1009) - f(a,b,2018)
  3. x是2018的倍数：y2y9 = f(a,b,2018)
  4. x既不是2的倍数，又不是1009的倍数: n2n9 = (b-a+1)-(y2n9+n2y9+y2y9)
  • 然后x只是2的倍数，那么y是1009的倍数即可：f(c,d,1009)
  • x只是1009的倍数, y是2的倍数即可：f(c,d,2)
  • x是2018的倍数,y任意取 c-d+1
  • x既不是2也不是1009的倍数，那么y必须是2018的倍数：f(c,d,2018)
    对应相乘相加即可(注意会爆int)

我们的代码：

/* Status Accepted Time 15ms Memory 1384kB Length 951 Lang G++ Submitted 2019-05-05 14:58:52 */
#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
using namespace std;
int f(int left,int right,int xx)
{
    return right/xx-(left-1)/xx;
}
struct Node
{
    int y2y9,y2n9,n2n9,n2y9;
    void init(int left,int right)
    {
        y2y9 = f(left,right,2018);
        y2n9 = f(left,right,2)-f(left,right,2018);
        n2y9 = f(left,right,1009)-f(left,right,2018);
        n2n9 = right-left+1-(y2n9+n2y9+y2y9);
    }
    void getAns(int L,int R)
    {
        LL res = 0;
        res += 1ll*n2n9*f(L,R,2018);
        res += 1ll*y2n9*f(L,R,1009);
        res += 1ll*n2y9*f(L,R,2);
        res += 1ll*y2y9*(R-L+1);
        printf("%lld\n",res);
    }
}xx;

int main()
{
    int a,b,c,d;
    while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
    {
        xx.init(a,b);
        xx.getAns(c,d);

    }
    return 0;
}

J. Vertex Cover(没出)

题意：
  现在有n个点构成的完全图，编号为0到n-1,第i个点的权重为2^i
  现在Alice从完全图里面选了若干条边，然后聪明的Bobo选了一些点来覆盖这些边。只要边的一个端点被选择就说这条边被覆盖了。Bobo选的点集是权重最小的。
  现在用二进制的形式给出Bobo选择的点集，现在问Alice可能选择的边集的个数
分析：
  由于点的权重是2^i，就是说这个点之前所有点的权重加起来都没有它大。所以我们如果已知边选点，肯定是贪心地选择下标小的点。
  就是说，如果我们选择了一个点V，那么必定至少存在一条边，边的一个端点是这个点V，另一个端点是下标比V大的点，那么Bobo才有选择这个点的理由

思路：

  • 按下标从大到小遍历点集中的点
  • 每个点x从<stron>下标比自己大的点中至少要连一条边(2^k-1)，k = (n-x)-(sum[n]-sum[x)</stron>
  • 点集中每个点x和<stron>下标比自己小的点的边可连可不连(2^(x-1))</stron>
  • 遍历一遍相乘即可

我们的代码：

/* Status Accepted Time 31ms Memory 2744kB Length 1124 Lang G++ Submitted 2019-05-06 10:42:37 */
#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
using namespace std;
const int mod = 1e9+7;
const int maxn = 1e5+20;
int n;
char s[maxn];
int a[maxn]; ///a[i] = 1 代表第i个点被选择了
int sum[maxn];
LL fast_pow(LL a,LL b)
{
    LL ans = 1;
    while(b)
    {
        if(b&1) ans = ans*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d%s",&n,s+1)!=EOF)
    {
        vector<int> v;
        int len =strlen(s+1);
        int cnt = 0;
        for(int i=len;i>0;--i)
        {
            a[++cnt] = s[i]-'0';
            if(s[i]=='1') v.push_back(cnt);
        }
        For(i,cnt+1,n) a[i] = 0;
        sum[0] = 0;
        For(i,1,n)
            sum[i] = sum[i-1]+a[i];
        LL ans = 1;
        for(auto &x:v)
        {
            ans = ans*fast_pow(2ll,x-1)%mod;
            ans = ans*((fast_pow(2ll,n-x-sum[n]+sum[x])-1+mod)%mod)%mod;
        }
        printf("%lld\n",ans);
    }
    
    return 0;
}
全部评论

相关推荐

头像 头像
一只辉
05-11 10:36
已编辑
华南理工大学 体育学类
点赞 评论 收藏
转发
头像
数字马力谁去
昨天 16:02
湖南师范大学 电子信息类
数字马力不当人？
据我了解，数字马力校招HC已经几乎没有了，然而，招聘上全是它们的招聘信息，不知为什么，难道是为了打个广告，提高知名度吗，第二，我投递的时候是在三月，笔试的时候是在四月，面试的时候是在五月，再来讲讲面试时候的经历吧，首先面试官并不会让你做自我介绍，根本不想对你有任何了解，直接开局问你做了什么项目，实习干了什么，面试时候的态度更是嘲讽，一个一边面，一直笑，旁边还有个人，回答完，就哈哈哈的大笑，嘲笑无余，搞不懂，一个外包，也不是蚂蚁的正式员工，这么讽刺，不知道还有多强呢，然后转手给你挂掉，不知有什么意义
投递数字马力（杭州）信息技术有限公司等公司7个岗位 >
点赞 评论 收藏
转发
头像
蓁蓁欣欣
05-10 15:22
已编辑
大连理工大学 计算机类
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议
# 牛客帮帮团来啦！有问必答 #
660144次浏览 10926人参与
# 无实习如何秋招上岸 #
212860次浏览 3311人参与
# 你的简历改到第几版了 #
295774次浏览 4476人参与
# 23届的你们都什么时候入职？ #
83330次浏览 724人参与
# 租房前辈的忠告 #
30986次浏览 2025人参与
# 找工作中的意难平 #
184256次浏览 3340人参与
# 硬件人的简历怎么写 #
76234次浏览 775人参与
# 华为开奖那些事 #
694530次浏览 5968人参与
# 简历中的项目经历要怎么写 #
422063次浏览 7175人参与
# 机械人怎么评价今年的华为 #
65846次浏览 530人参与
# 秋招开了，你想投哪些公司呢 #
115036次浏览 3234人参与
# 五一之后，实习真的很难找吗？ #
16826次浏览 105人参与
# 我想象的工作vs实际工作 #
90060次浏览 1523人参与
# 金融银行面经 #
4661次浏览 104人参与
# 你投了多少份简历，才拿到offer？ #
5280次浏览 59人参与
# 你已经投递多少份简历了 #
285973次浏览 4335人参与
# 第一份工作应该选择高薪还是大平台 #
33719次浏览 252人参与
# 本周投递记录 #
194179次浏览 5013人参与
# 工作压力大怎么缓解 #
9714次浏览 135人参与
# 打工人的辛酸 #
8054次浏览 113人参与
牛客网
牛客企业服务