100 + 100 + 0
倒是没什么好说的,开始一边在码 T2 一边在 hack lzh 双线作战,然后静下心来 Rush 完 T1 就弃考了,T3 也不是我考试时能写出来的 QwQ

# game

模拟 2048 游戏

n8,m105n\le 8, m\le 10^5

# Sol:

按题意模拟即可
感觉代码写的十分清新自然,贴一发

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
	#pragma GCC optimize(2)
#pragma GCC optimize(3)

/* ==============================
* Author : Odalys
*
* 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 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 mck insert
#define era erase
const int N = 10;
int n, m;
int Id (int x, int y) { return (x - 1) * n + y; }
set <int> emp;
int val[N][N], res[N][N];
pii gra[N * N];
inline void cache () {
For (i, 1, n) For (j, 1, n)
res[i][j] = val[i][j];
}
inline bool diff () {
For (i, 1, n) For (j, 1, n)
if (res[i][j] != val[i][j]) return true;
return false;
}

inline void upd (int k, int v) {
int top = 0;
for (auto x : emp) {
top++;
if (top == k) {
val[gra[x].fi][gra[x].se] = v;
emp.era(x);
break;
}
}
}

inline void Mckenna (int x, int y, int fx, int fy) {
val[x][y] = val[fx][fy];
emp.era(Id(x, y));
emp.mck(Id(fx, fy));
val[fx][fy] = 0;
} //move (fx, fy) to (x, y)

inline void move (int to) {
if (to == 0) {
For (i, 1, n - 1) For (j, 1, n) {
if (!val[i][j])
For (k, i + 1, n)
if (val[k][j]) {
Mckenna(i, j, k, j);
break;
}
}
}
if (to == 1) {
foR (i, n, 2) For (j, 1, n) {
if (!val[i][j]) {
foR (k, i - 1, 1)
if (val[k][j]) {
Mckenna(i, j, k, j);
break;
}
}
}
}
if (to == 2) {
For (j, 1, n - 1) For (i, 1, n) {
if (!val[i][j])
For (k, j + 1, n)
if (val[i][k]) {
Mckenna(i, j, i, k);
break;
}

}
}
if (to == 3) {
foR (j, n, 2) For (i, 1, n) {
if (!val[i][j])
foR (k, j - 1, 1)
if (val[i][k]) {
Mckenna(i, j, i, k);
break;
}
}
}
}

int tmp;

inline void merge (int to) {
if (to == 0) {
For (i, 1, n - 1) For (j, 1, n) {
if (val[i][j] == val[i + 1][j] && val[i][j]) {
tmp += val[i][j] * 2;
val[i + 1][j] = 0;
val[i][j] *= 2;
emp.mck(Id(i + 1, j));
}
}
}
if (to == 1) {
foR (i, n, 2) For (j, 1, n) {
if (val[i][j] == val[i - 1][j] && val[i][j]) {
tmp += val[i][j] * 2;
val[i - 1][j] = 0;
val[i][j] *= 2;
emp.mck(Id(i - 1, j));
}
}
}
if (to == 2) {
For (j, 1, n - 1) For (i, 1, n) {
if (val[i][j] == val[i][j + 1] && val[i][j]) {
tmp += val[i][j] * 2;
val[i][j + 1] = 0;
val[i][j] *= 2;
emp.mck(Id(i, j + 1));
}
}
}
if (to == 3) {
foR (j, n, 2) For (i, 1, n) {
if (val[i][j] == val[i][j - 1] && val[i][j]) {
tmp += val[i][j] * 2;
val[i][j - 1] = 0;
val[i][j] *= 2;
emp.mck(Id(i, j - 1));
}
}
}
}

inline void print () {
For (i, 1, n) {
For (j, 1, n) cout << val[i][j] << " ";
puts("");
}
puts("");
}

int main() {
read(n); read(m);
For (i, 1, n) For (j, 1, n)
emp.mck(Id(i, j)), gra[Id(i,j)] = mp(i, j);
int x, y, v;
read(x), read(y), read(v);
emp.era(Id(x, y)); val[x][y] = v;
read(x), read(y), read(v);
emp.era(Id(x, y)); val[x][y] = v;
int Ans1 = 0, Ans2 = 0;
For (i, 1, m) {
int d, k, v; read(d); read(k); read(v);
cache();
move(d);
tmp = 0;
merge(d);
move(d);
Ans2 += tmp;
if ( diff () ) Ans1++;
else break;
int r = emp.size();
upd (1 + (k % r), v);
}
printf ("%d\n%d", Ans1, Ans2);
return 0;
}

复杂度是 O(n3m)\mathrm O(n^3m)


# seq

一个长度为 nn 的序列,选出一个子序列,定义其权值为其和除以上升段 + 下降段总段数,最大化权值

n105n\le 10^5

# Sol:

贪心地发现答案要不是一整段上升的,要不一段上升一段下降的

于是就正反跑一遍 LIS 枚举一个断点搞一搞就好


# mst

一张无向图,边权为一个虚数,定义虚数比大小为模长的比较,求最大生成树。

# Sol:

假如我们知道答案向量的方向,我们把每条边向其取投影长度,那么按这个跑 kruskl 就是最大生成树长度。

所以我们就可以枚举每个方向求 max

这样显然会 T,于是考虑 kruskl 的过程中,我们并不关注每条边具体有多长,我们只关注两条边的相对关系,于是考虑一个类似临界的问题,考虑枚举两条向量,我们能求出一条向量使这两条投影长度相同,那么这两个区间内,每条边权的相对大小不会改变,于是 kruskl 求出的生成树边也不会改变,于是每个区间内取个代表向量,然后直接做即可。

更新于 阅读次数

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

Odalys 微信支付

微信支付

Odalys 支付宝

支付宝