3.27 网易春招（第一批）

小红在一个游戏里杀怪。这是个回合制游戏，小红和两只怪物相遇了。
第一只怪物有 a a a 血量，第二只怪物有 b b b 血量。
小红有两个技能：
第一个技能叫火球术，效果是对单体怪物造成 x x x 伤害。
第二个技能叫烈焰风暴，效果是对每只怪物造成 y y y 伤害。
小红想知道，自己最少使用多少次技能，可以击杀这两只怪物。
（当怪物血量小于等于0时，视为被击杀）

四个正整数 a , b , x , y a,b,x,y a,b,x,y，用空格隔开。
1 < a , b , x , y < 20 1lt a,b,x,ylt20 1 输出描述：

小红使用技能的最少次数。
示例1

输入
5 2 3 1
输出
3

对情况逐一判断。

#include
#include
using namespace std;
const int N=1010;
int res = 0;
int a,b,x,y;
int main()
{
    cin>>a>>b>>x>>y;
    if(y >= x) res = max((a + y - 1) / y, (b + y - 1) / y);
    else
    {
        while(a > 0 || b > 0)
        {
            if(2 * y >= x && a > 0 && b > 0)
            {
                res ++;
                a -= y;
                b -= y;
            }
            else if(a > y && b > y)
            {
                res += 2;
                a -= x;
                b -= x;
            }
            else if((a > 0 && b > 0) && (a <= y || b <= y))
            {
                res ++;
                a -= y;
                b -= y;
            }
            else if(a > 0 && b <= 0)
            {
                res ++;
                a -= x;
            }
            else if(b > 0 && a <= 0)
            {
                res ++;
                b -= x;
            }
        }
    }
    cout< 
第二题：小红标字母 
题目描述： 
小红拿到了一个字符串，她可以做任意次以下操作：
 标记这个字符串两个位置相邻的字母，并且这两个字母必须满足以下条件才可标记：两个字母相同或者两则字母在字母表中相邻。小红可以获得两个字母的分数。
 举个例子，'a’和’b’在字母表相邻，'t’和’s’在字母表相邻。
 我们规定，已经被标记的字母无法被重复标记。
 每个字符获得的分数是不同的，'a’可以获得1分，'b’可以获得2分，以此类推，'z’可以获得26分。
 小红想知道，自己最多可以获得多少分？
 
输入描述： 
输入一行只包含小写字母的非空字符串
    
     
      
       
        S
       
      
      
       S
      
     
    S，代表小红拿到的字符串。
 
    
     
      
       
        1
       
       
        <
       
       
        l
       
       
        e
       
       
        n
       
       
        (
       
       
        s
       
       
        )
       
       
        <
       
       
        200000
       
      
      
       1lt len(s)lt200000
      
     
    1 
输出描述： 
小红可以获得的最大分数。
 示例1
 
 
 
输入
 abdbb
 输出
 7
 说明
 第一次标记前两个字母’a’和’b’，获得3分。第二次标记后两个字母’b’和’b’，获得4分。
 
 
示例2
 
 
 
输入
 abb
 输出
 4
 
 
思路： 
找出所有连续可标记的字符串，若长度为偶数则直接加入答案，为奇数则可以删掉下标模2为0的字母中最小的那一个。
 
AC代码 
#include 
using namespace std;
const int N=2010;

string s;
int res,j;

int main()
{
    cin>>s;
    int n = s.size();
    for(int i = 1; i < n; i ++)
    {
        if((s[i] == s[i - 1]) || (s[i] == s[i - 1] + 1) || (s[i] == s[i - 1] - 1))
        {
            string tmp;
            tmp += s[i-1];
            tmp += s[i];
            for(j = i + 1; j < n; j ++)
            {
                if((s[j] == s[j - 1]) || (s[j] == s[j - 1] + 1) || (s[j] == s[j - 1] - 1)) tmp += s[j];
                else break;
            }
            int t = 0;
            char str = 'z';
            for(int q = 0; q < tmp.size(); q ++) 
            {
                t += tmp[q] - 'a' + 1;
                if(q % 2 == 0) str = min(str, tmp[q]);
            }
            if(tmp.size() % 2 == 0) res += t;
            else if(tmp.size() == 3) res += max(t - (tmp[0] - 'a' + 1), t - (tmp[tmp.size()-1] - 'a' + 1));
            else res += t - (str - 'a' + 1); 
            i = j;
        }
    }
    cout< 
第三题：完全二叉树构造 
题目描述： 
小红想构造一个总共 
    
     
      
       
        n
       
      
      
       n
      
     
    n 个节点完全二叉树，该二叉树满足以下两个性质：
 
所有节点的权值为 
     
      
       
        
         1
        
        
          
        
        
         n
        
       
       
        1~n
       
      
     1 n 的一个排列除了根节点以外，每个节点的权值和它父亲的权值的乘积为偶数。
 请你帮小红构造出这个二叉树，并按层序遍历的方式打印所有节点。
 
输入描述： 
一个正整数 
    
     
      
       
        n
       
      
      
       n
      
     
    n，代表二叉树的节点数量。
 
    
     
      
       
        2
       
       
        <
       
       
        n
       
       
        <
       
       
        1
       
       
        
         0
        
        
         5
        
       
      
      
       2lt n lt 10^5
      
     
    2 
输出描述： 
输出一行
    
     
      
       
        n
       
      
      
       n
      
     
    n个正整数，代表小红构造的二叉树的层序遍历的序列。
 示例1
 
 
 
输入
 4
 输出
 2 4 3 1
 说明
 这棵树的结构如下：
 2
 / 
 4 3
 /
 1
 显然，任意节点和它父亲权值的乘积都是偶数
 
 
思路： 
奇数节点全部放叶子上 剩下的放偶数节点
 
AC代码： 
#include
using namespace std;

int n;

int main()
{	
	cin >> n;
	vector tr(n + 1, 0);
	vector odd, even;
	for(int i = 1; i <= n; i++)
	{
		if(i % 2 == 0) even.push_back(i);
		else odd.push_back(i);
	}
	for(int i = n; i > 0; i--)
	{
		if(odd.empty())
		{
			tr[i] = even.back();
			even.pop_back();
		} 
		else 
		{
			tr[i] = odd.back();
			odd.pop_back();
		}
	}
	for(int i = 1; i <= n; i++) cout << tr[i] << " ";
	return 0;
}
 
第四题：过沼泽地 
题目描述： 
小红来到了一片沼泽地的岸边，她希望能通过这片沼泽地。
 这个沼泽地地图用一个矩阵进行表示。1代表沼泽，0代表平地。小红刚开始在矩阵的左上角，她需要从右下角离开地图。已知进入地图和离开地图的时间可以忽略。小红可以向左、向右或者向下走。
 当小红从沼泽进入沼泽，或者平地进入平地时，需要花费1单位时间。
 当小红从沼泽进入平地，或者平地进入沼泽，由于需要更换装备，所以要花2单位时间。
 小红可以从左上角进入地图，从右下角离开地图。
 小红想知道，经过这片沼泽地，最少需要花费多少单位时间。
 
输入描述： 
第一行输入两个正整数 
    
     
      
       
        n
       
      
      
       n
      
     
    n 和 
    
     
      
       
        m
       
      
      
       m
      
     
    m，用空格隔开，代表矩阵的行数和列数。
 接下来的 
    
     
      
       
        n
       
      
      
       n
      
     
    n 行，每行输入 
    
     
      
       
        m
       
      
      
       m
      
     
    m 个正整数 
    
     
      
       
        
         a
        
        
         
          i
         
         
          ,
         
         
          j
         
        
       
      
      
       a_{i,j}
      
     
    ai,j​，用来表示矩阵。
 
    
     
      
       
        2
       
       
        ≤
       
       
        n
       
       
        ,
       
       
        m
       
       
        ≤
       
       
        500
       
       
        ,
       
       
        0
       
       
        ≤
       
       
        
         a
        
        
         
          i
         
         
          ,
         
         
          j
         
        
       
       
        ≤
       
       
        1
       
      
      
       2leq n,mleq500 , 0leq a_{i,j}leq1
      
     
    2≤n,m≤500,0≤ai,j​≤1
 
输出描述： 
输出一个正整数，代表经过沼泽地的最少时间。
 
示例1
 
 
 
输入
 3 3
 1 0 0
 1 1 1
 0 0 1
 输出
 4
 说明
 从左上角进入，往下走一次，往右走两次，往下走一次，到右下角。后花费4单位时间。
 可以证明，这样花费的时间一定是最小的。
 
 
思路： 
正常DP即可
 
AC代码 
#include 
using namespace std;
const int N = 510;

int n,m;
int g[N][N];
int f[N][N];

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>g[i][j];
	memset(f,0x3f,sizeof f);
	f[1][1] = 0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(j + 1 <= m) f[i][j] = min(f[i][j], f[i][j + 1] + (g[i][j] == g[i][j+1] ? 1 : 2));
			if(i - 1 >= 0) f[i][j] = min(f[i][j], f[i - 1][j] + (g[i][j] == g[i - 1][j] ? 1 : 2));
			if(j - 1 >= 0) f[i][j] = min(f[i][j], f[i][j - 1] + (g[i][j] == g[i][j - 1] ? 1 : 2));
		}
	}
	cout<