全补完了，发个题解。
A.Slackline Adventure题意：给定n * m个点，求出有多少点对满足两点连线上没有其他点，且两点之间距离在l到r之间。
做法：两点相邻的情况单独计算。那么每一个点对等价于一个矩形，矩形对角线上没有点且对角线长度在l到r之间。
考虑枚举矩形的长和宽，可以得到答案为 2 ∑ i = 1 n − 1 ∑ j = 1 m − 1 ( n − i ) ( m − j ) [ g c d ( i , j ) = 1 ] [ l 2 ≤ i 2 + j 2 ≤ r 2 ] 2sum_{i = 1}^{n - 1} sum_{j = 1}^{m - 1} (n - i)(m - j) [gcd(i,j) = 1][l^2 leq i^2 + j^2 leq r^2] 2∑i=1n−1∑j=1m−1(n−i)(m−j)[gcd(i,j)=1][l2≤i2+j2≤r2]
显然这个东西可以用莫比乌斯反演来处理，枚举gcd得到
2 ∑ d = 1 n − 1 μ ( d ) ∑ i = 1 n − 1 d ( n − i ) ∑ j = 1 m − 1 d ( m − j ) [ l 2 ≤ i 2 + j 2 ≤ r 2 ] 2sum_{d = 1}^{n - 1}mu(d)sum_{i = 1}^{frac{n - 1}{d}}(n - i)sum_{j = 1}^{frac{m - 1}{d}}(m - j)[l^2 leq i^2 + j^2 leq r^2] 2∑d=1n−1μ(d)∑i=1dn−1(n−i)∑j=1dm−1(m−j)[l2≤i2+j2≤r2]
那么分别计算 i 2 + j 2 ≤ r 2 i^2 + j^2 leq r^2 i2+j2≤r2的答案和 i 2 + j 2 ≤ l 2 − 1 i^2 + j^2 leq l^2 - 1 i2+j2≤l2−1的答案，相减即可。
即计算下面这个式子
2
∑
d
=
1
n
−
1
μ
(
d
)
∑
i
=
1
n
−
1
d
(
n
−
i
)
∑
j
=
1
m
−
1
d
(
m
−
j
)
[
i
2
+
j
2
≤
k
]
2sum_{d = 1}^{n - 1}mu(d)sum_{i = 1}^{frac{n - 1}{d}}(n - i)sum_{j = 1}^{frac{m - 1}{d}}(m - j)[i^2 + j^2 leq k]
2∑d=1n−1μ(d)∑i=1dn−1(n−i)∑j=1dm−1(m−j)[i2+j2≤k]
枚举前两个求和符号是
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)的复杂度，然后二分算出第三部分的答案，那么总的复杂度就是
O
(
n
l
o
g
2
n
)
O(nlog^2n)
O(nlog2n)
#includeB.Marbles#include #include #include #define int long long using namespace std; typedef long long ll; const int maxn = 1e5 + 10; const int p = 1e9 + 7; int pp[maxn]; int n, m, l, r; int prime[maxn], mu[maxn]; void sieve() { mu[1] = 1; for ( int i = 2;i <= 1e5;i++ ) { if ( !pp[i] ) { prime[++prime[0]] = i; mu[i] = -1; } for ( int j = 1;j <= prime[0];j++ ) { if ( prime[j] * i > 1e5 ) { break; } pp[i * prime[j]] = 1; if ( i % prime[j] == 0 ) { mu[i * prime[j]] = 0; break; } mu[i * prime[j]] = -mu[i]; } } } ll calc(ll d, ll i, ll t) { int l = 0, r = (m - 1) / d + 1; int tt = 0; while ( l < r ) { int mid = (l + r) >> 1; if ( 1ll * d * d * i * i + 1ll * d * d * mid * mid <= t ) { tt = mid; l = mid + 1; } else { r = mid; } } return (1ll * tt * m % p - 1ll * d * ((1ll * tt * (tt + 1) / 2) % p) % p) % p; } ll f(ll n, ll m, ll t) { ll ret = 0; for ( ll i = 1;i <= n - 1;i++ ) { ll temp = 0; for ( ll j = 1;j <= (n - 1) / i;j++ ) { temp = (temp + (n - j * i % p) * calc(i, j, t) % p) % p; } ret = (ret + temp * mu[i]) % p; } return ret; } signed main() { sieve(); scanf("%lld%lld%lld%lld", &n, &m, &l, &r); ll maxx = f(n, m, 1ll * r * r); ll minn = f(n, m, 1ll * l * l - 1); ll ans = (maxx - minn) * 2 % p; if ( l == 1 ) { ans = (1ll * (n - 1) * m % p + 1ll * (m - 1) * n % p + ans) % p; } printf("%lldn", ((ans) % p + p) % p); return 0; }
每一枚棋子最终都会聚集在 ( 1 , 2 ) (1,2) (1,2)和 ( 2 , 1 ) (2,1) (2,1)，那么求一下sg函数即可
#includeC.Pizza Cutterusing namespace std; int sg[105][105], f[400], x[1010], y[1010]; int main() { sg[1][2] = sg[2][1] = 0; int i, j, k, n; for ( i = 1; i <= 100; i++ ) { for ( j = 1; j <= 100; j++ ) { if ( i == j ) continue; memset(f, 0, sizeof f); for ( k = 1; k <= max(i, j); k++ ) { int l = i - k, r = j - k; if ( l > 0 && l != j ) f[sg[l][j]] = 1; if ( r > 0 && i != r ) f[sg[i][r]] = 1; if ( l > 0 && r > 0 ) f[sg[l][r]] = 1; } for ( k = 0; k <= 400; k++ ) { if ( !f[k] ) { sg[i][j] = k; break; } } } } cin >> n; int ff = 0, ans = 0; for ( i = 1; i <= n; i++ ) cin >> x[i] >> y[i]; for ( i = 1; i <= n; i++ ) { if ( x[i] == 0 || y[i] == 0 || x[i] == y[i] ) { ff = 1; break; } ans ^= sg[x[i]][y[i]]; } if ( ff || ans ) cout << "Y" << endl; else cout << "N" << endl; return 0; }
切出来的最大块数就等于纵向的线的交点数+横向的线的交点数+
(
H
+
1
)
(
V
+
1
)
(H + 1)(V + 1)
(H+1)(V+1)
交点数只需要按照一边的坐标排个序，然后求逆序对数即可。
#includeD.Unraveling Monty Hallusing namespace std; const long long N = 1e5+100; long long ans, tr[N << 2], mx, maxx, maxy; long long v, h, use[N << 2]; long long lowbit(long long x){ return x & (-x); } struct ss1{ long long you, zuo; bool operator < (const ss1 &a )const{ return zuo < a.zuo; } }hh[N << 1]; struct ss2{ long long shang, xia; bool operator < (const ss2 &a )const{ return shang < a.shang; } }vv[N << 1]; bool cmp_zuo(ss2 a, ss2 b){ return a.shang < b.shang; } long long add(long long x){ while(x <= mx) tr[x] ++, x += lowbit(x); return x; } long long asksum(long long x){ long long re = 0; while(x) re += tr[x], x -= lowbit(x); return re; } long long ask(long long l, long long r){ return asksum(r) - asksum(l - 1); } long long read(){ long long x; scanf("%lld", &x); return x; } int main(){ cin >> maxx >> maxy; cin >> h >> v; mx = max(h * 2, v * 2); for(long long i = 1; i <= h; i ++) use[i] = hh[i].zuo = read(), use[i + h] = hh[i].you = read(); sort(use + 1, use + h * 2 + 1); for(long long i = 1; i <= h; i ++) hh[i].zuo = lower_bound(use + 1, use + h * 2 + 1, hh[i].zuo) - use, hh[i].you = lower_bound(use + 1, use + h * 2 + 1, hh[i].you) - use; for(long long i = 1; i <= v; i ++) use[i] = vv[i].shang = read(), use[i + v] = vv[i].xia = read(); sort(use + 1, use + v * 2 + 1); for(long long i = 1; i <= v; i ++) vv[i].shang = lower_bound(use + 1, use + v * 2 + 1, vv[i].shang) - use, vv[i].xia = lower_bound(use + 1, use + v * 2 + 1, vv[i].xia) - use; sort(hh + 1, hh + h + 1); sort(vv + 1, vv + v + 1); for(long long i = 1; i <= h; i ++){ long long zuo = hh[i].zuo; long long you = hh[i].you; ans += ask(you + 1, mx); add(you); } memset(tr, 0, sizeof(tr)); for(long long i = 1; i <= v; i ++){ long long xia = vv[i].xia; ans += ask(xia + 1, mx); add(xia); } cout << ans + (h + 1) * (v + 1); }
题面比较长，只需要求n - 1的数量即可。
#includeE.Enigma#include using namespace std; int main() { int n; scanf("%d", &n); int ans = 0; for ( int i = 1;i <= n;i++ ) { int x; scanf("%d", &x); if ( x != 1 ) ans++; } printf("%dn", ans); return 0; }
n 2 n^2 n2暴力就能过，我们队写了个bitset优化，写复杂了
#includeF.Music Festival#include #include #include #include #include #include using namespace std; const int maxn = 1e4 + 10; bitset bt1[30], bt2[30]; char s[maxn], t[maxn]; int main() { scanf("%s", s + 1); scanf("%s", t + 1); int n = strlen(s + 1); int m = strlen(t + 1); for ( int i = 1;i <= m;i++ ) { bt1[t[i] - 'A'][i] = 1; bt2[s[i] - 'A'][i] = 1; } int ans = 0; for ( int i = 1;i + m - 1 <= n;i++ ) { int flag = 0; for ( int j = 0;j <= 25;j++ ) { bitset temp = bt1[j] & bt2[j]; if ( temp.count() != 0 ) { flag = 1; } } if ( flag == 0 ) ans++; bt2[s[i] - 'A'][1] = 0; for ( int j = 0;j <= 25;j++ ) { bt2[j] >>= 1; bt2[j][0] = 0; } if ( i + m <= n ) bt2[s[i + m] - 'A'][m] = 1; } printf("%dn", ans); return 0; }
入门状压dp，离散化一下就行了。
#includeG.Gasolineusing namespace std; const int N = 2050; int dp[N][N], use[N << 2], nn, m, mi; vector < int > yanchu[N]; struct ss{ int s, e, song, st; }prog[N]; bool cmp_by_e(ss a, ss b){ return a.e < b.e; } int read(){ int x; scanf("%d", &x); return x; } int main(){ cin >> nn; for(int i = 0; i <= nn - 1; i ++){ mi = read(); for(int j = 1; j <= mi; j ++) prog[++ m].s = read(), prog[m].e = read(), prog[m].song = read(), prog[m].st = i; } sort(prog + 1, prog + m, cmp_by_e); for(int i = 1; i <= m; i ++) use[i] = prog[i].s, use[i + m] = prog[i].e; sort(use + 1, use + m * 2 + 1); for(int i = 1; i <= m; i ++) prog[i].s = lower_bound(use + 1, use + m * 2 + 1, prog[i].s) - use, prog[i].e = lower_bound(use + 1, use + m * 2 + 1, prog[i].e) - use; for(int i = 1; i <= m; i ++) yanchu[prog[i].e].push_back(i); for(int z = 0; z <= (1 << nn) - 1; z ++) for(int i = 1; i <= m * 2; i ++){ dp[i][z] = dp[i - 1][z]; for(int j = 0; j <= (int)yanchu[i].size() - 1; j ++){ int zz = (1 << prog[yanchu[i][j]].st), s = prog[yanchu[i][j]].s, v = prog[yanchu[i][j]].song; if((zz & z) && (dp[s][z] || dp[s][z ^ zz] || z == 0 || (z ^ zz) == 0)) dp[i][z] = max(dp[i][z], max(dp[s][z], dp[s][z ^ zz]) + v); } } if(dp[m * 2][(1 << nn) - 1] == 0) cout << -1; else cout << dp[m * 2][(1 << nn) - 1]; }
边权从小到大加边然后跑网络流判断是否满流即可，或者二分最大边权后跑网络流。
#includeH.Police Hypothesis#include #include #include #include using namespace std; const int maxn = 4e3 + 10; struct Edge { int val, to, next; }e[1000000]; struct EDGE { int u, v, w; bool operator<(const EDGE& x)const { return w < x.w; } }a[100000]; int head[maxn], tot = 1; int dep[maxn], cur[maxn]; int n, m, c; int s, t; void addedge(int u, int v, int w) { e[++tot] = Edge({ w,v,head[u] }); head[u] = tot; e[++tot] = Edge({ 0,u,head[v] }); head[v] = tot; } bool bfs() { for ( int i = 0;i <= n + m + 1;i++ ) { dep[i] = 0; cur[i] = head[i]; } queue qq; qq.push(s); dep[s] = 1; while ( !qq.empty() ) { int temp = qq.front(); qq.pop(); for ( int i = head[temp];~i;i = e[i].next ) { int to = e[i].to; if ( e[i].val && !dep[to] ) { dep[to] = dep[temp] + 1; if ( to == t ) return 1; qq.push(to); } } } return 0; } int dfs(int now = s, int flow = 0x3f3f3f3f) { if ( now == t ) return flow; int ret = 0; for ( int& i = cur[now];~i;i = e[i].next ) { int to = e[i].to; if ( e[i].val && dep[to] == dep[now] + 1 ) { int temp = dfs(to, min(e[i].val, flow)); ret += temp; e[i].val -= temp; e[i ^ 1].val += temp; if ( (flow -= temp) <= 0 ) break; } } if ( ret == 0 ) dep[now] = 0; return ret; } int main() { memset(head, -1, sizeof head); scanf("%d%d%d", &n, &m, &c); s = 0, t = n + m + 1; int sum = 0; for ( int i = 1;i <= n;i++ ) { int x; scanf("%d", &x); addedge(m + i, t, x); sum += x; } for ( int i = 1;i <= m;i++ ) { int x; scanf("%d", &x); addedge(s, i, x); } int ans = -1; for ( int i = 1;i <= c;i++ ) { scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].w); } sort(a + 1,a + c + 1); int temp = 0; for ( int i = 1;i <= c;i++ ) { addedge(a[i].v, a[i].u + m, 0x3f3f3f3f); while ( bfs() ) { temp += dfs(); } if ( temp == sum ) { ans = a[i].w; break; } } printf("%dn", ans); return 0; }
给定一棵节点上带字符的树，给定一个模式串，需要支持两种操作：
- 查询从 u u u到 v v v的字符串中包含多少模式串
- 修改某个节点上的字符
由于模式串长度最多只有100，所以可以树剖后用线段树维护长度为0~100的前缀哈希值和后缀哈希值，合并时的答案为左儿子的答案+右儿子的答案+跨过中间的答案。跨过中间的答案只需要暴力左儿子中的后缀长度来计算即可。
由于 u u u到 v v v和 v v v到 u u u的路径不同，所以我们还需要维护反过来看的字符串。
总复杂度 O ( 100 n l o g n ) O(100nlogn) O(100nlogn)
#includeI.Switches#include #include #include #include #define lson ( p << 1 ) #define rson ( p << 1 | 1 ) using namespace std; typedef long long ll; typedef unsigned int ull; const int maxn = 1e5 + 1; int n, q; char s[101]; char a[maxn]; struct Edge { int to, next; }e[maxn << 1]; int head[maxn], tot; int dfn[maxn], dep[maxn], top[maxn], fa[maxn], son[maxn]; int dfnn; int id[maxn]; int len; ull has; struct Tree { int len; int val; ull l[101], r[101]; }tree[maxn << 2][2]; ull po[maxn]; void addedge(int u, int v) { e[++tot] = Edge({ v,head[u] }); head[u] = tot; } void dfs1(int now = 1, int last = 0, int deep = 1) { top[now] = 1; fa[now] = last; dep[now] = deep; int maxson = -1; for ( int i = head[now];~i;i = e[i].next ) { int to = e[i].to; if ( to == last ) continue; dfs1(to, now, deep + 1); top[now] += top[to]; if ( top[to] > maxson ) { maxson = top[to]; son[now] = to; } } } void dfs2(int now = 1, int topf = 1) { top[now] = topf; dfn[now] = ++dfnn; id[dfnn] = now; if ( !son[now] ) return; dfs2(son[now], topf); for ( int i = head[now];~i;i = e[i].next ) { int to = e[i].to; if ( to == fa[now] || to == son[now] ) { continue; } dfs2(to, to); } } Tree combine(Tree x, Tree y) { Tree ret {}; ret.val = x.val + y.val; ret.len = y.len + x.len; for ( int i = 1;i < len;i++ ) { if ( x.r[i] * po[len - i] + y.l[len - i] == has ) { ret.val++; } } for ( int i = 1;i < len;i++ ) { if ( i <= x.len ) { ret.l[i] = x.l[i]; } else if ( i <= ret.len ) { ret.l[i] = x.l[x.len] * po[i - x.len] + y.l[i - x.len]; } else { ret.l[i] = 0; } } for ( int i = 1;i < len;i++ ) { if ( i <= y.len ) { ret.r[i] = y.r[i]; } else if ( i <= ret.len ) { ret.r[i] = x.r[i - y.len] * po[y.len] + y.r[y.len]; } else { ret.r[i] = 0; } } return ret; } void pushup(int p) { tree[p][0] = combine(tree[lson][0], tree[rson][0]); tree[p][1] = combine(tree[rson][1], tree[lson][1]); } void build(int l = 1, int r = n, int p = 1) { tree[p][0].len = tree[p][1].len = r - l + 1; if ( l == r ) { tree[p][0].l[1] = tree[p][0].r[1] = a[id[l]]; tree[p][1].l[1] = tree[p][1].r[1] = a[id[r]]; tree[p][0].val = tree[p][1].val = (tree[p][0].l[1] == has); return; } int mid = (l + r) >> 1; build(l, mid, lson); build(mid + 1, r, rson); pushup(p); } void update(int x, char ch, int l = 1, int r = n, int p = 1) { if ( l == r ) { tree[p][0].l[1] = tree[p][0].r[1] = ch; tree[p][1].l[1] = tree[p][1].r[1] = ch; tree[p][0].val = tree[p][1].val = (tree[p][0].l[1] == has); return; } int mid = (l + r) >> 1; if ( x <= mid ) { update(x, ch, l, mid, lson); } else update(x, ch, mid + 1, r, rson); pushup(p); } Tree query(int s, int t, int k, int l = 1, int r = n, int p = 1) { if ( s <= l && r <= t ) { return tree[p][k]; } int mid = (l + r) >> 1; Tree ret {}; if ( k == 0 ) { if ( s <= mid ) { ret = combine(query(s, t, k, l, mid, lson), ret); } if ( t > mid ) { ret = combine(ret, query(s, t, k, mid + 1, r, rson)); } } else { if ( s <= mid ) { ret = combine(ret, query(s, t, k, l, mid, lson)); } if ( t > mid ) { ret = combine(query(s, t, k, mid + 1, r, rson), ret); } // if ( t > mid ) { // ret = combine(ret, query(s, t, k, mid + 1, r, rson)); // } // if ( s <= mid ) { // ret = combine(ret, query(s, t, k, l, mid, lson)); // } } return ret; } int qpahth(int x, int y) { Tree ret1 {}, ret2 {}; while ( top[x] != top[y] ) { if ( dep[top[x]] >= dep[top[y]] ) { ret1 = combine(ret1, query(dfn[top[x]], dfn[x], 1)); x = fa[top[x]]; } else { ret2 = combine(query(dfn[top[y]], dfn[y], 0), ret2); y = fa[top[y]]; } } if ( dep[x] >= dep[y] ) { ret1 = combine(ret1, query(dfn[y], dfn[x], 1)); } else { ret2 = combine(query(dfn[x], dfn[y], 0), ret2); } Tree ret = combine(ret1, ret2); return ret.val; } int main() { po[0] = 1; for ( int i = 1;i <= 1e5;i++ ) { po[i] = po[i - 1] * 19260817; head[i] = -1; } scanf("%d%d", &n, &q); scanf("%s", s + 1); len = strlen(s + 1); for ( int i = 1;i <= len;i++ ) { has = has * 19260817 + s[i]; } scanf("%s", a + 1); for ( int i = 1;i <= n - 1;i++ ) { int u, v; scanf("%d%d", &u, &v); addedge(u, v); addedge(v, u); } dfs1(); dfs2(); build(); int opt; for ( int i = 1;i <= q;i++ ) { int u, v; scanf("%d", &opt); if ( opt == 1 ) { scanf("%d%d", &u, &v); printf("%dn", qpahth(u, v)); } else { char ch[3]; scanf("%d%s", &u, ch + 1); update(dfn[u], ch[1]); } } return 0; }
显然最多操作两轮，只需要 n 2 n^2 n2模拟即可。
#includeJ.Joining Capitals#include #include #include using namespace std; const int maxn = 1e3 + 10; int a[maxn]; vector vec[maxn]; int n, m; int l; int main() { scanf("%d%d", &n, &m); scanf("%d", &l); if ( l == 0 ) { printf("0n"); return 0; } for ( int i = 1;i <= l;i++ ) { int x; scanf("%d", &x); a[x] = 1; } for ( int i = 1;i <= n;i++ ) { int k; scanf("%d", &k); vec[i].resize(k); for ( int j = 0;j <= k - 1;j++ ) { int x; scanf("%d", &x); vec[i][j] = x; } } int ans = 0; for ( int i = 1;i <= n;i++ ) { ans++; for ( int j = 0;j < vec[i].size();j++ ) { a[vec[i][j]] ^= 1; } int flag = 0; for ( int j = 1;j <= n;j++ ) { if ( a[j] != 0 ) { flag = 1; } } if ( flag == 0 ) { printf("%dn", ans); return 0; } } for ( int i = 1;i <= n;i++ ) { ans++; for ( int j = 0;j < vec[i].size();j++ ) { a[vec[i][j]] ^= 1; } int flag = 0; for ( int j = 1;j <= n;j++ ) { if ( a[j] != 0 ) { flag = 1; } } if ( flag == 0 ) { printf("%dn", ans); return 0; } } printf("-1n"); return 0; }
一道裸的斯坦纳树，要求关键点的度数为1。
在转移的时候不进行以关键点为中间点的转移即可。
#includeK.Kepler#include #include #include #include using namespace std; const int maxn = 1e2 + 10; int n, k; struct TT { int x, y; }p[maxn]; struct Edge { double val; int to, next; }e[maxn * maxn << 1]; int head[maxn], tot; double dp[maxn][2000]; int key[maxn]; int vis[maxn]; void addedge(int u, int v, double w) { e[++tot] = Edge({ w,v,head[u] }); head[u] = tot; } double dist(int x, int y) { return sqrt(1.0 * (p[x].x - p[y].x) * (p[x].x - p[y].x) + (p[x].y - p[y].y) * (p[x].y - p[y].y)); } void spfa(int s) { queue qq; for ( int i = 0;i <= n - 1;i++ ) { if ( dp[i][s] != 0x3f3f3f3f ) { qq.push(i); vis[i] = 1; } } while ( !qq.empty() ) { int temp = qq.front(); qq.pop(); vis[temp] = 0; for ( int i = head[temp];~i;i = e[i].next ) { int to = e[i].to; if ( dp[to][s] > dp[temp][s] + e[i].val ) { dp[to][s] = dp[temp][s] + e[i].val; if ( !vis[to] ) { vis[to] = 1; qq.push(to); } } } } } int main() { scanf("%d%d", &n, &k); for ( int i = 0;i <= n - 1;i++ ) { scanf("%d%d", &p[i].x, &p[i].y); head[i] = -1; } for ( int i = 0;i <= n - 1;i++ ) { for ( int j = 0;j < i;j++ ) { addedge(i, j, dist(i, j)); addedge(j, i, dist(i, j)); } } for ( int i = 0;i <= n - 1;i++ ) { for ( int j = 0;j < (1 << k);j++ ) { dp[i][j] = 0x3f3f3f3f; } } for ( int i = 0;i <= k - 1;i++ ) { dp[i][1 << i] = 0; } for ( int s = 1;s < (1 << k);s++ ) { for ( int i = k;i <= n - 1;i++ ) { for ( int subs = (s - 1) & s;subs;subs = (subs - 1) & s ) { dp[i][s] = min(dp[i][s], dp[i][subs] + dp[i][s ^ subs]); } } spfa(s); } double ans = 0x3f3f3f3f; for ( int i = 0;i <= n - 1;i++ ) { ans = min(ans, dp[i][(1 << k) - 1]); } printf("%.5fn", ans); return 0; }
给定若干个包含原点的圆，不会有三个圆交在同一点，求这些圆的交点数，若超过 2 n 2n 2n个则输出 g r e a t e r greater greater
由于都包含原点，那么圆和圆之间要么是包含关系，要么是相交关系。那么就转化为求相交的圆的个数。
注意到圆心范围很小，我们可以将圆划分为若干个集合，每个集合里的圆都两两不相交，这样最多划分为 50 ∗ 50 50*50 50∗50个集合。
我们按照半径从小到大加入圆，枚举每一个集合，判断与该集合最外层的圆是否相交，如果相交，那么从大到小枚举该集合内的圆，逐个判断是否相交，一旦不相交就不再继续枚举。枚举结束后，选择一个不相交的集合加入其中，若不存在则放入一个新的集合中。
#includeL.Subway Lines#include #include #include #include #include using namespace std; const int maxn = 2e5 + 10; struct TT { double x, y, r; int id; bool operator<(const TT& t)const { return r < t.r; } }a[maxn]; struct Edge { int to, next; }e[maxn << 1]; int head[maxn], tot; int n; set st; int ans = 0; void addedge(int u, int v) { e[++tot] = Edge({ v,head[u] }); head[u] = tot; } bool check(int x, int y) { double t1 = (a[x].x - a[y].x) * (a[x].x - a[y].x) + (a[x].y - a[y].y) * (a[x].y - a[y].y); double t2 = (a[x].r - a[y].r) * (a[x].r - a[y].r); return t1 <= t2; } void solve(int tt,int now) { if ( check(tt, now) ) { return; } ans++; for ( int i = head[now];~i;i = e[i].next ) { int to = e[i].to; solve(tt, to); } } int main() { scanf("%d", &n); for ( int i = 1;i <= n;i++ ) { scanf("%lf%lf%lf", &a[i].x, &a[i].y, &a[i].r); a[i].id = i; } for ( int i = 1;i <= n;i++ ) { head[i] = -1; } sort(a + 1, a + n + 1); for ( int i = 1;i <= n;i++ ) { set ::iterator tt; int temp = 0; for ( auto j = st.begin();j != st.end();j++ ) { if ( check(i, *j) ) { temp = *j; tt = j; } else { solve(i, *j); } } if ( ans > n ) { break; } st.insert(i); if ( !temp ) { continue; } addedge(i, temp); st.erase(tt); } if ( ans > n ) { printf("greatern"); } else { printf("%dn", ans * 2); } return 0; }
树剖板子题，对一条路径上的点置为1，然后对另外一条路径进行查询。
#includeM.Modifying SAT#include #include #include #include #define lson ( p << 1 ) #define rson ( p << 1 | 1 ) using namespace std; const int maxn = 2e5 + 10; struct Edge { int to, next; }e[maxn << 1]; int head[maxn], tot; struct Tree { int val; int lazy; }tree[maxn << 2]; int n, q; int dep[maxn], top[maxn], siz[maxn], fa[maxn], son[maxn]; int id[maxn], wt[maxn]; int cnt; void addedge(int u, int v) { e[++tot] = Edge({ v,head[u] }); head[u] = tot; } void dfs1(int now = 1, int last = 0, int deep = 1) { fa[now] = last; dep[now] = deep; siz[now] = 1; int maxson = -1; for ( int i = head[now];~i;i = e[i].next ) { int to = e[i].to; if ( to == last ) continue; dfs1(to, now, deep + 1); siz[now] += siz[to]; if ( siz[to] > maxson ) { maxson = siz[to]; son[now] = to; } } } void dfs2(int now = 1, int topf = 1) { id[now] = ++cnt; top[now] = topf; if ( !son[now] ) return; dfs2(son[now], topf); for ( int i = head[now];~i;i = e[i].next ) { int to = e[i].to; if ( to == fa[now] || to == son[now] ) continue; dfs2(to, to); } } void pushdown(int p, int l = 1,int r = n) { int mid = (l + r) >> 1; tree[lson].val += (mid - l + 1) * tree[p].lazy; tree[rson].val += (r - mid) * (tree[p].lazy); tree[lson].lazy += tree[p].lazy; tree[rson].lazy += tree[p].lazy; tree[p].lazy = 0; } void update(int s, int t, int c, int l = 1, int r = n, int p = 1) { if ( s <= l && r <= t ) { int tt = (r - l + 1) * c; tree[p].val += tt; tree[p].lazy += c; return; } int mid = (l + r) >> 1; if ( tree[p].lazy ) pushdown(p, l, r); if ( s <= mid ) update(s, t, c, l, mid, lson); if ( t > mid ) update(s, t, c, mid + 1, r, rson); tree[p].val = tree[lson].val + tree[rson].val; } int query(int s, int t, int l = 1, int r = n, int p = 1) { if ( s <= l && r <= t ) { return tree[p].val; } int mid = (l + r) >> 1; if ( tree[p].lazy ) pushdown(p, l, r); int ret = 0; if ( s <= mid ) ret += query(s, t, l, mid, lson); if ( t > mid ) ret += query(s, t, mid + 1, r, rson); return ret; } int qpath(int x, int y) { int ret = 0; while ( top[x] != top[y] ) { if ( dep[top[x]] < dep[top[y]] ) swap(x, y); ret += query(id[top[x]], id[x]); x = fa[top[x]]; } if ( dep[x] > dep[y] ) swap(x, y); ret += query(id[x], id[y]); return ret; } void updpath(int x, int y, int c) { while ( top[x] != top[y] ) { if ( dep[top[x]] < dep[top[y]] ) swap(x, y); update(id[top[x]], id[x], c); x = fa[top[x]]; } if ( dep[x] > dep[y] ) swap(x, y); update(id[x], id[y], c); } int main() { scanf("%d%d", &n, &q); memset(head, -1, sizeof head); for ( int i = 1;i <= n - 1;i++ ) { int u, v; scanf("%d%d", &u, &v); addedge(u, v); addedge(v, u); } dfs1(); dfs2(); for ( int i = 1;i <= q;i++ ) { int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d); updpath(a, b, 1); int tt = qpath(c, d); printf("%dn", tt); updpath(a, b, -1); } return 0; }
可以转化为异或方程组，用高斯消元求解。由于要求字典序最大，我们选择从后向前消元，使自由元尽可能靠前，这样可以使得答案字典序最大。
#include#include #include #include #include #include #include #include #define debug(x) cout << #x << " : " << (x) << "n" using namespace std; const int maxn = 2e3 + 10; int m, n; bitset bt[maxn]; int ans[maxn]; int anss; void guass() { for ( int i = 1, now = 1;now <= n;now++ ) { int pos = 0; for ( int j = i;j <= m;j++ ) { if ( bt[j][now] ) { pos = j; break; } } if ( !pos ) { ans[n + 1 - now] = 1; continue; } swap(bt[pos], bt[i]); for ( int j = 1;j <= m;j++ ) { if ( j != i && bt[j][now] ) { bt[j] ^= bt[i]; } } i++; } for ( int i = 1;i <= m;i++ ) { if ( bt[i].count() == 1 && bt[i][n + 1] == 1 ) { anss = -1; return; } } for ( int i = 1;i <= m;i++ ) { if ( bt[i].count() == 0 ) { continue; } int tt = bt[i]._Find_first(); ans[n + 1 - tt] = bt[i][n + 1]; for ( int j = tt + 1;j <= n;j++ ) { ans[n + 1 - tt] = ans[n + 1 - tt] ^ bt[i][j]; } } return; } int main() { scanf("%d%d", &m, &n); char s[maxn]; for ( int i = 1;i <= m;i++ ) { int flag = 0; bt[i][n + 1] = 1; while ( 1 ) { scanf("%s", s + 1); int ttt = 1; if ( s[1] == '(' ) { ttt++; } if ( s[ttt] == 'a' ) { break; } if ( s[ttt] == 'o' ) { flag = 0; continue; } if ( s[ttt] == 'n' ) { flag = 1; continue; } int len = strlen(s + 1); int tt = 0; int id = 0; for ( int j = 1;j <= len;j++ ) { if ( tt && s[j] >= '0' && s[j] <= '9') { id = id * 10 + s[j] - '0'; } else { if ( s[j] >= '0' && s[j] <= '9' ) { tt = 1; id = s[j] - '0'; } } } bt[i][n + 1] = bt[i][n + 1] ^ flag; bt[i][n + 1 - id] = bt[i][n + 1 - id] ^ 1; if ( i == m && s[len] == ')' ) { break; } } } guass(); if ( anss == -1 ) { printf("impossiblen"); } else { for ( int i = 1;i <= n;i++ ) { if ( ans[i] ) { printf("T"); } else printf("F"); } } return 0; }
