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;
}
全部评论

相关推荐

11-20 16:28
北京联合大学 增长产品
点赞 评论 收藏
分享
11-22 00:55
武汉理工大学 汽车制造其它
点赞 评论 收藏
分享
10-30 17:07
University of California Riverside UE4
某些HR能不能有点职业素养
朋友圈挂人骂人巨婴😅😅
我已成为0offer的糕手：别惯着，胆子都是练出来的，这里认怂了，那以后被裁应届被拖工资还敢抗争？
点赞 评论 收藏
分享
头像
10-21 18:18
中南大学 机械设计/制造
华勤等开奖
#晒一晒我的offer# 有谁知道多少米吗
像好涩一样好学：这公司我也拿过 基本明确周六加班 工资还凑活 另外下次镜头往上点儿
晒一晒我的offer
点赞 评论 收藏
分享
11-19 13:00
已编辑
大连海事大学 后端
11.19【快手】-【质量与效能】-【北京】凉经
这两周一直在弄开题的事情。停止了投简历。把八股和leetcode也丢了。做实验，写ppt，写报告，准备开题，每天弄到晚上2-3点。烦！就应该敷衍了事，不该投入那么多时间！上周五才弄好。期间停止了八股和leetcode。很后悔。不该投入那么多时间。反正有老师在，肯定能过。但事情已经发生了。我没有抓住今天的面试机会。烦！简历是上周三开始恢复海投的，上周五快手约面，约的今早11点。答的不好。八股忘的差不多了。java不会acm模式。会脏面评嘛。先自我介绍。问我了不了解深度学习。让我讲一讲深度学习你觉得重要的地方。让我讲一讲怎么训练。胡扯了两句。面试官换了话题。开始问java。进程和线程的区别。没答好...
查看12道真题和解析
点赞 评论 收藏
分享
点赞 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
263792次浏览 2185人参与
# 0offer是寒冬太冷还是我太菜 #
887357次浏览 7909人参与
# 北方华创开奖 #
23660次浏览 260人参与
# 地方国企笔面经互助 #
2846次浏览 7人参与
# 学历or实习经历，哪个更重要 #
43425次浏览 328人参与
# 选完offer后，你后悔学本专业吗 #
13232次浏览 94人参与
# 查收我的offer竞争力报告 #
19504次浏览 255人参与
# 应届生被毁约被毁意向了怎么办 #
28195次浏览 243人参与
# 你最想要的公司福利是？ #
41853次浏览 146人参与
# 如何一边实习一边秋招 #
987348次浏览 12609人参与
# 一觉醒来，我觉醒了超级打工人系统 #
3302次浏览 36人参与
# 嵌入式转岗的难度怎么样 #
11199次浏览 251人参与
# 你最希望上岸的公司是？ #
76533次浏览 469人参与
# 如何写一份好简历 #
605015次浏览 8509人参与
# 面试体验感最好的是哪家？ #
83645次浏览 818人参与
# 机械应届生薪资要多少才合适？ #
12542次浏览 61人参与
# 牛客十周岁生日快乐 #
48737次浏览 759人参与
# 你认为第一份工作重要吗 #
5445次浏览 49人参与
# 985本硕1个中小厂offer，摆烂or继续努力 #
79930次浏览 589人参与
# 秋招OC许愿 #
228182次浏览 1880人参与
# 来聊聊机械薪资天花板是哪家 #
65727次浏览 445人参与
牛客网
牛客企业服务