除了Div. 1的E题, 其他6道题的名称都是Eminem的歌名......比赛的时候没注意, 看Editorial下面的评论才知道 (不过也只听过其中 Not Afraid 这一首). 题目质量不错. 比赛的时候不会C题, D题差5分钟调完......GG. 题解: 5/5. UPDATE: 把Div.1的E题也做了一下, 和Div.2 D题的思路很像. # A. The Monster 求两个数列{b, b+a, b+2a, ...}, {d, d+c, d+2c, ...}最小的公共元素, 不存在输出-1. (a, b, c, d是正整数, 均不超过100)
进入比赛页面, 发现网断了, 只好重启......太大意了......
扩展欧几里德可以搞, 但那时候没想到怎么找出符合题意的那组解. 猜测答案不会很大 (否则不符合数学的美感和Div.2 A题的难度), 试图证明, 失败......算了, 直接交, 通过了pretest, 松了口气.
Editorial里这样说: It's easy to show that if a, b, c, d ≤ N, and such i and j exist, then i, j ≤ N, so you can iterate over i and check if such j exists.
尝试了一下, 只会证明 i,j ≤ 2N. 发了个Talk问出题人, 不知是否会得到答复.
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)
using namespace std;
int main()
{
int a, b, c, d;
cin >> a >> b >> c >> d;
For (i, 0, 100000) {
int x = b + i*a;
if (x >= d && (x-d) % c == 0) {
printf("%d\n", x);
return 0;
}
}
puts("-1");
return 0;
}B. Not Afraid
n个布尔变量, m个CNF (conjunctive normal form), 每个CNF是变量或变量取反再与起来, 问是否存在一种取值, 使得某个CNF为真. 每个CNF内同一变量可能出现多次. 所有CNF内变量或变量取反的总数不超过10^4. (1 ≤ n,m ≤ 10^4)
一个CNF为真当且仅当被与起来的每个部分同时为真. 如果同时存在x和非x, 做不到; 否则, 做得到. 于是, 只需判断某个CNF内是否同时存在x和非x, 如果不存在, 输出YES; 如果均存在, 输出NO.
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)
using namespace std;
int main()
{
set<int> S;
int n, m;
cin >> n >> m;
Rep (i, 0, m) {
S.clear();
int k;
cin >> k;
bool ok = true;
Rep (j, 0, k) {
int x;
cin >> x;
if (S.count(-x))
ok = false;
S.insert(x);
}
if (ok) {
cout << "YES" << endl;
return 0;
}
}
cout << "NO" << endl;
return 0;
}C. Berzerk
一个圆圈, 圈上顺时针n个点标号1,2,...,n. 一个物品初始可能在2,3,...,n. A, B两人各有一个整数集合, 轮流操作, 每次可从自己的集合中选一个数x (1 ≤ x < n), 使物品顺时针移动x步, 同一个x可多次被选取, 先将物品移动至点1者胜利. 两人均采取最优策略, 如果面临失败和死循环两种选择, 选死循环. 对所有初始位置, A或B先手, 输出先手将会胜利, 失败, 还是死循环. (2 ≤ n ≤ 7000)
这个游戏跟Nim之类的不同. 它不是公平的, 也不是无环的. 看起来可以DP, 但不知道采取何种顺序, 于是比赛时去看D题了.
后来自己想也没搞出来. 试图寻找状态之间的依赖关系, 这只会使我陷入死循环而不能判定A或B陷入死循环. 也许可以考虑SPFA那样的更新? 通常系统最终会达到一个稳定而最优的状态. 但是怎么保证时间复杂度呢......
Editorial讲的不清楚, 看了别人的代码. 发现的确是考虑SPFA式的更新, 但是由于问题的特殊性, 每个点只会入队一次, 也就是说, 这其实是BFS. 从终态开始, 考虑哪些点会转移到它. 如果s是胜利态, 更新前驱的计数器; 如果s是失败态, 前驱一定胜利; 从未入队的点是死循环态.
这道题启发我们, 对于不在DAG上的递推关系, 更新比追溯好用.
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
using namespace std;
const int N = 7000;
typedef pair<int, int> ii;
const char* str[] = {"Lose", "Loop", "Win"};
int n, k[2], S[2][N], f[2][N], cnt[2][N];
queue<ii> Q;
inline void ext(int t, int x, int v)
{
f[t][x] = v;
Q.push(ii(t, x));
}
int main()
{
scanf("%d", &n);
For (i, 0, 1) {
scanf("%d", &k[i]);
Rep (j, 0, k[i])
scanf("%d", &S[i][j]);
}
ext(0, 0, -1);
ext(1, 0, -1);
while (!Q.empty()) {
ii s = Q.front();
int t = s.first, x = s.second, now = f[t][x];
Q.pop();
Rep (i, 0, k[t^1]) {
int y = (x - S[t^1][i] + n) % n;
if (now == 1) {
if (++cnt[t^1][y] == k[t^1]) ext(t^1, y, -1);
} else if (!f[t^1][y]) ext(t^1, y, 1);
}
}
For (i, 0, 1) {
Rep (j, 1, n)
printf("%s ", str[f[i][j] + 1]);
puts("");
}
return 0;
}D. Legacy
n个点m条边的单源最短路, 然而边有3种: - u -> v - u -> [l, r] - [l, r] -> v (1 ≤ n, m ≤ 10^5)
单源最短路应该只能跑单源最短路算法, 优化大概是在建图上. 看到区间, 想到线段树. [APIO 2015] Jakarta Skycrapers 分块建图, 能不能在线段树上建图呢? 发现是可以的, 但是父亲向儿子, 儿子向父亲都得连边. 这两种边混到一起是不行的, 于是来两棵线段树, 对应的叶子连一条有向边.
比赛的时候写程序花了50min, 没调完.
评论区有人问为什么非得要两棵, 就把我的思路解释了一下. 另一个奇怪的外国小哥先是说You are wrong 尽管他说自己并不知道怎么处理第三种边......他把自己的回复改来改去......现在把You are wrong去掉了......
评论区里说有只带一个log的做法, 还没仔细看.
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)
#ifdef __WIN32
#define LLFORMAT "I64"
#else
#define LLFORMAT "ll"
#endif
using namespace std;
const int N = 1e5;
typedef vector<int> Vec;
typedef long long ll;
const ll inf = 1LL<<60;
struct Edge {
int v, w;
};
int cnt = 0, lc[4*N], rc[4*N], ans[N];
vector<Edge> adj[4*N];
inline void add_edge(int u, int v, int w)
{
adj[u].push_back((Edge){v, w});
}
void build(int& o, int l, int r, int t)
{
o = cnt++;
if (l == r) return;
int m = (l+r)/2;
build(lc[o], l, m, t);
build(rc[o], m+1, r, t);
if (t == 0) {
add_edge(o, lc[o], 0);
add_edge(o, rc[o], 0);
} else {
add_edge(lc[o], o, 0);
add_edge(rc[o], o, 0);
}
}
void decompose(int o, int l, int r, int L, int R, Vec& v)
{
if (L <= l && r <= R) {
v.push_back(o);
return;
}
int m = (l+r)/2;
if (L <= m)
decompose(lc[o], l, m, L, R, v);
if (R > m)
decompose(rc[o], m+1, r, L, R, v);
}
void get_all(int o, int l, int r, Vec& v)
{
if (l == r) { v.push_back(o); return; }
int m = (l+r)/2;
get_all(lc[o], l, m, v);
get_all(rc[o], m+1, r, v);
}
int n, A, B;
inline void add(int x, int y, int l, int r, int w)
{
Vec fr, to;
decompose(B, 1, n, x, y, fr);
decompose(A, 1, n, l, r, to);
if (x == y) {
Rep (i, 0, to.size())
add_edge(fr[0], to[i], w);
} else {
Rep (i, 0, fr.size())
add_edge(fr[i], to[0], w);
}
}
ll d[4*N];
struct Node {
int v;
ll d;
bool operator>(const Node& o) const
{
return d > o.d;
}
};
priority_queue<Node, vector<Node>, greater<Node> > Q;
void dijkstra(int s)
{
fill_n(d, 4*n, inf);
d[s] = 0;
Q.push((Node){s, 0});
while (!Q.empty()) {
Node x = Q.top();
Q.pop();
int u = x.v;
if (x.d > d[u]) continue;
Rep (i, 0, adj[u].size()) {
Edge& e = adj[u][i];
if (d[e.v] > d[u] + e.w) {
d[e.v] = d[u] + e.w;
Q.push((Node){e.v, d[e.v]});
}
}
}
}
int main()
{
int q, s;
scanf("%d%d%d", &n, &q, &s);
build(A, 1, n, 0);
build(B, 1, n, 1);
Rep (i, 0, q) {
int t, u, v, l, r, w;
scanf("%d", &t);
if (t == 1) {
scanf("%d%d%d", &v, &u, &w); // v->u
add(v, v, u, u, w);
} else {
scanf("%d%d%d%d", &v, &l, &r, &w);
if (t == 2) // v->[l,r]
add(v, v, l, r, w);
else // [l,r]->v
add(l, r, v, v, w);
}
}
Vec a, b;
get_all(A, 1, n, a);
get_all(B, 1, n, b);
Rep (i, 0, n)
add_edge(a[i], b[i], 0);
dijkstra(b[s-1]);
Rep (i, 0, n)
printf("%"LLFORMAT"d%c", d[b[i]] == inf ? -1 : d[b[i]], " \n"[i == n-1]);
return 0;
}E. Till I Collapse
长度为n的序列, 每一项是[1,n]内的整数. 将序列划分为最少的段落, 使得每段出现的数的种数不超过k. 对k=1,2,...,n输出答案. (1 ≤ n ≤ 10^5)
由于每一段的长度至少为k, 发现枚举k=1,2,...,n, 每次跳转, 时间是
区间数颜色是可持久化线段树的经典应用嘛. 但是那种做法固定了区间, 不方便在树上二分. 设
这是我的做法. 对每个i, 把
记在j位置上, 维护区间 的最小值即可二分. 可以不用可持久化线段树. 这就要求i从小到大枚举, 和跳转的顺序一致. 这是可以做到的. 初始化 . 设 表示下一个和i相等的数的位置, 则i的加1不影响[nxt[i], n], 只是使[i, nxt[i])的答案-1. 类似于[bzoj 3585] mex的离线线段树做法. 每个位置放一个 vector记录左边哪些跳转到这里.Editorial的做法 (稍作修改, 因为Editorial说要用可持久化线段树, 其实没必要). 维护每个位置j的1-0值
, 表示 是否小于i, 这样, 一段区间的1-0值的和等于数的种数, 相当于把 数组差分. 修改变成两个单点修改: -1, +1. 维护区间和.
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)
using namespace std;
const int N = 1e5;
int mn[4*N], d[4*N], a[N+1], b[N+1], c[N+1], nxt[N+1], ans[N+1];
vector<int> s[N+1];
inline void up(int o) { mn[o] = min(mn[o*2], mn[o*2+1]); }
inline void down(int o, int v) { d[o] += v; mn[o] -= v; }
inline void down(int o)
{
if (d[o]) {
down(o*2, d[o]);
down(o*2+1, d[o]);
d[o] = 0;
}
}
void modify(int o, int l, int r, int L, int R)
{
if (L <= l && r <= R) {
down(o, 1);
return;
}
down(o);
int m = (l+r)/2;
if (L <= m) modify(o*2, l, m, L, R);
if (R > m) modify(o*2+1, m+1, r, L, R);
up(o);
}
// <= v rightmost
int query(int o, int l, int r, int v)
{
if (l == r) return l;
down(o);
int m = (l+r)/2;
return mn[o*2+1] <= v ? query(o*2+1, m+1, r, v) : query(o*2, l, m, v);
}
void build(int o, int l, int r)
{
if (l == r) {
mn[o] = b[l];
return;
}
int m = (l+r)/2;
build(o*2, l, m);
build(o*2+1, m+1, r);
up(o);
}
int main()
{
int n;
scanf("%d", &n);
For (i, 1, n) {
scanf("%d", &a[i]);
b[i] = b[i-1] + !c[a[i]];
c[a[i]] = 1;
s[0].push_back(i);
}
fill_n(c+1, n, n+1);
Down (i, n, 1) {
nxt[i] = c[a[i]];
c[a[i]] = i;
}
build(1, 1, n);
Rep (i, 0, n) {
Rep (j, 0, s[i].size()) {
int t = query(1, 1, n, s[i][j]);
s[t].push_back(s[i][j]);
++ans[s[i][j]];
}
modify(1, 1, n, i+1, nxt[i+1]-1);
}
For (i, 1, n)
printf("%d%c", ans[i], " \n"[i == n]);
return 0;
}1E. ALT
一棵n个结点的无根树, m个人, 每人有一条起点不等于终点的路径. 在树的边上放狗, 或者把狗狗直接送给人, 使得每个人要么有自己的狗, 要么他的路径的每条边上都有狗. 最小化狗的总数, 并给出一种最优方案. (2≤n≤2*10^4, 1≤m≤10^4)
背景 点覆盖: 在图中选出一个点集, 使得每条边至少有一个端点被选中. König定理: 二分图中最小点覆盖数 = 最大匹配数. 证明和构造方法
回到本题. 边在路径上 <=> 边被选或人被选. 于是, 把树上的边作为二分图的左部, 人作为二分图的右部, 如果某条边在某个人的路径上, 则将两者连边, 这个二分图的最小点覆盖即为答案. 暴力建图不可取, 让我们来优化一下.
分解一条链, 可以用线段树, 也可以用ST表. 在树上建线段树有点麻烦, ST表倒是很容易 - 就是找LCA的倍增算法. 先转有根树. 除了根, 其他点加一些虚拟结点, 表示向上的2^i条边. 将2i(i>0)与两个2(i-1)连边即可. 2^0连向表示原图上边的结点. 原来的二分图模型中, 人向边连边, 现在改为向虚拟结点连边. 跑一下最大流, DFS找方案就好了.
这个算法的时间复杂度为
Time complexity:
不是很明白......分层图, 边的容量为1 (似乎并不是, 有好些容量无穷的边)?
好久不写最大流, 又去A了一遍草地排水......
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)
#define pb push_back
using namespace std;
const int N = 2e4, M = 1e4, MAX_D = 15, inf = 1e8;
namespace MaxFlow {
const int MAX_V = 1+N+M+(MAX_D+1)*(N-1);
struct Edge {
int u, v, c;
};
vector<Edge> E;
vector<int> adj[MAX_V];
queue<int> Q;
int cur[MAX_V], level[MAX_V];
bool mark[MAX_V];
inline void add(int u, int v, int f)
{
adj[u].pb(E.size()); E.pb((Edge){u, v, f});
adj[v].pb(E.size()); E.pb((Edge){v, u, 0});
}
bool bfs(const int& s, const int&t, const int& n)
{
fill_n(level, n, -1);
level[s] = 0; Q.push(s);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
Rep (i, 0, adj[u].size()) {
Edge& e = E[adj[u][i]];
if (e.c && level[e.v] == -1) {
level[e.v] = level[u] + 1;
Q.push(e.v);
}
}
}
return ~level[t];
}
int dfs(int u, int f, const int& t)
{
if (u == t) return f;
int in = f, d;
for (int& i = cur[u]; i < (int)adj[u].size(); ++i) {
Edge& e = E[adj[u][i]];
if (level[e.v] == level[u]+1 && e.c && (d = dfs(e.v, min(f, e.c), t))) {
e.c -= d; E[adj[u][i]^1].c += d;
if (!(f -= d)) break;
}
}
return in - f;
}
void dfs1(int u)
{
mark[u] = true;
Rep (i, 0, adj[u].size()) {
Edge& e = E[adj[u][i]];
if (e.c && !mark[e.v]) dfs1(e.v);
}
}
int max_flow(int s, int t, int n)
{
int f = 0;
while (bfs(s, t, n)) {
fill_n(cur, n, 0);
f += dfs(s, inf, t);
}
dfs1(s);
return f;
}
}
using MaxFlow::add;
int n, m;
namespace Doubling {
#define PR(i, j) (n+m+(D+1)*((i)-2)+(j)+1)
struct Edge {
int v, e;
};
vector<Edge> adj[N + 1];
int anc[N + 1][MAX_D + 1], dep[N + 1], D;
inline void add_edge(int u, int v, int e)
{
adj[u].pb((Edge){v, e});
adj[v].pb((Edge){u, e});
}
void dfs(int u, int p)
{
anc[u][0] = p;
For (i, 1, D) {
anc[u][i] = anc[anc[u][i-1]][i-1];
if (anc[u][i]) {
add(PR(u, i), PR(u, i-1), inf);
add(PR(u, i), PR(anc[u][i-1], i-1), inf);
}
}
Rep (i, 0, adj[u].size()) {
Edge& e = adj[u][i];
if (e.v != p) {
add(PR(e.v, 0), e.e, inf);
dep[e.v] = dep[u] + 1;
dfs(e.v, u);
}
}
}
void path(int num, int u, int v)
{
num += n;
if (dep[u] > dep[v]) swap(u, v);
for (int h = dep[v]-dep[u], i = 0; h; h >>= 1, ++i)
if (h & 1) {
add(num, PR(v, i), 1);
v = anc[v][i];
}
if (u == v) return;
Down (i, D, 0)
if (anc[u][i] != anc[v][i]) {
add(num, PR(u, i), inf);
add(num, PR(v, i), inf);
u = anc[u][i];
v = anc[v][i];
}
add(num, PR(u, 0), 1);
add(num, PR(v, 0), 1);
}
}
inline void print(int fr, int to, bool b)
{
using MaxFlow::mark;
int cnt = 0;
For (i, fr, to) cnt += mark[i] == b;
printf("%d ", cnt);
For (i, fr, to) if (mark[i] == b) printf("%d ", i-fr+1);
puts("");
}
int main()
{
scanf("%d%d", &n, &m);
using Doubling::D;
while ((1<<D) < n-1) ++D;
For (i, 1, n-1) {
int u, v;
scanf("%d%d", &u, &v);
Doubling::add_edge(u, v, i);
add(i, n, 1);
}
Doubling::dfs(1, 0);
For (i, 1, m) {
int x, y;
scanf("%d%d", &x, &y);
Doubling::path(i, x, y);
add(0, n+i, 1);
}
int flow = MaxFlow::max_flow(0, n, 1+n+m+(D+1)*(n-1));
printf("%d\n", flow);
print(n+1, n+m, false);
print(1, n-1, true);
return 0;
}