CodeForces-EducationRound#78 题解报告

CodeForces-EducationalRound#78 | Here
题解代码 | Here

A. Shuffle Hashing

题意

给出两个字符串$s1,s2$,问是否能在$s2$中找到一串连续的字符串,使得与$s1$相似?

题解

由于数据范围很小所以可以使用$O(n^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
#include <bits/stdc++.h>
using namespace std;

#define all(v) v.begin(),v.end()

int main() {
std::ios::sync_with_stdio(false);
int n;
string str1,str2;
cin >> n;
while(n--) {
cin >> str1 >> str2;
if(str1.size() > str2.size()) {
cout << "NO\n";
continue;
}
sort(all(str1));
int size2= str2.size();
int size1= str1.size();
bool flag = 1;
for(int i=0; i<size2; i++) {
if(i+size1-1 >= size2) break;
string tmp = str2.substr(i,size1);
sort(all(tmp));
if(tmp==str1) {
cout << "YES\n";
flag = 0;
break;
}
}
if(flag) cout << "NO\n";
}
return 0;
}

B. A and B

题意

给出两个数字$a,b$,问最少经过多少轮可以使得$a=b$?

第$k$轮可以选择对$a$ 或 $b$加$k$,每一轮都不可跳过。

题解

仔细发现操作即将$1,2,3,4,5,…,n$,这个数列分成两部分,使得两部分之差的绝对值与$a-b$的绝对值(下文称之为$diff$)相等。

因此只要保证$[(1+n)*n + 2diff] \mod 4 = 0$ 即可,由于$x_0>x_1>=0$,因此$sum>diff$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

int main() {
std::ios::sync_with_stdio(false);
int t;
ll a,b,diff;
cin >> t;
while(t--) {
cin >> a >> b;
diff = abs(a-b);
if(a==b) { cout << 0 << endl; continue; }
diff <<= 1;
a = sqrt(diff); b = a+1;
while(a*b<diff) a++,b++;
while(abs(a*b-diff)%4!=0) a++,b++;
cout << a << endl;
}
return 0;
}

C. Berry Jam

题意

中间有一个楼梯,楼梯左右都放着$n$个果酱,果酱只有两种分别标记为$1,2$,通道很狭隘,每次只能从楼梯处搬出一个果酱(即左/右边最靠近楼梯的)。

问: 最少搬出多少能,让通道内的$1$号果酱个数=$2$号果酱个数?

题解

数据范围是$1e5$,所以做法的时间复杂度必为$O(n\log{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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5+100;
#define debug(x) cout << #x << " = " << x << endl;

int arr[maxn];
int tp[maxn];

map<int,int> lft;

int main() {
std::ios::sync_with_stdio(false);
int t,n,tmp;
cin >> t;
while(t--) {
cin >> n;
arr[0]=0;
lft.clear();
//input arr1
for(int i=1; i<=n; i++) {
cin >> tp[i];
if(tp[i]==1) arr[i] = arr[i-1]-1;
else arr[i] = arr[i-1]+1;
}
//input arr2
for(int i=n; i>=1; i--) { cin >> tp[i]; }
int now = 0;
for(int i=1; i<=n; i++) {
if(tp[i]==1) now--;
else now++;
lft[now] = i;
}
int mx = 0;
for(int i=1; i<=n; i++) {
int idx = lft[-1*arr[i]];
if(idx) mx = max(mx,i+idx);
if(arr[i] == 0) mx = max(mx,i);
}
mx = max(mx,lft[0]);
cout << (n*2-mx) << endl;
}
return 0;
}

D. Segment Tree

题意

题解

重要点: 如何在$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
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 mkp make_pair
#define pir pair<int,int>
#define all(v) v.begin(),v.end()

const int maxn = 5e5+100;
int f[maxn],n;
vector<pir> grp;
pir p[maxn];

void init(int n) {
for(int i=0; i<=n; i++) f[i]=i;
}

int getFa(int a) {
int tp,fa = a;
while(f[a] != a) a = f[a];
while(f[fa] != a) {
tp = f[fa];
f[fa] = a;
fa = tp;
}
return a;
}

set<pir> st;
bool check() {
int t=n-1;
int i,j,r,fa,fb;
for(auto now: grp) {
if(st.count(now)) {
st.erase(now);
} else {
i = now.second;
r = p[i].second;
for(auto gp: st) {
if(gp.first > r) break;
t--;
j = gp.second;
fa = getFa(j);
fb = getFa(i);
if(fa==fb) return 0;
else f[fa] = fb;
}
if(t<0) return 0;
st.insert(mkp(r,i));
}
}
return t==0;
}

int main() {
std::ios::sync_with_stdio(false);
int a,b;
cin >> n;
init(n);
for(int i=0; i<n; i++) {
cin >> p[i].first >> p[i].second;
grp.push_back(mkp(p[i].first,i));
grp.push_back(mkp(p[i].second,i));
}
sort(all(grp));
if(check()) cout << "YES\n";
else cout << "NO\n";
return 0;
}

本题总结

在本题中遭遇了TLE,主要是在线段间的合并时,寻找可连接边的复杂度到达了$O(n)$,而题解中寻找可合并线段的复杂度为$O(1)$,因此使用前者的总时间复杂度为$O(n^2)$,主要花费在寻找可连接边上了,看似优化,实际木大木大,嗐….

E. Tests for problem D

题意

即构造D题的数据。

题解

用包含的关系来防止构造出相交,因此在构造的时候为反向构造,即先构造的后收尾,后构造的先收尾。

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
#include <bits/stdc++.h>
using namespace std;

#define pbk push_back

const int maxn = 5e5+100;
vector<int> a[maxn];
int n,cnt;
int l[maxn],r[maxn];
void dfs(int u,int fa) {
for(int i=a[u].size()-1; i>=0; i--) {
int v = a[u][i];
if(v==fa) continue;
l[v]=cnt++;
}
r[u]=cnt++;
for(int i=0; i<a[u].size(); i++) {
int v = a[u][i];
if(v==fa) continue;
dfs(v,u);
}
}

int main() {
std::ios::sync_with_stdio(false);
int u,v;
cin >> n;
for(int i=0; i<n-1; i++) {
cin >> u >> v;
a[u].pbk(v);
a[v].pbk(u);
}
cnt = 1; l[1]=cnt++;
dfs(1,-1);
for(int i=1; i<=n; i++) cout << l[i] << " " << r[i] << endl;
return 0;
}


--------------------------END--------------------------
喜欢的话,不妨请我喝杯奶茶(≧∇≦)ノ