首页 > 代码库 > Codeforces Round #361 (Div. 2)
Codeforces Round #361 (Div. 2)
我以为这场是昨天没做完的那场= =，结果是以前没做完的一场。。前3题以前做过了。也懒得再看一遍了= =。虽然前面的题感觉再做一遍也不一定做的出的样子- -。不过D和E都是好题，补这场不亏。
D题，题意是问有多少区间，这段区间里面，在a数组中的max和在b数组中的min是相同的。做法是枚举左端点，考虑到max和min随着区域的增长都是单调的，因此可以二分右端点找出这个区间是不是可行。二分的复杂度是log，寻找给定区间的min或max的复杂度如果用线段树的话复杂度要再加上一个log，有被卡的可能性，因此二分以后考虑用st表进行O(1)寻找即可。这是我第一次写st表，留个代码当作模板。代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <iostream> 5 using namespace std; 6 const int N = 200000 + 5; 7 typedef long long ll; 8 9 int st_min[N][32], st_max[N][32]; 10 int preLog[N]; 11 int n; 12 int a[N],b[N]; 13 void init() 14 { 15 preLog[1] = 0; 16 for(int i=2;i<=n;i++) 17 { 18 preLog[i] = preLog[i-1]; 19 if((1 << preLog[i] + 1) == i) preLog[i]++; 20 } 21 for(int i=n;i>=1;i--) 22 { 23 st_max[i][0] = a[i]; 24 st_min[i][0] = b[i]; 25 for(int j=1;(i+(1<<j)-1)<=n;j++) 26 { 27 st_min[i][j] = min(st_min[i][j-1], st_min[i+(1<<j-1)][j-1]); 28 st_max[i][j] = max(st_max[i][j-1], st_max[i+(1<<j-1)][j-1]); 29 } 30 } 31 } 32 int query_min(int l,int r) 33 { 34 int len = r - l + 1, k = preLog[len]; 35 return min(st_min[l][k], st_min[r-(1<<k)+1][k]); 36 } 37 int query_max(int l,int r) 38 { 39 int len = r - l + 1, k = preLog[len]; 40 return max(st_max[l][k], st_max[r-(1<<k)+1][k]); 41 } 42 43 int main() 44 { 45 cin >> n; 46 for(int i=1;i<=n;i++) scanf("%d",a+i); 47 for(int i=1;i<=n;i++) scanf("%d",b+i); 48 init(); 49 ll cnt = 0; 50 for(int i=1;i<=n;i++) 51 { 52 int L = i, R = n; 53 int temp1 = -1; 54 while(L <= R) 55 { 56 int mid = L + R >> 1; 57 int max_a = query_max(i, mid); 58 int min_b = query_min(i, mid); 59 if(max_a == min_b) {temp1 = mid; R = mid - 1;} 60 else if(max_a > min_b) R = mid - 1; 61 else L = mid + 1; 62 } 63 if(temp1 != -1) 64 { 65 int temp2 = -1; 66 L = i, R = n; 67 while(L <= R) 68 { 69 int mid = L + R >> 1; 70 int max_a = query_max(i, mid); 71 int min_b = query_min(i, mid); 72 if(max_a == min_b) {temp2 = mid; L = mid + 1;} 73 else if(max_a > min_b) R = mid - 1; 74 else L = mid + 1; 75 } 76 cnt += temp2 - temp1 + 1; 77 } 78 } 79 cout << cnt << endl; 80 return 0; 81 }
E题，有n个线段，选出其中的k段，求它们的交集的贡献和。也是一个很经典的题目。既然是算贡献，那么扫一遍，如果当前的线段被覆盖的次数超过了k次，那么就用组合数计算一遍贡献即可。注意线段要用map来离散化；组合数用的是仓鼠的模板。代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <iostream> 5 #include <map> 6 using namespace std; 7 typedef long long ll; 8 const int N = 200000 + 5; 9 const int MOD = (int)1e9 + 7; 10 int F[N], Finv[N], inv[N];//F是阶乘，Finv是逆元的阶乘 11 void init(){ 12 inv[1] = 1; 13 for(int i = 2; i < N; i ++){ 14 inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD; 15 } 16 F[0] = Finv[0] = 1; 17 for(int i = 1; i < N; i ++){ 18 F[i] = F[i-1] * 1ll * i % MOD; 19 Finv[i] = Finv[i-1] * 1ll * inv[i] % MOD; 20 } 21 } 22 int comb(int n, int m){//comb(n, m)就是C(n, m) 23 if(m < 0 || m > n) return 0; 24 return F[n] * 1ll * Finv[n - m] % MOD * Finv[m] % MOD; 25 } 26 27 int n,k; 28 29 int main() 30 { 31 init(); 32 cin >> n >> k; 33 map<int,int> M; 34 for(int i=1;i<=n;i++) 35 { 36 int l,r; scanf("%d%d",&l,&r); 37 M[l] ++; M[r+1] --; 38 } 39 int last = M.begin()->first; 40 int temp = 0; 41 ll ans = 0; 42 for(map<int,int>::iterator it=M.begin();it!=M.end();it++) 43 { 44 ll num = it->first - last; 45 if(temp >= k) ans += comb(temp, k) * num % MOD; 46 ans %= MOD; 47 temp += it->second; 48 last = it->first; 49 } 50 cout << ans << endl; 51 return 0; 52 }
Codeforces Round #361 (Div. 2)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。