【比赛回顾】2020广工文远知行杯新生程序设计竞赛(初赛)
【比赛回顾】2020广工文远知行杯新生程序设计竞赛(初赛)
写在前面：
已经更新完除E和F以外的题解（因为这两道我没有时间做了，以后抽空做完后补充）。可能我的题解并不是最优的，欢迎交流和讨论~
A-倒水
问题分析：
既然不想装无限的水，为啥要放阳台…第一眼看到这个题目，感觉和19年决赛的 D-城市的税金题型类似，但仔细一看，这道题就太简单了。只要倒掉就清零，这里我们以记录下倒下的那一秒的时间做清零标志。那么每次查看的时候就用现在的时间减去标记的时间就好咯
AC代码：
#include <bits/stdc++.h>
using namespace std;
//用来标记桶为空的时间 默认0秒时全是空的
int a[100001];
int main()
{
int n,q,t,x;
int op;
cin >> n >> q;
while ( q-- )
{
cin >> op >> t >> x;
if ( op==1 )
//记录倒掉的时间
a[x] = t;
else
cout << t-a[x] << endl;
}
return 0;
}
B-秋夜easy
问题分析：
这孩子力气真大，这枣树枣子也真多hhh，这两个树我们知道，要想使它们数量一样，就一定要使先A多枣子的那一颗树，使它的枣子变少，不然永远都不可能达成要求。故一开始要先判断那颗树枣子更多 然后A一下它，再判断一下符不符合要求，符合就输出，不符合再重复这个步骤。
AC代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while ( t-- )
{
int a,b;
cin >> a >> b;
int ans=0;
while ( a!=b )
{
if ( a>b )
a /= 2;
else
b /= 3;
ans++;
}
cout << ans << endl;
}
return 0;
}
C-秋夜hard
问题分析：
震惊了，到底是怎么A能够使果子变多的！！hhh看到了一条致富之道。emmmm，对比一下上一题，这两个树我们知道，其实没有区别，因为操作方式都是一样的，而不像上一题一棵树/2一棵树/3。再看下题目要求，emmmm x的平方，那不就A出界了么（即超过10000）那A出界了是不能操作还是最多按10000算呢？
说实话当时想这个问题想了很久，但…突然想了想，只要数字大于100取平方就会A出界，那其实就很没用欸，如果取平方这个操作，那这道题的样例就有bug了，因为只要大于100的两个数，分别取平方A，两下就能都爆10000，不就数量相等了么？所以说取平方这个操作只是为了迷糊你的。
然后就是与上一题一样的思路咯~
要想使它们数量一样，就一定要使先A多枣子的那一颗树，使它的枣子变少，不然永远都不可能达成要求。故一开始要先判断那颗树枣子更多 然后A一下它，再判断一下符不符合要求，符合就输出，不符合再重复这个步骤。
AC代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while ( t-- )
{
int a,b;
cin >> a >> b;
int ans=0;
while ( a!=b )
{
if ( a>b )
a = sqrt(a);
else
b = sqrt(b);
ans++;
}
cout << ans << endl;
}
return 0;
}
D-好人easy
问题分析：
因为数字比较小，所以直接暴力遍历就能出来，关于判断回文，我采用的是放入数组中，然后对称判断是否符合回文性质，下面我详细注释说明了一下
AC代码：
#include <bits/stdc++.h>
using namespace std;
int a[7];
int main()
{
int n;
cin >> n;
int i,j;
for ( i=1; i<=n; i++ )
{
//小于等于9直接输出
if ( i<=9 )
cout << i << endl;
else
{
int temp = i;
int num=0;
//计算这是几位数
while ( temp>0 )
{
num++;
temp /= 10;
}
temp = i;
//从这个数字末位取余依次放入数组中
//即将这个数字每一位依次拷贝进入数组
for ( j=num; j>=1; --j )
{
a[j] = temp%10;
temp/=10;
}
temp = i;
int mark=0;
//只用检验一半就好
for ( j=1; j<=num/2; ++j )
{
if ( a[j] != a[num-j+1] )
{
mark = 1;
//如果不相等直接跳出循环
//mark=1即不符合条件
break;
}
}
if ( mark==0 )
cout << temp << endl;
}
}
return 0;
}
E-好人hard
F-矩阵求和
G-字符串哈希
问题分析：
这是我写过最凌乱的代码了，为了AC不顾一切hhhh，其实题目并不难理解，但就是题目字太多太绕了。但其实没有什么难度，就是按照要求将文字翻译成代码而已，实际上考验的还是基本功，下面的代码我加了详细的注释
AC代码：
#include <bits/stdc++.h>
using namespace std;
//这个没有严谨的说法
//我只是为了存储后面的特殊情况，找的一个比较后的地址而已
#define k 1000
int main()
{
//s存放的是一个个单词
//其实这个2000我是随便起的
//但我很怕越界，因为题目有说最大全部字母加起来100000个
//按照特别奇葩的数据 即一个字母一个单词，最多有100000个单词
//一开始我取的是150000，可是太多了，根本运行不了
//其实应该取133333是最准确的，因为最多1000000个单词和33333个合并字符串储存空间
//我就想取小点，看能不能AC先把，就取2000了
char s[2000][254];
// 因为s不能太大，我就专门起了一个s1来临时记录拼接的单词了
char s1[2000][254];
//清零
memset ( s,0,sizeof(s) );
memset ( s1,0,sizeof(s1) );
int n;
cin >> n;
int i=1,j=1;
//读入数据
for ( i=1; i<=n; ++i )
cin >> s[i];
int times=n/3;
int index = 1;
//计算次数并逐次输出
while ( times-- )
{
//每三个单词拼接成一个临时s1
for ( i=1; i<=3; ++i )
strcat(s1[index],s[j++]);
//偷懒直接使用C++自带的反转函数
reverse(s1[index],s1[index]+strlen(s1[index]) );
//输出第一个字母
cout << s1[index][0];
//计算中间的数值有没有超
int len=strlen(s1[index]);
if ( (len-2)>9 )
{
//若大于9则计算中间位数的位数
int num=0;
while ( len>0 )
{
num++;
len/=10;
}
cout << num;
}
else
//否则就直接输出
cout << len-2;
//输出最后一个字母
cout << s1[index][strlen(s1[index])-1] << endl;
//下标加一 指向下一个拼接字符串
++index;
}
//有的情况会有余1—2个单词，分别考虑
if ( n%3 == 1 )
{
strcat(s1[k],s[j]);
//按照题目要救加上 "pmznb"
strcat(s1[k],"pmznb");
strcat(s1[k],"pmznb");
//下面的操作和上面的一模一样，其实可以封装成函数，
//但懒得考虑了hh还是copy来的快一点
reverse(s1[k],s1[k]+strlen(s1[k]) );
cout << s1[k][0];
int len=strlen(s1[k]);
if ( (len-2)>9 )
{
int num=0;
while ( len>0 )
{
num++;
len/=10;
}
cout << num;
}
else
cout << len-2;
cout << s1[k][strlen(s1[k])-1] << endl;
}
//下同余1的情况
if ( n%3 == 2 )
{
strcat(s1[k],s[j++]);
strcat(s1[k],s[j++]);
strcat(s1[k],"pmznb");
reverse(s1[k],s1[k]+strlen(s1[k]) );
cout << s1[k][0];
int len=strlen(s1[k]);
if ( (len-2)>9 )
{
int num=0;
while ( len>0 )
{
num++;
len/=10;
}
cout << num;
}
else
cout << len-2;
cout << s1[k][strlen(s1[k])-1] << endl;
}
return 0;
}
H-给钱
问题分析：
算贪心算法？每次肯定取能够顶值得最大面值的啦，然后剩余得用1元补上去，下面同样有详细的注释。
AC代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while ( t-- )
{
int a,b,n,s;
cin >> a >> b >> n >> s;
//先计算最少用多少个n可以凑成s
int times=s/n;
if ( times<=a )
{
//如果小于a，就取times张就好，计算缺值用b能否补齐，能则符合题意
if ( times*n+b >= s )
cout << "YES" << endl;
else
cout << "NO" << endl;
}
else
{
//如果大于a，那么就把全部的n砸进去，然后计算这个大缺值能否用b补齐
if ( a*n+b >= s )
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
return 0;
}
I-粘土人
问题分析：
要求要最远，那么就是把手办往两边挪动咯，记得要小心注意顶位的情况，即到达最左和最右不能再移动了。
AC代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,x,a,b;
int t;
int maxmove;
int temp;
cin >> t;
while ( t-- )
{
cin >> n >> x >> a >> b;
//就默认a大把，这样子后面好操作少讨论
if (a<b)
{
temp = a;
a = b;
b = temp;
}
//计算最多两个手办都移动到最左和最右的步数
//n-a 和 b-1两者相加即是结果
maxmove = n-a+b-1;
//如果大于就直接输出，因为可以不挪完全部操作
if ( x>=maxmove )
cout << n-1 << endl;
else
cout << a-b+x << endl;
}
return 0;
}
J-dcnb
题解略
写在后面：
这一次的初赛可能是最简单的了吧，比第一次月赛和第二次月赛相比就小巫见大巫了，直接A爆的大神也是有的，但我还是差两题没时间做出来。
唯一有点新奇的是竟然有四道母子题。
一道是矩阵求和，我估计是一道要找规律的证明题吧，毕竟数据那么大，第二道是好人hard，好人太难了，也是大数据，用easy的方法肯定会超时，要用优化记忆的方法。