https://ac.nowcoder.com/acm/contest/7501
B - Intelligent Robot
题意:k 个线段,二维平面,要从 (sx,sy) 走到 (tx,ty),不能穿过线段,问最短距离。
线段相交判断+最短路
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 #include <bits/stdc++.h> #define debug(x) cout << #x << ":\t" << (x) << endl; using namespace std;#define ll long long const int N = 2e6 + 10 ;const int INF = 0x3f3f3f3f ;const ll inf = 0x3f3f3f3f3f3f3f3f ;const ll mod = 998244353 ;struct Point { double x, y; Point (double x = 0 , double y = 0 ) :x (x), y (y) {} }; typedef Point Vector;Vector operator +(Vector A, Vector B) { return Vector (A.x + B.x, A.y + B.y); } Vector operator -(Vector A, Vector B) { return Vector (A.x - B.x, A.y - B.y); } const double eps = 1e-10 ;int dcmp (double x) { if (fabs (x) < eps)return 0 ; else return x < 0 ? -1 : 1 ; } double Cross (Vector A, Vector B) { return A.x*B.y - A.y*B.x; }bool segmentInter (Point a1, Point a2, Point b1, Point b2) { double c1 = Cross (a2 - a1, b1 - a1), c2 = Cross (a2 - a1, b2 - a1), c3 = Cross (b2 - b1, a1 - b1), c4 = Cross (b2 - b1, a2 - b1); return dcmp (c1)*dcmp (c2) < 0 && dcmp (c3)*dcmp (c4) < 0 ; } int n, m, k, tot;typedef pair<Point, Point>pii;pii seg[N]; Point s, t; vector<Point>vc; double w[1010 ][1010 ];double dist (Point a, Point b) { double x1 = a.x, y1 = a.y; double x2 = b.x, y2 = b.y; return sqrt ((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2)); } typedef pair<double , int >pdi;double d[N];double bfs (int s, int t) { priority_queue<pdi, vector<pdi>, greater<pdi> >q; for (int i = 0 ; i < tot; i++)d[i] = 1e18 ; d[s] = 0 ; q.push ({ 0 ,s }); while (!q.empty ()) { int u = q.top ().second; double di = q.top ().first; q.pop (); if (di - d[u] > eps)continue ; if (u == t)return di; for (int v = 0 ; v < tot; v++) { if (dcmp (w[u][v]) == 0 )continue ; if (d[v] > d[u] + w[u][v]) { d[v] = d[u] + w[u][v]; q.push ({ d[v],v }); } } } return -1 ; } int main () { scanf ("%d%d%d" , &n, &m, &k); for (int i = 1 ; i <= k; i++) { Point a, b; scanf ("%lf%lf%lf%lf" , &a.x, &a.y, &b.x, &b.y); seg[i] = { a,b }; vc.push_back (a); vc.push_back (b); } scanf ("%lf%lf%lf%lf" , &s.x, &s.y, &t.x, &t.y); vc.push_back (s); vc.push_back (t); tot = (int )vc.size (); for (int i = 0 ; i < tot; i++) { for (int j = i + 1 ; j < tot; j++) { bool flg = 1 ; for (int p = 1 ; p <= k; p++) { if (segmentInter (vc[i], vc[j], seg[p].first, seg[p].second)) { flg = 0 ; break ; } } if (!flg)continue ; w[j][i] = w[i][j] = dist (vc[i], vc[j]); } } printf ("%.4lf\n" , bfs (tot - 2 , tot - 1 )); return 0 ; }
J - Matrix Subtraction
题意:每次操作选择一个 a*b 的矩形,每个元素+1,问能否得到给定的矩阵。
二维差分
还原出前缀和之前的差分数组,再模拟,看是否能得到一样的差分数组。
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 #include <bits/stdc++.h> #define debug(x) cout << #x << ":\t" << (x) << endl; using namespace std;#define ll long long const int N = 2e6 + 10 ;const int INF = 0x3f3f3f3f ;const ll inf = 0x3f3f3f3f3f3f3f3f ;const ll mod = 998244353 ;int T;int n, m, a, b;int mz[1010 ][1010 ], tmp[1010 ][1010 ];bool ck () { for (int i = 1 ; i <= n - a + 1 ; i++) { for (int j = 1 ; j <= m - b + 1 ; j++) { if (mz[i][j] < tmp[i][j])return false ; int x = mz[i][j] - tmp[i][j]; tmp[i][j] += x; tmp[i + a][j + b] += x; tmp[i + a][j] -= x; tmp[i][j + b] -= x; } } for (int i = 1 ; i <= n + 1 ; i++) { for (int j = 1 ; j <= m + 1 ; j++)if (mz[i][j] != tmp[i][j])return false ; } return true ; } int main () { scanf ("%d" , &T); while (T--) { scanf ("%d%d%d%d" , &n, &m, &a, &b); for (int i = 1 ; i <= n + 1 ; i++)for (int j = 1 ; j <= m + 1 ; j++)mz[i][j] = 0 ; for (int i = 1 ; i <= n; i++)for (int j = 1 ; j <= m; j++)scanf ("%d" , &mz[i][j]); for (int i = n + 1 ; i >= 1 ; i--) { for (int j = m + 1 ; j >= 1 ; j--) { mz[i][j] -= mz[i - 1 ][j] + mz[i][j - 1 ] - mz[i - 1 ][j - 1 ]; } } for (int i = 1 ; i <= n + 1 ; i++)for (int j = 1 ; j <= m + 1 ; j++)tmp[i][j] = 0 ; puts (ck () ? "^_^" : "QAQ" ); } return 0 ; }
A - Intelligent Warehouse
题意:给定 n 个数,从中选出一些数,满足:任意两个数都有倍数关系。问最多选几个。
dp
d p [ i ] dp[i] d p [ i ] 表示选出的所有数都是 i 的倍数,最多选几个。
只从质数倍转移,就不会有重复。
也可以想象成,每个数向它的质数倍的数连边,求最大团。
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 #include <bits/stdc++.h> #define debug(x) cout << #x << ":\t" << (x) << endl; using namespace std;#define ll long long const int N = 2e6 + 10 ;const int INF = 0x3f3f3f3f ;const ll inf = 0x3f3f3f3f3f3f3f3f ;const ll mod = 998244353 ;int dp[10000010 ];int a[N], mx, c[10000010 ];int n;int prime[10000010 ], vis[10000010 ], cnt;void sieve (int n) { for (int i = 2 ; i <= n; i++) { if (!vis[i])prime[cnt++] = i; ll d; for (int j = 0 ; j < cnt && (d = 1ll * prime[j] * i) <= n; j++) { vis[d] = 1 ; if (i%prime[j] == 0 )break ; } } } int main () { scanf ("%d" , &n); for (int i = 1 ; i <= n; i++)scanf ("%d" , &a[i]), c[a[i]]++, mx = max (mx, a[i]); sieve (mx); for (int i = mx; i >= 1 ; i--) { for (int j = 0 ; j < cnt && 1ll * prime[j] * i <= mx; j++) { dp[i] = max (dp[i], dp[i*prime[j]]); } dp[i] += c[i]; } int ans = 0 ; for (int i = 1 ; i <= mx; i++)ans = max (ans, dp[i]); printf ("%d\n" , ans); return 0 ; }
D - Router Mesh
题意:给定一张无向图,问对于每个点,删掉它之后图上的联通块个数。
点双联通分量
一个割点所在的点双联通分量的个数就是删掉它之后它所在的联通块会分裂成新的联通块的个数。
所以只要先求出原图联通块个数,再Tarjan求点双即可。
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 #include <bits/stdc++.h> #define debug(x) cout << #x << ":\t" << (x) << endl; using namespace std;#define ll long long const int N = 2e6 + 10 ;const int INF = 0x3f3f3f3f ;const ll inf = 0x3f3f3f3f3f3f3f3f ;const ll mod = 998244353 ;vector<int >G[N]; struct edge { int u, v; }; int pre[N], iscut[N], bccno[N], dfs_clock, bcc_cnt;vector<int >bcc[N]; stack<edge>S; int dfs (int u, int fa) { int lowu = pre[u] = ++dfs_clock; int child = 0 ; for (int i = 0 ; i < (int )G[u].size (); i++) { int v = G[u][i]; edge e = edge{ u,v }; if (!pre[v]) { S.push (e); child++; int lowv = dfs (v, u); lowu = min (lowu, lowv); if (lowv >= pre[u]) { iscut[u] = true ; bcc_cnt++; bcc[bcc_cnt].clear (); for (;;) { edge x = S.top (); S.pop (); if (bccno[x.u] != bcc_cnt) { bcc[bcc_cnt].push_back (x.u); bccno[x.u] = bcc_cnt; } if (bccno[x.v] != bcc_cnt) { bcc[bcc_cnt].push_back (x.v); bccno[x.v] = bcc_cnt; } if (x.u == u && x.v == v)break ; } } } else if (pre[v] < pre[u] && v != fa) { S.push (e); lowu = min (lowu, pre[v]); } } if (fa < 0 && child == 1 )iscut[u] = 0 ; return lowu; } void find_bcc (int n) { memset (pre, 0 , sizeof (pre)); memset (iscut, 0 , sizeof (iscut)); memset (bccno, 0 , sizeof (bccno)); dfs_clock = bcc_cnt = 0 ; for (int i = 1 ; i <= n; i++) { if (!pre[i])dfs (i, -1 ); } } int n, m;int cnt[N], c;int par[N];int find (int x) { return par[x] == x ? x : par[x] = find (par[x]); }void uni (int x, int y) { par[find (x)] = find (y); }int main () { scanf ("%d%d" , &n, &m); for (int i = 1 ; i <= n; i++)par[i] = i; for (int i = 1 ; i <= m; i++) { int u, v; scanf ("%d%d" , &u, &v); G[u].push_back (v); G[v].push_back (u); uni (u, v); } find_bcc (n); for (int i = 1 ; i <= bcc_cnt; i++) { for (int u : bcc[i])cnt[u]++; } for (int i = 1 ; i <= n; i++)if (par[i] == i)c++; for (int i = 1 ; i <= n; i++) { printf ("%d%c" , c + cnt[i] - 1 , " \n" [i == n]); } return 0 ; }
F - Design Problemset
题意:共有 n 种题目,每种有 a i a_i a i 个,要凑出几个题目集,每个题目集的题数必须在 [ L , R ] [L,R] [ L , R ] ,每个题目集包含的每种题目的题数必须在 [ l i , r i ] [l_i,r_i] [ l i , r i ] 。问最多凑出几个题目集。
二分
首先,如果 ∑ l [ i ] > L \sum l[i]>L ∑ l [ i ] > L 或 ∑ r [ i ] < R \sum r[i]<R ∑ r [ i ] < R 则一个都凑不出。
二分答案。
有 m 个题目集,则首先每种题目必须满足 a [ i ] / m ≥ l [ i ] a[i]/m\ge l[i] a [ i ] / m ≥ l [ i ] 。
某个题目集多出来的题目可以通过某种题目加加减减,达到调节的作用,所以实际上,只要总的个数是足够的,就一定可以通过内部调节,使得每个题目集都足够。
先平均分配,再看每种题目还剩余多少,以及上限还剩多少,两者的min就是还能放进来的题目数量。
会爆ll,要__int128
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 #include <bits/stdc++.h> #define debug(x) cout << #x << ":\t" << (x) << endl; using namespace std;#define ll long long const int N = 2e6 + 10 ;const int INF = 0x3f3f3f3f ;const ll inf = 0x3f3f3f3f3f3f3f3f ;const ll mod = 998244353 ;inline __int128 read () { __int128 x = 0 , f = 1 ; char ch = getchar (); while (ch<'0' || ch>'9' ) { if (ch == '-' ) f = -1 ; ch = getchar (); } while (ch >= '0' &&ch <= '9' ) { x = x * 10 + ch - '0' ; ch = getchar (); } return x * f; } inline void write (__int128 x) { if (x < 0 ) { putchar ('-' ); x = -x; } if (x > 9 ) write (x / 10 ); putchar (x % 10 + '0' ); } int n;__int128 u, d; __int128 a[N]; __int128 l[N], r[N]; __int128 b[N], rs[N]; bool ck (__int128 m) { __int128 sum = 0 ; for (int i = 1 ; i <= n; i++) { if (a[i] < l[i] * m)return false ; b[i] = min (r[i], a[i] / m); sum += b[i]; rs[i] = a[i] - b[i] * m; } sum *= m; for (int i = 1 ; i <= n; i++) { sum += min ((r[i] - b[i])*m, rs[i]); } return sum >= d * m; } __int128 sl, sr; int main () { scanf ("%d" , &n); d = read (); u = read (); __int128 L = 0 , R = 0 ; for (int i = 1 ; i <= n; i++)a[i] = read (), R += a[i]; for (int i = 1 ; i <= n; i++)l[i] = read (), r[i] = read (), sl += l[i], sr += r[i]; if (sl > u || sr < d) { puts ("0" ); return 0 ; } while (L < R) { __int128 mid = (L + R + 1 ) / 2 ; if (ck (mid))L = mid; else R = mid - 1 ; } write (L); puts ("" ); return 0 ; }
E - Phone Network
题意:给定 n 个数,每个数在 1 到 n 之间,对于每个 i i i ,问最短的区间,包含 [ 1 , i ] [1,i] [ 1 , i ] 。
线段树
假设已经得到了 i-1 的答案,现在要求 i 。
i 作为分割点,把这个数列分成几块,对于一个包含了 [ 1 , i − 1 ] [1,i-1] [ 1 , i − 1 ] 的区间,如果它的左端点和右端点不在同一块,那么就说明这个区间包含 i i i ,则他也就包含 [ 1 , i ] [1,i] [ 1 , i ] 。
而对于那些不包含 i i i 的区间,需要找到它的左端点所在的块,把右端点扩展到分割点处。
这样所有区间都包含 [ 1 , i ] [1,i] [ 1 , i ] 了。
对于每个点,维护它作为左端点的,最短的包含 [ 1 , i ] [1,i] [ 1 , i ] 的区间。
在每一块中,不包含 i i i 的区间的左端点必定是连续的一段,线段树维护每个区间的右端点的最大值,就可以二分出来。这些区间需要扩展。
再来一个线段树维护每个区间的长度的最小值。区间右端点扩展时需要更新。
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 #include <bits/stdc++.h> #define debug(x) cout << #x << ":\t" << (x) << endl; using namespace std;#define ll long long const int N = 2e6 + 10 ;const int INF = 0x3f3f3f3f ;const ll inf = 0x3f3f3f3f3f3f3f3f ;const ll mod = 998244353 ;int n, m;int a[N], rr[N];vector<int >vc[N]; #define mid ((l+r)>>1) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 int mx[N << 2 ], laz1[N << 2 ];void up1 (int rt) { mx[rt] = max (mx[rt << 1 ], mx[rt << 1 | 1 ]); } void down1 (int rt) { int & x = laz1[rt]; if (x) { mx[rt << 1 ] = x; laz1[rt << 1 ] = x; mx[rt << 1 | 1 ] = x; laz1[rt << 1 | 1 ] = x; x = 0 ; } } void build1 (int l, int r, int rt) { if (l == r) { mx[rt] = rr[l]; return ; } build1 (lson); build1 (rson); up1 (rt); } int qry1 (int ql, int qr, int l, int r, int rt) { if (ql <= l && qr >= r)return mx[rt]; down1 (rt); int ans = 0 ; if (ql <= mid)ans = max (ans, qry1 (ql, qr, lson)); if (qr > mid)ans = max (ans, qry1 (ql, qr, rson)); return ans; } void upd1 (int ql, int qr, int x, int l, int r, int rt) { if (ql <= l && qr >= r) { laz1[rt] = max (laz1[rt], x); mx[rt] = max (mx[rt], x); return ; } down1 (rt); if (ql <= mid)upd1 (ql, qr, x, lson); if (qr > mid)upd1 (ql, qr, x, rson); up1 (rt); } int tr[N << 2 ], laz2[N << 2 ];void up2 (int rt) { tr[rt] = min (tr[rt << 1 ], tr[rt << 1 | 1 ]); } void down2 (int rt, int l, int r) { int & x = laz2[rt]; if (x) { tr[rt << 1 ] = x - mid + 1 ; tr[rt << 1 | 1 ] = x - r + 1 ; laz2[rt << 1 ] = x; laz2[rt << 1 | 1 ] = x; x = 0 ; } } void build2 (int l, int r, int rt) { if (l == r) { tr[rt] = rr[l] - l + 1 ; return ; } build2 (lson); build2 (rson); up2 (rt); } void upd2 (int ql, int qr, int x, int l, int r, int rt) { if (ql <= l && qr >= r) { tr[rt] = x - r + 1 ; laz2[rt] = x; return ; } down2 (rt, l, r); if (ql <= mid)upd2 (ql, qr, x, lson); if (qr > mid)upd2 (ql, qr, x, rson); up2 (rt); } int main () { scanf ("%d%d" , &n, &m); for (int i = 1 ; i <= m; i++)vc[i].push_back (0 ); for (int i = 1 ; i <= n; i++) { scanf ("%d" , &a[i]); vc[a[i]].push_back (i); } for (int i = 1 ; i <= n; i++) { rr[i] = i; } build1 (1 , n, 1 ); build2 (1 , n, 1 ); for (int i = 1 ; i <= m; i++) { int p = (int )vc[i].size (); for (int j = 0 ; j < p - 1 ; j++) { int L = vc[i][j] + 1 , R = vc[i][j + 1 ]; int k = 0 ; while (L <= R) { int mi = (L + R) / 2 ; if (qry1 (vc[i][j] + 1 , mi, 1 , n, 1 ) < vc[i][j + 1 ]) { k = mi; L = mi + 1 ; } else R = mi - 1 ; } if (!k)continue ; upd1 (vc[i][j] + 1 , k, vc[i][j + 1 ], 1 , n, 1 ); upd2 (vc[i][j] + 1 , k, vc[i][j + 1 ], 1 , n, 1 ); } if (vc[i].back () < n) { upd1 (vc[i].back () + 1 , n, INF, 1 , n, 1 ); upd2 (vc[i].back () + 1 , n, INF, 1 , n, 1 ); } printf ("%d%c" , tr[1 ], " \n" [i == m]); } return 0 ; }
G - Tree Projection
题意:有一棵树,A 数组是以 A 1 A_1 A 1 为根时的拓扑序,B 数组以 B 1 B_1 B 1 为根时的 dfs 序,要构造出这棵树。
构造
遍历dfs序,每次把新点连到前面的拓扑序最小的点上。
这样就保证了每个点一定都连在它的祖先上,则dfs序一定符合条件。拓扑序也显然符合条件。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <bits/stdc++.h> #define debug(x) cout << #x << ":\t" << (x) << endl; using namespace std;#define ll long long const int N = 2e6 + 10 ;const int INF = 0x3f3f3f3f ;const ll inf = 0x3f3f3f3f3f3f3f3f ;const ll mod = 998244353 ;int n;int df[N], tp[N], pos[N];int main () { scanf ("%d" , &n); for (int i = 1 ; i <= n; i++)scanf ("%d" , &tp[i]), pos[tp[i]] = i; for (int i = 1 ; i <= n; i++)scanf ("%d" , &df[i]); puts ("YES" ); int mn = INF, id = 0 ; for (int i = 1 ; i <= n; i++) { if (i != 1 )printf ("%d %d\n" , df[i], df[id]); if (mn > pos[df[i]]) { mn = pos[df[i]]; id = i; } } return 0 ; }
K - Sqrt Approaching
题意:给定 A , B , n A,B,n A , B , n ,求一组 C , D C,D C , D 满足 ( B C − A D ) ( C − D n ) < 0 (BC - AD)(C - D\sqrt{n}) < 0 ( BC − A D ) ( C − D n ) < 0 ,( 1 ≤ A ≤ 1 0 99990 , 1 ≤ B ≤ 1 0 99990 , 2 ≤ n ≤ 1 0 9 , 1 ≤ C < 1 0 1 0 5 , 1 ≤ D < 1 0 1 0 5 ) (1\le A\le 10^{99990},1\le B\le 10^{99990},2\le n\le 10^9,1\le C<10^{10^5},1\le D<10^{10^5}) ( 1 ≤ A ≤ 1 0 99990 , 1 ≤ B ≤ 1 0 99990 , 2 ≤ n ≤ 1 0 9 , 1 ≤ C < 1 0 1 0 5 , 1 ≤ D < 1 0 1 0 5 ) 。
式子变成 A B < C D < n \frac{A}{B}<\frac{C}{D}<\sqrt{n} B A < D C < n 或 n < C D < A B \sqrt{n}<\frac{C}{D}<\frac{A}{B} n < D C < B A
也就是找到一个在 A B \frac{A}{B} B A 和 n \sqrt{n} n 之间的分数。
a n + 1 = a n + n a n a_{n +1} = a_{n} + \frac{n}{a_{n}} a n + 1 = a n + a n n
上面这个数列收敛于 n \sqrt{n} n ,代入 A B \frac{A}{B} B A 得到 A + n B A + B \frac{A + nB}{A + B} A + B A + n B ,再迭代一次,得到答案。
1 2 3 4 5 6 7 a = int (input ()) b = int (input ()) n = int (input ()) a, b = a + n * b, a + b a, b = a + n * b, a + b print (a)print (b)