random mushup
现场时比较乱,尤其是第一题,理不清思路,补题时好很多,学到三分查找,数论,延迟标记等。
三分查找
数论,模运算
DP求连续子数组元素和最大值
埃氏筛
线段树,延迟标记,区间更新
二维直线
双指针
A. New Year and Rating
根据每一次比赛前的等第列出不等式,若最终不等式右端无穷大,则Infinity,若右小于左,则Impossible,否则确定原值为右端最大值,知道原值后加上所有得分即为最终值。
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 <iostream> #include <algorithm> using namespace std;const int INF = 0x3f3f3f3f ;int main () { int n; cin >> n; int high_div2 = -INF; int low_div1 = INF; int so_far = 0 ; for (int i = 0 ; i < n; ++i) { int change, division; cin >> change >> division; if (division == 2 ) high_div2 = max (high_div2, so_far); else low_div1 = min (low_div1, so_far); so_far += change; } if (high_div2 == -INF) cout << "Infinity" << endl; else if (high_div2 >= low_div1) cout << "Impossible" << endl; else cout << 1899 - high_div2 + so_far << endl; return 0 ; }
C. Elections
知道要得几票,如何确定最小消耗钱数?
从每个候选人中扣除,直至他们的票数都小于该值,从所有选票中取,直至我的票数等于该值。
如何知道得几票?
三分查找。
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 #include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std;#define ll long long typedef pair<ll, int > pii;int n, m;vector<pii>vc,G[3050 ]; ll cost (int k) { ll res = 0 ; int get = G[1 ].size (); vc.clear (); for (int i = 2 ; i <= m; i++) { for (int j = 0 ; j < G[i].size (); j++) { if (G[i].size () - j >= k) { res += G[i][j].first; get++; } else vc.push_back (G[i][j]); } } sort (vc.begin (), vc.end ()); for (int i = 0 ; i < k - get; i++) { res += vc[i].first; } return res; } int main () { cin.sync_with_stdio (false ); cin >> n >> m; for (int i = 1 ; i <= n; i++) { ll p, mon; cin >> p >> mon; if (p != 1 )vc.push_back (pii (mon, i)); G[p].push_back (pii (mon, i)); } sort (vc.begin (), vc.end ()); for (int i = 1 ; i <= m; i++) { sort (G[i].begin (), G[i].end ()); } int st = G[1 ].size (); int ed = n; while (ed-st>2 ) { int p1 = ((st + ed) >> 1 ); int p2 = ((p1 + ed) >> 1 ); if (cost (p1) < cost (p2))ed = p2; else st = p1; } ll ans = cost (st); for (int i = st+1 ; i <= ed; i++) { ans = min (ans, cost (i)); } cout << ans; return 0 ; }
D. Neko does Maths
已知a,b,求a+k,b+k的最小公倍数的最小值。
即求( a + k ) ( b + k ) g c d ( a + k , b + k ) (a+k)(b+k)gcd(a+k,b+k) ( a + k ) ( b + k ) g c d ( a + k , b + k ) ,我们知道g c d ( m , n ) = g c d ( m − n , n ) gcd(m,n)=gcd(m-n,n) g c d ( m , n ) = g c d ( m − n , n ) ,故g c d ( a + k , b + k ) = g c d ( a − b , b + k ) gcd(a+k,b+k)=gcd(a-b,b+k) g c d ( a + k , b + k ) = g c d ( a − b , b + k ) ,gcd(a-b,b+k)必然是(a-b)的因数,而(a-b)已知,因此枚举其因数为 i ,假设其为(a-b)与(b+k)的gcd,则i也是(b+k)的因数,b原本不是i的倍数,加上k后为倍数。由于已知a+i-a%i为i的倍数 ,则且(a-b)为 i 的倍数 ,则((a-b)-(a+i-a%i))为i的倍数,即(b+i-a%i)为i的倍数,得到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 #include <iostream> #include <cmath> using namespace std;#define ll long long ll gcd (ll a, ll b) { if (a == 0 ) return b; return gcd (b%a, a); } ll a, b; int main () { cin >> a >> b; if (a == b) { cout << 0 ; return 0 ; } if (a > b)swap (a, b); ll gp = b - a; ll ans = 0 ; ll mina = a * b / gcd (a, b); for (ll i = 1 ; i <= sqrt (gp) + 1 ; i++) { if (gp%i == 0 ) { ll k = i - b % i; ll nw = (a + k)*(b + k) / gcd (a + k, b + k); if (nw < mina) { mina = nw; ans = k; } k = gp / i - b % (gp / i); nw = (a + k)*(b + k) / gcd (a + k, b + k); if (nw < mina) { mina = nw; ans = k; } } } cout << ans; return 0 ; }
E. Weakness and Poorness
DP求子数组元素和绝对值的最大值
三分查找使最大值最小的x
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 #include <iostream> #include <cmath> #include <algorithm> #include <cstring> using namespace std;const int maxn = 2e5 + 5 ;#define ll long long double a[maxn];int n;double mx, mn;double calc (double k) { double res1 = 0 ; double res2 = 0 ; double sum1 = 0 , sum2 = 0 ; for (int i = 1 ; i <= n; i++) { sum1 = max (sum1 + a[i]+k, a[i]+k); res1 = max (sum1, res1); sum2 = min (sum2 + a[i]+k, a[i]+k); res2 = min (sum2, res2); } return max (fabs (res1), fabs (res2)); } int main () { cin.sync_with_stdio (false ); cin >> n; for (int i = 1 ; i <= n; i++) { double p; cin >> p; a[i] = p; if (p >= 0 )mx = max (p, mx); else mn = min (mn, p); } int dt = 100 ; double st = 0 - mx, ed = 0 - mn; while (dt--) { double p1 = st+(ed-st)/3 ; double p2 = st+(ed-st)*2 /3 ; double c1 = calc (p1), c2 = calc (p2); if (c1 > c2) { st = p1; } else ed = p2; } double ans = min (calc (st), calc (ed)); printf ("%.10f" , ans); return 0 ; }
F. Prefix Sum Primes
先打印出素数表(埃氏),再用二和一凑出表中数,先尽量用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 49 50 51 52 53 54 55 56 57 #include <iostream> #include <algorithm> #include <map> using namespace std;const int maxn = 2e5 + 5 ;int n, ans;map<int , int >mp; bool is_prime[2 *maxn];int prime[2 *maxn];void sieve (int n) { int p = 0 ; for (int i = 0 ; i < n; i++) is_prime[i] = 1 ; is_prime[0 ] = is_prime[1 ] = 0 ; for (int i = 2 ; i <= n; i++) { if (is_prime[i]) { prime[p++] = i; for (int j = 2 * i; j <= n; j += i)is_prime[j] = 0 ; } } } int main () { std::ios::sync_with_stdio (false ); cin >> n; for (int i = 0 ; i < n; i++) { int a; cin >> a; mp[a]++; } int now = 0 ; int t = 0 ; sieve (2 * (n+5 )); int k=0 ; while (mp[1 ] > 0 && mp[2 ] > 0 ) { int to = prime[t] - now; int num_2 = min (mp[2 ], to / 2 ); mp[2 ] -= num_2; to -= (2 * num_2); for (int i = 0 ; i < num_2; i++) cout << 2 << ' ' ; int num_1 = min (mp[1 ], to); mp[1 ] -= num_1; to -= num_1; for (int i = 0 ; i < num_1; i++) cout << 1 << ' ' ; now = prime[t]; t++; } if (mp[1 ] > 0 ) { for (int i = 0 ; i < mp[1 ];i++) cout << 1 << ' ' ; } else if (mp[2 ] > 0 ) { for (int i = 0 ; i < mp[2 ];i++) cout << 2 << ' ' ; } return 0 ; }
G. Painting the Fence
线段树+延迟标记,叶节点记录实际颜色,其他节点记录被涂的颜色,即懒标记。
查询和更新时,向下推颜色。
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 #include <iostream> #include <algorithm> #include <queue> using namespace std;#define lson 2*id #define rson 2*id+1 const int maxn = 3e5 + 5 ;int n, m;int a[maxn];deque<int >q[maxn]; struct P { int color; int l, r; }tr[maxn*4 ]; void down (int id) { int & x = tr[id].color; if (x != 0 ) { tr[lson].color = x; tr[rson].color = x; x = 0 ; } } void update (int id,int st,int ed,int x) { if (st <= tr[id].l&&ed>=tr[id].r) { tr[id].color = x; return ; } down (id); int mid = (tr[id].l + tr[id].r) >> 1 ; if (ed <= mid) update (lson, st, ed, x); else if (st > mid) update (rson, st, ed, x); else { update (lson, st, mid, x); update (rson, mid+1 , ed, x); } } void build (int l, int r, int id) { tr[id].color = 0 ; tr[id].l = l; tr[id].r = r; if (l == r) { tr[id].color = a[l]; return ; } int mid = (l + r) >> 1 ; build (l,mid,lson); build (mid+1 ,r,rson); } int query (int id,int que) { if (tr[id].l == tr[id].r) return tr[id].color; down (id); int mid = (tr[id].l + tr[id].r) >> 1 ; if (que <= mid)return query (lson, que); else return query (rson, que); } int main () { cin.sync_with_stdio (false ); cin >> n; for (int i = 1 ; i <= n; i++) { cin >> a[i]; q[a[i]].push_back (i); } build (1 , n, 1 ); cin >> m; for (int i = 0 ; i < m; i++) { int x; cin >> x; if (q[x].size () <= 1 ) continue ; int st = q[x].front (), ed = q[x].back (); while (query (1 , st) != x&&!q[x].empty ()) { q[x].pop_front (); if (!q[x].empty ()) st = q[x].front (); } while (query (1 , ed) != x&&!q[x].empty ()) { q[x].pop_back (); if (!q[x].empty ()) ed = q[x].back (); } if (q[x].size () > 1 ) { update (1 , st, ed, x); } } for (int i = 1 ; i <= n; i++) { cout << query (1 , i) <<' ' ; } return 0 ; }
I. Barcelonian Distance
有五种方式从A到B
只沿着格子走。
沿着格子走到A上方线上点,沿线走到B上方点,沿格子走到B
右到上
右到右
上到右
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <iostream> #include <cmath> #include <algorithm> using namespace std;int main () { double a, b, c, x1, y1, x2, y2; double xa[5 ], ya[5 ], xb[5 ], yb[5 ]; double ans; int i, j, k; cin >> a >> b >> c; cin >> x1 >> y1 >> x2 >> y2; ans = fabs (x1 - x2) + fabs (y1 - y2); xa[1 ] = x1; ya[1 ] = -(a*xa[1 ] + c) / b; ya[2 ] = y1; xa[2 ] = -(b*ya[2 ] + c) / a; xb[2 ] = x2; yb[2 ] = -(a*xb[2 ] + c) / b; yb[1 ] = y2; xb[1 ] = -(b*yb[1 ] + c) / a; ans = min (ans, fabs (y1 - ya[1 ]) + fabs (y2 - yb[2 ]) + hypot (fabs (xa[1 ] - xb[2 ]), fabs (ya[1 ] - yb[2 ]))); ans = min (ans, fabs (y1 - ya[1 ]) + fabs (x2 - xb[1 ]) + hypot (fabs (xa[1 ] - xb[1 ]), fabs (ya[1 ] - yb[1 ]))); ans = min (ans, fabs (x1 - xa[2 ]) + fabs (y2 - yb[2 ]) + hypot (fabs (xa[2 ] - xb[2 ]), fabs (ya[2 ] - yb[2 ]))); ans = min (ans, fabs (x1 - xa[2 ]) + fabs (x2 - xb[1 ]) + hypot (fabs (xa[2 ] - xb[1 ]), fabs (ya[2 ] - yb[1 ]))); printf ("%.10lf\n" , ans); return 0 ; }
K. Santa Claus and Robot
双指针,记录开头和结尾,若下一步与中间相矛盾,则答案+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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 #include <iostream> #include <map> #include <vector> #include <string> using namespace std;const int maxn = 2e5 + 5 ;int n;map<char , int >mp; int st, ed;int ans;int main () { std::ios::sync_with_stdio (false ); cin >> n; string s; cin >> s; int len = n; while (ed < len) { char now = s[ed]; if (now == 'L' ) { if (mp['L' ] < 0 ) { st = ed; mp['U' ] = 0 ; mp['L' ] = 1 ; ans++; } else mp['L' ]++; } else if (now == 'R' ) { if (mp['L' ] > 0 ) { st = ed; mp['U' ] = 0 ; mp['L' ] = -1 ; ans++; } else mp['L' ]--; } else if (now == 'U' ) { if (mp['U' ]<0 ) { st = ed; mp['U' ] = 1 ; mp['L' ] = 0 ; ans++; } else mp['U' ]++; } else { if (mp['U' ] > 0 ) { st = ed; mp['U' ] = -1 ; mp['L' ] = 0 ; ans++; } else mp['U' ]--; } ed++; } ans++; cout << ans << endl; return 0 ; }