专栏首页Tanger的思源地ACM之7-22日作业题解

ACM之7-22日作业题解

1.A讲故事

题目描述

一天,天上掉下来了一个可爱的小妹妹,小妹妹天天缠着你给她讲故事。并且让你在N天内给她讲K(K ≤ N)个不同小故事。你把你知道的所有K个故事从1到K进行编号。她每天会要求你讲某一个小故事,例如第i天她会要求你给他讲第ai个小故事。 由于小妹妹有间歇性失忆,所以她可能会在一些天内要求你讲你已经讲过的故事。如果你每天都按照她的要求来的话,可能会出现无法在N天内讲完K个故事的情况(小妹妹可能没有要 求过讲某个故事)

1.A讲故事

题目描述

一天,天上掉下来了一个可爱的小妹妹,小妹妹天天缠着你给她讲故事。并且让你在N天内给她讲K(K ≤ N)个不同小故事。你把你知道的所有K个故事从1到K进行编号。她每天会要求你讲某一个小故事,例如第i天她会要求你给他讲第ai个小故事。 由于小妹妹有间歇性失忆,所以她可能会在一些天内要求你讲你已经讲过的故事。如果你每天都按照她的要求来的话,可能会出现无法在N天内讲完K个故事的情况(小妹妹可能没有要 求过讲某个故事)

你为了完成任务可能在某些情况下,不得不拒绝她的要求,给她讲其他的小故事。但是你在第i天拒绝了小妹妹的请求的话,小妹妹对你的好感度就会下降b

如何在降低最小好感度的情况下在N天内讲完K给小故事。请输出最少降低的好感度。

输入

第一行两个正整数,N K (1≤ K ≤N ≤ 10^5) N为总天数,K为需要讲述的故事个数

第二行N个正整数 a1 a2 …… an (1 ≤ ai ≤ k) 第n天要求的故事序号

第三行N个正整数 b1 b2 …… bn(1 ≤ bi ≤ 10^9) 第i天拒绝要求降低的好感度

输出

一行,满足条件的前提下最少降低的好感度。

样例输入

8 7
1 1 3 1 5 3 7 1
5 7 4 8 1 3 5 2

样例输出

10 

提示

对样例一,最佳的方案是在 1, 6, 8 天把故事改为 2, 4, 6 号,降低的好感度为 a1 + a6 + a8 = 5 + 3 + 2 = 10

对样例二,不需要做调整

参考程序 c++

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
struct data_p{int a;ll b;}num[100005];
int n,k,maxl[100005],now=0;
ll ans;
bool cmp(data_p x,data_p y){return x.b<y.b;}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i].a);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i].b);
        
        if(num[ maxl[ num[i].a ] ].b<num[i].b)
        maxl[num[i].a]=i;
    }
    
    for(int i=1;i<=k;i++)
    {
        if(!maxl[i])continue;
        num[maxl[i]].b=1000000000;
        now++;
    }
    
    sort(num+1,num+n+1,cmp);
    
    for(int i=1;i<=k-now;i++)
    {
        ans+=num[i].b;
    }
    printf("%lld",ans);
    return 0;
} 

题解

贪心问题求最优解,先排序让降低好感度最小的排在前面,先对重复且降低好感度最小的故事提出来,然后再根据要调整的天数来依此相加。

B: 数学题

题目描述

今天,你向你的心上人表白了,可是TA说:

我这里有一个长度为n(2 ≤ n ≤ 30)的数列,数列的第i项是2i。现在保证数列长度n是一个偶数,将数列平均分成两份,如果你能得出两份的最小差值,我就答应你。

看着自己的心上人,你光速的写了一个程序,算出了最小差值。

输入

第一行 T (T≤100) 表示 (你心上人的个数) 有T组数据

接下来的T行每一行有一个 数组长度n (2 ≤ n ≤ 30)且保证n是偶数

输出

对于每一个测试数据都输出最小差值

样例输入

2
2
4

样例输出

2
6

提示

用笔算

参考程序 c++(个人写的)

#include<cstdio>
#include<iostream>
#include<math.h>
using namespace std;
long long sum1,sum2;
int main(){
    int t,n,i,step;
    cin>>t;
    while(t--){
        cin>>n;
        if(n%2!=0)
        continue;
        else{
        sum1=0,sum2=0,step=1;
        for(i=1;i<=n-1;i++){
            step=step*2;
            sum1=sum1+step;
            }
            step=1;
        for(i=1;i<=(n/2)-1;i++){
            step=step*2;
            sum2=sum2+step;
        }
        cout<<pow(2,n)+2*sum2-sum1<<endl;}
    }
    return 0;
} 

题解

3.C:数的划分

题目描述

将整数n分成k份,且每份不能为0,问有多少种不同的分法。注:当n=7,k=3时,下面三种分法被视为是相同的

1 1 5
1 5 1
5 1 1

输入

一行两个整数n,k

输出

一行一个整数,即不同的分法数

样例输出

7 3

样例输出

4

提示

对于样例的四种分法:

1 1 5
1 2 4
1 3 3
2 2 3

0<=n<=200,2<=k<=6

参考程序

#include<iostream>//(深搜)
using namespace std;
int n,k,ans=0;
void dfs(int past,int cnt,int num)
{
    if(cnt==1)
    {
        ans++;
        return;
    }
    for(int i=past;i<=num/cnt;i++)
    dfs(i,cnt-1,num-i);
}
int main()
{
    cin>>n>>k;
    dfs(1,k,n);
    cout<<ans;
    return 0;
}

题解

也就是递归+搜索,其中past代表当前分出来的数,cnt代表是剩下还可以分几次,num代表分完past之后 剩下的数。其实思想是很简单的,只要能理解,用笔写一写就可以知道了,反正懂得都懂。

4.D:扩散

题目描述

一个点每过一个单位时间就会向四个方向扩散一个距离,如图。

两个点a、b连通,记作e(a,b),当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、v都必定存在路径e(u,a0),e(a0,a1),…,e(ak,v)。给定平面上的n给点,问最早什么时刻它们形成一个连通块。

输入

第一行一个数n,以下n行,每行一个点坐标X[i] Y[i]。

输出

一个数,表示最早的时刻所有点形成连通块。

样例输入

2
0 0
5 5

样例输出

5

提示

1≤N≤50; 1≤X[i],Y[i]≤10^9

参考程序

#include<bits/stdc++.h>
using namespace std;
const int N=100;
int n,dis[N][N],anss;
struct node{
    int x,y;
}a[N];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) 
    scanf("%d%d",&a[i].x,&a[i].y);
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
        dis[i][j]=abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y); 
    for (int k=1;k<=n;k++) 
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        dis[i][j]=min(dis[i][j],max(dis[i][k],dis[k][j]));
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
        anss=max(anss,dis[i][j]);
    printf("%d\n",(anss+1)/2);
    return 0; 
}

题解

先来科普一下曼哈顿距离:**d(i,j)=|xi-xj|+|yi-yj|**,也就是直线距离

我们假设有两个点A,B,他们的坐标分别为(X1,Y1),(X2,Y2).那么现在我们要这两个点扩散,要多长时间? 假设X1< X2,且Y1< Y2,那么它们想要尽量靠拢就要向对方的方向扩散。那么A点每扩散一次,他们之间的距离-1, 同理B点每扩散一次,距离-1。

说明: 每次扩散A、B的曼哈顿距离-2. 1.如果曼哈顿距离(设其为dis)为奇数,那最后一次距离只差1。所以需要dis/2+1的时间,也就是(dis+1)/2;

2,如果曼哈顿距离为偶数,那正好dis/2的时间后他们会正好相遇。而(dis+1)/2后对结果没有影响(因为是下取整)

假设有三个点ABC,其中A离原点最近,C离原点最远,假设AB我们用了t1秒,BC我们用了t2秒,不考虑B,AC用了t3秒 ,那么就会有min(t1,t2)< t3,所以我们只需枚举每两个节点,用ans更新最大值即可,找到最大值就是答案了。(最远的两个点都扩散完了, 其他点肯定早他妈扩散完了)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ACM之7-25日作业题解

    一个如下的 6×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

    Tanger
  • ACM之7-23日作业题解

    给你一个数组a,注意下标从0开始 如果数组中的每个奇数下标为奇数且数组中的每个偶数的下标为偶数则叫好数组否则就是不好数组 比如...

    Tanger
  • ACM之7.21日作业题解

    题解:这里的A是用来存放各位数的一个数组因为最多只有10个不同的数字所以A[10]恰好 够用,result[300]是用来打标记的,用过的数组就改false为t...

    Tanger
  • AI 人才遭疯抢,Google 为 22 岁印度毕业生开出 1000w+ 年薪

    他就是仅有 22 岁的 Aditya Paliwal。2013 年到 2018 年,Aditya Paliwal 参加了为期五年的计算机综合 M.Tech 双学...

    IT派
  • 这位AI毕业生,Google得不到他,就拿百万抢他!

    他就是仅有 22 岁的 Aditya Paliwal。2013 年到 2018 年,Aditya Paliwal 参加了为期五年的计算机综合 M.Tech 双学...

    用户1737318
  • 22岁大学生获谷歌天价offer,年薪百万!

    导读:在印度各地的顶级工程学院中,通过院校的安排获得一个高薪的工作是十分常见的,但如果你能一个世界顶级科技企业的offer,而且年薪千万,你会有怎样的心情呢?

    华章科技
  • 22岁印度大学生获谷歌天价offer,击败6000人年薪百万

    【新智元导读】来自印度孟买22岁的Aditya Paliwal得到了谷歌在纽约的人工智能研究部门工作的offer,年薪1200万卢比,约合115.5万元人民币。...

    新智元
  • 2019年ACM Fellow出炉,陈熙霖、陶大程、周礼栋、谢源、李向阳等7位华人学者入选

    AI 科技评论消息,纽约时间12月11日,美国计算机学会(ACM)宣布了 2019 年新当选 ACM Fellow 名单,共有 58 位科学家当选,其中包括 7...

    AI科技评论
  • 最全2019 AI/计算机/机器人顶会时间表来了,共收录36场会议,投稿冲鸭!

    下面,是量子位给大家整理的2019 AI顶会时间表,包含会议举办的时间、地点、投稿截止日期、官方网址/社交媒体地址,还有H5指数(谷歌学术的期刊会议评判标准,即...

    量子位
  • 【推荐系统教程】当机器学习遇到推荐系统,悉尼科技大学Liang Hu博士最新分享

    【导读】第32届AAAI大会-AAAI 2018将于2月2号-7号在美国新奥尔良召开,悉尼科技大学Liang Hu博士即将在大会作报告“When Advance...

    WZEARW
  • AI一分钟 | 北京发放自动驾驶首批牌照,百度获准测试;亿航美国分公司申请破产,债务高达数百万美元

    整理 | 费棋 一分钟AI 北京市自动驾驶测试管理联席工作小组向百度发放了北京市首批自动驾驶测试试验用临时号牌,自动驾驶测试车辆开始正式上路测试。 贾跃亭亮相美...

    AI科技大本营
  • 周末荐

    腾讯技术工程官方号
  • 【专知荟萃07】自动文摘AS知识资料全集(入门/进阶/代码/数据/专家等)(附pdf下载)

    【导读】主题荟萃知识是专知的核心功能之一,为用户提供AI领域系统性的知识学习服务。主题荟萃为用户提供全网关于该主题的精华(Awesome)知识资料收录整理,使得...

    WZEARW
  • 北大主场夺金ACM-ICPC全球总决赛,总教练罗国杰分享背后“秘笈”

    昨天(4月19日)下午,第42届ACM-ICPC国际大学生程序设计竞赛全球总决赛,在北京大学邱德拔体育馆举行,这也是2005年上海、2010年哈尔滨之后,中国第...

    量子位
  • 2018年机器学习和数据科学重要会议概览

    来源:KDnuggets 编译:Bing 一月 美洲 BAFI 2018:金融和工业商业分析第三次会议(3rd Conf. on Business Analyt...

    企鹅号小编
  • 2019 ACM Fellow刚刚发榜!陶大程、谢源、陈熙霖等7位华人学者当选

    全球最大的计算机领域专业性学术组织ACM(美国计算机协会)刚刚公布2019年最新当选的ACM Fellow,一共58位科学家当选,其中包括7位华人,表彰他们在人...

    新智元
  • 【ACMMM2017硅谷盛宴】多媒体领域各大奖项出炉!电子科大斩获最佳论文!中科院自动化所多媒体计算组获得IEEE期刊最佳论文!

    【导读】第25届ACM国际多媒体会议(ACM International Conference onMultimedia, 简称ACM MM)于2017年10月...

    WZEARW
  • 【AI 引擎】谷歌借助AI开发新移动app | NASA开发虚拟火星漫游游戏 | 阿里图像搜索之父入围ACM

    1.传谷歌开发新移动消息应用:集成人工智能技术 ? 北京时间12月23日早间消息,《华尔街日报》援引消息人士的说法称,谷歌正在开发一款新的移动消息服务。这款新服...

    新智元
  • 累积八年真题!全网超详细蓝桥杯试题解析 | 寻找C站宝藏

    很多小伙伴私信我在软件开发中算法的知识应该怎么学习,对于算法的训练又应该去参加哪些比赛,有很多也问过我一些关于ACM和蓝桥杯的一些知识。

    灰小猿

扫码关注云+社区

领取腾讯云代金券