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-22 11:52
广州大学华软软件学院 网络客服
仿青藤之恋社交交友软件 即时通讯 聊天 微信小程序 App
​&nbsp;《欧几里》是一款一比一模仿《青藤之恋》的社交交友软件开源项目，主打高学历优质人群交友，功能上基本还原青藤之恋，以双向喜欢后解锁聊天，目前适配微信小程序，手机App，H5，三端通用，功能完整，盈利模式完善，高度配置化，功能模块化，高内聚，低耦合，一天快速上线，已对接支付接口，只需要简单的修改配置文件中相关信息，即可实现快速部署上线，减少开发的时间成本，金钱成本，技术成本，将更多的精力放在产品运营上。仅供学习研究之用，请勿商用，商用请支持正版演示地址：H5演示地址https://www.wxmblog.com/oujili安卓APK下载地址：https://www.wxmblog.com/de...
点赞 评论 收藏
分享
11-19 10:26
牛客运营
今年的校招薪资，有点猛啊。。。
25届秋招企业陆续开奖，今年的薪资和往年不太相同；今年可以说是“下猛药”、“沙峰了”（哈哈&nbsp;牛牛这牛生没见过这么多钱🥺）前有拿了50+白菜价的我牛可乐的朋友后有连拿3个sp的我失散多年的兄弟更有总包90+，还在纠结其他offer的哥们我以为这只是个例，没想到这居然是常态。。。在【2024最新名企校招薪资爆料】的资料包里，就看到不少新出的逆天校招薪资。这个资料不收费，点击下方链接或扫码，邀请2位同学组团，即可一起免费领取！🔴&nbsp;你将获得：✅&nbsp;大厂内部真人爆料，真实薪资更靠谱✅&nbsp;不同岗位薪资汇总，了解薪资更全面✅&nbsp;牛客独家整理出品，过了这村没这店拿offer，别犹豫，点击马上领取&gt;&gt;...
想润的芹菜人狠话不多：转人工
点赞 评论 收藏
分享
10-13 13:35
第一拖拉机制造厂拖拉机学院 Java
逆天
太逆天了这个
挣K存W养DOG：他真的很中意你，为什么不回他
点赞 评论 收藏
分享
昨天 14:55
小红书_社区技术部_前端开发(实习员工)
9.24古茗一面
今年没想到卷成这样，面试表现挺好的，但是问多久出结果，说是候选人特别多，可能要很久，然后就一直没给后续，估计是进池子了。自我介绍如何了解到的我们公司心动的复杂权限场景以及性能优化，按钮权限，菜单权限，接口权限都是怎么实现的ci/cd是什么大文件的分片上传怎么实现的如何保证每一片的完整性文件传输某一片失败的该怎么办为什么这样子设计介绍一下promisetry&nbsp;catch能否监听到promise的错误，为什么promise.race的特点promise还有什么方法hash路由与history路由的区别为什么history需要服务端配置入口地址小程序开发的了解前端浏览器缓存mvc和mvvm是什么什么...
查看26道真题和解析 面经烤面筋
点赞 评论 收藏
分享
点赞 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
263471次浏览 2181人参与
# 0offer是寒冬太冷还是我太菜 #
887047次浏览 7909人参与
# 北方华创开奖 #
23653次浏览 260人参与
# 地方国企笔面经互助 #
2844次浏览 7人参与
# 学历or实习经历，哪个更重要 #
43389次浏览 328人参与
# 选完offer后，你后悔学本专业吗 #
13189次浏览 94人参与
# 查收我的offer竞争力报告 #
19473次浏览 255人参与
# 应届生被毁约被毁意向了怎么办 #
28178次浏览 243人参与
# 你最想要的公司福利是？ #
41821次浏览 145人参与
# 如何一边实习一边秋招 #
987266次浏览 12609人参与
# 一觉醒来，我觉醒了超级打工人系统 #
3293次浏览 36人参与
# 嵌入式转岗的难度怎么样 #
11194次浏览 251人参与
# 你最希望上岸的公司是？ #
76492次浏览 469人参与
# 如何写一份好简历 #
604965次浏览 8508人参与
# 面试体验感最好的是哪家？ #
83624次浏览 818人参与
# 机械应届生薪资要多少才合适？ #
12534次浏览 61人参与
# 牛客十周岁生日快乐 #
48712次浏览 759人参与
# 你认为第一份工作重要吗 #
5441次浏览 49人参与
# 985本硕1个中小厂offer，摆烂or继续努力 #
79904次浏览 589人参与
# 秋招OC许愿 #
228117次浏览 1880人参与
# 来聊聊机械薪资天花板是哪家 #
65701次浏览 445人参与
牛客网
牛客企业服务