前言

继续更完这几个博客，再鸽就要明年了…

复盘

I - Intervals on the Ring

给定$m$个区间，$1 \leq l \leq r \leq 10^3$，请你构造若干个区间（不超过$2000$），使得你所构造的区间的交集等于$m$个区间的并集。

签到题。首先观察到不超过2000，可以联想对于某一个位置，最多使用两个区间的交来表示出来。

那么我们就有一种构造方案：

对于某一不在区间并内的位置$pos$​​​，我们可以用区间$[1,pos-1],[pos+1,n]$两个区间的交来表示这个位置是不存在的（对于$pos-1$和$pos+1$可能超过边界的情况需要讨论）。

而求区间并，用差分算一下就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/* vegetable1024 | oi-liu.com | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 2005
#define int long long
using namespace std;
int t, n, m, d[maxn], a[maxn], cnt, ans1[maxn], ans2[maxn];
int read(){
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9')    ch = getchar();
    while(ch >= '0' && ch <= '9')  x = x * 10 + ch - '0', ch = getchar();
    return x;
}

signed main(void)
{
    t = read();
    while(t--)
    {
        cnt = 0;
        memset(d, 0, sizeof(d));
        n = read();
        m = read();
        for(int i = 1; i <= m; i++)
        {
            int lf = read(), rt = read();
            if(lf <= rt)    
                d[lf]++, d[rt + 1]--;
            else
                d[lf]++, d[n + 1]--, d[1]++, d[rt + 1]--;
        }
        for(int i = 1; i <= n; i++)
            a[i] = a[i - 1] + d[i];
        /*
        for(int i = 1; i <= n; i++)
            printf("%d ", a[i]);
        putchar('\n');
        */
        int pos = 1;
        while(pos <= n)
        {
            int now = pos;
            while(a[now] == 0 && now <= n)    now++;
            if(now != pos)
            {
                cnt++;
                ans1[cnt] = now == n + 1 ? 1 : now;
                ans2[cnt] = pos == 1 ? n : pos - 1;
                pos = now + 1;
            }
            else    pos++;
        }
        if(cnt == 0)
        {
            cnt++;
            printf("%lld\n", cnt);
            printf("%lld %lld\n", 1, n);
            continue;
        }
        printf("%lld\n", cnt);
        for(int i = 1; i <= cnt; i++)
            printf("%lld %lld\n", ans1[i], ans2[i]);
    }
    return 0;
}

F - Hamburger Steak

二分/贪心。

这题比赛时候读假了，以为分两个锅煎的时候，从第一个锅出来后要立刻转移到第二个锅…

然后就写挂了（

读对题之后，第一个想法是二分最小可行的时间。

下界设为$L$，在本题中，理应是煎的时间最长的$Steak$所需要的时间。

上界不知道，于是就设置为所有需要煎的时间的和。

$check$的时候贪心的从第一个锅放到第$n$个锅，这里要明确从第一个锅出来后不一定要立刻转移到第二个锅，这样我们就能：

  • 当前锅剩余时间足够煎完这块，就贪心放下去
  • 当前锅时间不够了，就分两个锅贪心放下去。
  • 由于我们的下界是煎的时间最长的$Steak$所需时间，因此所有的$Steak$​一定能在这种策略下在两个锅中被煎完，而且时间上不会重叠。
  • $check$时候看一下，如果需要锅的数量超过了$n$，则返回$false$.

由于二分是$log$的，这样也足够通过该题了。

不过事实上是不需要二分的，最小时间我们只需要取$max(\lceil \frac{sum}{n} \rceil, max(t_{1 \dots n}))$​​

同样明确，从第一个锅出来后不一定要立刻转移到第二个锅，因此我们要做到让每个$Steak$​煎炸的时间尽可能地平均，也就是$\lceil \frac{sum}{n} \rceil$​。当然，由于每个$Steak$​最多只能在两个锅中出现，而且时间不能重叠，因此下界一定要设为$max(t_{1 \dots n})$​。

二分代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/* vegetable1024 | liushan.site | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
    std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
    std::cout << head << ", ";
    Print(rail...);
}

int read(){
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9')    ch = getchar();
    while(ch >= '0' && ch <= '9')  x = x * 10 + ch - '0', ch = getchar();
    return x;
}
int n, m, mxt, t[maxn];
bool check(int val){
    int sum = 0, pos = 1;
    for(int i = 1; i <= n; i++)
    {
        if(sum + t[i] <= val)    sum += t[i];
        else
        {
            sum = t[i] - (val - sum);
            pos++;
        }
        if(pos > m)    return false;
    }
    return true;
}
void solve(int val){
    int sum = 0, pos = 1;
    for(int i = 1; i <= n; i++)
    {
        if(sum == val)
        {
            pos++;
            sum = 0;
            printf("%lld %lld %lld %lld\n", 1LL, pos, sum, sum + t[i]);
            sum += t[i];
        }
        else if(sum + t[i] <= val)    
        {
            printf("%lld %lld %lld %lld\n", 1LL, pos, sum, sum + t[i]);
            sum += t[i];
        }
        else
        {
            printf("%lld %lld %lld %lld %lld %lld %lld\n", 2LL, pos + 1, 0LL, t[i] - (val - sum), pos, sum, val);
            sum = t[i] - (val - sum);
            pos++;
        }
    }
}
signed main(void)
{
    n = read(); m = read();
    for(int i = 1; i <= n; i++)    
        t[i] = read(), mxt = max(mxt, t[i]);
    int lf = mxt, rt = 1e18, ans = -1;
    while(lf <= rt)
    {
        int mid = (lf + rt) / 2;
        check(mid) ? ans = mid, rt = mid - 1 : lf = mid + 1;
    }
    //Print(ans);
    solve(ans);
    return 0;
}

H - Hopping Rabbit

扫描线。

比赛时候看着以为是数论题，要解方程，然后又炸了（

实际上，关键点在于每次的移动长度都是$d$，要让兔子怎么跳都不会跳进陷阱，只需要在$(0,0)$到$(d,d)$​这段矩形区域中，找到不被覆盖的点。

而为了将那些不在这个区域内的陷阱拉过来，我们可以用取模的方法（加上分类讨论），将所有的陷阱都映射到$(0,0)$到$(d,d)$​这段矩形区域。此时，再对这个区域做一次扫描线面积并，发现哪一行的面积不为$d$​，就可以输出对应的点了。

区域映射见下图：

image-20210904153651199

对应测试数据：

1
2
3
4
5
4 3
2 -2 4 -1
-3 -2 -2 1
-1 -1 1 1
-10 1 10 2

另外，最开始的时候用了个扫描线线段树是对每个边建节点的模板，调整的时候写了几个$bug$​​，脑子有点糊糊的，后面换了对点建节点的模板，感觉还是这个好理解一点。

模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
struct Line {
    //表示为线的矩形的左右边界
	int x, y1, y2;
    int mark;
    bool operator < (const Line &A){
        return x < A.x;;
    }
};
struct SegTree {
	int lf, rt;
    int len;
    int lazy;
} tree[maxn];
void Build(int now, int lf, int rt) {
	tree[now].lf = lf; 
    tree[now].rt = rt;
	tree[now].len = 0;
	if(lf == rt)    return;
	int mid = (lf + rt) >> 1;
	Build(lson(now), lf, mid);
	Build(rson(now), mid + 1, rt);
}
void Pushdown(int now) {
	if(tree[now].lazy != 0) 
    {
		tree[lson(now)].len += tree[now].lazy;
		tree[rson(now)].len += tree[now].lazy;
		tree[lson(now)].lazy += tree[now].lazy;
		tree[rson(now)].lazy += tree[now].lazy;
		tree[now].lazy = 0;
	}
}
void Update(int now, int L, int R, int v) {
	int nowlf = tree[now].lf, nowrt = tree[now].rt;
    if(nowlf >= L && nowrt <= R) 
    {
		tree[now].len += v;
		tree[now].lazy += v;
		return;
	}
	Pushdown(now);
	int mid = (nowlf + nowrt) >> 1;
	if(L <= mid) 
        Update(lson(now), L, R, v);
	if(R > mid) 
        Update(rson(now), L, R, v);
	tree[now].len = min(tree[lson(now)].len, tree[rson(now)].len);
}
int ask(int now, int L, int R) {
	if(tree[now].lf >= L && tree[now].rt <= R) {
		return tree[now].len;
	}
	Pushdown(now);
	int mid = (tree[now].lf + tree[now].rt) >> 1;
    int res = (1LL << 30);
	if(L <= mid) 
        res = min(res, ask(lson(now), L, R));
	if(R > mid)
        res = min(res, ask(rson(now), L, R));
	return res;
}
vector<Line> SL[maxn];
//注意这里(0, 0)(0, 0)实际上代表(0, 0)(1, 1)这个矩形
//[0, 1] -> (0), [1, 2] -> (1)
void add(int x1, int y1, int x2, int y2) {
	SL[x1].push_back({x1, y1, y2, 1});
    //注意这里是x2 + 1 类似差分的思想
    SL[x2 + 1].push_back({x2 + 1, y1, y2, -1});
}

之前写的巨丑矩形转化代码（可能有BUG，最后调炸了就没用这个写了…）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
void inits(){
    for(int i = 1; i <= n; i++)
    {
        int mod = d;
        int nx1, nx2, ny1, ny2;
        if(r[i].x2 - r[i].x1 >= mod && r[i].y2 - r[i].y1 >= mod)
            nx1 = ny1 = 0, nx2 = ny2 = mod;
        else if(r[i].x2 - r[i].x1 >= mod)
            nx1 = 0, nx2 = mod,
            ny1 = (r[i].y1 % mod + mod) % mod, ny2 = (r[i].y2 % mod + mod) % mod;
        else if(r[i].y2 - r[i].y1 >= mod)
            ny1 = 0, ny2 = mod,
            nx1 = (r[i].x1 % mod + mod) % mod, nx2 = (r[i].x2 % mod + mod) % mod;
        else
            nx1 = (r[i].x1 % mod + mod) % mod, nx2 = (r[i].x2 % mod + mod) % mod,
            ny1 = (r[i].y1 % mod + mod) % mod, ny2 = (r[i].y2 % mod + mod) % mod;
         
        //Print(nx1, nx2, ny1, ny2);
 
        if(nx1 <= nx2 && ny1 <= ny2)
            nr[++cnt] = (retc){nx1, nx2, ny1, ny2};
        else if(nx1 <= nx2 && ny1 > ny2)
            nr[++cnt] = (retc){nx1, nx2, 0, ny2},
            nr[++cnt] = (retc){nx1, nx2, ny1, mod};
        else if(ny1 <= ny2 && nx1 > nx2)
            nr[++cnt] = (retc){0, nx2, ny1, ny2},
            nr[++cnt] = (retc){nx1, mod, ny1, ny2};
        else
            nr[++cnt] = (retc){0, nx2, 0, ny2},
            nr[++cnt] = (retc){nx1, mod, ny1, mod},
            nr[++cnt] = (retc){0, nx2, ny1, mod},
            nr[++cnt] = (retc){nx1, mod, 0, ny2};
    }
    for(int i = 1; i <= cnt; i++)
    {
        if(nr[i].x1 == nr[i].x2 || nr[i].y1 == nr[i].y2)    continue;
        fr[++fcnt] = (retc){nr[i].x1, nr[i].x2, nr[i].y1, nr[i].y2};
    }
    cnt = fcnt;
    /*
    printf("---\n");
    for(int i = 1; i <= cnt; i++)
        Print(fr[i].x1, fr[i].y1, fr[i].x2, fr[i].y2);
    printf("---\n");
    */
}

最后的$AC$代码：

参考学习了：2021牛客暑期多校训练营6 H. Hopping Rabbit（扫描线） - 脂环 - 博客园 (cnblogs.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>
#define int long long
#define maxn 800005
#define lson(x) (x << 1)
#define rson(x) (x << 1) + 1
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)

using namespace std;
int n, d;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
    std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
    std::cout << head << ", ";
    Print(rail...);
}
 
int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
        ch == '-' ? f = -1, ch = getchar() : ch = getchar();
    while(ch >= '0' && ch <= '9') 
        x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}

struct Line {
	int x, y1, y2;
    int mark;
    bool operator < (const Line &A){
        return x < A.x;;
    }
};
struct SegTree {
	int lf, rt;
    int len;
    int lazy;
} tree[maxn];
void Build(int now, int lf, int rt) {
	tree[now].lf = lf; 
    tree[now].rt = rt;
	tree[now].len = 0;
	if(lf == rt)    return;
	int mid = (lf + rt) >> 1;
	Build(lson(now), lf, mid);
	Build(rson(now), mid + 1, rt);
}
void Pushdown(int now) {
	if(tree[now].lazy != 0) 
    {
		tree[lson(now)].len += tree[now].lazy;
		tree[rson(now)].len += tree[now].lazy;
		tree[lson(now)].lazy += tree[now].lazy;
		tree[rson(now)].lazy += tree[now].lazy;
		tree[now].lazy = 0;
	}
}
void Update(int now, int L, int R, int v) {
	int nowlf = tree[now].lf, nowrt = tree[now].rt;
    if(nowlf >= L && nowrt <= R) 
    {
		tree[now].len += v;
		tree[now].lazy += v;
		return;
	}
	Pushdown(now);
	int mid = (nowlf + nowrt) >> 1;
	if(L <= mid) 
        Update(lson(now), L, R, v);
	if(R > mid) 
        Update(rson(now), L, R, v);
	tree[now].len = min(tree[lson(now)].len, tree[rson(now)].len);
}
int ask(int now, int L, int R) {
	if(tree[now].lf >= L && tree[now].rt <= R) {
		return tree[now].len;
	}
	Pushdown(now);
	int mid = (tree[now].lf + tree[now].rt) >> 1;
    int res = (1LL << 30);
	if(L <= mid) 
        res = min(res, ask(lson(now), L, R));
	if(R > mid)
        res = min(res, ask(rson(now), L, R));
	return res;
}
vector<Line> SL[maxn];
void add(int x1, int y1, int x2, int y2) {
	SL[x1].push_back({x1, y1, y2, 1});
    SL[x2 + 1].push_back({x2 + 1, y1, y2, -1});
}
signed main() {
    IO;
	cin >> n >> d;
	for(int i = 1; i <= n; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		x2--, y2--;
		if(x2 - x1 + 1 >= d) x1 = 0, x2 = d - 1; 
		if(y2 - y1 + 1 >= d) y1 = 0, y2 = d - 1;
		x1 = (x1 % d + d) % d, x2 = (x2 % d + d) % d, y1 = (y1 % d + d) % d, y2 = (y2 % d + d) % d;
		if(x2 >= x1) {
			if(y2 >= y1) {
				add(x1, y1, x2, y2);
			} else {
				add(x1, y1, x2 ,d - 1);
				add(x1, 0, x2 ,y2);
			}
		} else {
			if(y2 >= y1) {
				add(x1, y1, d - 1, y2);
				add(0, y1, x2, y2);
			} else {
				add(x1, y1, d - 1, d - 1);
				add(0, y1, x2, d - 1);
				add(x1, 0, d - 1, y2);
				add(0, 0, x2, y2);
			}
		}
	}
	Build(1, 0, d - 1);
	int ansx = -1, ansy = -1;
	for(int i = 0; i < d; i++) {
		if(ansx != -1) break;
		for(auto l : SL[i]) {
			Update(1, l.y1, l.y2, l.mark);
		}
        //Print(i, tree[1].len, d);
		if(ask(1, 0, d - 1) == 0) {
			for(int j = 0; j <= d - 1; j++) {
				if(ask(1, j, j) == 0) {
					ansx = i, ansy = j;
					break;
				}
			}
		} 
	}
	if(ansx != -1) {
		cout << "YES\n";
		cout << ansx << " " << ansy << endl;
	} else {
		cout << "NO\n";
	}
	return 0;
}