A-沙漏

简单输出图像问题。

练习题：720、721、730。

#include<bits/stdc++.h>

using namespace std;

int n;

char x;

int all=1,num=1;//num表示第一层和最后一层的符号数量，all表示总的符号数量

void work(int cnt) //cnt为该层要打印的符号数量

{

int kg=(num-cnt)/2;//该层每一边要打印的空格数

for(int i=1;i<=kg;i++) cout<<" ";

for(int i=1;i<=cnt;i++) cout<<x;

for(int i=1;i<=kg;i++) cout<<" ";

cout<<endl;

}

int main()

{

cin>>n>>x;

while(all<=n) //用循环推断出第一层和最后一层应该有多少个符号

{

num+=2;

all+=num*2;

}

// 多加了一次需要减掉

all-=num*2;

num-=2;

for(int i=num;i>=1;i-=2) work(i); //打印上半部分

for(int i=3;i<=num;i+=2) work(i); //打印下半部分

cout<<n-all;

return 0;

}

B-因子

一个数可以分解为较小的因数和较大的因数的乘积，其中较小的因数i始终满足i*i<=n，所以只需要枚举i即可，时间复杂度可以接受。如果i为n的因数，则可以通过n/i算出另一个较大的因数。

算出所有因数后，将因数排序，问题转化成求最长连续的数，简单循环即可。

练习题：500、830。

#include<bits/stdc++.h>

using namespace std;

int main()

{

int n;

vector<int> factor;

cin>>n;

for(int i=2;i*i<=n;i++) //推出n的所有因子

{

if(n%i==0)

{

factor.push_back(i);

if(i*i!=n) factor.push_back(n/i);

}

}

factor.push_back(n);

sort(factor.begin(),factor.end());

//找最长连续的因子

int maxx=1,now=1;

int len=factor.size();

for(int i=1;i<len;i++)

{

if(factor[i]-factor[i-1]==1)

{

now++;

maxx=max(maxx,now);

}

else now=1;

}

cout<<maxx;

return 0;

}

C-古老森林

先序遍历：先根、后左子树、最后右子树。

后序遍历：先左子树、后右子树、最后根。

首先假设该树是二叉搜索树，尝试根据二叉搜索树的性质通过先序遍历求后序遍历。对于一个二叉搜索树而言，左子树中的元素均小于根，右子树中的元素均大于等于根，故每个子树的先序遍历序列都可以按顺序划分为：根（x）、左子树（值小于x的结点）、右子树（值大于等于x的结点）这连续的三部分。通过大小关系可以很容易的将这三部分划分开来，接着在左子树和右子树中递归 ，继续划分。

由于最后要输出后序遍历，所以递归时先左子树、再右子树，递归回来之后再输出根。

如果第一次求后序遍历失败了（也就是说在某个子树中它不符合二叉搜索树的性质，导致提前return，后序遍历序列不全），那么就假设该树是二叉搜索树的镜像，重新求一遍。

如果两次都失败了，输出NO，否则输出成功的那一次的后序遍历序列。

练习题：2200、2201、2202。

#include <bits/stdc++.h>

using namespace std;

bool isMirror;

vector<int> pre, post;

void getpost(int x, int tail) //找这棵树的后序遍历序列

// x为当前所在的点，tail为以x为根的子树在先序遍历序列中的最后一个位置

{

if(x > tail) return ;

// 根据二叉搜索树的性质来得到 i 和 j

// 经过循环后，x+1 ~ i这部分为左子树，j ~ tail这部分为右子树

int i = x, j = tail + 1;

if(!isMirror)

{

while(i + 1 <= tail && pre[x] > pre[i + 1]) i++;

while(j - 1 > x && pre[x] <= pre[j - 1]) j--;

}

else //镜像的二叉搜索树，左子树中的值均比x大，右子树均比x小

{

while(i + 1 <= tail && pre[x] <= pre[i + 1]) i++;

while(j - 1 > x && pre[x] > pre[j - 1]) j--;

}

if(j - i != 1) return ; //证明不符合二叉搜索树的性质

// 后序遍历要先遍历左子树，再遍历右子树，再遍历根

getpost(x + 1, i);

getpost(j, tail);

post.push_back(pre[x]);

}

int main()

{

int n;

scanf("%d", &n);

for(int i = 0; i < n; i++)

{

int x;

scanf("%d", &x);

pre.push_back(x);

}

getpost(0, n - 1);

if(post.size() != n)

// 一开始默认这棵树不是镜像

// 如果发现不满足性质，则认为它可能是镜像，再计算一次

{

isMirror = true;

post.clear();

getpost(0, n - 1);

}

if(post.size() == n) // 是二叉搜索树或镜像

{

printf("YES\n");

for(int i = 0; i < n; i++)

printf("%d ", post[i]);

}

else printf("NO");

return 0;

}

D-分配策略

仔细理解题意，即可发现该题实际上是裸的分组背包。m可以看作背包容量，n可以看作n组，每组里的物品相互冲突（也就是说选0台设备、选1台设备......这些事件是相互冲突的），一件“物品”的“体积”就是选几台，价值就是矩阵中的值。

所以该题dp的思想和分组背包完全相同，同样，可以采用滚动数组优化代码。

但这道题在普通分组背包之外还有额外的要求，即需要输出具体的方案，还需要注意字典序问题。因此可以再定义一个数组s，s[i][j]表示前i个公司买j台设备取到最大利润时的最小字典序。在dp[i][j]相同时，取较小的字典序来更新s[i][j]。由于分配的设备数量是数字，所以可以用该数字+'a'来得到一个字母，将这个字母加在字符串s中来表示分配策略。比如公司1买了2台设备，公司2买了0台设备，字符串就可以表示为ca。

最终的答案存储在dp[n][m]和s[n][m]中 ，将s[n][m]中的每个字母转为数字即可输出方案。

练习题：2480、2481。

#include<bits/stdc++.h>

using namespace std;

int a[20][20],n,m;

int dp[20][20];

//dp[i][j]表示前i个公司买j台设备的最大利润

string s[20][20];

//s[i][j]表示前i个公司买j台设备的最小字典序

int main()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)

{

for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);

for(int j=m;j>=0;j--) //前i家公司共买j台设备

//为了方便之后进行数组降维，这里倒序枚举

{

for(int k=0;k<=j;k++) //公司i买k台设备

{

string tmp=s[i-1][j-k]+(char)('a'+k); //买0个用a表示，1一个用b表示，以此类推

if(dp[i][j]<dp[i-1][j-k]+a[i][k])

{

dp[i][j]=dp[i-1][j-k]+a[i][k]; //背包

s[i][j]=tmp;

}

else if(dp[i][j]==dp[i-1][j-k]+a[i][k] && (s[i][j].empty() || tmp<s[i][j])) //保证字典序最小

s[i][j]=tmp;

}

}

}

printf("%d\n",dp[n][m]);

string ans=s[n][m];

for(int i=0;i<n;i++) printf("%d %d\n",i+1,(int)(ans[i]-'a'));

return 0;

}

背包问题显然可以使用滚动数组来节省空间，修改后如下，注意要倒序枚举j，并在更新s[j]时进行一些微调：

#include<bits/stdc++.h>

using namespace std;

int a[20],n,m;

int dp[20];

//dp[j]表示前i个公司买j台设备的最大利润

string s[20];

//s[j]表示前i个公司买j台设备的最小字典序

int main()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)

{

for(int j=1;j<=m;j++) scanf("%d",&a[j]);

for(int j=m;j>=0;j--) //前i家公司共买j台设备

//倒序枚举

{

string sj;

for(int k=0;k<=j;k++) //公司i买k台设备

{

string tmp=s[j-k]+(char)('a'+k); //买0个用a表示，1一个用b表示，以此类推

if(dp[j]<dp[j-k]+a[k])

{

dp[j]=dp[j-k]+a[k]; //背包

sj=tmp;

}

else if(dp[j]==dp[j-k]+a[k] && (sj.empty() || tmp<sj)) //保证字典序最小

sj=tmp;

}

s[j]=sj;

}

}

printf("%d\n",dp[m]);

string ans=s[m];

for(int i=0;i<n;i++) printf("%d %d\n",i+1,(int)(ans[i]-'a'));

return 0;

}

ex. 实际上这道题使用搜索+剪枝也可以通过，有兴趣可以写一写，思想比dp更简单，考试时应该至少要写出搜索来。