? ?上周，我说过了，每周进行一次往年的普及组模拟赛，昨天我就考了一次，最终得分是300分，不是第四题没有搞出来，反而是第三题没有搞出来，因为第三题是一道数据结构的题目，应该用二叉树来解决，而我连学都没有学过，暴力也出不来，就得了个“鸭蛋”！
? 我们先来看第一题“优秀的拆分”?
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
?
题目描述
一般来说，一个正整数可以拆分成若干个正整数的和。例如，1=1，10=1+2+3+41 = 1，10 = 1 + 2 + 3 + 41=1，10=1+2+3+4?等。
对于正整数?𝑛?的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下，𝑛?被分解为了若干个不同的?2?的正整数次幂。注意，一个数?x?能被表示成?2?的正整数次幂，当且仅当?x?能通过正整数个?2?相乘在一起得到。
例如，10=8+2=23+2110 = 8 + 2 = 2^3 + 2^1 是一个优秀的拆分。但是，7=4+2+1=2^2+2^1+2^0?就不是一个优秀的拆分，因为?1?不是?2?的正整数次幂。
现在，给定正整数?𝑛，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案。
输入描述:
输入只有一行，一个正整数?𝑛，代表需要判断的数。
输出描述:
如果这个数的所有拆分中，存在优秀的拆分。那么，你需要从大到小输出这个拆分中的每一个数，相邻两个数之间用一个空格隔开。可以证明，在规定了拆分数字的顺序后，该拆分方案是唯一的。若不存在优秀的拆分，输出“-1”（不包含双引号）。
示例1
输入
6
输出
4 2
说明
6=4+2=22+216 = 4 + 2 = 2^2 + 2^16=4+2=22+21?是一个优秀的拆分。注意，6 = 2 + 2 + 2 不是一个优秀的拆分，因为拆分成的 3 个数不满足每个数互不相同。
示例2
输入
7
输出
-1
备注:
对于?20%?的数据，𝑛≤10 对于另外?20%的数据，保证?𝑛?为奇数。 对于另外?20%?的数据，保证?𝑛?为?2?的正整数次幂。 对于?80%?的数据，𝑛≤1024 对于?100%的数据，1≤𝑛≤1×10^7
??? 首先，题目表明，是要是2的0次方就不是优秀的拆分，想要出先2的0次方，那么这个数必须是一个奇数，索引表说，要先判断这个数是否是奇数，如果是就直接输出“-1”，如果不是，那么写一个函数，作用数把这个数转化为2进制，将里面的1全部化为2的i次方，直接就可以输出了。
我的代码：
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int n;
void gui(int n)
{
if(n==0)
return;
int i=1;
while(n/2>=i)
i*=2;
cout<<i<<" ";
return gui(n-i);
}
int main()
{
int n;
cin>>n;
if(n%2==1)
cout<<-1;
else
gui(n);
return 0;
}
? 这个第一道题，就是一道送分题，连没有学算法的人都可以做出来！?
? 然后，我们看一下第二题“直播 获奖”！
题目描述
NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为?𝑤%，即当前排名前?𝑤%的选手的最低成绩就是即时的分数线。
? 更具体地，若当前已评出了 p?个选手的成绩，则当前计划获奖人数为?max(1,?𝑝×𝑤%?)，其中?𝑤?是获奖百分比，?𝑥?表示对?x?向下取整，?max(𝑥,𝑦) 表示?𝑥?和?𝑦?中较大的数。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。
作为评测组的技术人员，请你帮 CCF 写一个直播程序。
输入描述:
第?1?行两个正整数?𝑛,?𝑤。分别代表选手总数与获奖率。 第?2?行有?𝑛?个非负整数，依次代表逐一评出的选手成绩。
输出描述:
只有一行，包含?𝑛?个非负整数，依次代表选手成绩逐一评出后，即时的获奖分数线。相邻两个整数间用一个空格分隔。
示例1
输入
10 60 200 300 400 500 600 600 0 300 200 100
输出
200 300 400 400 400 500 400 400 300 300
说明
? 注意，在第 9 名选手的成绩评出之后，计划获奖人数为 5 人，但由于有并列，因此实际会有 6 人获奖。
示例2
输入
10 30 100 100 600 100 100 100 100 100 100 100
输出
100 100 600 600 600 600 100 100 100 100
备注:
对于所有测试点，每个选手的成绩均为不超过?600?的非负整数，获奖百分比?𝑤𝑤w?是一个正整数且?1≤𝑤≤991 。 ? 在计算计划获奖人数时，如用浮点类型的变量（如 C/C++中的 float、double，Pascal 中的 real、double、extended 等）存储获奖比例?𝑤%，则计算?5×60%时的结果可能为 3.000001，也可能为 2.999999，向下取整后的结果不确定。因此，建议仅使用整型变量，以计算出准确值。
? ??这道题最后专门给我们说了的，每个选手的成绩均为不超过600的非负整数，这是一个重点，于是我想，能不能逐一枚举从1道600的每一个分数，判断这个数是不是分数线呢？刚开始由于是在暴力枚举，心里有些没底，觉得可能会超时，码了二十多分钟后，暴力法成功过样例，提交上去，竟然没有超时，复杂度是O(n log600)。
枚举代码：
#include<iostream>
#include<cstdio>
using namespace std;
int a[601]={0},n,w;
int main(void)
{
int p=0;
scanf("%d%d",&n,&w);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
a[x]++;
p=i*w/100;
if(p==0)p++;
for(int j=600;j>=0;j--)
{
if(a[j]>=1)
p-=a[j];
if(p<=0)
{
printf("%d ",j);
break;
}
}
}
printf("\n");
return 0;
}
这道题难度也算是一般般吧！?
? 之后我看到了第三题“表达式”
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
?
题目描述
小 C 热衷于学习数理逻辑。有一天，他发现了一种特别的逻辑表达式。在这种逻辑表达式中，所有操作数都是变量，且它们的取值只能为?000?或?111，运算从左往右进行。如果表达式中有括号，则先计算括号内的子表达式的值。特别的，这种表达式有且仅有以下几种运算：
- 与运算：𝑎&𝑏。当且仅当?𝑎?和?𝑏?的值都为?1?时，该表达式的值为?1。其余情况该表达式的值为?0。
- 或运算：𝑎∣𝑏。当且仅当?𝑎?和?𝑏?的值都为?0?时，该表达式的值为?0。其余情况该表达式的值为?1。
- 取反运算：!𝑎。当且仅当?𝑎?的值为 0?时，该表达式的值为?1。其余情况该表达式的值为?0。
小 C 想知道，给定一个逻辑表达式和其中每一个操作数的初始取值后，再取反某一个操作数的值时，原表达式的值为多少。
为了化简对表达式的处理，我们有如下约定：
表达式将采用后缀表达式的方式输入。后缀表达式的定义如下：
- 如果?𝐸?是一个操作数，则?𝐸𝐸E?的后缀表达式是它本身。
- 如果?𝐸?是?𝐸1𝑜𝑝𝐸2??形式的表达式，其中?𝑜𝑝?是任何二元操作符，且优先级不高于?𝐸1、𝐸2??中括号外的操作符，则?E?的后缀式为?𝐸1′𝐸2′𝑜𝑝𝐸_1^′ 𝐸_2^′ 𝑜𝑝E1′?E2′?op，
其中?𝐸1′、𝐸2′𝐸_1^′、𝐸_2^′E1′?、E2′??分别为?𝐸1、𝐸2的后缀式。 - 如果?𝐸?是 (𝐸1?) 形式的表达式，则?𝐸1??的后缀式就是?𝐸的后缀式。
同时为了方便，输入中：
a) 与运算符（&）、或运算符（|）、取反运算符（！）的左右均有一个空格，但表达式末尾没有空格。
b) 操作数由小写字母 x 与一个正整数拼接而成，正整数表示这个变量的下标。例如：x10，表示下标为?10?的变量?𝑥10?。数据保证每个变量在表达式中出现恰好一次。
输入描述:
第一行包含一个字符串?𝑠，表示上文描述的表达式。 第二行包含一个正整数?𝑛，表示表达式中变量的数量。表达式中变量的下标为?1,2,…,𝑛 第三行包含?𝑛?个整数，第?i?个整数表示变量?𝑥𝑖??的初值。 第四行包含一个正整数q，表示询问的个数。 接下来?𝑞?行，每行一个正整数，表示需要取反的变量的下标。注意，每一个询问的修改都是临时的，即之前询问中的修改不会对后续的询问造成影响。数据保证输入的表达式合法。变量的初值为 0 或 1。
输出描述:
输出一共有?𝑞?行，每行一个?0?或?1，表示该询问下表达式的值。
示例1
输入
x1 x2 & x3 | 3 1 0 1 3 1 2 3
输出
1 1 0
说明
该后缀表达式的中缀表达式形式为 (𝑥1 & 𝑥2) | 𝑥3。 对于第一次询问，将 𝑥1 的值取反。此时，三个操作数对应的赋值依次为0，0，1。原表达式的值为 (0 & 0) | 1 = 1。 对于第二次询问，将 𝑥2 的值取反。此时，三个操作数对应的赋值依次为1，1，1。原表达式的值为 (1 & 1) | 1 = 1。 对于第三次询问，将 𝑥3 的值取反。此时，三个操作数对应的赋值依次为1，0，0。原表达式的值为 (1 & 0) | 0 = 0。
示例2
输入
x1 ! x2 x4 | x3 x5 ! & & ! & 5 0 1 0 1 1 3 1 3 5
输出
0 1 1
说明
该表达式的中缀表达式形式为?(!𝑥1)&(!((𝑥2∣𝑥4)&(𝑥3&(!𝑥5))))
备注:
对于?20%?的数据，表达式中有且仅有与运算（&）或者或运算（|）。 对于另外?30%?的数据，∣𝑠∣≤1000，𝑞≤1000，𝑛≤1000 对于另外?20%的数据，变量的初值全为?0?或全为?1。 对于?100%?的数据，1≤∣𝑠∣≤1×106，1≤𝑞≤1×105，2≤𝑛≤1×105 其中，∣𝑠∣表示字符串?𝑠?的长度。
??我看到这样又长又是字符串的题目就脑壳疼，光是看题+理解题意就用了半个小时的时间，理解样例更是花了我40分钟的时间都没有理解，所以，拜拜喽，这道题太难了，我连一丝丝头绪都没有，于是，我决定先去码第四题，看看能不能攻下！
? 第四题是“方格取数”！
题目描述
设有?𝑛×𝑚 的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，
求它能取到的整数之和的最大值。
输入描述:
第 1 行两个正整数?𝑛,𝑚 接下来?n?行每行?m?个整数，依次代表每个方格中的整数。
输出描述:
一个整数，表示小熊能取到的整数之和的最大值。
示例1
输入
3 4 1 -1 3 2 2 -1 4 -1 -2 2 -3 -1
输出
9
说明
? ? 按上述走法，取到的数之和为 1 + 2 + (-1) + 4 + 3 + 2 + (-1) + (-1) = 9，可以证明为最大值。
?注意，上述走法是错误的，因为第?222?行第?222?列的方格走过了两次，而根据题意，不能重复经过已经走过的方格。
?
另外，上述走法也是错误的，因为没有走到右下角的终点。?
示例2
输入
2 5 -1 -1 -3 -2 -7 -2 -1 -4 -1 -2
输出
-10
说明
按上述走法，取到的数之和为(-1) + (-1) + (-3) + (-2) + (-1) + (-2) = -10，可以证明为最大值。因此，请注意，取到的数之和的最大值也可能是负数。
备注:
对于?20%?的数据，𝑛,𝑚≤5 对于?40%?的数据，𝑛,𝑚≤50 对于?70?的数据，𝑛,𝑚≤300 对于?100%的数据，1≤𝑛,𝑚≤1000，方格中整数的绝对值不超过10^4
??我看到这道题的第一眼，就觉得这是一道搜索题，可以用到深度优先搜索，于是我花了呢二十多分钟写了一个BFS，小样例过了，大样例超时了，只得到了40分，于是我想，在哪里可以剪枝呢，二十分钟后无果，我怀疑思路和算法想错了，于是就想到了动态规划！
? 如果只是简单的往下和往右走就是直接dp，而如果是可以往上走，那么就要设置dp维度，dp[i][j][0]代表(i,j)从左转移下来dp[i][j][0]代表(i,j)从左转移下来，dp[i][j][1]代表(i,j)从上转移下来dp[i][j][1]代表(i,j)从上转移下来，dp[i][j][2]代表(i,j)从下转移下来dp[i][j][2]代表(i,j)从下转移下来，这个dp显然循环是要从先枚举列，再枚举行！
然后又码了二十多分钟，dp完成直接满分过了！
dp代码：
#include <bits/stdc++.h>
using namespace std;
#define mem2(p, x) memset(p, x, sizeof(p))
const int N=1009;
int n,m,a[N][N];
long long dp[N][N],fu1[N],fu2[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
scanf("%d",a[i]+j);
}
memset(dp,0x8f,sizeof(dp));
mem2(fu1,0x8f);
mem2(fu2,0x8f);
dp[0][1]=0;
for(int i=1;i<=n;i++)
dp[i][1]=a[i][1]+dp[i-1][1];
for(int j=2;j<=m;j++)
{
for(int i=1;i<=n;i++)
fu1[i]=max(fu1[i-1],dp[i][j-1])+a[i][j];
for(int i=n;i;i--)
fu2[i]=max(fu2[i+1],dp[i][j-1])+a[i][j];
for(int i=1;i<=n;i++)
dp[i][j]=max(fu2[i],fu1[i]);
}
cout<<dp[n][m];
return 0;
}? 现在，整场模拟考试还有半个小时的时间就结束了，我将思路放在了第三题上面，半小时后，依然爆零，就这样，第二场模拟考我得了300分。
? 考完试后，我拿出爸爸买的NOI2020年鉴，看了一下第3题的解题报告，竟然要用到数据结构中的二叉树和表达式树，难怪我不会做，原来我没有学啊！
? 之后呢，我上网随意找了找，这一找，找到了第4题的背后，居然是2000年的提高组题目，难怪这么难啊！?