目录
第一题.满足约束
第二题:传递信息
第三题:无线替换
第四题:环球旅行
第五题:求和游戏
第六题:大相径庭数组
总结:其实这次考试主要都是一些思维性的题集,并没有过难的东西,只要能找到其中的式子,每道题都可以很简单的求解出来,而且计算机本身就是与数学有很大的关系,其中简单来说,唯有坚持下来,掌握思维,但是主要也是凭借个人的努力,若不努力,至强者也有可能变为弱者,才可在计算机领域做出一番贡献。
水题:国际象棋(超级水题建议直接跳过)
题解:很水的一道题,没什么技术含量,就只需要判断那个字母没出现过,进行判断就可以了
(竖着移动是字母不变数字变,横着移动是数字不变字母变,到了原位置分别判断一下即可)
AC代码:
#include <stdio.h>
#include <stdlib.h>
char a,b;
char c[9]={'1','2','3','4','5','6','7','8','\0'};//存储棋盘的纵坐标
char d[9]={"abcdefgh"};//存储棋盘的横坐标
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf(" %c%c",&a,&b);//输入当前落子的坐标
for(int i=0;i<8;i++)
{
if(d[i]!=a)//输出横向移动的可能
{
printf("%c%c\n",d[i],b);
}
}
for(int i=0;i<8;i++)
{
if(c[i]!=b)//输出纵向移动的可能
{
printf("%c%c\n",a,c[i]);
}
}
}
return 0;
}
第一题.满足约束
题解:其实这道题就是一道小学思维题,去寻找一个区间内符合的数的多少,对于1条件,我们可以把它视为前面的卡的范围,若有不同的1,则将对应的最大值更新,对于2条件,我们应当视为后面的卡的范围,若有不同的2,则应将其对应的最小值更新,这样才能卡到最精确的范围,对于3,我们只需要看3的数字有多少在这个范围内,相应减去就可以得到结果,话不多说
AC代码:
#include <stdio.h>
#include <stdlib.h>
int a[105];//约束条件类型
int x[105];//约束条件对应的数字
int c[105];//3类型中放的数字
int max(int x,int y)//用于更新1的最大值
{
return x>y?x:y;
}
int min(int x,int y)//用于更新2的最小值
{
return x<y?x:y;
}
int main()
{
int t;
scanf("%d",&t);//输入测试样例的数量
while(t--)
{
int n;
scanf("%d",&n);输入有多少组数
int k=0;
int sx=0,fx=0x3f3f3f3f;//sx代表范围的左位置,fx代表范围的右位置
for(int i=0; i<n; i++)
{
scanf("%d %d",&a[i],&x[i]);
if(a[i]==1)
{
sx=max(x[i],sx);//更新范围的左端
}
if(a[i]==2)
{
fx=min(x[i],fx);//更新范围的右端
}
if(a[i]==3)
{
c[k++]=x[i];//存储类型3的元素
}
}
int count=fx-sx+1;//定义数字的数量count
for(int i=0;i<k;i++)
{
if(c[i]>=sx&&c[i]<=fx)
{
count--;//只要类型3的元素在这个范围内有就要-1
}
}
if(count<0)
{
count=0;//有可能会出现小于0的情况
}
printf("%d\n",count);
}
return 0;
}
第二题:传递信息
题解,也是很简单的一道思维题目,只需要计算每次间隔到底是要关机还是开机等时间
计算发完消息最小的耗电量,然后和电量作对比即可
#include <stdio.h>
#include <stdlib.h>
unsigned long long m[200005];//用于统计每次发消息的时间点
unsigned long long min(unsigned long long x,unsigned long long y)
{
return x<y?x:y;//取小值
}
int main()
{
int t;
scanf("%d",&t);//输入测试样例
while(t--)
{
unsigned long long n,f,a,b;//分别输入消息数,剩余电量,单位时间耗电,还有关机所用电量
scanf("%llu%llu%llu%llu",&n,&f,&a,&b);
for(int i=1; i<=n; i++)
{
scanf("%llu",&m[i]);//输入每条消息的时间点
}
unsigned long long t=0;//定义总时间t
for(int i=0; i<n; i++)
{
t+=min((m[i+1]-m[i])*a,b);//每次取时间段的最小耗电量
}
if(f>t)//若剩余电量大于最小耗电量,那么就可以发送完毕
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
第三题:无线替换
题解,纯思维题目,没有任何技巧可言,只需要判断三种情况
1.什么时候有无限种情况,当下面的字符串带有a且长度不为1时可以无限延伸,从而实现无限种可能
2,.什么时候会有一种可能呢,那就是下面的字符串是a,且长度为1
3.当时正常情况的时候我们可以将底下的串当成一个整体,进行插入,若至少替换一个的话,就可以找到规律,写出通项式存储在数组中,最后加上不变的情况就好,但是要注意数组要开的大一点,不然有些数据过不去
话不多说,看AC代码
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
unsigned long long dp[51];//用于存储上面字符串长度对应的结果数
unsigned long long jie(unsigned long long n)//将数据开的大了一点
{
dp[1]=1;
for(int i=2;i<=50;i++)
{
dp[i]=dp[i-1]*2+1;
}
return dp[n];//返回对应的结果
}
int main()
{
int q;
scanf("%d",&q);
while(q--)
{
char s[60];
char t[60];
scanf("%s",s);//输入对应的字符串
scanf("%s",t);
getchar();
unsigned long long len1=strlen(s);
unsigned long long len2=strlen(t);
unsigned long long count=0,flag=0;
for(int i=0; i<len2; i++)
{
if(t[i]=='a'&&len2!=1)
{
flag=1;
printf("-1\n");//第一种情况的特判
break;
}
if(t[i]=='a'&&len2==1)
{
flag=1;
printf("1\n");//第二种情况的特判
break;
}
}
if(flag==0)
{
count=jie(len1);
printf("%llu\n",count+1);//普通情况的求解
}
}
return 0;
}
第四题:环球旅行
题解,这题需要用到前缀和
#include <stdio.h>
#include <stdlib.h>
unsigned long long a[100005], b[100005], c[100005];
// 定义比较大小的函数
int max(int x, int y)
{
return x > y ? x : y;
}
// 定义比较大小的函数
int min(int x, int y)
{
return x < y ? x : y;
}
int main()
{
int n, m;
// 输入 n 和 m 的值
scanf("%d%d", &n, &m);
// 输入每一列的高度
for (int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
}
// 计算向上和向下移动时的伤害
for (int i = 1; i <= n - 1; i++)
{
b[i] = b[i - 1] + max(a[i] - a[i + 1], 0);
c[i] = c[i - 1] + max(a[i + 1] - a[i], 0);
}
while (m--)
{
int s, t;
// 输入移动的起始和目标位置
scanf("%d%d", &s, &t);
if (s < t)
{
// 输出向上移动的伤害
printf("%llu\n", b[t - 1] - b[s - 1]);
}
else
{
// 输出向下移动的伤害
printf("%llu\n", c[s - 1] - c[t - 1]);
}
}
return 0;
}
第五题:求和游戏
Summation Game
题解:首先需要考虑的是爱丽丝该删去哪些数,因为要去最优解,那么肯定是要去删除最大的值,因为假如把最大值留着,这个鲍勃肯定回下黑手乘-1,使其变为最小值,不利于爱丽丝的使和最大的策略,对应的结果应当是s[n]-s[n-k]
对于鲍勃而言,修改x的个数的话,我们需要考虑修改剩下的较大的数,这样才能有最优策略,使和最小,那么对应的结果为2*s[max(n-i-x,0)]-s[n-i]
因此我们可以得到求解这题的思路,首先就是现将数组排序,因为爱丽丝和鲍勃都是对最大的部分进行操作,因此我们可以用i去遍历爱丽丝的选择,从去掉0个遍历到去掉k个,即我们的循环从
n-k,一直遍历到k,不变的部分就是s[i-x],若是i-x小于0的话就是s[0],变动的部分就是s[i]-s[i-x],
变动的部分是鲍勃将后面的大数变为相反数,即给变动部分加个负号即可,这题有一个减少时间复杂度的部分就是用前缀和统计一下每个部分的大小,方便后面的计算
本题考点:前缀和以及排序(手写快排一直过不去,所以直接调用了C++的sort函数)
#include<bits/stdc++.h>
using namespace std;
int a[200005];
int s[200005];
int main()
{
int t;
scanf("%d",&t);//输入测试用例数量
while(t--)
{
int n,k,x;
scanf("%d%d%d",&n,&k,&x);//输入数组长度n,删除元素数量k,以及x的值
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);//输入数组元素
}
sort(a+1,a+n+1); //对数组进行排序
for(int i=1; i<=n; i++)
{
s[i]=s[i-1]+a[i];//计算前缀和
}
int sum=-0x3f3f3f3f;//初始化结果为一个较小的值
for(int i=max(0,n-k); i<=n; i++)//模拟从k取最大到k取0
{
sum=max(sum,s[max(0,i-x)]-(s[i]-s[max(0,i-x)]));//计算最大值,
//第一部分的s[max(0,i-x)]代表的是绝对不会受到影响的部分,这些直接相加即可
//第二部分是(s[i]-s[max(0,i-x)])求鲍勃这个人将会反转的数的大小,通过前缀和将后几个数的大小求出来,然后前面加个负号,代表相反数
}
printf("%d\n",sum);
}
return 0;
}
第六题:大相径庭数组
Very Different Array
题解:求最大值肯定是要用双指针去寻找前后两项的差值,具体来说,对于数组a中的第i个元素,计算它与数组b中倒数第i个元素的差的绝对值,以及它与数组b中正数第i个元素的差的绝对值,然后将这两个绝对值中较大的那个加到sum中。
考点:双指针和排序(排序还是用的sort函数,别问我为什么,问就是和上个题一样手写代码被WA了)别人都是手撕代码,我是纯被代码手撕
第一种做法:
#include <bits/stdc++.h>
using namespace std;
int a[300000];//用于存储弟弟的数组
int b[300000];//用于存储哥哥的数组
int main()
{
int t;
scanf("%d",&t);//输入测试样例的数量
while (t--)
{
int n,m;
scanf("%d%d",&n,&m);//输入弟弟和哥哥各自元素的数量
for (int i=0; i<n; i++)
{
scanf("%d",&a[i]);//输入弟弟手中的数组
}
for (int i=0; i<m; i++)
{
scanf("%d",&b[i]);//输入哥哥手中的数组
}
sort(a,a+n);//对两个数组进行升序排序
sort(b,b+m);
long long sum=0;//sum表示最终结果
for (int i = 0; i<n; i++)//遍历a数组中的每一个元素,去和b数组找出最大差值
{
sum+=max(abs(a[i]-b[m-i-1]), abs(a[i]-b[n-i-1]));//求取最大值
}
printf("%lld\n",sum);
}
return 0;
}
第二种做法:(ps:来自于我一个兄弟)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,x,y,temp;
scanf("%d",&n);
while(n--){
set<int>a,b;
set<int>::iterator l1,l2,r1,r2; //众所周知set里只能有一个重复元素
map<int,int>maps1,maps2;//原本想用数组当作桶的但是ai和bi太大了只能映射了
long long sum=0;//数据看起来还是比较大的
scanf("%d %d",&x,&y);
for(int i=1;i<=x;i++){
scanf("%d",&temp);
maps1[temp]++;//若同一个元素有多个则记录一下
a.insert(temp);//将元素插入容器a
}
for(int i=1;i<=y;i++){
scanf("%d",&temp);
maps2[temp]++;
b.insert(temp);
}
while(!a.empty()){//思路证明过程不详
l1=a.begin(),l2=b.begin(),r1=a.end(),r2=b.end();//l1,l2,r1,r2分别是两个数组的最小和最大元素
r1--,r2--;//至于为什么减减是因为end返回的是最后一个元素的下一个位置的迭代器
if(abs(*r1-*l2)>abs(*l1-*r2)){
sum+=(int)abs(*r1-*l2);
maps1[*r1]--;
maps2[*l2]--;
if(maps1[*r1]==0)a.erase(*r1);//如果删除到数量为0了就在set中将其删除
if(maps2[*l2]==0)b.erase(*l2);
}
else{
sum+=(int)abs(*l1-*r2);
maps1[*l1]--;
maps2[*r2]--;
if(maps1[*l1]==0)a.erase(*l1);
if(maps2[*r2]==0)b.erase(*r2);
}
}
printf("%lld\n",sum);
}
return 0;
}
总结:其实这次考试主要都是一些思维性的题集,并没有过难的东西,只要能找到其中的式子,每道题都可以很简单的求解出来,而且计算机本身就是与数学有很大的关系,其中简单来说,唯有坚持下来,掌握思维,但是主要也是凭借个人的努力,若不努力,至强者也有可能变为弱者,才可在计算机领域做出一番贡献。
寄语:(ps:写给我女朋友的)(个位看官建议跳过这部分)
朝朝思,夜夜看
我对你的思念如同那北极星一样,亘古不变
你眼中有春与秋,胜过我爱过见过的一切山川与河流
我走过许多地方
我见过春日夏风 秋叶冬雪
也踏遍南水北山 东麓西岭
都没什么好看的
都不及那个黄昏,冲我展眉一笑的你