网易雷火9.18笔试

1.21年icpc银川站原题?

找到起始点（1，1，）(左上为0)，然后dfs，

#include <bits/stdc++.h>

using namespace std;

int n,m;
const int N = 105;
struct P{
	int l,u,r,d;
}p[N][N];
int ans[N][N];
int getx(int x){
	return (x / m) + (x % m != 0);
}
int gety(int x){
	return (x % m == 0) ? m : (x % m);;
}
void solve(int x,int y,int X,int Y){
	if(x < 1 || x > n || y < 1 || y > m) return;
	if(X < 1 || X > n || Y < 1 || Y > m) return;
	if(ans[x][y]) return;	
	ans[x][y] = (X - 1) * m + Y;	
	solve(x,y - 1, getx(p[X][Y].l),gety(p[X][Y].l));
	solve(x,y + 1, getx(p[X][Y].r),gety(p[X][Y].r));
	solve(x - 1,y, getx(p[X][Y].u),gety(p[X][Y].u));
	solve(x + 1,y, getx(p[X][Y].d),gety(p[X][Y].d));
	return;
}
int main() {
	scanf("%d %d",&n,&m);	
	int fx = -1,fy = -1;
	for(int i = 1; i <= n; ++ i) {
		for(int j = 1; j <= m; ++ j) {
			int id,l,r,u,d;
			scanf("%d",&id);
			scanf("%d %d %d %d",&l,&u,&r,&d);
			int x = getx(id),y = gety(id);
			if(l == 0 && u == 0){
				fx = x;
				fy = y;
			}
			p[x][y] = {l,u,r,d};
		}
	}
	solve(1,1,fx,fy);
	for(int i = 1;i <= n; ++ i){
		for(int j = 1;j <= m; ++ j){
			printf("%d%c",ans[i][j]," \n"[j == m]);
		}
	}
	return 0;
}

2.假设答案坐标一定包含第i个点，那么包含第 i 个点的答案坐标不超过710个（R = 20的情况下），把所有可能的点拿出来算一下答案，取最优复杂度(7e8) 居然过了。

应该还可以把700n个点，拿出来去重，优化复杂度

PS.在别处看到正解，将遍历x,y附近的所有可行点px,py，将这个点的值 + 1，unordered_map, 在所有的700n个点中，找到权值最大的点，复杂度O(700n)

#include <bits/stdc++.h>

using namespace std;

int n,m;
const int N = 10030;


int R;

int x[N],y[N];
bool isok(int x,int y,int X,int Y) {
	return ((x - X) * (x - X) + (y - Y) * (y - Y)) <= R * R;
}

int get(int X,int Y) {
	int cnt = 0;
	for(int i = 1; i <= n; ++ i) {
		if(isok(X,Y,x[i],y[i])) ++ cnt;
	}
	return cnt;
}

int dx[N],dy[N];
vector<pair<int,int> >v;

int main() {


	freopen("test.in","r",stdin);

	scanf("%d",&R);

	for(int x = -R; x <= R; ++ x) {
		for(int y = -R; y <= R; ++ y) {
			if((x * x + y * y) <= R * R) {
				v.push_back({x,y});
			}
		}
	}

	scanf("%d",&n);

	for(int i = 1; i <= n; ++ i) {
		scanf("%d %d",x + i,y + i);
	}
	int mx = 1,ansx = 0,ansy = 0;
	for(int i = 1; i <= n; ++ i) {

		for(auto pr : v) {

			int d = x[i] + pr.first;
			int p = y[i] + pr.second;
			int res = get(d,p);
			if(res > mx) {
				ansx = d;
				ansy = p;
				mx = res;
			} else if(res == mx) {
				if(d > ansx) {
					ansx = d;
					ansy = p;
				} else if(d == ansx) {
					ansx = d;
					ansy = max(ansy,p);
				}
			}
		}
	}
	printf("%d %d\n",ansx,ansy);
	return 0;
}

3.祖玛

输出L1 + L2 -> 过11%

4.显然每个人会不停的去摘花，我们二分一下用时最长的一个人的用时为 T，那么每个人能取到的的第1.2种花的数量假设为x,y，满足 x * a1 + y * a2 <= T

那么每个人能够得到，多个 <x,y>的二元组，类似分组背包的思路check一下T，是否可行，可能写的有点问题，但是过了（?。

写的时候忘了分组背包咋写了，整了个二维的（很尬

代码中的一些上下界都是试出来的，比如sum 从10 * m -> 4 * m，由超时 -》 AC。

和2021CCPC华为云挑战赛第三题有点像

#include <bits/stdc++.h>

using namespace std;

int n,m;
const int N = 5e4 + 5;

int dp[202][N];

const int inf = 1e8;

int x[N],y[N];

bool check(int t) {


	int sum = 0;
	for(int i = 1; i <= n; ++ i) sum = sum + t / y[i];
	sum = min(sum,4 * m);
	for(int i = 0; i <= n; ++ i) {
		for(int j = 0; j <= sum; ++ j) {
			dp[i][j] = 0;
		}
	}
	//cout << "sum = " << sum << endl;
	for(int i = 1; i <= n; ++ i) {
		int px = 0,py = t / y[i];
//		cout << " ****** " << endl;
//		cout << px << " " << py << endl;
		for(int d = 1; (d * x[i]) <= t; ++ d) {
			int nx = d,ny = (t - d * x[i]) / y[i];
			int val = d,cost = py - ny;
			for(int W = sum; W >= cost; -- W) {
				dp[i][W] = max(dp[i][W],dp[i - 1][W - cost] + val);
			}
		}
		for(int W = m; W >= 0; -- W) dp[i][W] = max(dp[i][W],dp[i - 1][W]);
	}

	int up = sum - m;
	if(up < 0) return false;
	for(int i = 0; i <= up; ++ i) if(dp[n][i] >= m) return true;

	return false;
}
int main() {


	freopen("test.in","r",stdin);

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

	for(int i = 1; i <= n; ++ i) {
		scanf("%d %d",x + i,y + i);
	}


	int l = 0,r = 5e4,ans = 0;

	while(l <= r) {
		int mid = (l + r) / 2;
		if(check(mid)) {
			ans = mid;
			r = mid - 1;
		} else l = mid + 1;
	}
	printf("%d\n",ans);
	return 0;
}

#网易雷火笔试##网易雷火##笔经#