网易雷火9.18笔试
1.21年icpc银川站原题?
找到起始点(1,1,)(左上为0),然后dfs,
2.假设答案坐标一定包含第i个点,那么包含第 i 个点 的答案坐标不超过710个(R = 20的情况下),把所有可能的点拿出来 算一下答案,取最优 复杂度(7e8) 居然过了。
#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; }
应该还可以把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; }
输出L1 + L2 -> 过11%
4.显然每个人会不停的去摘花,我们二分一下用时最长的一个人的用时为 T,那么每个人能取到的的第1.2种花的数量假设为x,y,满足 x * a1 + y * a2 <= T
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; }