这一套题没什么思维难度......比赛时完成前4题, D题FST, 因为顺手把一个int开成char了. TAT E题想避免线段树, 结果我的简化完全是错误的......对数连通块的基本操作和平面图/多面体的欧拉定理理解不深刻. 涨回了两场前的Rating. 题解: 5/5 # A. Vladik and Courtesy Vladik,Valera分别拥有a,b个物品, 轮流丢东西, 一开始Vladik丢1个, 然后每个人每次比对方多丢1个, 问谁最先不能丢. (1≤a,b≤10^9)
根据等差数列求和公式, 直接模拟的时间复杂度是
int main()
{
int a, b;
scanf("%d%d", &a, &b);
for (int i = 1; ; i += 2) {
a -= i;
if (a < 0) { puts("Vladik"); break; }
b -= i+1;
if (b < 0) { puts("Valera"); break; }
}
return 0;
}B. Vladik and Complicated Book
给出1~n的一个排列p, m个询问, 问p[l,r]从小到大排序后, p[x]的位置是否改变. 询问并不真的改变序列. (1≤n,m≤10^4, 1≤li≤xi≤ri≤n)
可持久化线段树? n,m很小, 所以暴力求区间内有多少小于v的数? 不放心还本地测试了一下. >_<
const int N = 1e4;
int p[N+1];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
rep (i, 1, n+1) scanf("%d", p+i);
while (m--) {
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
int a = p[x], cnt = 0;
rep (i, l, r+1) cnt += p[i] < a;
puts(cnt == x-l ? "Yes" : "No");
}
return 0;
}C. Vladik and Memorable Trip
给一个长度为n的序列a, 选出一些分离的区间 (不要求它们覆盖整个序列), 使得相等的ai要么分在同一个区间里, 要么都不被选中. 一个区间的舒适度等于区间内所有数去重后的异或和. 求所有区间舒适度的最大代数和. (1≤n≤5000, 0≤ai≤5000)
常见的模型,
实现的时候, 左指针的左移分为两类: 主动, 被动 (以满足相等的ai分在同一个区间的限制). 处理出每个值第一次和最后一次出现的位置.
也可以直接预处理所有区间的舒适度.
const int N = 5001;
int l[N], r[N], a[N], dp[N];
int main()
{
int n;
scanf("%d", &n);
rep (i, 1, n+1) {
scanf("%d", a+i);
r[a[i]] = i;
}
per (i, n, 1) l[a[i]] = i;
rep (i, 1, n+1) {
dp[i] = dp[i-1];
for (int j = i, k = l[a[i]], s = 0; j; --k) {
while (j >= k) {
if (r[a[j]] > i) goto end;
k = min(k, l[a[j]]);
if (j == l[a[j]]) s ^= a[j];
--j;
}
dp[i] = max(dp[i], dp[j] + s);
}
end: ;
}
printf("%d\n", dp[n]);
return 0;
}D. Vladik and Favorite Game
交互题. 给一个n*m的地图, 起点在(1,1). 有可通行的格子, 终点, 危险的格子 (走上去游戏失败). 向交互库发送上,下,左,右移动一格的指令控制角色行走, 保证起点与终点连通. 交互库返回移动后角色的坐标. 试图向地图之外移动会使角色原地不动. 现在, 上下移动的指令的功能可能被交换, 左右也可能被交换. 控制角色从起点走到终点. (向交互库发送的指令不超过2mn个, 1≤n,m≤100)
起点在(1,1). 试图向地图之外移动会使角色原地不动. 这两点很关键. 先用BFS搜出一条最短路. 如果第一步是右移, 那么, 向交互库发送右移的指令是安全的 - 往左走会使角色原地不动. 判断一下角色是否没有移动, 据此对方向键进行修正. 贴着地图的上边缘走一会儿, 直到第一个该下移的位置. 同样, 在此处对方向键进行修正. 如果从未遇到下移, 说明终点就在第一行. 先下移, 再右移的情况是对称的.
#define x first
#define y second
using namespace std;
const int N = 100, dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
typedef pair<int, int> P;
inline P go(char c)
{
printf("%c\n", c);
fflush(stdout);
int x, y;
scanf("%d%d", &x, &y);
return P(x, y);
}
char dir[] = "UDLR", s[N+2][N+2];
int n, m, l, ud = 1<<30, lr = 1<<30, fr[N+2][N+2], seq[N*N], d[N+2][N+2];
void bfs(const P& f)
{
rep (i, 1, n+1) rep (j, 1, m+1) d[i][j] = -1;
queue<P> Q;
Q.push(f);
d[f.x][f.y] = 0;
while (!Q.empty()) {
P u = Q.front(); Q.pop();
rep (i, 0, 4) {
P v(u.x + dx[i], u.y + dy[i]);
if (s[v.x][v.y] != '.' || d[v.x][v.y] != -1) continue;
fr[v.x][v.y] = i;
d[v.x][v.y] = d[u.x][u.y] + 1;
Q.push(v);
}
}
P t(1, 1);
while (t != f) {
int i = fr[t.x][t.y] ^ 1;
t.x += dx[i];
t.y += dy[i];
if (i <= 1) ud = min(ud, l);
else lr = min(lr, l);
seq[l++] = i;
}
}
inline void correct(P& v, int d)
{
P t = go(dir[d]);
if (t == v) {
swap(dir[d], dir[d^1]);
v = go(dir[d]);
} else {
v = t;
}
}
int main()
{
P f;
scanf("%d%d", &n, &m);
rep (i, 1, n+1) {
scanf("%s", s[i]+1);
rep (j, 1, m+1) if (s[i][j] == 'F') f = P(i, j);
}
bfs(f);
P v(1, 1);
rep (i, 0, l) {
int d = seq[i];
if (i == ud) correct(v, d);
else if (i == lr) correct(v, d);
else v = go(dir[d]);
}
return 0;
}E. Vladik and Entertaining Flags
给一个n*m的矩阵, 每一个格子填着一个正整数. 连通块是一个极大的格子集合, 集合中所有格子上的数字相同, 并且两两之间存在一条四连通的路径, 路径上的所有格子上的数字跟起点/终点相同. q个询问, 问以(1,l)为左上, (n,r)为右下的矩形中连通块的数目. (1≤n≤10, 1≤m,q≤10^5, 格子上的数≤10^6, 1≤l≤r≤m)
一看和 APIO 2017 T1 很像, 欧拉定理? n很小, m不大, 线段树?
我选择了前者......这样没用上n≤10的条件, 而且看起来不像Div.2 E题的风格. 还自以为是地做出一个简化: 一条边两边的格子颜色相同, 则认为连通块数目+1, 还交了一发. 囧......环的情况呢? 平面图的欧拉定理也不对, 试了一下, 它仅适用于只有一个连通块的平面图. APIO 2017 T1 的具体题面我忘记了, 应该有一些特殊之处.
那就好好写线段树吧......额外地维护一个矩形左右两侧各个格子的连通情况, 用0~2m-1给它们标号 (同一个号码当且仅当处于同一个连通块). 借助于并查集合并两个相邻的矩形, 进行重标号.
启示: 蹦出一个新想法, 或者运用一个不熟悉的公式/定理, 可以先适当地手玩一下.
#define ALL 1, 0, m-1
#define LEFT o*2, l, m
#define RIGHT o*2+1, m+1, r
using namespace std;
const int N = 10, M = 1e5;
int n, a[N][M];
struct UF {
int f[4*N];
int F(int x)
{
return f[x] == -1 ? x : f[x] = F(f[x]);
}
void reset()
{
fill_n(f, 4*n, -1);
}
bool merge(int x, int y)
{
x = F(x), y = F(y);
if (x != y) return f[y] = x, true;
else return false;
}
} U;
struct Info {
int c, l, r, v[2][N];
Info() {}
Info(int i): l(i), r(i)
{
v[0][0] = v[1][0] = 0;
rep (j, 1, n)
v[0][j] = v[1][j] = v[0][j-1] + (a[j][i] != a[j-1][i]);
c = v[0][n-1] + 1;
}
Info operator+(const Info& o) const
{
static int id[4*N];
fill_n(id, 4*n, -1);
U.reset();
Info ret;
ret.l = l;
ret.r = o.r;
ret.c = c + o.c;
rep (i, 0, n)
if (a[i][r] == a[i][o.l])
ret.c -= U.merge(v[1][i], o.v[0][i] + 2*n);
int cnt = 0;
rep (i, 0, n) {
int t = U.F(v[0][i]);
if (id[t] == -1) id[t] = cnt++;
ret.v[0][i] = id[t];
t = U.F(o.v[1][i] + 2*n);
if (id[t] == -1) id[t] = cnt++;
ret.v[1][i] = id[t];
}
return ret;
}
};
struct Seg {
Info v[4*M];
void build(int o, int l, int r)
{
if (l == r) return v[o] = Info(l), void();
int m = (l+r)/2;
build(LEFT);
build(RIGHT);
v[o] = v[o*2] + v[o*2+1];
}
Info query(int L, int R, int o, int l, int r)
{
if (L <= l && r <= R) return v[o];
int m = (l+r)/2;
if (R <= m) return query(L, R, LEFT);
else if (L > m) return query(L, R, RIGHT);
else return query(L, R, LEFT) + query(L, R, RIGHT);
}
} T;
int main()
{
int m, q;
scanf("%d%d%d", &n, &m, &q);
rep (i, 0, n) rep (j, 0, m) scanf("%d", &a[i][j]);
T.build(ALL);
while (q--) {
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", T.query(l-1, r-1, ALL).c);
}
return 0;
}