首页 > 代码库 > 百练2812:恼人的青蛙
百练2812:恼人的青蛙
传送门:http://bailian.openjudge.cn/practice/2812/
【题解】
垃圾题目毁我青春。
暴力枚举两个点,判断是否成立。
瞎jb判一判,剪剪枝就过了。
大概就是排序后如果当前x+dx已经大于n了就break
(听说会快很多(并没有))
我怎么这么傻逼啊:反正只有一条路径,只要找头两个即可,那么会省去很多时间。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5000 + 10; const int mod = 1e9+7; # define RG register # define ST static int n, m, K, ans = 0; struct point { int x, y; point() {} point(int x, int y) : x(x), y(y) {} friend bool operator == (point a, point b) { return a.x == b.x && a.y == b.y; } friend bool operator != (point a, point b) { return !(a==b); } friend bool operator < (point a, point b) { return a.x < b.x || (a.x == b.x && a.y < b.y); } friend bool operator > (point a, point b) { return a.x > b.x || (a.x == b.x && a.y > b.y); } }p[M]; bool mp[M][M]; inline bool in(int x, int y) { return 1 <= x && x <= n && 1 <= y && y <= m; } int main() { point cur; cin >> n >> m >> K; for (int i=1; i<=K; ++i) { scanf("%d%d", &p[i].x, &p[i].y); mp[p[i].x][p[i].y] = 1; } sort(p+1, p+K+1); for (int i=1; i<=K; ++i) for (int j=i+1, t; j<=K; ++j) { int dx = p[j].x - p[i].x, dy = p[j].y - p[i].y; if(p[j].x + dx < 1 || p[j].x + dx > n) break; if(in(p[i].x - dx, p[i].y - dy)) continue; if(p[j].y + dy < 1 || p[j].y + dy > m) continue; t = 2; cur = p[j]; while(in(cur.x + dx, cur.y + dy) && mp[cur.x + dx][cur.y + dy]) { cur = point(cur.x + dx, cur.y + dy); ++t; } if(in(cur.x + dx, cur.y + dy)) continue; if(t != 2) ans = max(ans, t); } cout << ans << endl; return 0; }
百练2812:恼人的青蛙
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。