A - Archery Tournament
一开始往化简公式的方向去想，结果没什么用。
考虑与一条垂线相交的圆的个数。不难YY，当圆的个数最多时，大概就是这个样子的:
.png)
我们稍微推一下式子，然后就能发现其个数不超过(O(log C))，其中(C)为坐标范围（即1e9）。
接下来的事情就简单了，我们把数据离散化后就能用线段树查询过某一条垂线的所有圆了，再暴力判断是哪一个就可以了。
时间复杂度(O(n log ^2 n))。
#include <bits/stdc++.h>
#define sqr(x) (1ll * (x) * (x))
using namespace std;
const int N = 400010;
struct circle {
int x,y;
bool inside(int a,int b) {
return sqr(x - a) + sqr(b - y) < sqr(y);
}
} cir[N];
int n;
struct data {
int tp,x,y;
} dat[N];
vector<int> tmp,ins;
set<int> q[N << 2];
void modify(int l,int r,int v,int sgn,int x=1,int lp=1,int rp = n) {
if (l > rp || r < lp) return;
if (lp >= l && rp <= r) {
if (sgn) q[x].insert(v);
else q[x].erase(v);
return;
}
int mid = (lp + rp) >> 1;
modify(l,r,v,sgn,x<<1,lp,mid);
modify(l,r,v,sgn,x<<1|1,mid+1,rp);
}
void add(int id,int sgn) {
int l = lower_bound(tmp.begin(),tmp.end(),dat[id].x - dat[id].y) - tmp.begin() + 1;
int r = upper_bound(tmp.begin(),tmp.end(),dat[id].x + dat[id].y) - tmp.begin();
modify(l,r,id,sgn);
}
void query(int p,int x=1,int lp=1,int rp=n) {
if (lp > p || rp < p) return;
for (set<int>::iterator t = q[x].begin() ; t != q[x].end() ; ++ t)
ins.push_back(*t);
if (lp == rp) return;
int mid = (lp + rp) >> 1;
if (p <= mid) query(p,x<<1,lp,mid);
else query(p,x<<1|1,mid+1,rp);
}
int doit(int a,int b) {
ins.clear();
int p = lower_bound(tmp.begin(),tmp.end(),a) - tmp.begin() + 1;
query(p);
for (int i = 0 ; i < (int)ins.size() ; ++ i) {
if (cir[ins[i]].inside(a,b)) {
add(ins[i],0);
return ins[i];
}
}
return -1;
}
int main() {
scanf("%d",&n);
for (int i = 1 ; i <= n ; ++ i) {
scanf("%d%d%d",&dat[i].tp,&dat[i].x,&dat[i].y);
if (dat[i].tp == 2)
tmp.push_back(dat[i].x);
else cir[i].x = dat[i].x, cir[i].y = dat[i].y;
}
sort(tmp.begin(),tmp.end());
tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
for (int i = 1 ; i <= n ; ++ i) {
if (dat[i].tp == 1)
add(i,1);
else printf("%d
",doit(dat[i].x,dat[i].y));
}
return 0;
}
C - Connections
类比targan，我们考虑构造一棵dfs树。那么，单靠dfs树上的这些边，我们就能保证从根结点能到达任意一个结点。然后就只用让任意一个结点都能到达根结点就好了。于是我们在反图上以同样的点为根结点建dfs树（反图仍然强连通），把这两棵树并在一起，边数最多为(2n-2)，能满足本题要求。
时间复杂度(O(n))。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,m,a[N],b[N],ned[N],vis[N];
struct edge {
int la,b,id;
};
struct tree {
edge con[N << 1];
int tot,fir[N];
void add(int from,int to,int num) {
con[++tot] = (edge) {fir[from],to,num};
fir[from] = tot;
}
void init() {
tot = 0;
for (int i = 1 ; i <= n ; ++ i)
fir[i] = 0;
}
void dfs(int pos) {
vis[pos] = 1;
for (int i = fir[pos] ; i ; i = con[i].la) {
if (vis[con[i].b]) continue;
ned[con[i].id] = 1;
dfs(con[i].b);
}
}
} g,ig;
int main() {
int T;
scanf("%d",&T);
while (T --) {
scanf("%d%d",&n,&m);
g.init();
ig.init();
for (int i = 1 ; i <= m ; ++ i)
scanf("%d%d",&a[i],&b[i]), g.add(a[i],b[i],i), ig.add(b[i],a[i],i), ned[i] = 0;
for (int i = 1 ; i <= n ; ++ i)
vis[i] = 0;
g.dfs(1);
for (int i = 1 ; i <= n ; ++ i)
vis[i] = 0;
ig.dfs(1);
for (int i = 1, j = 1 ; i <= m && j <= m - 2 * n ; ++ i)
if (!ned[i]) printf("%d %d
",a[i],b[i]), ++ j;
}
return 0;
}
I - Interactive Sort
首先一个重要的性质：数据随机。
考虑通过偶数比较来把奇数排序。假如我们把任意一个偶数与所有奇数比较，那么我们就能够把奇数分成两组，并且得出这个偶数是什么。把一些数随机地分为两组，这与快速排序十分相似。因此，我们希望能避免把每个偶数都与所有奇数比较。
假设我们现在已经把奇数分为(k)组，那么，对于我们新取出的一个偶数(x)，其中至少有(k-1)组满足其中所有元素都大于（或小于）(x)。然而，具体地确定被(x)划分的是哪一组是很困难的，因为那一组有的元素大于(x)，有的小于。那我们不妨就只确定到两组，这个可以用二分实现。然后我们就把两组划分为三组。
这个算法本质就是快速排序，只不过多了二分查找。
然后粗糙计算一下询问次数的常数。把两组划分为三组相较于把一组划分为两组大概是2倍常数，二分查找估计为常数加1。快排期望复杂度的常数是2，故这个算法的常数可以认为是5。对于(n=5000)，常数为5的(O(n log n))次询问，不会超出本题的限制。
时间复杂度上，暴力维护分组是(O(n^2))的，可以用数据结果做到(O(n log^2 n))。
#include <bits/stdc++.h>
#define gc() getchar()
using namespace std;
const int N = 10010;
struct data {
int l,r;
} dat[N];
int n,cnt,a[N],tmp[N],tcnt,ans[N];
int ask(int x,int y) {
char tmp;
printf("? %d %d
",x,y);
fflush(stdout);
for (tmp = gc() ; tmp != '<' && tmp != '>' ; tmp = gc());
return tmp == '<';
}
int main() {
int l,r,mid,p,num;
scanf("%d",&n);
for (int i = 1 ; i <= (n+1)/2 ; ++ i) a[i] = i;
dat[1] = (data) {1,(n+1)/2};
cnt = 1;
for (int i = 1 ; i <= n/2 ; ++ i) {
l = 1, r = cnt;
while (l + 1 < r) {
mid = (l + r) >> 1;
if (ask(i,a[dat[mid].l])) r = mid;
else l = mid;
}
p = dat[l].l;
num = tcnt = 0;
for (int j = dat[l].l ; j <= dat[l].r ; ++ j)
if (ask(i,a[j])) tmp[++tcnt] = a[j];
else a[p++] = a[j], num ++;
for (int j = 1 ; j <= tcnt ; ++ j)
a[p+j-1] = tmp[j];
if (num != 0 && num != dat[l].r - dat[l].l + 1) {
ans[i] = (num + dat[l].l-1) << 1;
++ cnt;
for (int j = cnt ; j >= l + 2 ; -- j)
dat[j] = dat[j-1];
dat[l+1] = (data) {dat[l].l + num,dat[l].r};
dat[l] = (data) {dat[l].l,dat[l].l + num - 1};
continue;
}
if (l == r) {
ans[i] = n;
continue;
}
p = dat[r].l;
num = tcnt = 0;
for (int j = dat[r].l ; j <= dat[r].r ; ++ j)
if (ask(i,a[j])) tmp[++tcnt] = a[j];
else a[p++] = a[j], num ++;
for (int j = 1 ; j <= tcnt ; ++ j)
a[p+j-1] = tmp[j];
ans[i] = (num + dat[r].l - 1) << 1;
if (num == 0 || num == dat[r].r - dat[r].l + 1) continue;
++ cnt;
for (int j = cnt ; j >= r + 2 ; -- j)
dat[j] = dat[j-1];
dat[r+1] = (data) {dat[r].l + num,dat[r].r};
dat[r] = (data) {dat[r].l,dat[r].l + num - 1};
}
printf("!");
for (int i = 1 ; i <= n/2 ; ++ i)
printf(" %d",ans[i]);
for (int i = 1 ; i <= (n+1)/2 ; ++ i)
ans[a[i]] = (i<<1) - 1;
for (int i = 1 ; i <= (n+1)/2 ; ++ i)
printf(" %d",ans[i]);
puts("");
return 0;
}
L - Laminar Family
这题有多个做法，这里仅涉及我本人的做法。
我们考虑按长度从大到小枚举路径，那么当我们枚举到路径(k)时，我们就不需要考虑(k)包含其他路径的情况，因为能被(k)包含的路径还没加进来。那么，(k)这一条路径要么已经完全被其他另一条路径覆盖了，要么完全没被覆盖。于是，我们枚举路径时对这条路径上的所有结点都染色（不同路径的颜色不同），那么答案是Yes就等价于，对于所有路径，它上面的结点在染上它的颜色之前的颜色都是相同的（或都没有颜色）。这个可以用树链剖分+线段树实现。
时间复杂度(O(n log ^2 n))。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
struct edge {
int la,b;
} con[N << 1];
int tot,fir[N];
void add(int from,int to) {
con[++tot] = (edge) {fir[from],to};
fir[from] = tot;
}
int fa[N],sz[N],hson[N],top[N],dfn[N],dep[N],cnt,n,m,ans;
void dfs_init(int pos) {
dep[pos] = dep[fa[pos]] + 1;
sz[pos] = 1;
for (int i = fir[pos] ; i ; i = con[i].la) {
if (con[i].b == fa[pos]) continue;
fa[con[i].b] = pos;
dfs_init(con[i].b);
sz[pos] += sz[con[i].b];
if (sz[con[i].b] > sz[hson[pos]])
hson[pos] = con[i].b;
}
}
void dfs_build(int pos,int tp) {
top[pos] = tp;
dfn[pos] = ++cnt;
if (hson[pos]) dfs_build(hson[pos],tp);
for (int i = fir[pos] ; i ; i = con[i].la) {
if (con[i].b == fa[pos] || con[i].b == hson[pos])
continue;
dfs_build(con[i].b,con[i].b);
}
}
int lca(int x,int y) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x,y);
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x,y);
return x;
}
struct node {
int tag,val;
} t[N << 2];
inline void puttag(int x,int v) {
t[x].tag = v;
t[x].val = v;
}
void push_down(int x) {
if (!t[x].tag) return;
puttag(x<<1,t[x].tag);
puttag(x<<1|1,t[x].tag);
t[x].tag = 0;
}
inline int merge(int x,int y) {
if (x == -2) return y;
if (y == -2) return x;
if (x == -1 || y == -1) return -1;
if (x != y) return -1;
return x;
}
void push_up(int x) {
if (t[x].tag) push_down(x);
t[x].val = merge(t[x<<1].val,t[x<<1|1].val);
}
void modify(int l,int r,int v,int x=1,int lp=1,int rp=n) {
if (l > rp || r < lp) return;
if (lp >= l && rp <= r)
return (void)(puttag(x,v));
int mid = (lp + rp) >> 1;
push_down(x);
modify(l,r,v,x<<1,lp,mid);
modify(l,r,v,x<<1|1,mid+1,rp);
push_up(x);
}
int query(int l,int r,int x=1,int lp=1,int rp=n) {
if (l > rp || r < lp) return -2;
if (lp >= l && rp <= r)
return t[x].val;
int mid = (lp + rp) >> 1;
push_down(x);
return merge(query(l,r,x<<1,lp,mid),query(l,r,x<<1|1,mid+1,rp));
}
bool doit(int x,int y,int id) {
int res = 1, tmp = -2;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x,y);
tmp = merge(tmp,query(dfn[top[x]],dfn[x]));
if (tmp == -1) res = 0;
modify(dfn[top[x]],dfn[x],id);
x = fa[top[x]];
}
if (dep[x] < dep[y]) swap(x,y);
tmp = merge(tmp,query(dfn[y],dfn[x]));
if (tmp == -1) res = 0;
modify(dfn[y],dfn[x],id);
return res;
}
struct data {
int u,v,len;
bool operator < (const data& x) const {
return len > x.len;
}
} dat[N];
int main() {
int a,b,c;
scanf("%d%d",&n,&m);
for (int i = 1 ; i < n ; ++ i) {
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs_init(1);
dfs_build(1,1);
for (int i = 1 ; i <= m ; ++ i) {
scanf("%d%d",&a,&b);
c = lca(a,b);
dat[i] = (data) {a,b,dep[a] + dep[b] - 2 * dep[c]};
}
sort(dat+1,dat+m+1);
ans = 1;
for (int i = 1 ; i <= m ; ++ i)
ans &= doit(dat[i].u,dat[i].v,i);
if (ans) puts("Yes");
else puts("No");
return 0;
}
小结：还有好几道题根本没法补……感觉自己缺少创造性的思维，也许是应该多做这种类型的题目了。