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. 如何知道得几票?

    三分查找。

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)gcd(a+k,b+k)(a+k)(b+k)gcd(a+k,b+k),我们知道gcd(m,n)=gcd(mn,n)gcd(m,n)=gcd(m-n,n),故gcd(a+k,b+k)=gcd(ab,b+k)gcd(a+k,b+k)=gcd(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);//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

 

  1. DP求子数组元素和绝对值的最大值
  2. 三分查找使最大值最小的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);
//cout << c1 << c2<<endl;
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

  1. 只沿着格子走。
  2. 沿着格子走到A上方线上点,沿线走到B上方点,沿格子走到B
  3. 右到上
  4. 右到右
  5. 上到右
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;//a上
ya[2] = y1; xa[2] = -(b*ya[2] + c) / a;//a右
xb[2] = x2; yb[2] = -(a*xb[2] + c) / b;//b上
yb[1] = y2; xb[1] = -(b*yb[1] + c) / a;//b右
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;
}