广联达5.13笔试
四道编程题，纯白板 20 20 30 30
第一道是
5个人分金币，好像不是贪心
每个人要把金币分成五堆，如果不能分成五堆，自己可以添加金币，最后每个人都添加了一个金币，然后还剩1000~2000金币，求每个人分到了多少金币
第二题是
给定一颗二叉树和数值。
求二叉树中的路径和等于给定值的所有路径。
第三题跟蓝桥杯3月校内赛第8题类似
【问题描述】
有一块空地，将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。
选了其中的一些小块空地，灌溉，其他小块仍然保持是空地。
每个月，已经灌溉了的地会向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为1。
问k月后有多少地没被灌溉
【输入格式】
输入的第一行包含两个整数 n, m。
接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 1，表示被灌溉。
接下来包含一个整数 k。
有一块空地，将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。
选了其中的一些小块空地，灌溉，其他小块仍然保持是空地。
每个月，已经灌溉了的地会向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为1。
问k月后有多少地没被灌溉
【输入格式】
输入的第一行包含两个整数 n, m。
接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 1，表示被灌溉。
接下来包含一个整数 k。
#include<iostream>
#include<queue>
#include<cstring>
#define loop(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
struct block{
int x;
int y;
int month;
};
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
int map[1001][1001];
int main()
{
ios::sync_with_stdio(false);//加快读取
cin.tie(0);
cout.tie(0);
int n,m,k,count=0;
char s;
queue<block> q;//队列中存放可扩展的已灌溉小块
memset(map,0,sizeof(map));//初始化数组
cin>>n>>m;
loop(i,0,n-1){
loop(j,0,m-1){
cin>>s;
if(s=='1'){
q.push({i,j,0});//进队
map[i][j]=1; //标记进队
}
}
}
cin>>k;
while(!q.empty()){
block b=q.front();//取队首，向四周灌溉
int month=b.month;
if(month<k){
loop(i,0,3){//循环做出四个新坐标
int n_x=b.x+dx[i];
int n_y=b.y+dy[i];
if(n_x>=0&&n_x<n&&n_y>=0&&n_y<m&&map[n_x][n_y]==0){//新坐标在范围内且未被访问
map[n_x][n_y]=1;
q.push({n_x,n_y,month+1});
}
}
}
q.pop();//出队首，队首向四周灌溉完毕
}
loop(i,0,n-1){
loop(j,0,m-1){
if(map[i][j]==0)
count++;
}
}
cout<<count;
return 0;
} 其中第四道是leetcode原题 312，不过没时间了就没写了，看题解是可以用动态规划做。
class Solution {
public int maxCoins(int[] nums) {
// reframe the problem
int n = nums.length + 2;
int[] new_nums = new int[n];
for(int i = 0; i < nums.length; i++){
new_nums[i+1] = nums[i];
}
new_nums[0] = new_nums[n - 1] = 1;
// cache the results of dp
int[][] memo = new int[n][n];
// find the maximum number of coins obtained from adding all balloons from (0, len(nums) - 1)
return dp(memo, new_nums, 0, n - 1);
}
public int dp(int[][] memo, int[] nums, int left, int right) {
// no more balloons can be added
if (left + 1 == right) return 0;
// we've already seen this, return from cache
if (memo[left][right] > 0) return memo[left][right];
// add each balloon on the interval and return the maximum score
int ans = 0;
for (int i = left + 1; i < right; ++i)
ans = Math.max(ans, nums[left] * nums[i] * nums[right]
+ dp(memo, nums, left, i) + dp(memo, nums, i, right));
// add to the cache
memo[left][right] = ans;
return ans;
}
} 
