【清华软院机试】2018年预推免机试及题解
文章目录
-
-
- 题目分类
- 1.时间转换
- 2.麦森数
- 3.戳气球
-
题目来自这位博主的回忆 【链接】
部分内容在半猜测半搜索下，找到了原题，并给出了对应的链接，可以在里面提交代码验证。
题目分类
- 时间转换 ：模拟题
- 麦森数 ： 高精度乘法+快速幂
- 戳气球 ：区间DP
1.时间转换
已知某世界时间为以下进制：
100秒1分钟
100分钟1小时
10小时1天
100天1个月
10个月1年
且人类的1天=该世界1天（这个条件巨坑，一小时没看到QAQ）
输入人类世界的一天，格式如下：
h: m:s d.m.y
其中2000<=y<=50000
输出某世界对应的时间，格式如下：
h: m:s d.m.y
其中人类世界的0:0:0 1.1.2000是某世界的0:0:0 1.1.0
题解 ：
闰年的判定还是需要会。能4不能100，或能400为闰年。然后天以上和天以下分开算，并化为对应的月年和分秒。这个模拟题相对之前较简单，但闰年的区分还是要注意一下。
#include<cstdio>
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
using namespace std;
int month[12]={31,28,31,30,31,30,31,31,30,31,30,31};
int countmonth(int i,int year)
{
int tmp=0;
for(int j=0;j<i;j++)
tmp+=month[j];
if((year%4==0&&year%100!=0)||year%400==0)
if(i>2)
tmp+=1;
return tmp;
}
int countyear(int year)
{
int tmp=0;
for(int i=0;i<year;i++)
if((year%4==0&&year%100!=0)||year%400==0) tmp+=366;
else tmp+=365;
return tmp;
}
int main()
{
int hh,hm,hs,hda,hmo,hye;
int ah,am,as,ada, amo, aye;
scanf("%d:%d:%d %d.%d.%d",&hh,&hm,&hs,&hda,&hmo,&hye);
//1.1 2000对应 1.1 0,所以年需要减2000，1月有31天，所以需要减去（31-100）天
hye-=2000;
int tmpd=countyear(hye)+countmonth(hmo,hye)+hda+69;
float tmpd2=(1.0*(1.0*(1.0*(1.0*hs/60)+hm)/60)+hh)/24;
aye=tmpd/1000;
tmpd=tmpd%1000;
amo=tmpd/100;
ada=tmpd%100;
int tmpd3=tmpd2*100000;
ada+=tmpd3/100000;
tmpd3=tmpd3%100000;
ah=tmpd3/10000;
tmpd3=tmpd3%10000;
am=tmpd3/100;
as=tmpd3%100;
printf("%d:%d:%d %d.%d.%d\n",ah,am,as,amo,ada,aye);
return 0;
}
// 12:0:0 1.1.20002.麦森数
洛谷（P1045）：【题目链接】
形如 2^{P}-1 的素数称为麦森数，这时 P 一定也是个素数。但反过来不一定，即如果 P 是个素数， 2^{P}-1
不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是
P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。 任务：输入 P （ 1000<P<3100000
），计算 2^{P}-1 的位数和最后500位数字（用十进制高精度数表示）
输入格式 ：
文件中只包含一个整数 P （ 1000<P<3100000 ）
输出格式 ：
第一行：十进制高精度数 2^{P}-1 的位数。 第2-11行：十进制高精度数 2^{P}-1 的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）不必验证 2^{P}-1 与 P 是否为素数。
输入样例#1 ：
1279
输出样例#1 ：
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087
题解 ：
先进行每个位置上的计算，然后处理进位问题。算法需要使用快速幂。进位使用反向存储的序列，容易处理。（反正我写的自闭了，虽然并没有非常超纲）
#include<cstdio>
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
using namespace std;
//高精度乘法计算
int mul(int a[],int b[])
{
int c[1020];
fill(c,c+1020,0);
for(int i=0;i<=500;i++)
for(int j=0;j<=500;j++)
c[i+j]+=a[i]*b[j];
for(int i=0;i<=500;i++)
if(c[i]>=10)
{
c[i+1]+=c[i]/10;
c[i]=c[i]%10;
//printf("%d",c[i]);
}
for(int i=0;i<=500;i++)
a[i]=c[i];
}
int main()
{
int n;
scanf("%d",&n);
cout<<floor(log10(2)*n+1)<<endl;
//快速幂
int ans[501],b[501];
fill(ans,ans+501,0);
fill(b,b+501,0);
ans[0]=1;
b[0]=2;
int t=n;
//这是一个比较好的快速幂模板
while(t!=0)
{
if(t%2) mul(ans,b);
t=t/2;
//2^16需要2^8和2^8相乘才能得到，所以是bb
mul(b,b);
}
ans[0]-=1;
int k=0;
for(int i=500-1;i>=0;i--)
{
if(k%50==0&&k!=0) printf("\n");
printf("%d",ans[i]);
k++;
}
return 0;
}3.戳气球
leetcode hard题 ：【题目链接】
题解 ：
dp[j][i]=max(dp[j][i],dp[j][k]+dp[k][i]+a[k]*a[i]*a[j])，这是对应的状态转移方程。
- 边界填充：填充1，可以让区间分解时，最小的区间 如5 也可以换算成 1 5 1 这样的区间结构，从而进行对应的计算。
- 方程解释：dp[j][i]表示从j-i的区间里，最后一个被戳破时区间的最大得分（不包括j,i） 。方程表示，如果最后一个被戳破的为k号，则计算k号得分（k最后被戳破，所以j,i为其相邻气球 ）,在k戳破前，dp[j][k]和dp[k][i]为互不干扰的两个子问题（无论哪个被戳破，均不会对另一个问题造成影响）。
- 遍历顺序：由转移方程得知，j-i的区间需要先求出j-k,k-i的区间，所以需要一个从区间短到区间长的遍历。其他并没有特殊要求，均可做出答案
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
using namespace std;
int main()
{
int n;
int a[999],dp[499][499];
memset(dp,0,sizeof(dp));
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
a[n+1]=a[0]=1;
for(int len=3;len<=n+2;len++)
for(int i=n+1;i-len+1>=0;i--)
{
int j=i-len+1;
for(int k=j+1;k<i;k++)
dp[j][i]=max(dp[j][i],dp[j][k]+dp[k][i]+a[k]*a[i]*a[j]);
}
printf("%d\n",dp[0][n+1]);
return 0;
}
// 4
// 3 1 5 8