结果填空
A. 跑步训练
【问题】
小明要做一个跑步训练。 初始时，小明充满体力，体力值计为 10000。如果小明跑步，每分钟损耗600的体力。如果小明休息，每分钟增加 300 的体力。体力的损耗和增加都是均匀变化的。
小明打算跑一分钟、休息一分钟、再跑一分钟、再休息一分钟……如此循环。如果某个时刻小明的体力到达0，他就停止锻炼。 请问小明在多久后停止锻炼。
为了使答案为整数，请以秒为单位输出答案。 答案中只填写数，不填写单位。
【解题】
按题意模拟即可，先按分钟变化，当体力不足600时跳出循环，按比例再加上相应的秒数即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int i,j;
int ti=0;
int power=10000;
while(1)
{
if(power>=600)
{
power-=600;
ti+=60;
}
else break;
power+=300;
ti+=60;
}
ti+=power/10;//每分钟减600,均匀减小,故每秒减600/60=10;
printf("%d\n",ti);
return 0;
}
//ans==3880;
ans:3880
B. 合并检测
[问题]
新冠疫情由新冠病毒引起，最近在A国蔓延，为了尽快控制疫情，A国准备给大量民众进病毒核酸检测。
然而，用于检测的试剂盒紧缺。 为了解决这一困难，科学家想了一个办法：合并检测。即将从多个人（k个）采集的标本放到同一个试剂盒中进行检测。如果结果为阴性，则说明这k个人都是阴性，用一个试剂盒完成了 k 个人的检测。如果结果为阳性，则说明 至少有一个人为阳性，需要将这 k 个人的样本全部重新独立检测（从理论上看， 如果检测前 k−1 个人都是阴性可以推断出第 k 个人是阳性，但是在实际操作中 不会利用此推断，而是将 k 个人独立检测），加上最开始的合并检测，一共使用 了 k + 1 个试剂盒完成了 k 个人的检测。 A 国估计被测的民众的感染率大概是 1%，呈均匀分布。请问 k 取多少能最节省试剂盒？
【解题】
简单概率题，由于均匀分布，每个所测民众感染的概率为0.01，没感染的概率为0.99，则当k个人中所有的人都没感染的时候这k人一个试剂盒就够了，只有一个人感染就要加多k个(即k+1个)。
故对k个检测者得所需试剂盒为：
0.99^k+(1-0.99^k)*(k+1)
=1-k*0.99^k+k
这个方程是超函数，无法直接手算最值,因此变换式子一下用程序找
视x=k-k*0.99^k, y=1
x+y的最小值当且仅当x==y时,
即k-k*0.99^k==1(再化简一下)
1-0.99^k==1/k
写个程序找方程两侧误差最小的k整数取值即可
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
int i,j;
int n;
double base=0.99;
double ans1,ans2;
double err=99999;
int best;
for(int k=1;k<=100;k++)
{
ans1=pow(base,k);
ans2=1-1.0/k;
if(abs(ans1-ans2)<err)
{
best=k;
err=abs(ans1-ans2);
}
}
printf("%d\n",best);
return 0;
}
//ans==10;
ans:10
C. 分配口罩
【问题】
某市市长获得了若干批口罩，给定每批口罩的数量，市长要把口罩分配给市内的2所医院。由于物流限制，每一批口罩只能全部分配给其中一家医院。市长希望2所医院获得的口罩总数之差越小越好。 请你计算这个差最小是多少？
【解题】
这个题就是把数组分成两个部分，求两部分和最小值的包装版本，可以用暴力dfs也可以dp(0-1背包作背包容量为sum/2的dp)，结果填空且只有15个数，直接暴力搜即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll num[15]={
9090400,8499400,5926800,8547000,4958200,4422600,5751200,4175600,6309600,5865200,6604400,4635000,10663400,8087200,4554000};
ll minn=0x3f3f3f3f;
ll sum;
void dfs(int pos,ll now)
{
if(pos>=15)
{
minn=min(minn,abs(sum-2*now));
return ;
}
dfs(pos+1,now+num[pos]);//选
dfs(pos+1,now); //不选
}
int main()
{
int i,j;
int n,m;
sum=0;
for(i=0;i<15;i++)
{
sum+=num[i];
}
dfs(0,0);
printf("%lld\n",minn);
return 0;
}
//ans==2400;
ans:2400
D. 矩阵
【问题】
把1∼2020放在2×1010的矩阵里。要求同一行中右边的比左边大，同一列中下边的比上边的大。一共有多少种方案？
答案很大，你只需要给出方案数除以2020的余数即可。
【解题】
DP进行方案数计数，dp(i,j)表示前i个数选其中j个放入第一行，转移策略如代码中注释所示。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2500;
int dp[maxn][maxn];//dp[i][j]表示前i个数放其中j个到第一行的方案数;
int main()
{
int i,j;
memset(dp,0,sizeof(dp));
dp[1][1]=1;//1肯定放到第一行(若放到第二行不可能比第一行大)
//维护dp表的下三角即可(j>i的上三角无意义)
//dp策略:
//1.数字放在第一行肯定可以,后面遍历的数字越来越大;
//2.数字放在第二行的条件是目前第一行的数字比第二行多,
// 因为若目前少,则之后肯定得有更大的数放到第一行,与要求冲突
for(i=2;i<=2020;i++)
{
for(j=1;j<=i;j++)
{
dp[i][j]=(dp[i][j]+dp[i-1][j-1])%2020;//放到第一行;
if(i-j<=j)//i-j为放第二行的数字数,即放第二行的数字数小于第一行的数字数的情况(此时i是正要遍历的,所以等号可取)
{
//放到第二行;
dp[i][j]=(dp[i][j]+dp[i-1][j])%2020;
}
}
}
printf("%d\n",dp[2020][1010]);
return 0;
}
//ans==1340
ans:1340
E. 完美平方数
【问题】
如果整个整数X本身是完全平方数，同时它的每一位数字也都是完全平方数，我们就称X是完美平方数。 前几个完美平方数是 0、1、4、9、100、144…
请你计算第 2020 个完美平方数是多少？
【解题】
以为直接暴搜就可以，没想到第2020个这么大，暴搜出不来…待更…
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
ll i;
int tot=7;//现在已找到第7个(0,1,4,9,49,100,144);
i=13;//12*12==144,从13*13开始即可
ll ans;
while(tot<2020)
{
ll num=i*i;
while(num!=0)
{
ll now=num%10;
if(now!=0&&now!=1&&now!=4&&now!=9)//数位不是完全平方数
{
break;
}
num/=10;
}
if(num==0)
{
tot++;
//printf("%d\n",tot);
}
if(tot==2020) ans=i*i;
i++;
}
printf("%lld\n",ans);
return 0;
}
//ans:
ans:
程序题
F. 解码
【问题】
小明有一串很长的英文字母，可能包含大写和小写。
在这串字母中，有很多连续的是重复的。小明想了一个办法将这串字母表达得更短：将连续的几个相同字母写成字母 + 出现次数的形式。 例如，连续的5个a，即aaaaa，小明可以简写成a5（也可能简写成 a4a、 aa3a 等）。
对于这个例子：HHHellllloo，小明可以简写成 H3el5o2。为了方便表达，小明不会将连续的超过9个相同的字符写成简写的形式。
现在给出简写后的字符串，请帮助小明还原成原来的串。
【解题】
这题也是思路很直接，若是数字再补上num-1个字母即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=105;
char s1[maxn];
char s2[maxn*maxn];
int main()
{
int i,j;
scanf("%s",s1);
char now=s1[0];
s2[0]=now;
int len=0;
for(i=1;i<strlen(s1);i++)
{
if(s1[i]>='0'&&s1[i]<='9')
{
for(j=1;j<s1[i]-'0';j++)
{
s2[++len]=now;
}
}
else
{
now=s1[i];
s2[++len]=now;
}
}
s2[++len]='\0';
printf("%s\n",s2);
return 0;
}
G. 走方格
【问题】
在平面上有一些二维的点阵。
这些点的编号就像二维数组的编号一样，从上到下依次为第1至第n行， 从左到右依次为第1至第m列，每一个点可以用行号和列号来表示。 现在有个人站在第1行第1列，要走到第n行第m列。只能向右或者向下走。
注意，如果行号和列数都是偶数，不能走入这一格中。
问有多少种方案。
【解题】
经典DP计数题，加了一个行号列号偶数不能走的限制。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50;
int dp[maxn][maxn];
int main()
{
int i,j;
int n,m;
scanf("%d%d",&n,&m);
if(n%2==0&&m%2==0) printf("0\n");
else
{
memset(dp,0,sizeof(dp));
dp[1][1]=1;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(i%2==0&&j%2==0) dp[i][j]=0;
else
{
dp[i][j]=max(dp[i][j],dp[i-1][j]+dp[i][j-1]);
}
}
}
printf("%d\n",dp[n][m]);
}
return 0;
}
H. 整数小拼接
【问题】
给定一个长度为n的数组A1,A2,···,An。你可以从中选出两个数Ai和Aj(i不等于j)，然后将Ai和Aj一前一后拼成一个新的整数。例如12和345可以拼成12345或34512。注意交换Ai和Aj的顺序总是被视为2种拼法，即便是Ai=Aj时。
请你计算有多少种拼法满足拼出的整数小于等于 K。
【解题】
将各数字以字符串形式输入，按长度排序，对每次遍历得到的两个数字，若两数字的长度之和小于K的长度，直接ans+2，若两数的长度之和大于K的长度，直接break出遍历(因为按长度排序了，现在的长度大于了K，之后的长度肯定也大于K)，这样其实是O(n^2)+一点优化（对于n为10 ^ 5的数据量其实是可以卡的，此处有没有更优的方法？）
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=1e5+6;
typedef long long ll;
struct node{
char s[20];
int len;
}a[maxn];
char str[20];
bool cmp(node a,node b)
{
return a.len<b.len;
}
ll get_value(char* s)
{
ll value=0;
for(int i=0;i<strlen(s);i++)
{
value=value*10+s[i]-'0';
}
return value;
}
int main()
{
int i,j,k;
int n;
/*
以字符串形式输入:
若len<lenk,直接选;
若len==lenk再判断;
若len>lenk直接出来;
*/
scanf("%d %s",&n,str);
int l=strlen(str);
for(i=1;i<=n;i++)
{
scanf("%s",&a[i].s);
a[i].len=strlen(a[i].s);
//printf("%s",a[i].s);
}
ll ans=0;
ll str_v=get_value(str);
//printf("%lld\n",str_v);
sort(a+1,a+1+n,cmp);
for(i=1;i<=n;i++)
{
bool fin=false;
for(j=i+1;j<=n;j++)
{
if(a[i].len+a[j].len<l)
{
ans+=2;
}
else if(a[i].len+a[j].len==l)
{
ll v1=get_value(a[i].s);
ll v2=get_value(a[j].s);
ll va=v1*pow(10,a[j].len)+v2;
ll vb=v2*pow(10,a[i].len)+v1;
if(va<=str_v) ans++;
if(vb<=str_v) ans++;
}
else
{
fin=true;
break;//因为按长度从小到大排,现在不行之后的肯定也不行;
}
}
if(fin) break;
}
printf("%lld\n",ans);
return 0;
}
I. 超级胶水
【问题】
小明有n颗石子，按顺序摆成一排。他准备用胶水将这些石子粘在一起。每颗石子有自己的重量，如果将两颗石子粘在一起，将合并成一颗新的石子，重量是这两颗石子的重量之和。
为了保证石子粘贴牢固，粘贴两颗石子所需要的胶水与两颗石子的重量乘积成正比，本题不考虑物理单位，认为所需要的胶水在数值上等于两颗石子重量的乘积。
每次合并，小明只能合并位置相邻的两颗石子，并将合并出的新石子放在原来的位置。
现在，小明想用最少的胶水将所有石子粘在一起，请帮助小明计算最少需要多少胶水。
【解题】
这道题第一眼是贪心，第二眼是区间DP，但瞄了一下数据范围，贪心或区间DP应该都不能拿满(估计O(n^2))，手算了一波好像按照花费是乘积，重量变成两者之和这种约束是无论怎么选总花费都一样的…都为各重量两两乘积的和。
数学归纳法证明：
设总花费为f
当n=2时，设石头重量分别为a,b，则f=a*b正确;
当n=3时，设石头重量分别为a,b,c，
则所有合并方式分别为:
f1=a*b+(a+b)*c=a*b+a*c+b*c;
f2=a*c+(a+c)*b=a*b+a*c+b*c;
f3=b*c+(b+c)*a=a*b+a*c+b*c;
f=f1=f2=f3，正确;
假设当n=k时结论正确,设石头重量分别为a1,a2,...ak
即f=a1*a2+a1*a3+...+a1*an+...+a(k-1)*ak
当n=k+1时，设石头重量分别为a1,a2,...ak,a(k+1)
无论将a(k+1)在哪一步进行合并，
其都可以看成是a(k+1)与ai的一个置换(1<=i<=k)
设a(k+1)与其中的ai进行了置换，
石头表示为(a1,a2,...,a(k+1),...ak),ai
对于前面括号中的部分，由假设的n=k的情况可以得到:
f1=a1*a2+...a1*an+...a(k+1)*a(i+1)+...+a(k+1)*ak+...+a(k-1)*ak
对前面括号的合并后可以看成剩两堆石头X,ai，
其中X的重量为a1+a2+...+a(k+1)+...+ak
对数量为2的情况，
花费f2=(a1+a2+...+a(k+1)+...+ak)*ai
=a1*ai+a2*ai+...ak*ai+a(k+1)*ai
故当n=k+1时，
总花费为f=f1+f2=a1*a2+...+a1*a(k+1)+...+ak*a(k+1)
因此假设正确。
故得到各重量两两乘积的和即可，时间复杂度O(n)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+6;
typedef long long ll;
ll num[maxn];
ll sum,ans;
int main()
{
int i,j;
int n;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&num[i]);
}
sum=num[1];
ans=0;
for(i=2;i<=n;i++)
{
ans+=sum*num[i];
sum+=num[i];//前i个石头的重量和;
}
printf("%lld\n",ans);
return 0;
}
J. 网络分析
【问题】
小明正在做一个网络实验。
他设置了n台电脑，称为节点，用于收发和存储数据。
初始时，所有节点都是独立的，不存在任何连接。
小明可以通过网线将两个节点连接起来，连接后两个节点就可以互相通信了。两个节点如果存在网线连接，称为相邻。
小明有时会测试当时的网络，他会在某个节点发送一条信息，信息会发送到每个相邻的节点，之后这些节点又会转发到自己相邻的节点，直到所有直接或间接相邻的节点都收到了信息。所有发送和接收的节点都会将信息存储下来。 一条信息只存储一次。
给出小明连接和测试的过程，请计算出每个节点存储信息的大小。
【解题】
并查集+路径压缩减少搜索量，在进行1号操作时，并查集检查两个节点是否连通，若不连通则并查集连接起来；在进行2号操作时，遍历/bfs/dfs一遍检查连通节点加上相应的信息值。（是否有更好做法？）
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e4+5;
const int maxm=1e5+5;
int f[maxn];
int store[maxn];
int find(int x)//并查集+路径压缩
{
while(x!=f[x])
{
f[x]=f[f[x]];
x=f[x];
}
return x;
}
int main()
{
int i,j;
int n,m;
int op,msg1,msg2;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
f[i]=i;
store[i]=0;
}
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&op,&msg1,&msg2);
int fa=find(msg1);
if(op==1)//1.连接节点操作;
{
int fb=find(msg2);
if(fa!=fb) f[fa]=fb;
}
else //2.所联通部分节点都增加信息;
{
for(j=1;j<=n;j++)
{
int fb=find(j);
if(fa==fb) store[j]+=msg2;
}
}
}
for(i=1;i<=n;i++)
{
if(i!=n) printf("%d ",store[i]);
else printf("%d\n",store[i]);
}
return 0;
}
转载：https://blog.csdn.net/weixin_44756457/article/details/108880397