抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

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更新最大值即可,找到最大值就是答案了。(最远的两个点都扩散完了,
其他点肯定早他妈扩散完了)

评论