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