Codeforces Round #310 (Div. 一) A B C D题
Codeforces Round #310 (Div. 1) A B C D题
B题：
C题：
D题：
PS：
本题解包含题目：
| 555A |
Case of Matryoshkas
|
| 555B |
Case of Fugitive
|
| 555C |
Case of Chocolate
|
| 555D |
Case of a Top Secret
|
A题：
n（2*10^5）个大小不同的套娃 按照小的能套在大的里面的规则 已经按输入顺序套好了m个 问 最少拆、套几次可以形成1在2里 2在3里……n-1在n里 这种情况
思路：
我们可以这样理解一次操作——将大套娃拆开取出里面、套上一个大号的套娃 很明显每一步都是针对当前要处理的套娃中最大的那个进行的 那么最终状态一定是找到最长的1…x连续序列 除了这个序列外所有套娃全拆开 再按顺序套好
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cstdlib>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long LL;
#define N 200010
int n, m, now;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int p;
scanf("%d", &p);
for (int j = 1; j <= p; j++) {
int x;
scanf("%d", &x);
if (x == j) now++;
}
}
printf("%d\n", n - now - m + 1 + n - now);
return 0;
}
B题：
数轴上有n（2*10^5）个不相交的区间和m（2*10^5）个桥 每座桥可以连接相邻两个区间[a,b]和[c,d]当且仅当桥长l<=d-a且l>=c-b 每座桥最多使用一次 求 建桥的方案
思路：
两个相邻区间可建桥的桥长范围是[c-b,d-a] 将这些范围和桥排序 很明显对于一座桥 要么不使用 要么就应该把它分配给 满足桥长范围约束条件下(在[c-b,d-a]范围内) 可容纳最长桥长(d-a)最小 的那个位置 那么用堆维护就好了
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cstdlib>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long LL;
#define N 200010
int n, m, cnt;
int ans[N];
struct bridge {
LL l;
int id;
bool operator<(const bridge ff) const {
return l < ff.l;
}
} b[N];
struct section {
LL l, r, id;
bool operator<(const section ff) const {
return l < ff.l;
}
} s[N];
struct node {
int id;
LL r;
node() {
}
node(LL r, int id) {
this->r = r;
this->id = id;
}
bool operator<(const node ff) const {
return r > ff.r;
}
};
priority_queue<node> qu;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%I64d%I64d", &s[i].l, &s[i].r);
for (int i = 1; i < n; i++) {
LL tmpl, tmpr;
tmpr = s[i + 1].r - s[i].l;
tmpl = s[i + 1].l - s[i].r;
s[i].l = tmpl;
s[i].r = tmpr;
s[i].id = i;
}
sort(s + 1, s + n);
for (int i = 1; i <= m; i++) {
scanf("%I64d", &b[i].l);
b[i].id = i;
}
sort(b + 1, b + m + 1);
int idx = 1;
for (int i = 1; i <= m; i++) {
while (idx < n && s[idx].l <= b[i].l) {
qu.push(node(s[idx].r, s[idx].id));
idx++;
}
if (qu.empty()) continue;
node x = qu.top();
qu.pop();
if (x.r < b[i].l) break;
cnt++;
ans[x.id] = b[i].id;
}
if (cnt == n - 1) {
puts("Yes");
printf("%d", ans[1]);
for (int i = 2; i < n; i++) printf(" %d", ans[i]);
puts("");
} else puts("No");
return 0;
}
C题：
n*n(10^9)的格子 按/方向对角线划开 保留左上部分 m(2*10^5)个询问 每次在/对角线上选一点 向左或向上延伸到最近的空格 并将路线上的格子变成空格 输出变成空格的格子数
思路：
很明显先离散化 我们将横向延伸和纵向延伸分开讨论
由于只有向左和向上两个方向 因此对于向左延伸 只需记录当前y坐标下 最大空格的x是多少 用x做差就是输出值 然后更新对应x区间在横向延伸上的y值记录 向上延伸同理
那么只需要建横纵两棵线段树 单点查询 区间修改 就好了
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cstdlib>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long LL;
#define N 200010
#define L(x) (x<<1)
#define R(x) ((x<<1)|1)
#define MID(x,y) ((x+y)>>1)
int n, m;
struct ops {
int x, y, to;
} op[N];
int x[N], y[N], vis[N];
struct tree {
int l, r, lazy, near;
} f[2][N << 2];
void init(int l, int r, int i) {
for (int j = 0; j < 2; j++) {
f[j][i].l = l;
f[j][i].r = r;
f[j][i].near = f[j][i].lazy = 0;
}
if (l == r) return;
int mid = MID(l, r);
init(l, mid, L(i));
init(mid + 1, r, R(i));
}
void down(int i, int j) {
if (f[j][i].lazy) {
f[j][L(i)].lazy = max(f[j][L(i)].lazy, f[j][i].lazy);
f[j][L(i)].near = max(f[j][L(i)].near, f[j][i].lazy);
f[j][R(i)].lazy = max(f[j][R(i)].lazy, f[j][i].lazy);
f[j][R(i)].near = max(f[j][R(i)].near, f[j][i].lazy);
f[j][i].lazy = 0;
}
}
void update(int l, int r, int i, int j, int key) {
if (f[j][i].l == l && f[j][i].r == r) {
f[j][i].near = max(f[j][i].near, key);
f[j][i].lazy = max(f[j][i].lazy, key);
return;
}
down(i, j);
int mid = MID(f[j][i].l, f[j][i].r);
if (r <= mid) update(l, r, L(i), j, key);
else if (l > mid) update(l, r, R(i), j, key);
else {
update(l, mid, L(i), j, key);
update(mid + 1, r, R(i), j, key);
}
}
int query(int p, int i, int j) {
if (f[j][i].l == f[j][i].r) return f[j][i].near;
down(i, j);
int mid = MID(f[j][i].l, f[j][i].r);
if (p <= mid) return query(p, L(i), j);
else return query(p, R(i), j);
}
int main() {
char UL[5];
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d%s", &op[i].x, &op[i].y, UL);
x[i] = op[i].x;
y[i] = op[i].y;
if (UL[0] == 'U') op[i].to = 0;
else op[i].to = 1;
}
sort(x + 1, x + m + 1);
sort(y + 1, y + m + 1);
for (int i = 1; i <= m; i++) {
op[i].x = lower_bound(x + 1, x + m + 1, op[i].x) - x;
op[i].y = lower_bound(y + 1, y + m + 1, op[i].y) - y;
}
init(1, m, 1);
for (int i = 1; i <= m; i++) {
if (!vis[op[i].x]) {
int to, tmpx, tmpy, ans;
to = op[i].to;
tmpx = (to) ? op[i].y : op[i].x;
tmpy = (to) ? op[i].x : op[i].y;
ans = query(tmpx, 1, to);
printf("%d\n", (to) ? (x[tmpy] - x[ans]) : (y[tmpy] - y[ans]));
vis[op[i].x] = 1;
update(ans + 1, tmpy, 1, to^1, tmpx);
} else printf("0\n");
}
return 0;
}
D题：
数轴上有n(2*10^5)个钉子 m(2*10^5)次询问 每次询问在某个钉子上用l长的绳子挂一重物并向右推重物 绳子开始旋转并且可能会碰到新的钉子 然后就绕新的钉子旋转 直到绳子绕一个钉子不停旋转为止 问 这个钉子的标号是几
思路：
除了模拟过程以外并不能想到什么好方法= = 当然模拟的过程中每次找新的钉子要二分去找 那么复杂度看似O(mnlogn)
但是随便想一下就知道 绝对不可能这么坏 旋转中心变换的区间越来越小 期望情况下每次能减少大约一半的钉子数 那么效率比O(mlognlogn)差一些是完全可以接受的 我写了一下 还是TLE在16组数据…
因为这里需要一个小优化 因为考虑到绳子很长 所以旋转中心很可能经常在x,y两个钉子上不停地相互交换 因此如果现在的旋转中心是y 上一次是x 下一次又要到x去 那么我们就计算绕圈圈的次数 这样可以快速缩小旋转中心变换的区间
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cstdlib>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long LL;
#define N 200010
int n, m;
int x[N], y[N];
struct peg {
int x, id;
bool operator<(const peg ff) const {
return x < ff.x;
}
} tmp[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &x[i]);
tmp[i].x = x[i];
tmp[i].id = i;
}
sort(x + 1, x + n + 1);
sort(tmp + 1, tmp + n + 1);
for (int i = 1; i <= n; i++)
y[tmp[i].id] = i;
while (m--) {
int i, l, to = 1, cnt = 0, last = -1;
scanf("%d%d", &i, &l);
i = y[i];
while (true) {
if (cnt == 2) {
printf("%d\n", tmp[i].id);
break;
}
if (to) {
if (i + 1 > n || x[i + 1] - x[i] > l) {
cnt++;
to ^= 1;
continue;
}
cnt = 0;
int pos = x[i] + l;
int idx = upper_bound(x + 1, x + n + 1, pos) - x - 1;
if (idx == last) {
if (l / (x[idx] - x[i]) % 2) {
l %= x[idx] - x[i];
last = i;
i = idx;
to ^= 1;
} else {
l %= x[idx] - x[i];
}
} else {
l -= x[idx] - x[i];
last = i;
i = idx;
}
} else {
if (i - 1 < 1 || x[i] - x[i - 1] > l) {
cnt++;
to ^= 1;
continue;
}
cnt = 0;
int pos = x[i] - l;
int idx = lower_bound(x + 1, x + n + 1, pos) - x;
if (idx == last) {
if (l / (x[i] - x[idx]) % 2) {
l %= x[i] - x[idx];
last = i;
i = idx;
to ^= 1;
} else {
l %= x[i] - x[idx];
}
} else {
l -= x[i] - x[idx];
last = i;
i = idx;
}
}
to ^= 1;
}
}
return 0;
}
PS：
博客沉寂了很久了 终于我又来刷题了~~~
上面看不懂的可以留言问我（毕竟语言表述能力有限= = 感觉自己写好差……）
版权声明：本文为博主原创文章，未经博主允许不得转载。