题目链接:Codeforces 383B Volcanoes
题目大意:给出n和m,表示在一个n*n的图上,从(1,1)开始移动,每可以向下或向右移动,问是否可以移动(n,n),m表示说有m块障碍物,给出它们的坐标。
解题思路:将障碍物按照y坐标大小后按照x坐标排序,然后对于每一列考虑可以移动到的区间。ans始终等于2*n-2。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100005;
struct state {
int x, y;
}blo[N], rec[N], cur[N];
ll n, m;
inline bool cmp (const state& a, const state& b) {
if (a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
void init () {
cin >> n >> m;
int xx, yy;
for (int i = 0; i < m; i++) {
scanf("%d%d", &xx, &yy);
blo[i].x = xx; blo[i].y = yy;
}
}
bool judge () {
// if (n > m) return true;
sort(blo, blo + m, cmp);
int cnt = 1;
rec[0].x = 1, rec[0].y = 1;
for (int i = 0; i < m; i++) {
if (blo[i].y != blo[i-1].y + 1) {
cnt = 1;
rec[0].y = n;
}
int k, tmp = 0, c = 0;
for (k = i + 1; blo[k].y == blo[i].y; k++); k--;
for (int j = i; j <= k; j++) {
if (blo[j].x > tmp + 1) {
cur[c].x = tmp + 1; cur[c].y = blo[j].x - 1;
c++;
}
tmp = blo[j].x;
}
if (n > tmp) {
cur[c].x = tmp + 1; cur[c].y = n; c++;
}
int t = 0;
for (int i = 0; i < cnt; i++) {
while (cur[t].x <= rec[i].y && t < c) {
if (cur[t].y >= rec[i].x) {
cur[t].x = max(cur[t].x, rec[i].x);
} else {
cur[t].x = cur[t].y = -1;
}
t++;
}
if (t >= c) break;
}
cnt = 0;
for (int i = 0; i < t; i++) if (cur[i].x != -1 && cur[i].y != -1) {
rec[cnt].x = cur[i].x; rec[cnt].y = cur[i].y; cnt++;
}
if (cnt == 0) return false;
i = k;
}
if (blo[m-1].y != n) return true;
if (rec[cnt-1].y == n) return true;
return false;
}
int main () {
init();
if (judge()) cout << 2 * n - 2 << endl;
else printf("-1\n");
return 0;
}
分享到:
相关推荐
波兰球和游戏: ://codeforces.com/problemset/problem/755/B 问题779 B.怪异的舍入: : 问题845 A.国际象棋锦标赛: : 问题884 B.日语填字游戏反击: : 问题985 A.国际象棋的放置: : 问题1042 A.长凳: : 问题1105...
268C Beautiful Sets of Points 传送门 题意:在n*m的格点图里尽量多的选点,使点之间两两距离不为整数,同时不能选(0,0). 构造水题了,很明显每行/列最多放一个,那么最多应该放min(n,m)+1个,由于0,0不能选,直接...
Codeforces - 1107B. Digital root & 1107C. Brutality(规律 & 贪心)Codeforces - 1107B.
# sublime-plugin-for-codeforces 自定义构建,用于从 codeforces 获取测试用例并检查程序是否正确。 平台:GNU/Linux 语言:Python2.7.9 描述:这个程序从 codeforces 中获取测试用例,并告诉你程序的输出是否与...
codeForces C ++中的Code Force解决方案
编码 C ++中的Codeforce问题的解决方案
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
打codeforces的神器
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces每日一练。 题意: 给定n个点,m条有向边,以及k时间。求不超过k时间1-n最多能经过多少个点。 思路: 数据<=5000,说明是个暴力dp。 那么可以用dp[i][j]维护从1到i点经过了j个点,然后初始化为inf,再设...
codeforces编程网站预测分数插件
Codeforces扩展包 是否曾经想让Codeforce拥有方便的快捷键,自动更新排行榜,可以按需隐藏/显示的问题标签,更好的站点导航,深色主题或以上所有功能? 这些和更多功能可以在Codeforces ++中获得! 该扩展是开源的,...
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
解决问题(문제해결) ACM-ICPC凭证,BOJ,CodeForces,Codewars,SCPC,摇动,TopCoder凭证
Codeforces 185A - Plant 全测试点49个
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
竞争性编程的一些重要链接
Codeforces global round 10 codes
Codeforces round 678 division 2 codes