首页 > 代码库 > Codeforces731D 80-th Level Archeology
Codeforces731D 80-th Level Archeology
考虑将两个单词变成有序,我们可以得到一个或者两个旋转次数的区间。
然后考虑将两组单词变成有序,比如[l,mid]和[mid+1,r],对于mid和mid+1这两个单词我们可以求出使他们有序的旋转次数的区间。
然后将这个区间与[l,mid]的区间以及[mid+1,r]的区间求交,就可以得到使[l,r]有序的旋转次数的区间。
上面这个过程我们可以用分治来进行,区间求交可以用扫描线法。
#include <bits/stdc++.h> using namespace std; vector<int> words[500010]; int cnt[1000010]; int n, c; int tot = 0; void calc(int a, int b) { int idx = 0; while (idx < words[a].size() && idx < words[b].size()) { if (words[a][idx] != words[b][idx]) break; idx++; } if (idx < words[a].size() && idx < words[b].size()) { if (words[a][idx] < words[b][idx]) { cnt[0]++; cnt[c - words[b][idx] + 1]--; cnt[c + 1 - words[a][idx]]++; cnt[c]--; tot++; } else { cnt[c + 1 - words[a][idx]]++; cnt[c - words[b][idx] + 1]--; tot++; } } else if (idx == words[a].size() && idx != words[b].size()) { cnt[0]++; cnt[c]--; tot++; } else if (idx != words[a].size() && idx == words[b].size()) tot++; else { cnt[0]++; cnt[c]--; tot++; } } void divideConquer(int l, int r) { if (l == r) return; int mid = (l + r) >> 1; divideConquer(l, mid); divideConquer(mid + 1, r); calc(mid, mid + 1); } int main() { scanf("%d%d", &n, &c); for (int i = 0; i < n; i++) { int l, w; scanf("%d", &l); while (l--) { scanf("%d", &w); words[i].push_back(w); } } divideConquer(0, n - 1); bool ok = false; int sum = 0; for (int i = 0; i < c; i++) { sum += cnt[i]; if (sum == tot) { ok = true; printf("%d", i); break; } } if (!ok) printf("-1"); return 0; }
Codeforces731D 80-th Level Archeology
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。