C. Evolution Game
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 #include <bits/stdc++.h> using namespace std; typedef pair<int , int > Pair; const int maxn = 5e3 +5 ;Pair p[maxn]; int a[maxn], ans[maxn], n, w, mark; int main () { cin >> n >> w; for (int i = 0 ; i < n; ++i) { cin >> a[i]; p[i].first = a[i]; p[i].second = i; } sort (p, p + n); for (int i = n - 1 ; i >= 0 ; --i) { for (int j = max (p[i].second - w, 0 ); j <= min (p[i].second + w, n - 1 ); ++j) if (a[j] > a[p[i].second]) ans[p[i].second] = max (ans[p[i].second], ans[j] + 1 ); } for (int i = 0 ; i < n; ++i) mark = max (mark, ans[i]); cout << mark << endl; return 0 ; }
D. Bus Stop
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 #include <bits/stdc++.h> using namespace std; int T, n, data[2000010 ], ans;int main () { ios::sync_with_stdio (false ); cin.tie (0 ); cin >> T; while (T--) { ans = 0 ; cin >> n; if (!n) { cout << 0 << endl; continue ; } for (int i=0 ;i<n;i++) cin >> data[i]; int l = 0 , r = 0 ; while (r < n) { if (data[r] - data[l] <= 20 ) r++; else { ans++; l = r; } } ans++; cout << ans << endl; } return 0 ; }
E. How Many Groups
题意:定义一个运算符 ‘~’ ,若 ∣ x − y ∣ ≤ 2 |x-y|\leq 2 ∣ x − y ∣ ≤ 2 则x x x ~ y y y 。现给出一组数字,将它们从小到大排列,若满足相邻两个数字 ∣ x − y ∣ ≤ 2 |x-y|\leq 2 ∣ x − y ∣ ≤ 2 ,则可归为一组。最多可以修改2次,每次可任选1个元素+1或-1,每个元素最多被选中一次,求元素最多的那一组中的元素个数。
简单dp
设dp[i] [j] [k]表示到第 i 个数,且前一个数的值为 j,目前一共修改了 k 次,的最大元素个数。
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 #include <bits/stdc++.h> using namespace std;#define ll long long const int INF = 0x3f3f3f3f ;const int maxn = 1e6 + 10 ;const int N = 1e6 ;int T, n;int a[maxn], dp[110 ][210 ][5 ];inline int read () { char ch = getchar (); int x = 0 , f = 1 ; while (ch < '0' || ch > '9' ) { if (ch == '-' ) f = -1 ; ch = getchar (); } while ('0' <= ch && ch <= '9' ) { x = x * 10 + ch - '0' ; ch = getchar (); } return x * f; } int main () { T = read (); for (int tt = 1 ; tt <= T; tt++) { n = read (); for (int i = 1 ; i <= n; i++)a[i] = read (); sort (a + 1 , a + n + 1 ); memset (dp, 0 , sizeof (dp)); dp[1 ][a[1 ]][0 ] = dp[1 ][a[1 ] - 1 ][1 ] = dp[1 ][a[1 ] + 1 ][1 ] = 1 ; for (int i = 2 ; i <= n; i++) { for (int k = 0 ; k <= 2 ; k++) { dp[i][a[i]][k] = max (dp[i][a[i]][k], max (dp[i-1 ][a[i]][k],max (dp[i - 1 ][a[i] - 2 ][k], dp[i - 1 ][a[i] - 1 ][k])) + 1 ); dp[i][a[i]][k] = max (dp[i][a[i]][k], max (dp[i - 1 ][a[i] + 1 ][k], dp[i - 1 ][a[i] + 2 ][k]) + 1 ); dp[i][a[i] - 1 ][k + 1 ] = max (dp[i][a[i] - 1 ][k + 1 ], max (dp[i-1 ][a[i]-1 ][k],max (dp[i - 1 ][a[i] - 2 ][k], dp[i - 1 ][a[i] - 3 ][k])) + 1 ); dp[i][a[i] - 1 ][k + 1 ] = max (dp[i][a[i] - 1 ][k + 1 ], max (dp[i - 1 ][a[i]][k], dp[i - 1 ][a[i] + 1 ][k]) + 1 ); dp[i][a[i] + 1 ][k + 1 ] = max (dp[i][a[i] + 1 ][k + 1 ], max (dp[i-1 ][a[i]+1 ][k],max (dp[i - 1 ][a[i]][k], dp[i - 1 ][a[i] - 1 ][k])) + 1 ); dp[i][a[i] + 1 ][k + 1 ] = max (dp[i][a[i] + 1 ][k + 1 ], max (dp[i - 1 ][a[i] + 2 ][k], dp[i - 1 ][a[i] + 3 ][k]) + 1 ); } } int ans = 0 ; for (int i = 1 ; i <= n; i++) { for (int j = a[i] - 1 ; j <= a[i] + 1 ; j++) for (int k = 0 ; k <= 2 ; k++)ans = max (ans, dp[i][j][k]); } printf ("Case %d: %d\n" , tt, ans); } return 0 ; }
F. Lucky Pascal Triangle
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 #include <bits/stdc++.h> using namespace std;typedef long long LL;const int tot = 22 ;const LL mod = 1e9 +7 , inv = 500000004 ;LL p[50 ], a[50 ], b[50 ], s[10 ], mark, q; int T;LL f (LL n) { if (n <= 7 ) return 0 ; int i = upper_bound (p, p + tot, n) - p - 1 ; if (n == p[i]) return a[i]; LL t1 = n % p[i], t2 = 2 * (p[i] % mod) - (n % p[i]) % mod + mod - 1 ; LL t3 = (((t1 % mod) * (t2 % mod)) % mod * inv) % mod; LL t4 = s[n / p[i]] * a[i] + s[max (n / p[i] - 1 , 0ll )] * b[i] + (n / p[i] + 1 ) * f (n % p[i]); return ((t4 % mod + n / p[i] * t3) % mod ) % mod; } int main () { p[0 ] = 1 ; for (int i = 1 ; i <= 7 ; ++i) s[i] = s[i - 1 ] + i; for (int i = 1 ; i < tot; ++i) p[i] = p[i - 1 ] * 7 ; for (int i = 1 ; i < tot; ++i) b[i] = (((p[i] % mod) * ((p[i] - 1 ) % mod)) % mod * inv) % mod; for (int i = 1 ; i < tot; ++i) a[i] = ((s[7 ] * a[i - 1 ]) % mod + (s[6 ] * b[i - 1 ]) % mod) % mod; cin >> T; for (int kase = 1 ; kase <= T; ++kase) { cin >> q; printf ("Case %d: " , kase); cout << f (q + 1 ) << endl; } return 0 ; }
G. Communication
找强连通分量的个数。
由于数据很小,并且当时不会Tarjan,就用了并查集+判环。
但是正解还是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 #include <bits/stdc++.h> using namespace std;#define ll long long typedef pair<int , int > pii;const int INF = 0x3f3f3f3f ;const int maxn = 300 ;int vis[300 ];int cnt[300 ][300 ];int T, n, m;int par[maxn], rk[maxn];void init (int n) { for (int i = 0 ; i < n; i++) { par[i] = i; rk[i] = 0 ; } } int find (int x) { if (par[x] == x)return x; else return par[x] = find (par[x]); } void unite (int x, int y) { x = find (x); y = find (y); if (x == y)return ; if (rk[x] < rk[y])par[x] = y; else { par[y] = x; if (rk[x] == rk[y])rk[x]++; } } bool same (int x, int y) { return find (x) == find (y); } vector<int >G[maxn]; void dfs (int t, int u) { vis[u] = 1 ; cnt[t][u] = 1 ; for (int i = 0 ; i < G[u].size (); i++) { int v = G[u][i]; if (vis[v])continue ; dfs (t, v); } } int main () { scanf ("%d" , &T); while (T--) { memset (cnt, 0 , sizeof (cnt)); scanf ("%d%d" , &n, &m); for (int i = 0 ; i < n; i++)G[i].clear (); init (n); for (int i = 0 ; i < m; i++) { int u, v; scanf ("%d%d" , &u, &v); G[u].push_back (v); } for (int i = 0 ; i < n; i++) { memset (vis, 0 , sizeof (vis)); dfs (i,i); } for (int i = 0 ; i < n; i++) { for (int j = 0 ; j < n; j++) { if (i == j)continue ; if (cnt[i][j] && cnt[j][i])unite (i, j); } } int ans = 0 ; for (int i = 0 ; i < n; i++) { if (par[i] == i)ans++; } printf ("%d\n" , ans); } return 0 ; }
H. As Rich as Crassus
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 #include <bits/stdc++.h> using namespace std; typedef long long ll; int T;ll ans, m[10 ], r[10 ]; const ll n = 3 ; ll ex_gcd (ll a, ll b, ll &x, ll &y) { if (!b) { x = 1 ;y = 0 ; return a; } ll ret = ex_gcd (b, a%b, y, x); y -= a/b * x; return ret; } ll CRT (ll *m, ll*r, ll n) { if (!n) return 0 ; ll M = m[0 ], R = r[0 ], x, y, d; for (int i=1 ;i<n;i++) { d = ex_gcd (M, m[i], x, y); if ((r[i] - R) % d) return -1 ; x = (r[i] - R) / d * x % (m[i]/d); R += x * M; M = M / d * m[i]; R %= M; } return R >= 0 ? R : R + M; } int main () { ios::sync_with_stdio (false ); cin.tie (0 ); cin >> T; while (T--) { cin >> m[0 ] >> m[1 ] >> m[2 ]; cin >> r[0 ] >> r[1 ] >> r[2 ]; ans = CRT (m, r, n); ll res = pow ((double )ans, 1.0 /3.0 ); while (res * res * res < ans) res++; cout << res << endl; } return 0 ; }
J. Floating-Point Hazard
微积分,近似计算。
设
f ( x ) = x 3 f(x)=\sqrt[3]{x}
f ( x ) = 3 x
则
f ( x + Δ x ) − f ( x ) Δ x = f ′ ( x ) \frac{f(x+\Delta x)-f(x)}{\Delta x}=f'(x)
Δ x f ( x + Δ x ) − f ( x ) = f ′ ( x )
f ( x + Δ x ) − f ( x ) = f ′ ( x ) ⋅ Δ x f(x+\Delta x)-f(x)=f'(x)\cdot \Delta x
f ( x + Δ x ) − f ( x ) = f ′ ( x ) ⋅ Δ x
其中
f ′ ( x ) = 1 3 x − 2 3 f'(x)=\frac{1}{3}x^{-\frac{2}{3}}
f ′ ( x ) = 3 1 x − 3 2
本题中 $$\Delta x=10^{-15}$$
注意 ∑ \sum ∑ 是整数求和,∫ a b f ( x ) d x \int_{a}^{b} f(x) {\rm d}x ∫ a b f ( x ) d x 是对 f ( x ) ⋅ d x f(x)\cdot dx f ( x ) ⋅ d x 的面积求和。本题要求的是前者。
1 2 3 4 5 6 7 8 9 10 11 12 13 #include <bits/stdc++.h> using namespace std;int low, high;int main () { while (cin >> low >> high) { if (!low) break ; double sum = 0 ; for (int i = low; i <= high; ++i) sum += pow (double (i), -2.0 /3.0 ); printf ("%.5E\n" , sum * 1e-15 / 3.0 ); } return 0 ; }
K. The Stream of Corning 2
题意:有两种操作:
在 t1 时刻插入一个数 v,这个数会在 t2 时刻消失。
查询 T 时刻第 K 大的数。
查询第 K 大的数,自然想到用权值线段树。
然而如果每次都遍历一遍找到那些仍然存在的数,则复杂度为 O ( n 2 ) O(n^2) O ( n 2 ) 。考虑用单调队列维护,以结束时间递增的方式存储所有数字,当进行查询操作时,从头开始若堆顶数字消失时间小于当前查询时间,则删除,直到堆顶数字消失时间大于等于当前查询时间。
由于每个数最多被删除一遍,而线段树删除操作为 log n \log n log n ,所以整体复杂度为 O ( n log n ) O(n\log n) O ( n log n ) 。
比赛时也不知道怎么想到划分树去了,但划分树的修改需要重建树,单次重建为 O ( n log n ) O(n\log n) O ( n log n ) ,也没有必要,因为划分树和主席树都用来查询区间第 K 大,用来查询全局第 K 大实在是没必要。
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 #include <bits/stdc++.h> using namespace std;#define ll long long #define mid ((l+r)>>1) #define lch (rt<<1),l,mid #define rch (rt<<1)|1,mid+1,r const int INF = 0x3f3f3f3f ;const int maxn = 1e6 + 10 ;const int N = 1e6 ;int T, n;int tr[maxn << 2 ];void pushup (int rt) { tr[rt] = tr[rt << 1 ] + tr[(rt << 1 ) | 1 ]; } void update (int x, int b, int rt, int l, int r) { if (l == r) { tr[rt] += b; return ; } if (x <= mid)update (x, b, lch); else update (x, b, rch); pushup (rt); } int query (int rt, int l, int r, int k) { if (l == r)return l; if (tr[rt<<1 ] >= k)return query (lch, k); else return query (rch, k - tr[rt<<1 ]); } struct X { int val, time; }; struct cmp { bool operator () (const X& a, const X&b) { return a.time > b.time; } }; int main () { scanf ("%d" , &T); for (int tt = 1 ; tt <= T; tt++) { memset (tr, 0 , sizeof (tr)); printf ("Case %d:\n" , tt); priority_queue<X, vector<X>, cmp>q; scanf ("%d" , &n); for (int i = 0 ; i < n; i++) { int op; scanf ("%d" , &op); if (op == 1 ) { int t1, v, t2; scanf ("%d%d%d" , &t1, &v, &t2); q.push (X{ v,t2 }); update (v, 1 , 1 , 1 , N); } else { int t, k; scanf ("%d%d" , &t, &k); while (!q.empty () && q.top ().time < t) { update (q.top ().val, -1 , 1 , 1 , N); q.pop (); } if (q.size () < k)printf ("-1\n" ); else printf ("%d\n" , query (1 , 1 , N, k)); } } } return 0 ; }
L. Largest Allowed Area
二维前缀和+二分
题意:给出一个01矩阵,要求划出一个正方形区域,使得正方形中有且仅有一个1。求满足条件的最大的正方形的边长。
二维前缀和,可以求出每一个区域包含的1的个数。
1 a[i][j] += a[i-1 ][j] + a[i][j-1 ] - a[i-1 ][j-1 ];
则以 ( x 1 , y 1 ) (x1,y1) ( x 1 , y 1 ) 为左上角,( x 2 , y 2 ) (x2,y2) ( x 2 , y 2 ) 为右下角的矩形区域包含1的个数为:
1 ans (x1, y1, x2, y2)=a[x2][y2] - a[x2][y1 - 1 ] - a[x1 - 1 ][y2] + a[x1 - 1 ][x2 - 1 ]
枚举正方形左上角,二分确定边长。
分三种情况:
若当前区域没有1,则需要扩大正方形,L=mid+1
当前区域有1个1,则需要扩大正方形,同时记录答案,L=mid+1, ans=max(ans,mid)
当前区域有多个1,则需要缩小正方形,R=mid-1
顺便记一下二分死循环的一些坑。
若要找到小于等于k的第一个数 ,则若m i d < = k mid<=k mi d <= k ,要L = m i d L=mid L = mi d ,反之R = m i d − 1 R=mid-1 R = mi d − 1 .但此时若L = m i d < = k , R = m i d + 1 L=mid<=k,R=mid+1 L = mi d <= k , R = mi d + 1 .则会使L=mid死循环,所以此时应改进mid取法。
mid = (L + R + 1) / 2
若要找到第一个大于等于k的数 ,则若m i d > = k mid>=k mi d >= k ,要R = m i d R=mid R = mi d ,反之L = m i d + 1 L=mid+1 L = mi d + 1 .此时若取m i d = ( L + R + 1 ) / 2 mid=(L+R+1)/2 mi d = ( L + R + 1 ) /2 反而会使R = m i d R=mid R = mi d 死循环 。所以此时应使mid变回去。
mid = (L + R) / 2
还有一个对内存的小优化:
mid = (L + R + 1) / 2 --> mid = L + (R - L + 1) / 2
mid=( L + R) / 2 --> mid = L + (R - L) / 2
可防止精度溢出。
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 #include <bits/stdc++.h> using namespace std;#define ll long long inline int read () { char ch = getchar (); int x = 0 , f = 1 ; while (ch < '0' || ch > '9' ) { if (ch == '-' ) f = -1 ; ch = getchar (); } while ('0' <= ch && ch <= '9' ) { x = x * 10 + ch - '0' ; ch = getchar (); } return x * f; } const int INF = 0x3f3f3f3f ;const int maxn = 1005 ;const int N = 1e6 ;int T, r, c;int mz[maxn][maxn];int check (int x, int y, int len) { return mz[x + len - 1 ][y + len - 1 ] - mz[x + len - 1 ][y-1 ] - mz[x-1 ][y + len - 1 ] + mz[x - 1 ][y - 1 ]; } int main () { T = read (); while (T--) { int ans = 0 ; r = read (); c = read (); for (int i = 1 ; i <= r; i++) { for (int j = 1 ; j <= c; j++)mz[i][j] = read (); } for (int i = 1 ; i <= r; i++) for (int j = 1 ; j <= c; j++) mz[i][j] += mz[i - 1 ][j] + mz[i][j - 1 ] - mz[i - 1 ][j - 1 ]; for (int i = 1 ; i <= r; i++) { for (int j = 1 ; j <= c; j++) { int L = 1 , R = min (r - i + 1 , c - j + 1 ); while (L <= R) { int mid = (L + R) >> 1 ; int cnt = check (i, j, mid); if (cnt == 1 )L = mid + 1 , ans = max (ans, mid); else if (cnt == 0 )L = mid + 1 ; else R = mid - 1 ; } } } printf ("%d\n" , ans); } return 0 ; }
本题还要加个快读,否则会T。