2023级HAUT新生周赛（四）题解
A.我要成为复数高手
按照复数加法的运算规则运算即可，注意一些复数有简写形式：
1.当虚数的系数为1/-1时系数省略，
2.当实数部分的系数为0时，实数部分省略。
3.当虚数部分的系数为0时，虚数部分省略。
5.当虚数部分的符号为负数时，加号省略。
#include<stdio.h>
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int a, b,c,d,a1,a2;
scanf("%d %d %d %d",&a,&b,&c,&d);
a1 = a + c;
a2 = b + d;
if(a1==0)//实数部分系数为0
{
if(a2==1)
{
printf("i\n");
}
else if(a2==-1)
{
printf("-i\n");
}
else if(a2==0)//虚数系数的特殊情况。
{
printf("0\n");
}
else
{
printf("%di\n",a2);
}
}
else//实数部分为0
{
printf("%d",a1);
if(a2==0)
{
printf("\n");
}
else if(a2==-1)
{
printf("-i\n");
}
else if(a2==1)
{
printf("+i\n");
}//虚数系数的特殊情况。
else
printf("%+di\n",a2);
}
}
return 0;
}
B.依稀记得，那是一个烟雨蒙蒙的早晨。
签到题，根据自由落体公式输出5*t*t即可
#include<stdio.h>
int main()
{
int t;
scanf("%d",&t);
printf("%d\n",5*t*t);
return 0;
}
C.现在是幻想时刻。
考虑贪心，假设在第i个时刻卖出，那么一定在前i天股票价格最低时买入最佳，注意，如果最小值都大于现在剩余的钱，那么这个时候无法买入。枚举天数，记录前缀中的最小值，记录这个过程中的最大值即可。
#include<stdio.h>
int main()
{
int n,k;
scanf("%d %d",&n,&k);
int ans = 0;
int min1 = 1e7;
int x;
for(int i = 0;i<n;++i)
{
scanf("%d",&x);
if(x<=min1)
min1 = x;
if(min1<=k)
if(x-min1>=ans)
ans = x-min1;
}
printf("%d\n",ans);
return 0;
}
D 命运之夜
与运算：如果两个数a，b的第i位都为1，那么与运算之后，答案的第i位也为1.
或运算：如果两个数a，b的第i为中存在1个1，那么或运算之后，答案的第i位为1；
考虑a,b第i位的四种情况
- 1 1：与运算结果第i位为1，或运算结果第i位为1.
- 1 0 :与运算结果第i位为0，或运算结果第i位为1.
- 0 1：与运算结果第i位为0，或运算结果第i位位1.
- 0 0：与运算结果第i位为0，或运算结果第i为为0.
不难发现，与运算和或运算的答案内1的个数和与运算前a，b两数的1的个数和相同，
那么，我们可以先预处理出来每个数的二进制位含多少1，cnt数组记录一下，然后枚举以它为i时，大于i的部分有多少下标满足条件（有多少数的二进制中1的个数大于等于k-cnt[i]）。让ans+=满足k-cnt[i]的个数即可。
#include<stdio.h>
long long arr[110000];
int cnt[90];//cnt[i]表示有多少数的二进制位中1的个数等于i。
int crr[110000];////crr[i]表示第i个数的二进制位中有多少1。
long long sum[90];//sum[i]表示有多少数的二进制位中1的个数大于等于i。
int main()
{
int n,k;
scanf("%d %d",&n,&k);
for(int i = 1;i<=n;++i)
{
scanf("%lld",&arr[i]);
int cnt1 = 0;
for(int j = 0;j<=30;++j)//计算每个数中有多少1
{
int c = (1<<j);
if(c&arr[i])
{
cnt1++;
}
}
crr[i] = cnt1;
cnt[cnt1]++;
}
for(int i = 70;i>=0;--i)
{
sum[i] = sum[i+1]+cnt[i];
}
int c = 0;
long long ans = 0;
for(int i = 1;i<=n;++i)
{
int t = k-crr[i];
for(int j = crr[i];j>=0;--j)//将自身减去。保证当前sum[i]表示的是大于i中有多少数的二进制位中1的个数大于等于i。避免重复。
{
sum[j]--;
}
if(t<0)
t = 0;
//cout<<t<<endl;
ans+=sum[t];
}
printf("%lld\n",ans);
return 0;
}
E 大富翁！启动！
影响最终收益的有当前所处的位置和当前已经获取的金币。
考虑动态规划，dp[i]表示到第i个点时小A可以获取多少收益。那么dp[i]的最大值会从dp[i-1]，dp[i-2],dp[i-3],dp[i-4],dp[i-5],dp[i-6]中的最大值+第i格获取的金币。dp[n+1]即为终点。
注意，由于获取的金币可以为负数，需要初始化dp[i]为最小值。
#include<stdio.h>
long long arr[110000];
long long dp[110000];
int main()
{
int n;
scanf("%d",&n);
for (int i = 1; i <= n; ++i)
{
scanf("%lld",&arr[i]);
}
for (int i = 1; i <= n+10; ++i)
{
dp[i] = -1e12;
}
for (int i = 1; i <= n + 1; ++i)
{
for (int j = i - 1; j >= 0 && j >= i - 6; --j)
{
if(dp[j]>dp[i])
dp[i] = dp[j];
}
dp[i] += arr[i];
}
printf("%lld\n",dp[n+1]);
return 0;
}
F.历经千辛万苦，只为得到你
签到题，直接输出即可。
#include<stdio.h>
int main()
{
printf("AC!!!\n");
return 0;
}
G.火柴的奇怪用途.
由于n很小，考虑暴力，x，y，那么当n=24的时候，x，y最大可能是多少呢？由于1花费的火柴数最少，那么让x,y均为1111时，此时已经消耗16火柴，而且此时z的位数最小，但仍一共需要28根火柴，那么x，y一定不大于1111，从0开始枚举x，y时间复杂度为n方，可以通过这道题。
#include<stdio.h>
int main()
{
int a[2333]={0},b;
int c[10]={6,2,5,5,4,5,6,3,7,6};//预处理每个个数需要多少火柴。
int ans=0,i,p;
scanf("%d",&b);
for(i=0;i<=2222;i++)
{
p=i;
if(p==0)
a[p] = 6;
while(p>0)//求每个数所用的火柴棒
{
int d = p%10;
a[i]=a[i]+c[d];
p=p/10;
}
}
for(int i=0;i<=1111;i++)
{
for(int j=0;j<=1111;j++)
if(a[i]+a[j]+a[i+j]+4<=b)ans++;//X,Y,Z,加号与等号。
}
printf("%d",ans);
return 0;
}
H.奇怪的魔法书
s2串很小，直接暴力匹配即可。
如果ba可以等于s2，那么一定有ba的长度=s2的长度。
可以枚举后缀b，然后求出前缀a。然后把ba串与s2比较，如果一样，那么就让ans++即可。
#include<stdio.h>
#include<string.h>
int main()
{
char arr[110000];
char brr[110];
scanf("%s %s",arr,brr);
int m = strlen(brr);
int n = strlen(arr);
int ans = 0;
for(int i = 1;i<m;++i)//枚举后缀长度
{
int p = m-i;
char drr[1100] ={0};
int cnt = 0;
for(int j = 0;j<i;++j)
{
drr[cnt] = arr[n-i+j];
cnt++;
}
for(int j = 0;j<p;++j)
{
drr[cnt] = arr[j];
cnt++;
}
if(strcmp(drr,brr)==0)
{
ans++;
}
}
printf("%d\n",ans);
return 0;
}