2022-10-29周赛


题目来自: 2021-2022 Russia Team Open, High School Programming Contest (VKOSHP XXII)

有人不会算复杂度啦,把$O(26^2n)$的算成了$O(26!\times 26n)$了,然后就没敢写。

I - Wheel of Fortune

SOLUTION

dfs爆搜,一共只会有$26$层。

CODE
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>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const pii mod = {1e9 + 7, 1e9 + 9}, base = {131, 251};
const int N = 1e5 + 10;

pll operator*(const pll &p1, const pll &p2) {
return {p1.first * p2.first % mod.first, p1.second * p2.second % mod.second};
}

pll operator+(const pll &p1, const pll &p2) {
return {(p1.first + p2.first) % mod.first, (p1.second + p2.second) % mod.second};
}

pll operator-(const pll &p1, const pll &p2) {
return {(p1.first - p2.first + mod.first) % mod.first, (p1.second - p2.second + mod.second) % mod.second};
}

int ok = 1;
int ch[N][26];
string s[N];

void dfs(const vector<int>& v, vector<bool> rc){
if(!ok) return;
vector<int> cnt(26);
for(int i : v){
for(int j = 0; j < 26; j++){
if(rc[j]) continue;
cnt[j] += ch[i][j];
}
}
int c = 0;
vector<bool> rp(26);
for(int i = 0; i < 26; i++){
rp[i] = rc[i];
if(cnt[i] == v.size()) c++, rp[i] = true;
}
if(!c){
ok = 0;
return;
}
map<pll, vector<int>> mp;
for(int i : v){
pll res = {0, 0};
for(char j : s[i]){
if(rp[j - 'a']) res = res * base + pll{j - 'a' + 1, j - 'a' + 1};
else res = res * base + pll{114514, 114514};
}
mp[res].push_back(i);
}
for(const auto& i : mp){
if(i.second.size() > 1){
dfs(i.second, rp);
}
}
}

void solve() {
int m, n;
cin >> m >> n;
vector<int> vec(n);
vector<bool> is(26);
for(int i = 0; i < n; i++){
cin >> s[i];
vec[i] = i;
for(char j : s[i]){
ch[i][j - 'a'] = 1;
}
}
dfs(vec, is);
if(ok) cout << "YES\n"; else cout << "NO\n";
}

int main() {
int T = 1;
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// cin >> T;
while (T--) solve();
return 0;
}

H - Lots of Parabolas

SOLUTION

三分搜索。

属实没发现它居然是个单峰。

CODE
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;

typedef long long ll;

typedef pair<int, int> pii;
typedef double ld;
typedef pair<ld, ld> pdd;
const int N = 1e5 + 10, Log = 20, inf = 0x3f3f3f3f;

struct node{
int a, b, c;
ld calc(ld x){
return x * x * a + b * x + c;
}
}p[N];

int n;

ld f(ld x){
ld mx = 1e20, mn = -1e20;
for(int i = 0; i < n; i++){
if(p[i].a < 0) mx = min(mx, p[i].calc(x));
else mn = max(mn, p[i].calc(x));
}
return mx - mn;
}

ld ternary_search(ld l, ld r) {
int it = 200; //set the error limit here
while (it--) {
ld m1 = l + (r - l) / 3;
ld m2 = r - (r - l) / 3;
ld f1 = f(m1); //evaluates the function at m1
ld f2 = f(m2); //evaluates the function at m2
if (f1 < f2)
l = m1;
else
r = m2;
}
return l; //return the maximum of f(x) in [l, r]
};

void solve() {
cin >> n;
ld l = -1e19, r = 1e19;
for(int i = 0, a, b, c; i < n; i++){
cin >> a >> b >> c;
p[i] = {a, b, c};
}
ld x = ternary_search(l, r), y = 1e20;
for(int i = 0; i < n; i++){
if(p[i].a < 0) y = min(y, p[i].calc(x));
}
cout << x << ' ' << y << '\n';
}

int main() {
int T = 1;
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << fixed << setprecision(20);
// cin >> T;
while (T--) solve();
return 0;
}