Educational Codeforces Round 65 (Rated for Div. 2)题解
题目链接
A. Telephone Number
水题，代码如下：
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;
}
B. Lost Numbers
现在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;
}
C. News Distribution
并查集水题，维护每个集合拥有元素的个数即可。
代码如下：
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;
}
D. Bicolored RBS
我这个一开始也写的并查集来找，最后还是一直没有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;
}
E. Range Deleting
删去值域为\([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;
}
F. Scalar Queries
填坑来了...
这是一个十分巧妙的题。反正我没想出来...
题目中定义了\(f(l,r)=\sum_{i=1}^{r-l+1}b_i*i\)，这里的\(b_i\)就是原数组\(a_1,a_2,\cdots,a_n\)中的\(a_l,a_{l+1},\cdots,a_{r}\)排序过后的值。
然后题目要求计算\(\sum_{1\leq l\leq r\leq n}f(l,r)\)。
直接考虑有点麻烦，我们就可以考虑每一个数的贡献。
假设现在考虑的为\(a_i\)，那么包含它的区间就有\(i*(n-i+1)\)个，对于每一个区间，假设比\(a_i\)小的数的个数为\(x_i\)，那么此时\(a_i\)的贡献就为\((x_i+1)*a_i\)，我们对于每个区间的1提出来，那么总共就是\(i*(n-i+1)*a_i\)。易知最终的答案就为\((\sum_{j=1}^{i*(n-i+1)}x_j)*a_i\)。
现在我们的任务就是统计包含\(a_i\)的所有区间中，比\(a_i\)小的数的个数。
此时我们也转换一下，考虑每一个数的贡献，对于在\(a_i\)左边的数，其贡献就为\(j*(n-i+1)\);在右边的贡献就为\(k*i\)，这里\(j,k\)分别指从左边开始第几个，从右边开始第几个。因为左右两边等价，我们分析左边：\((n-i+1)*\sum_{j=1}^{i}j*[a_j<a_i]\)。
右边求和的式子，我们用树状数组就可以解决了。
关键在于这两次转化。cf题解里面全是用的数学公式来推导，其实也没有那么麻烦，但感觉这进一步加深了我对数学思维在竞赛中应用的理解吧...
代码如下：
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5, MOD = 1e9 + 7;
int n;
ll a[N], b[N], c[N];
ll s[2][N] ;
int lowbit(int x) {
return x & (-x) ;
}
ll query(int x) {
ll ans = 0;
for(ll i = x; i > 0; i -= lowbit(i)) ans += c[i] ;
return ans ;
}
void update(int x, int val) {
for(int p = x; p < N; p += lowbit(p)) c[p] += val ;
}
void add(ll &x, ll y) {
x += y;
if(x >= MOD) x %= MOD ;
}
ll mul(ll x, ll y) {
x *= y;
if(x >= MOD) x %= MOD ;
return x;
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
sort(b + 1, b + n + 1);
int D = unique(b + 1, b + n + 1) - b - 1;
ll ans = 0;
for(int k = 0; k < 2; k++) {
memset(c, 0, sizeof(c)) ;
for(int i = 1; i <= n; i++) {
int p = lower_bound(b + 1, b + D + 1, a[i]) - b;
s[k][i] = query(p) ;
update(p, i) ;
}
reverse(a + 1, a + n + 1) ;
}
reverse(s[1] + 1, s[1] + n + 1) ;
for(int i = 1; i <= n; i++) {
add(ans, mul(a[i], mul(i, n - i + 1))) ;
add(ans, mul(a[i], mul(s[0][i], n - i + 1))) ;
add(ans, mul(a[i], mul(s[1][i], i))) ;
}
cout << ans;
return 0;
}
![P1880 [NOI1995] 石子合并 题解](https://www.kunjuke.com/file/css/thumb/2.jpg/280-180.jpg)
