喜提河南icpc金牌

赛事

赛事感受

先吐槽一下主办方的系统，开赛时系统众生平等的卡顿打不开网页，不平等的是每个队伍的系统上显示的时间进度都不同，导致有队伍提前看题提交21sac赛后被喷的，然后就是测评系统卡顿，我们队代码提交之后等了近十分钟，还没有得到反馈，最后是代码打印，我们提交了两次打印，近两个小时才给我们送过来，此前bug已经调好了，主办方的这些相关设备都是得升级。
做题，我们是开赛后一个队友从前往后看题，我从后往前看，另一个队友写模板，我们看题很快，找到了三个签到题（m、j、b）都是一次ac，然后我看了i计算几何，这是个板子题，然后我写模板，中间另外两名队友讨论了k有思路，但未注意细节喜提罚时一发，然后也是ac了。然后我继续写几何模板，中间队友又看了e，我们讨论了思路认为可行，继续交换身份，但还是细节问题又喜提一发罚时，我在给他俩的代码调试时发现了优先队列为空的情况，排除了这个错误后，由于没有找到别的可能错误，也是抱着试试的心理交了一发，然后他俩继续讨论思路，我继续写几何模板（计算几何真的是太长了），期间我时不时看测评界面都是pending（主办方测评系统该升级了），大概第五次，我看到刚提交的绿色反馈，全队狂喜。再然后他俩跟着榜单走，看了剩下的题目，我写好后，对着模板复查了代码，然后我就直接跑计算面积的函数修改了代码（删除了return，替换为cout，改了导致了TLE，不应该改的QWQ），一键提交，也是得到了TLE，然后我打印了代码，由于一直没有给我们送来，我拿着系统的错误代码反馈对着模板改，结果看到了no return，然后我就把函数类型double改为void，再找不到别的错误，就再次抱着试试的心理，然后疯狂刷新界面，喜提ac。这是赛时过了三个小时，也是我们最后开出来的一个，这题开后我们的排名是前15名，拿金牌很有希望，剩下的俩小时，由于罚时太高，我们求稳打算再开，实在找不到能ac的思路，提交也是止步于此了QWQ。然后我们封榜前是前20名，到赛完也没再开出一个题QWQ。最后滚榜我们的排名正好在金尾，喜提大学第一块金牌，燃尽了！！!。
我们本次比赛获得金牌也是气运好，也感谢学弟们跟我组队拿奖，本来只能拿到银牌的有了学弟的加持也是喜提金牌hhh。
img

题解

B

将$(2^i<=n)$的数累加即可。时间$O(1)$，空间$O(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
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define mod 100000007
#define MOD 998244353
#define x first
#define y second
#define db long double

using namespace std;

const int N  =  2e5 + 10, M = 1010, P = 25;

inline void solve() {
	int x;
	cin >> x;
	int ans = 0;
	for(int i = 0; i < 32; i ++) {
		if(ans +  (1ll << i) <= x) {
			ans += (1ll << i);
		}
	} cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	int _ = 1;
	cin >> _;
	cout << fixed << setprecision(6);
	while(_ --) {
		solve();
	} return _ ^ _;
}

E

用并查集维护生成树，根据增加的黑边和白边顺序维护$(ss<=(s+1)(s+1))$，更新生成树和答案。时间$O(nlog(n))$，空间$O(n)$。

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
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define mod 100000007
#define MOD 998244353
#define x first
#define y second
#define db long double

using namespace std;

const int N  =  2e5 + 10, M = 1010, P = 25;

struct node {
    int v, x, y, c;
};
int fa[N];

int find(int x) {
    if(fa[x] != x) {
        fa[x] = find(fa[x]);
    } return fa[x];
}

void merge(int x, int y) {
    fa[find(x)] = find(y);
}

bool cmp(const node &a, const node &b) {
    return a.v < b.v;
}

int kruskal(vector<node> &fs, int n) {
    sort(fs.begin(), fs.end(), cmp);
    for(int i = 1; i <= n; i ++) {
        fa[i] = i;
    } int cnt = 0, s = 0, ff = 0;
    for(const auto &f : fs) {
        if(find(f.x) != find(f.y)) {
            merge(f.x, f.y);
            cnt += f.v;
            if(f.c == 0) {
                s ++;
            } ff ++;
            if(ff == n - 1) {
                break;
            }
        }
    } return cnt + s * s;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<node> fs(m);
    for(int i = 0; i < m; i ++) {
        cin >> fs[i].x >> fs[i].y >> fs[i].v >> fs[i].c;
    } cout << kruskal(fs, n) << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _ = 1;
    // cin >> _;
    cout << fixed << setprecision(6);
    while(_ --) {
        solve();
    } return _ ^ _;
}

I

将给出的点集和点集左右端点横坐标一并存入凸包，跑凸包模板即可。时间$O(nlog(n))$，空间$O(n)$。

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define mod 100000007
#define MOD 998244353
#define x first
#define y second
// #define db long double
// #define double long double

using namespace std;

const int N = 2e5 + 10, M = 1010, P = 25;

const double eps = 1e-6;

vector<pdd> in;

int sign(double x) {
    if(fabs(x) < eps) {
        return 0;
    } if(x < 0) {
        return -1;
    } return 1;
}

bool operator == (pdd a, pdd b) {
    return !sign(a.x - b.x)&&!sign(a.y - b.y);
}
pdd operator - (pdd a, pdd b) {
    return pdd(a.x - b.x, a.y - b.y);
}
pdd operator + (pdd a, pdd b) {
    return pdd(a.x + b.x, a.y + b.y);
}
double operator ^ (pdd a, pdd b) {
    return a.x * b.y - a.y * b.x;
}
double operator * (pdd a, pdd b) {
    return a.x * b.x + a.y * b.y;
}
pdd operator * (pdd a, double b) {
    return pdd(a.x * b, a.y * b);
}
pdd operator / (pdd a, double b) {
    return pdd(a.x / b, a.y / b);
}
static double cross(pdd a,pdd b) {
    return a.x * b.y - a.y * b.x;
}
static double dot(pdd a,pdd b) {
    return a.x * b.x + a.y * b.y;
}

static double dis2(pdd a, pdd b){
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
double dis(pdd a, pdd b){
    return sqrt((a.x - b.x) * (a.x - b.x) * 1.0 + (a.y - b.y) * (a.y - b.y) * 1.0);
}
double culk(pdd a, pdd b){
    return (a.y - b.y) / (a.x - b.x);
}

void quicksort(int l, int r) {               //快排 
    if(l<r) {
        swap(in[l], in[(l + r) / 2]);
        int i = l, j = r;
        pdd x = in[l];
        while(i < j) {
            while(i < j&&(cross(in[j] - in[0], x - in[j]) < 0||(cross(in[j] - in[0], x - in[j]) == 0&&dis2(in[j], in[0]) > dis2(x, in[0])))) {
                j--;
            } if(i < j) {
                in[i ++] = in[j];
            } while(i < j&&(cross(in[i] - in[0], x - in[i]) > 0||(cross(in[i] - in[0], x - in[i]) == 0&&dis2(in[i], in[0]) < dis2(x, in[0])))) {
                i++;
            } if(i < j) {
                in[j --] = in[i];
            }
        } in[i] = x;
        quicksort(l, i - 1);
        quicksort(i + 1, r);
    }
}
void convexHell() {                          //查找凸包上的点 
    int ori = 0;
    for(int i = 0; i < in.size(); i ++) {
        if(in[i].y < in[ori].y||(in[i].y == in[ori].y&&in[i].x < in[ori].x)) {
            ori = i;
        }
    } swap(in[0], in[ori]);
    quicksort(1, in.size() - 1);
    vector<pdd> tmp(in.size() + 10);
    int nw = -1;
    for(int i = 0; i < in.size(); i ++) {
        while(nw >= 1) {
            if(cross(tmp[nw] - tmp[nw - 1], in[i] - tmp[nw]) > 0) {
                break;
            } else if(cross(tmp[nw] - tmp[nw - 1],  in[i] - tmp[nw]) == 0) {
                nw --;
                break;
            } else {
                nw --;
            }
        } tmp[++ nw] = in[i];
    } in.clear();
    for(int i = 0; i <= nw; i ++) {
        in.emplace_back(tmp[i]);
    }
}

void cularea() {                       //计算面积
    convexHell();
    double ans = 0;
    for(int i = 0; i < in.size(); i ++){
        ans += cross(in[i], in[(i + 1) % in.size()]);
    } cout << ans / 2.0  << '\n';
}

inline void solve() {
    int n;
    cin >> n;
    pdd l = {1e7, 0}, r = {0, 0};
    for(int i = 0; i < n; i ++) {
        pdd t;
        cin >> t.x >> t.y;
        l.x = min(l.x, t.x);
        r.x = max(r.x, t.x);
        in.emplace_back(t);
    } in.emplace_back(l);
    in.emplace_back(r);
    cularea();
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _ = 1;
    // cin >> _;
    cout << fixed << setprecision(6);
    while(_ --) {
        solve();
    } return _ ^ _;
}

J

由于敲击的字母顺序与所给的字符串无关，只需将所给的字符串排序后顺序扫描更新答案。时间$O(n)$，空间$O(n)$。

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
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define mod 100000007
#define MOD 998244353
#define x first
#define y second
#define db long double

using namespace std;

const int N  =  2e5 + 10, M = 1010, P = 25;

inline void solve() {
	string s;
	cin >> s;
	int ans = 0;
	char c = 'a';
	sort(s.begin(), s.end());
	for(int i = 0; i < s.size(); i ++) {
		ans += abs(s[i] - c) + 1;
		c = s[i];
	} cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	int _ = 1;
	// cin >> _;
	cout << fixed << setprecision(6);
	while(_ --) {
		solve();
	} return _ ^ _;
}

K

由于n <= 10很小，只要暴力跑全排列找出符合答案的排列即可。时间$O(n!*n^2)$，空间$O(n)$。

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
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define mod 100000007
#define MOD 998244353
#define x first
#define y second
#define db long double

using namespace std;

const int N  =  2e5 + 10, M = 1010, P = 25;

vector<int> p(P);
vector<bool> st(P);
vector<pdd> f(P);
vector<double> ff(P);
bool ok;
int n;

double get(pdd a, pdd b) {
    double x = a.x - b.x, y = a.y - b.y;
    return sqrt(x * x + y * y);
}

void check() {
    for(int i = 1; i < n; i ++) {
        for(int j = i + 1; j <= n; j ++) {
            double t = get(f[i], f[j]);
            double a = ff[p[i]], b = ff[p[j]];
            if(t > fabs(a - b)&&t < fabs(a + b)) {
                return ;
            }
        }
    } ok = true;
}

void dfs(int u) {
    if(ok) {
        return ;
    } if(u == n + 1) {
        check();
        if(ok) {
            for(int i = 1; i <= n; i ++) {
                cout << p[i] << " \n"[i == n];
            }
        }
        return ;
    } for(int i = 1; i <= n; i ++) {
        if(!st[i]) {
            st[i] = true;
            p[u] = i;
            dfs(u + 1);
            st[i] = false;
        }
    }
}

inline void solve() {
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> f[i].x >> f[i].y;
    } for(int i = 1; i <= n; i ++) {
        cin >> ff[i];
    } ok = false;
    dfs(1);
    if(!ok) {
        cout << "-1\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _ = 1;
    // cin >> _;
    cout << fixed << setprecision(6);
    while(_ --) {
        solve();
    } return _ ^ _;
}

M

签到题，根据题目模拟即可。时间$O(1)$，空间$O(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
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define mod 100000007
#define MOD 998244353
#define x first
#define y second
#define db long double

using namespace std;

const int N  =  2e5 + 10, M = 1010, P = 25;

inline void solve() {
	int x;
	string s;
	cin >> x >> s;
	if(s == "MiB"){
		cout << x * (1ll << 10)  <<  " KiB\n";
	} else {
		cout << x * 1000 << " KB\n";
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	int _ = 1;
	// cin >> _;
	cout << fixed << setprecision(6);
	while(_ --) {
		solve();
	} return _ ^ _;
}