【普及组】模拟赛C组
写在前面：
? ? ? ? 我没了啊
????????10分钟打完T1和T2(分数+200)
????????T3看完不会,跳过(所以火星人到底是怎么交换两个手指的啊！还有我TM怎么就成了宇航员？)
????????后面T4怒打900+行代码(time-3h)(分数+0，哭)
? ? ? ? 最后20分钟，无能狂怒(TM的，T4样例都过不了)
? ? ? ? 算了，不哭，失败是成功他娘，明天加油(日常灌鸡汤)
T1:
题目大意：
?????????鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！”。 鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。
有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”
我们假定多多在每个单位时间内，可以做下列四件事情中的一件：
从路边跳到最靠近路边（即第一行）的某棵花生植株；
从一棵植株跳到前后左右与之相邻的另一棵植株；
采摘一棵植株下的花生；
从最靠近路边（即第一行）的某棵花生植株跳回路边。
现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。 例如在图2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为13, 7, 15, 9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。
正解:
看眼题目，这不就暴力吗
直接上，然后给有花生的草排个序就行(数据这么水，选择排序走起)
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,h,p[25][25],f,s;
struct abc{
int q,p,x;
}a[500];
int main(){
scanf("%d%d%d",&n,&m,&h);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&p[i][j]);
if(p[i][j]){
a[++f].p=i;
a[f].q=j;
a[f].x=p[i][j];
}
}
for(int i=1;i<f;i++){
for(int j=i+1;j<=f;j++){
if(a[i].x<a[j].x){
swap(a[i].x,a[j].x);
swap(a[i].q,a[j].q);
swap(a[i].p,a[j].p);
}
}
}
if(2*a[1].p+1>h){
printf("0");
return 0;
}
s+=a[1].x;
h-=(a[1].p+1);
for(int i=1;i<=f;i++){
if(h>=a[i].p){
s+=a[i+1].x;
h-=(abs(a[i+1].p-a[i].p)+abs(a[i+1].q-a[i].q)+1);
}
else{
printf("%d",s-a[i].x);
return 0;
}
}
printf("%d",s);
}T2:
题目大意：
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树[1]，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
T的根结点为R，其类型与串S的类型相同；
若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。
现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历[2]序列。
[1] 二叉树：二叉树是结点的有限集合，这个集合或为空集，或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。
[2] 后序遍历：后序遍历是深度优先遍历二叉树的一种方法，它的递归定义是：先后序遍历左子树，再后序遍历右子树，最后访问根。
正解：
看眼题目，啊。。。这，老水题了，递归就能做(好像二重循环也行)
代码：
#include<bits/stdc++.h>
using namespace std;
int n,ans;
char c[2000];
int dg(int l,int r){
if(l==r){
if(c[l]=='0'){
printf("B");
return 2;
}
else{
printf("I");
return 3;
}
}
int x=dg(l,(l+r)/2),y=dg((l+r)/2+1,r);
if(x==1||y==1){
printf("F");
return 1;
}
if(x==y){
if(x==2){
printf("B");
return 2;
}
else{
printf("I");
return 3;
}
}
printf("F");
return 1;
}
int main(){
scanf("%d\n",&n);
n=1<<n;
for(int i=1;i<=n;i++)
scanf("%c",&c[i]);
dg(1,n);
}T3:
题目大意：
人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。 火星人用一种非常简单的方式来表示数字——掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为1，2，3……。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。 一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指——拇指、食指、中指、无名指和小指分别编号为1，2，3，4和5，当它们按正常顺序排列时，形成了5位数12345，当你交换无名指和小指的位置时，会形成5位数12354，当你把五个手指的顺序完全颠倒时，会形成54321，在所有能够形成的120个5位数中，12345最小，它表示1；12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指时能够形成的6个3位数和它们代表的数字： 三进制数 123 132 213 231 312 321 代表的数字 1 2 3 4 5 6 现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。
考试时：
第一眼：火星人？
第二眼：万根手指？
第三眼：妈，我上火星了！！！
正解：
改题后：什么鬼，就这就这就这？(考试的时候怎么没对)
类似于找规律吧(用next_premutation()的家伙们，提前毕业(鼓掌))
自己看代码理解，别抄(博主复制不易，请勿再次复制)
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,a[10010],b[10010];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int aa=1;aa<=m;aa++){
if(a[n]>a[n-1]) swap(a[n],a[n-1]);
else
for(int i=n-2;i>=1;i--){
int minn=1e9,x;
for(int j=i+1;j<=n;j++)
if(a[j]>a[i]&&minn>a[j]) minn=a[j],x=j;
if(minn==1e9) continue;
swap(a[i],a[x]);
sort(a+i+1,a+n+1);
break;
}
}
for(int i=1;i<=n;i++) printf("%d ",a[i]);
}T4:
题目大意：
考试时：
10min打完高精度
然后看着(1000<P<3100000)陷入了沉思
接着放弃思考，怒打900+行优化(原地爆0，哭)
正解：
我们使用数学来求出位数后再用快速幂和高精度即可(考试的时候你怎么没想到)
不过我们今天不说这个(相信你们都会上面的)
我们讲yzn奆佬的方法
————————————华丽的分割线————————————————
我们知道long long可表示的范围是(-2^63~2^63-1)
所以我们可以不用跑普通高精度的for(1~n) x*=2(简写，相信你们可以看懂)
直接跑一个for(1~n/50) x*=1<<50 和一个for(1~n%50) x*=2
代码：
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
long long a[1005],n,m,w,t;
void nm(int x){
if(x) t=1125899906842624;
else t=2;
w=0;
for(int i=1;i<=500;i++){
a[i]=a[i]*t+w;
w=a[i]/10;
a[i]%=10;
}
}
int main(){
scanf("%lld",&n);
m=n/log2(10)+1;
printf("%lld\n",m);
a[1]=1;
for(int i=1;i<=n/50;i++) nm(1);
for(int i=1;i<=n%50;i++) nm(0);
a[1]-=1;
for(int i=500;i>=1;i--)
printf("%lld",a[i]);
}写在后面：
我最近的脑子好像有什么问题
那么多简单的题都能WA
算了明天继续加油(祝所有人明天考试rp++)
你们的三连就是对我最好的支持，谢谢(真心的感谢)