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();
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;
}
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;
}
|
