水题，代码如下：
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int a[N] ;
int n, T;
char s[N] ;
int main() {
cin >> T;
while(T--) {
cin >> n;
scanf("%s", s + 1) ;
int fir = 1;
for(;fir <= n; fir++) if(s[fir] == '8') break ;
if(n - fir + 1 >= 11) cout << "YES" << '\n' ;
else cout << "NO" << '\n' ;
}
return 0;
}现在cf B题都开始交互了= =。
这个题直接询问\((1,2),(2,3),(3,4),(4,5)\)即可解出前5个，剩下一个就确定了。
判断是否成立的话我是直接随机的，毕竟长度比较小。
代码如下：
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10;
// 0 3, 1 1 = 64
int b[N][N] ;
int c[N] ;
int n, T;
int main() {
srand(time(NULL));
for(int i = 1; i <= 4; i++) {
printf("? %d %d\n", i, i + 1);
fflush(stdout);
cin >> b[i - 1][i] ;
}
vector <int> a;
a.push_back(4);
a.push_back(8);
a.push_back(15);
a.push_back(16);
a.push_back(23);
a.push_back(42);
while(1) {
int f = 1;
for(int i = 0; i < 4; i++) {
if(a[i] * a[i + 1] != b[i][i + 1]) f = 0;
}
if(f) break ;
random_shuffle(a.begin(), a.end());
}
printf("!");
for(auto v : a) printf(" %d",v);
printf("\n") ;
fflush(stdout) ;
return 0;
}并查集水题，维护每个集合拥有元素的个数即可。
代码如下：
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
int n, m;
int f[N], sum[N];
int find(int x) {
return f[x] == x ? f[x] : f[x] = find(f[x]) ;
}
void Union(int x, int y) {
int fx = find(x), fy = find(y) ;
if(fx != fy) {
f[fx] = fy;
sum[fy] += sum[fx] ;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0) ;
cin >> n >> m;
for(int i = 1; i <= n; i++) f[i] = i, sum[i] = 1;
for(int i = 1; i <= m; i++) {
int k, last = -1;
cin >> k;
int x;
for(int i = 1; i <= k; i++) {
cin >> x;
if(last == -1) last = x;
else Union(last, x) ;
}
}
for(int i = 1; i <= n; i++) {
int fa = find(i);
cout << sum[fa] << ' ';
}
return 0;
}我这个一开始也写的并查集来找，最后还是一直没有A。。。后面发现其实简单的，我原来的写法则要讨论很多的情况。
因为给定的括号串一定是合法的，所以配对的两个括号它们所在位置的奇偶性一定是相同的。
因为我们要求深度最大最小，那么我们对于左括号，一个给1，一个给0就行了，这样可以使得尽量两边都最小。如果对于一个‘)‘，给它的颜色为0，那么后面也接着从0开始染色，因为如果把中间已经匹配了的消去，那么就可以保证染色是1，0，1，0...这样。
代码如下：
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n;
char s[N] ;
int main() {
int c = 0;
cin >> n;
scanf("%s", s + 1) ;
for(int i = 1; i <= n; i++) {
if(s[i] == '(') {
++c;
cout << (c & 1);
} else {
cout << (c & 1);
--c;
}
}
cout << '\n' ;
return 0;
}删去值域为\([l,r]\)的数后，如果剩下的数满足条件，那么我们就可以得到\(down[l-1]<up[r+1]\)，这里的\(down[i]\)表示值为i并且满足前面的值满足单调分布时的最大位置，\(up[i]\)则表示最小位置。
然后我们枚举枚举下界，来确定上界就行了，下界增大时，上界不会减小，所以复杂度是\(O(n)\)的。
这个题的关键就是能够想到维护值域的前缀、后缀信息。
代码如下：
Code
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f;
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int n, m;
int a[N], up[N], dw[N], mn[N], mx[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++) mn[i] = n + 1;
for(int i = 1; i <= n; i++) {
cin >> a[i] ;
mn[a[i]] = min(mn[a[i]], i) ;
mx[a[i]] = max(mx[a[i]], i) ;
}
dw[0] = 0;
for(int i = 1; i <= m; i++) {
if(dw[i - 1] < mn[i]) {
dw[i] = max(dw[i - 1], mx[i]) ;
} else dw[i] = n + 2;
}
up[m + 1] = n + 1;
for(int i = m; i >= 1; i--) {
if(up[i + 1] > mx[i]) {
up[i] = min(mn[i], up[i + 1]);
} else up[i] = -1;
}
int j = 2;
ll ans = 0;
for(int i = 0; i < m; i++) {
while(j <= m && (i + 1 >= j || dw[i] > up[j])) ++j;
if(dw[i] < up[j]) ans += m - j + 2;
}
cout << ans;
return 0;
}未完待续...
Educational Codeforces Round 65 (Rated for Div. 2)题解
原文：https://www.cnblogs.com/heyuhhh/p/10878286.html