Gym - 101190H Hard Refactoring——模拟

Gym - 101190H Hard Refactoring——模拟

题意：给定一些区间，问这些区间是否能完全覆盖【-(1<<15), (1<<15) - 1】,如果能的话输出true，完全没有覆盖的话输出false，否则按任意顺序输出区间合并后的结果，可能有错误输入，对于错误输入忽略就可以

思路：从输入中读取区间，存入结构体中，然后按照左区间排序，进行区间合并，合并时注意【1,2】【3,4】也是可以合并的

最后还有一个坑，对于【-(1<<15),y】【y,(1<<15) - 1】这种样例其实输出的是x<=y  x >=y

做这种题还是要静下心来

#include #include #include #include using namespace std;const int INF = 1e8;char str[1010];struct Seg { int L, R; bool operator < (const Seg &temp) { return L < temp.L; }}seg[1010], ans[100000];int main() { freopen("hard.in", "r", stdin); freopen("hard.out", "w", stdout); int cnt = 0; while (gets(str) != NULL) { bool flag = false; for (int i = 0; i < str[i] != '\0'; i++) { if (str[i] == '&') { flag = true; break; } } if (flag) { int i = 0, num1 = 0, num2 = 0, flag1 = 1, flag2 = 1; for (; str[i] != '&'; i++) { if (str[i] == '-') flag1 = -1; if ('0' <= str[i] && str[i] <= '9') { num1 = num1 * 10 + str[i] - '0'; } } num1 *= flag1; for (; str[i] != '\0'; i++) { if (str[i] == '-') flag2 = -1; if ('0' <= str[i] && str[i] <= '9') { num2 = num2 * 10 + str[i] - '0'; } } num2 *= flag2; if (num1 <= num2) { ++cnt; seg[cnt].L = num1, seg[cnt].R = num2; } } else { for (int i = 0; str[i] != '\0'; i++) { if (str[i] == '>') { int num = 0, flag = 1; for (; str[i] != '\0'; i++) { if (str[i] == '-') flag = -1; if ('0' <= str[i] && str[i] <= '9') { num = num * 10 + str[i] - '0'; } } num *= flag; ++cnt; seg[cnt].L = num, seg[cnt].R = INF; break; } else if (str[i] == '<') { int num = 0, flag = 1; for (; str[i] != '\0'; i++) { if (str[i] == '-') flag = -1; if ('0' <= str[i] && str[i] <= '9') { num = num * 10 + str[i] - '0'; } } num *= flag; ++cnt; seg[cnt].L = -INF, seg[cnt].R = num; break; } } } } if (cnt == 0) { printf("false\n"); return 0; } sort(seg + 1, seg + 1 + cnt); int acnt = 1; ans[acnt].L = seg[1].L, ans[acnt].R = seg[1].R; for (int i = 2; i <= cnt; i++) { if (ans[acnt].R >= seg[i].L - 1) { ans[acnt].R = max(ans[acnt].R, seg[i].R); } else { ++acnt; ans[acnt].L = seg[i].L, ans[acnt].R = seg[i].R; } } if (ans[1].L <= -(1<<15) && ans[1].R >= (1<<15) - 1) { printf("true\n"); } else if (ans[1].L > (1<<15) - 1 || ans[1].R < -(1<<15)) { printf("false\n"); } else { for (int i = 1; i <= acnt; i++) { if (ans[i].L <= -(1<<15)) { printf("x <= %d", ans[i].R); } else if (ans[i].R >= (1<<15) - 1) { printf("x >= %d", ans[i].L); } else { printf("x >= %d && x <= %d", ans[i].L, ans[i].R); } if (i != acnt) printf(" ||"); printf("\n"); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。