2015 아 스타 콘테스트 - Round 2B 문제 풀이
제목 의 대의
평면 안에 N 개의 점 이 있 고 Ti 시각 에 (Xi, Yi) 점 에서 공연 이 있 습 니 다. 0 시간 에 곰 은 임의의 출발점 에서 출발 하고 이동 속 도 는 1 개의 디자인 노선 으로 모든 공연 시간 에 공연 장소 거리 에서 의 최대 치 최소 답안 출력 점수 형식 입 니 다.
알고리즘 사고
평면 상의 맨 해 튼 거 리 는 좌 표를 통 해 전환 할 수 있 고 1 차원 수축 의 문제 가 될 수 있다. 즉, 두 점 사이 의 맨 해 튼 거 리 는 두 점 이 x + y 수축 공간 과 x - y 수축 공간 에서 거리의 최대 치 와 같다. 본 문제 에 대해 두 개의 수축 에서 동시에 시간 에 따라 정렬 할 수 있 는 지 판단 한 다음 에유지 구간 의 교 집합 은 매번 원래 구간 을 좌우 로 이동 할 수 있 는 거 리 를 확장 한 다음 에 현재 좌표 양쪽 의 실행 가능 한 구역 과 최종 구역 이 비어 있 는 지 여 부 를 판단 합 니 다. 실행 가능 한 구역 의 점 은 두 개의 정점 사이 에 있 을 수 있 기 때문에 모든 좌 표를 2 로 곱 하고 마지막 에 패 리 티 에 따라 출력 합 니 다.
시간 복잡 도: O (NLogN)
코드
/** * Copyright © 2015 Authors. All rights reserved. * * FileName: A.cpp * Author: Beiyu Li <[email protected]> * Date: 2015-06-09 */
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
typedef long long LL;
typedef pair<int, int> Pii;
const int inf = 0x3f3f3f3f;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;
const int maxn = 50000 + 5;
int n;
struct Point {
int t;
LL x[2];
bool operator<(const Point &p) const { return t < p.t; }
} a[maxn];
bool check(LL d)
{
rep(o,2) {
LL l = a[0].x[o] - d, r = a[0].x[o] + d;
for (int i = 1; i < n; ++i) {
LL dt = a[i].t - a[i-1].t;
l = max(l - dt * 2, a[i].x[o] - d);
r = min(r + dt * 2, a[i].x[o] + d);
if (l > r) return false;
}
}
return true;
}
int main()
{
int T, cas = 0;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
rep(i,n) {
int x, y;
scanf("%d%d%d", &x, &y, &a[i].t);
a[i].x[0] = (LL)(x + y) * 2;
a[i].x[1] = (LL)(x - y) * 2;
}
sort(a, a + n);
LL l = 0, r = infLL;
while (l < r) {
LL mid = l + ((r - l) >> 1);
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("Case #%d:
", ++cas);
printf("%I64d/%I64d
", r & 1? r: r / 2, (r & 1) + 1);
}
return 0;
}1002 연결 파이프
제목 의 대의
N * M 크기 의 농토 가 있 습 니 다. 밭 마다 높이 가 있 습 니 다. 인접 한 두 밭 사이 에 파 이 프 를 건설 하 는 대 가 는 높이 차이 입 니 다. 지금 은 파이프 로 모든 농 지 를 연결 하고 최소 대 가 를 물 어 봐 야 합 니 다.
알고리즘 사고
격자 그림 의 최소 생 성 트 리
시간 복잡 도: O (N2logN 2)
코드
/** * Copyright © 2015 Authors. All rights reserved. * * FileName: B.cpp * Author: Beiyu Li <[email protected]> * Date: 2015-06-09 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
typedef long long LL;
typedef pair<int, int> Pii;
const int inf = 0x3f3f3f3f;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;
const int maxn = 1000 + 5;
int n, m;
int a[maxn][maxn];
int dis[maxn][maxn];
bool vis[maxn][maxn];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
bool inside(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; }
int prim()
{
int res = 0;
priority_queue<Pii> que;
memset(dis, 0x3f, sizeof(dis));
memset(vis, false, sizeof(vis));
dis[0][0] = 0; que.push(Pii(0, 0));
while (!que.empty()) {
int x = que.top().second / m, y = que.top().second % m;
que.pop();
if (vis[x][y]) continue; vis[x][y] = true, res += dis[x][y];
rep(i,4) {
int nx = x + dx[i], ny = y + dy[i];
if (!inside(nx, ny)) continue;
int w = abs(a[x][y] - a[nx][ny]);
if (w < dis[nx][ny]) {
dis[nx][ny] = w;
que.push(Pii(-dis[nx][ny], nx * m + ny));
}
}
}
return res;
}
int main()
{
int T, cas = 0;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
rep(i,n) rep(j,m) scanf("%d", &a[i][j]);
printf("Case #%d:
", ++cas);
printf("%d
", prim());
}
return 0;
}1003 바둑판 점령
제목 의 대의
N * M 의 바둑판 이 있 습 니 다. 처음에 일부 칸 을 점령 했 습 니 다. 만약 에 한 칸 이 상하 좌우 로 인접 한 4 개의 칸 중 두 개의 공공 점 이 있 는 칸 이 점령 당 하면 이 칸 도 점령 당 합 니 다. 마지막 에 몇 개의 칸 이 점령 당 했 는 지 물 어 봅 니 다.
알고리즘 사고
한 칸 이 점령 당 하면 최대 상하 좌우 로 인접 한 4 칸 의 상 태 를 바 꿔 BFS 를 사용 하고, 매번 팀 머리 와 인접 한 칸 이 점령 당 하 는 지 살 펴 보고, 입단 하면 된다.
시간 복잡 도: O (N2)
코드
/** * Copyright © 2015 Authors. All rights reserved. * * FileName: C.cpp * Author: Beiyu Li <[email protected]> * Date: 2015-06-09 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
typedef long long LL;
typedef pair<int, int> Pii;
const int inf = 0x3f3f3f3f;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;
const int maxn = 500 + 5;
int n, m, g;
bool vis[maxn][maxn];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
bool inside(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; }
bool check(int x, int y)
{
rep(i,4) {
int x1 = x + dx[i], y1 = y + dy[i];
int x2 = x + dx[(i+1)%4], y2 = y + dy[(i+1)%4];
if (inside(x1, y1) && vis[x1][y1] &&
inside(x2, y2) && vis[x2][y2]) return true;
}
return false;
}
int main()
{
int T, cas = 0;
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &n, &m, &g);
int res = 0, x, y;
queue<Pii> que;
memset(vis, false, sizeof(vis));
while (g--) {
scanf("%d%d", &x, &y);
que.push(Pii(--x, --y));
}
while (!que.empty()) {
int x = que.front().first, y = que.front().second;
que.pop();
if (vis[x][y]) continue; vis[x][y] = true, ++res;
rep(i,4) {
int nx = x + dx[i], ny = y + dy[i];
if (!inside(nx, ny)) continue;
if (check(nx, ny)) que.push(Pii(nx, ny));
}
}
printf("Case #%d:
", ++cas);
printf("%d
", res);
}
return 0;
}1004 마법 인자
제목 의 대의
제 시 된 실수 X 에 대해 10 위 를 넘 지 않 는 모든 정수 N 을 찾 아 N * X 를 만족 시 키 는 것 은 여전히 정수 이 고 N 의 첫 번 째 와 마지막 위 치 를 교환 하 는 형식 이다.
알고리즘 사고
10 + c, N ∗ X = c ∗ 10k + b ∗ 10 + a 는 b = X ∗ (a ∗ 10k + c) − (c ∗ 10k + a) 1 − X ÷ 10 개의 X 를 점수 형식 X = yz 득, b = y \8727, b = y ∗ (a \8727k + c) − (c ∗ 10k + a) 1 − X 10 개의 X 를 X 로 X 를 점수 형식 X = yz 득, b = y \8727, b = y \8727, b = y ∗ (a \8727k + c) - z ∗ (c \8727k + c + a) - 10 k + a) - 10 개의 X X 를 점수 형식 X = yz 득, b 10. 이로부터 우 리 는 a, c 와 k 의 값 을 매 거 하여 충분 한 범위 의 b 를 얻 을 수 있 는 지 확인 할 수 있다.
시간 복잡 도: O (103)
코드
/** * Copyright © 2015 Authors. All rights reserved. * * FileName: D.cpp * Author: Beiyu Li <[email protected]> * Date: 2015-06-10 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
typedef long long LL;
typedef pair<int, int> Pii;
const int inf = 0x3f3f3f3f;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;
int main()
{
int T, cas = 0;
scanf("%d", &T);
while (T--) {
double x;
scanf("%lf", &x);
int y = x * 1000000 + 0.5, z = 1000000, m = (z - y) * 10;
vector<LL> vec;
for (LL i = 1, p = 10; i < 10; ++i, p *= 10) {
for (int a = 1; a < 10; ++a) rep(c,10) {
LL b = y * (a * p + c) - z * (c * p + a);
if (b % m) continue; b /= m;
if (0 <= b && b * 10 < p)
vec.push_back(a * p + b * 10 + c);
}
}
sort(vec.begin(), vec.end());
printf("Case #%d:
", ++cas);
printf("%d
", (int)vec.size());
foreach(it,vec) printf("%I64d%c", *it, "
"[it==--vec.end()]);
}
return 0;
}
1005 시퀀스 변환
제목 의 대의
정수 수열 을 제시 하고 가장 적은 수 를 조정 하여 이 수열 을 엄 격 히 증가 시 켜 야 한다.
알고리즘 사고
임의의 두 개의 조정 할 필요 가 없 는 수 에 대해 서 는 Aj - Aj ≥ j - i, 즉 Ai - i ≤ Aj - j 가 있어 야 한다. 따라서 수열 각 비트 의 수 치 를 아래 표 에서 빼 면 조정 할 필요 가 없 는 수 는 반드시 비 강하 자 서열 을 구성 하여 가장 긴 비 강하 자 서열 의 길 이 를 찾 아야 한다. 총 길이 로 빼 면 최소 조정 해 야 할 개수 이다.
시간 복잡 도: O (NLogN)
코드
/** * Copyright © 2015 Authors. All rights reserved. * * FileName: E.cpp * Author: Beiyu Li <[email protected]> * Date: 2015-06-10 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
typedef long long LL;
typedef pair<int, int> Pii;
const int inf = 0x3f3f3f3f;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;
const int maxn = 100000 + 5;
int n;
int a[maxn], g[maxn];
int main()
{
int T, cas = 0;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
rep(i,n) scanf("%d", &a[i]);
memset(g, 0x3f, sizeof(g));
int ret = 0;
rep(i,n) {
int p = upper_bound(g + 1, g + n + 1, a[i] - i) - g;
ret = max(ret, p);
g[p] = a[i] - i;
}
printf("Case #%d:
", ++cas);
printf("%d
", n - ret);
}
return 0;
}1006 뒤 집기 게임
제목 의 대의
N * M 칸 중 일 부 는 검은색 이 고 일 부 는 흰색 입 니 다. 한 칸 을 선택 할 때마다 한 번 씩 누 르 면 칸 과 주변 에 있 는 칸 이 뒤 집 히 고 색깔 이 고장 나 서 누 를 수 없습니다. 모든 칸 을 흰색 으로 바 꿀 수 있 는 지 물 어보 세 요.
알고리즘 사고
먼저, 각 칸 마다 최대 한 번 조작 할 수 있 기 때문에 각 칸 의 조작 여 부 는 0 / 1 상태 로 그 다음 을 표시 할 수 있 습 니 다. 작업 의 효과 가 반대로 설정 되 어 있 기 때문에 각 칸 의 상태 가 바 뀌 는 것 은 관련 작업 의 차이 나 마지막 에 해당 합 니 다. 매번 조작 이 상기 줄 에 가장 많은 영향 을 미 치기 때 문 입 니 다.그래서 첫 번 째 줄 의 조작 이 확 정 된 후에 첫 번 째 줄 의 상 태 는 두 번 째 줄 의 조작 으로 만 조정 할 수 있 기 때문에 두 번 째 줄 의 조작 도 이에 따라 확정 된다. 이 를 통 해 모든 칸 의 조작 은 첫 번 째 줄 의 선형 차이 나 조합 이 라 고 할 수 있다. 그러면 우 리 는 첫 번 째 줄 의 조작 을 M 개의 0 / 1 변수 로 설정 할 수 있다.모든 칸 의 조작 은 하나의 이 또는 방정식 으로 K 개의 고장 난 칸 과 N + 1 줄 의 칸 (존재 한다 고 가정) 이다. 조작 결 과 는 반드시 0 답 이 어야 한다. 이 방정식 팀 에 대해 풀이 가 있 는 지 없 는 지, 고 스 소원 으로 풀 수 있다.
시간 복잡 도: O (N3)
코드
/** * Copyright © 2015 Authors. All rights reserved. * * FileName: F.cpp * Author: Beiyu Li <[email protected]> * Date: 2015-06-10 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <bitset>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
typedef long long LL;
typedef pair<int, int> Pii;
const int inf = 0x3f3f3f3f;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;
const int maxn = 256 + 5;
int gauss(bitset<maxn> a[], int n, int m)
{
int rank = 0;
for (int i = 0; i < m; ++i) {
int r = rank;
while (r < n && !a[r].test(i)) ++r;
if (r >= n) continue;
swap(a[rank], a[r]);
for (int j = rank + 1; j < n; ++j)
if (a[j].test(i)) a[j] ^= a[rank];
++rank;
}
for (int i = rank; i < n; ++i) if (a[i].test(m)) return -1;
return rank;
}
int n, m, k;
bool g[maxn][maxn], a[maxn][maxn];
bitset<maxn> b[maxn][maxn], vec[maxn*2];
int main()
{
int T, cas = 0;
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &n, &m, &k);
rep(i,n) {
char s[maxn];
scanf("%s", s);
rep(j,m) g[i][j] = (s[j] == 'B');
}
memset(a, true, sizeof(a));
rep(i,k) {
int x, y;
scanf("%d%d", &x, &y);
a[--x][--y] = false;
}
k = 0;
rep(j,m) b[0][j].reset(), b[0][j].set(j);
rep(i,n) {
rep(j,m) if (!a[i][j]) vec[k++] = b[i][j];
rep(j,m) {
b[i+1][j] = b[i][j];
if (i) b[i+1][j] ^= b[i-1][j];
if (j) b[i+1][j] ^= b[i][j-1];
if (j + 1 < m) b[i+1][j] ^= b[i][j+1];
if (g[i][j]) b[i+1][j].flip(m);
}
}
rep(j,m) vec[k++] = b[n][j];
printf("Case #%d:
", ++cas);
puts(~gauss(vec, k, m)? "YES": "NO");
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode - 503. 다음 더 큰 요소 II (Next Greater Element II) [중간] - 분석 및 코드 (Java)순환 배열 (마지막 요소 의 다음 요 소 는 배열 의 첫 번 째 요소) 을 지정 하고 모든 요소 의 다음 요 소 를 출력 합 니 다.숫자 x 의 다음 더 큰 요 소 는 배열 에 따라 순 서 를 옮 겨 다 니 는 것 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
