120min, 5题。本菜鸡怒跪。

1、变身程序员

(读取时可以按行读取，直到读到空行为止，再对读取过的所有行做转换处理)
输出描述：
如果能将所有的产品经理变成程序员，输出最小的分钟数；
如果不能将所有的产品经理变成程序员，输出-1。
示例1： 输入：
0 2
1 0
输出：
-1
示例2：
输入：
1 2 1
1 1 0
0 1 1
输出：
3
示例3：
输入：
1 2
2 1
1 2
0 1
0 1
1 1
输出：
4

此题与https://leetcode.com/problems/rotting-oranges/类似。

基本思想就是将所有的程序员入队，BFS所有的产品经理，最后检查是否还有产品经理存在。

#define _CRT_SECURE_NO_WARNINGS

#include
#include
#include
#include
#include

using namespace std;

struct node {
int x, y;
int time;
node() {}
node(int xx, int yy, int t) :x(xx), y(yy), time(t) {}
};

queue q;

int dir[][] = { {,-},{,},{-,},{,} };

int main()
{
int grid[][];
int row = , col = ;
string str;

 /\*按行读取输入\*/  
 while (getline(cin, str))  
 {  
     col = ;  
     for (int i = ; str\[i\]; i++)  
     {  
         if (str\[i\] != ' ')  
         {  
             grid\[row\]\[col++\] = str\[i\] - '';  
         }  
     }

     row++;  
 }

 for(int i = ;i < row;i++)  
     for (int j = ; j < col; j++)  
     {  
         if (grid\[i\]\[j\] == )  
         {  
             //将所有程序员入队  
             q.push(node(i, j, ));  
         }  
     }

 node s;  
 while (!q.empty())  
 {  
     s = q.front();

     /\*四个方向遍历\*/  
     for (int i = ; i < ; i++)  
     {  
         int newx = s.x + dir\[i\]\[\];  
         int newy = s.y + dir\[i\]\[\];

         //没有越界并且找到一枚产品经理  
         if (newx >=  && newx < row && newy >=  && newy < col && grid\[newx\]\[newy\] == )  
         {  
             grid\[newx\]\[newy\] = ;  
             q.push(node(newx, newy, s.time + ));  
         }  
     }  
     q.pop();  
 }

 for (int i = ; i < row; i++)  
     for (int j = ; j < col; j++)  
     {  
         if (grid\[i\]\[j\] == )  
         {  
             printf("-1\\n");  
             return ;  
         }  
     }

 printf("%d\\n", s.time);

 return ;  

}

2、特征提取

示例： 输入：

4   

2 1 1 2 2

输出： 说明：
特征<，>在连续的帧中出现3次，相比其他特征连续出现的次数大，所以输出3
备注：
如果没有长度大于2的特征运动，返回1

可以使用pair存储当前特征，使用map存储当前特征上一次出现的行数以及当前特征连续出现的长度。

还是对C++不熟唉

#define _CRT_SECURE_NO_WARNINGS

#include
#include
#include

using namespace std;

int main()
{
int N, M, fea_num, res;
scanf("%d", &N);

 while (N--)  
 {  
     scanf("%d", &M);  
     res = ;  
     pair<int, int> cur;  
     //当前特征上一次出现的行数以及连续出现的长度  
     map<pair<int, int>, int> lastIndex, length;  
     for (int i = ; i < M; i++)  
     {  
         scanf("%d", &fea\_num);  
         for (int j = ; j < fea\_num; j++)  
         {  
             scanf("%d%d", &cur.first, &cur.second);  
             if (lastIndex\[cur\] == i)  
             {  
                 length\[cur\]++;  
             }  
             else  
             {  
                 length\[cur\] = ;  
             }  
             lastIndex\[cur\] = i + ;  
             res = max(res, length\[cur\]);  
         }  
     }  
     if (res <= )  
         printf("1\\n");  
     else  
         printf("%d\\n", res);  
 }

 return ;  

}

3、机器人跳跃

示例1： 输入：
输出： 示例2： 输入：
输出： 示例3： 输入：
输出： 备注： <= N <= ^
<= H(i) <= ^

据说是小学数学，还想了半天。

根据题意可推出：$dp[k + 1] = 2*dp[k] - H[k + 1]$

#define _CRT_SECURE_NO_WARNINGS

#include
#include
#include

using namespace std;

int main()
{
int N;
scanf("%d", &N);
vector H(N + );

 for (int i = ; i < N; i++)  
 {  
     scanf("%d", &H\[i + \]);  
 }

 vector<int> dp(N + );  //dp\[k\]表示从第k级开始需要的能量

 for (int i = N - ; i >= ; i--)  
 {  
     dp\[i\] = ceil((dp\[i + \] + H\[i + \]) / 2.0);  
 }

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

 return ;  

}

4、毕业旅行问题

示例： 输入：

输出：

典型的TSP问题，据说动态规划能够得到理论最优解，然而本渣看不懂状态转移方程。

贪心算法：从某城市出发，每次在未到达的城市中选择最近的一个，直到遍历完所有城市，最后回到出发地。

#define _CRT_SECURE_NO_WARNINGS

#include

using namespace std;

#define INF 1<<30;

int main()
{
int n, m[][], res = ;
int edge_count = , flag[] = { , };
int cur = , next;
scanf("%d", &n);

 for(int i = ;i < n;i++)  
     for (int j = ; j < n; j++)  
     {  
         scanf("%d", &m\[i\]\[j\]);  
     }

 while (edge\_count < n)  
 {  
     int min = INF;  
     for (int j = ; j < n; j++)  
     {  
         if (!flag\[j\] && m\[cur\]\[j\] && m\[cur\]\[j\] < min)  
         {  
             next = j;  
             min = m\[cur\]\[j\];  
         }  
     }  
     res += m\[cur\]\[next\];  
     flag\[next\] = ;  
     edge\_count++;  
     cur = next;  
 }

 res += m\[cur\]\[\];

 return ;  

}

5、过河

示例： 输入：

输出：

每次过河只能2个或3个人，这种过河问题遵循“能者多劳”原则，即花费时间少的人折返去接其他人。

#define _CRT_SECURE_NO_WARNINGS

#include
#include

using namespace std;

int a[], dp[];

int main()
{
int n, N;
scanf("%d", &N);

 while (N--)  
 {  
     scanf("%d", &n);  
     for (int i = ; i < n; i++)  
     {  
         scanf("%d", &a\[i\]);  
     }

     sort(a, a + n);  
     dp\[\] = a\[\], dp\[\] = a\[\];  
     for (int i = ; i <= n; i++)  
     {  
         //前i个人过河的最短时间  
         dp\[i\] = min( dp\[i - \] + a\[\] + a\[i - \],dp\[i - \] + a\[\] + a\[i - \] );  
     }

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

 return ;  

}