首页 Races

这场个人感觉还是比较好的一场，无超纲知识点，思维难度在线，码量不太大。
但考场上表现不够良好，感觉自己数形结合能力不是十分突出（？当然有可能是 C 不懂逆排列是啥），对一些常见 tricktrick 不够熟练，以及 dp 基本功不够扎实。
目前补题记录 (4/6)(4/6) ，感觉 FF 大概率会鸽

# Solutions:

# A

给你 a,ba,b 两个序列，要求对于每个 bib_i 求出 gcd⁡(a1+bi,a2+bi,…,an+bi)\gcd(a_1+b_i, a_2+b_i,\dots ,a_n+b_i)
要求做到 O(n)O(n)

考虑把经典的辗转相减 gcd⁡(a,b)=gcd⁡(a,b−a)\gcd(a,b) = \gcd(a,b-a) 拓展到整个序列

那就是 gcd⁡(a1+bi,a2+bi−(a1+bi),…,an+bi−(an−1+bi)\gcd(a_1+b_i, a_2+b_i-(a_1+b_i),\dots ,a_n+b_i - (a_{n-1}+b_i)

也就是 gcd⁡(a1+b1,G)\gcd(a_1+b_1, G) 其中 GG 为差分数组的 gcd⁡\gcd

于是可以做到 O(n)O(n)

# B

若干个瓶子，每个瓶子有容积 aia_i ，与初始水量 bib_i ，你可以将一个瓶子中的水到一部分到其他瓶子中，但会损耗一半倒出的水，显然每个瓶子不能超过它本身体积，对于每个 i∈[1,n]i\in [1,n] ，求出只选 ii 个瓶子能装出的最大水量。
n,ai,bi≤100n,a_i,b_i\le 100

考虑 dpdp

容易发现你将 aa 倒到 bb 中再倒入 cc 中是肯定没有直接倒入 cc 中优秀的，所以确定最终框架：选择 ii 个瓶子后每个瓶子想方设法往里倒。

设选择的 ii 个瓶子总初始水量为 xx ，剩余体积为 vv ，其他瓶子中总水量为 yy ，答案是 x+min⁡{y2,v}x+\min{\{\frac{y}{2},v\}}

注意到值域都很小于是可以考虑背包，设 dpi,j,kdp_{i,j,k} 为前 ii 个瓶子中选了 jj 个总体积为 kk 的最大初始水量，于是随便搞一下就好。

# C

一个 n×nn\times n 的矩阵，每行每列都是一个 1→n1\to n 的排列，给一个操作序列， U/D/L/R 表示整体向上 / 下 / 左 / 右循环位移一位， I/C 表示每行 / 列替换为其逆排列，求操作后的矩阵。

前四种操作你记录一个总体移了几位的标记就好了。

考虑啥是逆排列，几何意义是把排列表示为平面直角坐标系上 (i,ai)(i,a_i) 的形式然后再交换每个点的横纵坐标。

那我们把每个点表示为 (i,j,ai,j)(i,j,a_{i,j}) 的三元组，后两个操作的本质就是交换第一第三个元素与第一第二个元素。

那每个操作我们可以 O(1)O(1) 打 tagtag ，最后在 n×nn\times 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
/* ==============================
 *  Author : Odalys 
 *
 *  Blog : Odalys8191.github.io
 *
 *  Mail : minyuenu@gmail.com
 * =============================== */
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
	T w=1; a=0;
	char ch=getchar();
	for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
	a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int> 
#define pii pair<int, int> 
#define vi vector<int> 
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i) 
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int N = 1000;
int n, m;
int Id (int i, int j) { return (i - 1) * n + j; }
int a[N * N | 1][3];
int Ans[N][N];
int pos[3], mv[3];
inline void solve () {
	read(n); read(m); 
	For (i, 0, 2) pos[i] = i, mv[i] = 0;  
	For (i, 1, n) For (j, 1, n) {
		int cur = Id(i, j);
		a[cur][0] = i, a[cur][1] = j, read(a[cur][2]); 
	}
	For (i, 1, m) {
		char ch = getchar();
		if (ch == 'U') mv[pos[0]]--;
		if (ch == 'D') mv[pos[0]]++;
		if (ch == 'L') mv[pos[1]]--;
		if (ch == 'R') mv[pos[1]]++;
		if (ch == 'I') swap(pos[1], pos[2]);
		if (ch == 'C') swap(pos[0], pos[2]); 
	}
	For (i, 1, n * n) {
		For (j, 0, 2) a[i][j] = (a[i][j] - 1 + mv[j] + n * m) % n + 1;
		Ans[a[i][pos[0]]][a[i][pos[1]]] = a[i][pos[2]];
	}
	For (i, 1, n) { For (j, 1, n) printf("%d ", Ans[i][j]); puts("");}
}

int main() {
	int cases; read(cases);
	while (cases--) solve(), puts("");
	return 0;
}

# D

给定一个 0/10/1 串，你可以对 00 与 11 数目相同的一段区间进行操作为，每个取反，再整体翻转。
求若干次操作后字典序最小的串。

草，这什么神仙思维题。

人类智慧。

把 00 看成 −1-1 ，11 看成 +1+1 ，把前缀和序列搞出来，那一段区间可以操作当且仅当 suml−1=sumrsum_{l-1} = sum_{r} 。

操作的本质就是把一段区间前缀和序列取反，为什么呢？

一目了然，不言而喻。

然后考虑一个神仙思路，我们把前缀和值看做一个个点，相邻前缀和值连边。

这样会得出一张有向图，相邻点之间前缀和值相差为 11 ，每条边若它的起点比终点大 11 则代表字符 00 ，否则代表字符 11

考虑这张图初始只有一条欧拉路（即经过每条边恰好一次的路径），把边代表字符写下了就是原串。

那么我们一次操作相当于是把其中一个环的路径整体取反，但路径上代表字符不变。

然后我们发现把边都看成无向边，这张图所有的欧拉回路都能被这种操作从最初那张图构造出来。

那就做个贪心找字典序最小的欧拉路即可。

# E

两堆石头， 每次可在一堆中选大于 11 的任意个石头，若某人操作时局面为 (0,0)(0,0) 或给出的 nn 个二元组中其中一个就输了，问先手是否必败。

n≤105,x≤109n\le 10^5, x\le 10^9

很妙的题，细节有点多。

若没给一个二元组，那就是一个 nimnim 游戏了，当且仅当 x=yx=y 是局面必败。考虑从几何角度来看，若把每个 (x,y)(x,y) 放到笛卡尔坐标系上，根据基本的博弈论知识，我们知道，能到必败态的为必胜态，反之为必败态，那首先 (0,0)(0,0) 为必败态，故 x=0,y=0x=0,y=0 的点都为必胜态，而 (1,1)(1,1) 能到的 (1,0),(0,1)(1,0), (0,1) 都是必胜态，故它为必败态…

考虑加入一些shortcuts\texttt{shortcuts} 后怎么做，那是不是，还是从 (0,0)(0,0) 往右走，对于点 (x,y)(x,y) ，若同行左侧 / 同列下侧有shortcuts\texttt{shortcuts}，那就这个点反而为必胜态了，然后相应推推即可。

考虑把值域离散化后，那我们往右上爬的过程相当于是走几步后走一段斜率为 11 的直线，那我们用 setset 模拟这个过程即可，感觉我没什么脑子，于是贺了网上别人的代码。

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
/* ==============================
 *  Author : Odalys 
 *
 *  Blog : Odalys8191.github.io
 *
 *  Mail : minyuenu@gmail.com
 * =============================== */
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
	T w=1; a=0;
	char ch=getchar();
	for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
	a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define ins insert 
#define pb push_back
#define mp make_pair
#define mii map<int, int> 
#define pii pair<int, int> 
#define vi vector<int> 
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i) 
#define foR(i,l,r) for (int i = l; i >= r; --i)
#define y1 _y1
#define mt make_tuple
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10;
map <int, int> mx, my; 
set < tuple<int, int, int> > line;
map <pii, bool> lost;
int n, q;
int main() {
	read(n); read(q); 
	For (i, 1, n) {
		int x, y; read(x); read(y);
		lost[mp(x, y)] = 1;
		if (mx.find(x) == mx.end()) mx[x] = y; else ckmin(mx[x], y);
		if (my.find(y) == my.end()) my[y] = x; else ckmin(my[y], x);
	}
	int x = 0, y = 0;
	for (auto i = mx.begin(), j = my.begin(); i != mx.end() || j != my.end();) {
		while (i != mx.end() && (i -> fi) < x) ++i;
		while (j != my.end() && (j -> fi) < y) ++j;
		int x1 = inf, x2 = inf, y1 = inf, y2 = inf;
		if (i != mx.end()) x1 = (i -> fi), y1 = (i -> se);
		if (j != my.end()) x2 = (j -> se), y2 = (j -> fi); 
		int mn = min(x1 - x, y2 - y);
//		cout << mn << endl;
		bool fx = 0, fy = 0;
		if (x + mn == x1 && y1 <= y + mn) fx = 1;
		if (y + mn == y2 && x2 <= x + mn) fy = 1;
		if (mn + 1 - max(fx, fy)) line.ins(mt(x + mn - max(fx, fy), x, y));
		if (!max(fx, fy)) fx = fy = 1;
		x += mn + fx, y += mn + fy;
	}
	line.ins(mt(inf, x, y));
/*	for (auto v = line.begin(); v != line.end(); v++) {
//		cout << v;
		printf("%d %d %d\n", get<0>(*v), get<1>(*v), get<2>(*v));
	}*/
	For (i, 1, q) {
		int x, y; read(x); read(y);
		if (lost[mp(x, y)]) {puts("LOSE"); continue; }
		auto it = line.lower_bound (mt(x, 0, 0));
		if (it == line.end() || get<1>(*it) > x) { puts("WIN"); continue; }
		puts(get<2>(*it) + x - get<1>(*it) == y ? "LOSE" : "WIN");
	}
}
更新于 阅读次数 次

请我喝[茶]~(￣▽￣)~*

Odalys 微信支付

微信支付

Odalys 支付宝

支付宝