| Solved | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| 6/6 | O | O | O | Ø | Ø | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A CF1175E - Minimal Segment Cover
题目描述
给定一组区间，每次询问某一个区间最少能由给定区间的多少个完全覆盖。
区间个数$q\leq n\leq 2e5$，给定区间以及询问区间均保证$0\leq l,r\leq 5e5$。
解题思路
记录每一个点向右走$k$个区间能走到的最右端，用倍增存储。
每次查询从大到小搞一搞区间即可。
AC代码
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
typedef long long ll;
using namespace std;
int n,m;
int dis[M][N+5];
int sol(int l,int r){
int i,ans=0;
for(i=M-1;i>=0;i--)if(dis[i][l]<r)l=dis[i][l],ans+=(1<<i);
if(dis[0][l]<r)return -1;
return ans+1;
}
int main(){
int i,j,l,r,mr=0;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++){
scanf("%d%d",&l,&r);
dis[0][l]=max(dis[0][l],r);
mr=max(mr,r);
}
for(i=1;i<=mr;i++)dis[0][i]=max(dis[0][i],i);
for(i=1;i<=mr;i++)dis[0][i]=max(dis[0][i],dis[0][i-1]);
for(i=1;i<M;i++)for(j=0;j<=mr;j++)dis[i][j]=dis[i-1][dis[i-1][j]];
for(i=0;i<m;i++)scanf("%d%d",&l,&r),printf("%d\n",sol(l,r));
return 0;
}
B CF1175D - Array Splitting
题目描述
给一个整数数列，要把它分成$k$段，从左到右分别赋权值$1,2,…,k$（即：在第$j$个区间内的点$i$对应权值为$a_i=j$），求$\sum_{i=1}^na_ix_i$的最大值。
解题思路
画一个图很显然可得知，答案为$k\times sum$减去$k-1$个互不相同的前缀和。排个序即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef long long ll;
using namespace std;
ll ans,a[N];
int main(){
int i,n,k;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)scanf("%I64d",&a[i]),ans+=a[i]*k,a[i]+=a[i-1];
sort(a+1,a+n);
for(i=1;i<k;i++)ans-=a[i];
printf("%I64d\n",ans);
return 0;
}
C CF1175C - Electrification
题目描述
给定一个递增序列$1\leq a_i\leq 10^9,1\leq n\leq 2\times 10^5$，以及$0\leq k<n$，让你任意打乱$a_i$的顺序，构造数列$d_i=|a_i-x|$使得$d_{k+1}$最小，求出$x$。
解题思路
暴力找出差距最小的长度为$k$的区间，求其中点即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef long long ll;
using namespace std;
int n,k,t,a[N];
int main(){
int i;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&k);
int mx=2e9,temp=1;
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i+k<=n;i++)if(mx>a[i+k]-a[i])mx=a[i+k]-a[i],temp=i;
printf("%d\n",(a[temp]+a[temp+k])/2);
}
return 0;
}
D/E 1172C1/C2 - Nauuo and Pictures (easy/hard version)
题目描述
有$n$个陈列品，每一个有一个正整数权值。$nauuo$喜欢其中某一些陈列品，有$m$次参观，每次每个陈列品按照权值对应的概率出现，如果是他喜欢的那么该陈列品的权值加一，否则减一。求出$m$次参观后每一个陈列品权值的期望。
解题思路
设$f[i][j][w]$表示参观了$i+j$次，其中$i$次是他喜欢的，$j$次是他不喜欢的，之后初始权值为$w$的喜欢的陈列品最终权值期望，设初始喜欢的权值和为$gv$，不喜欢的权值和为$bv$，则当前分别为$gv+i,bv-j$。从后向前递推：
$f[i][j][w]=\frac{w}{gv+bv+i-j}f[i+1][j][w+1]+\frac{gv-w}{gv+bv+i-j}f[i+1][j][w]+\frac{bv}{gv+bv+i-j}f[i][j+1][w]$。
给一个结论：$f[i][j][w]=f[i][j][1]\times w$，很容易证明。
所以$f[i][j][w]=\frac{w(w+1)}{gv+bv+i-j}f[i+1][j][1]+\frac{(gv-w)w}{gv+bv+i-j}f[i+1][j][1]+\frac{bv\times w}{gv+bv+i-j}f[i][j+1][1]$
$=\frac{w(gv+1)}{gv+bv+i-j}f[i+1][j][1]+\frac{bv\times w}{gv+bv+i-j}f[i][j+1][1]$
同理处理出不喜欢的陈列品权值期望。预处理出逆元即可保证复杂度。
AC代码
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
typedef long long ll;
using namespace std;
int mod=998244353;
int qp(int x,int p){
ll ans=1;
for(;p;p>>=1,x=(ll)x*x%mod)if(p&1)ans=ans*x%mod;
return ans;
}
ll f[M][M],g[M][M];
int n,m,a[N],inv[M<<1];
ll gv,bv,w[N];
int main(){
int i,v,j,k;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++){
scanf("%I64d",&w[i]);
if(a[i])gv+=w[i];else bv+=w[i];
}
for(i=0;i<=m<<1;i++)inv[i]=qp(bv+gv+i-m,mod-2);
for(i=m;i>=0;--i){
f[i][m-i]=g[i][m-i]=1;
for(j=min(m-i-1LL,bv);j>=0;--j){
int qpow=inv[i-j+m];
f[i][j]=((bv-j)*f[i][j+1]+(gv+i+1)*f[i+1][j])%mod*qpow%mod;
g[i][j]=((bv-j-1)*g[i][j+1]+(gv+i)*g[i+1][j])%mod*qpow%mod;
}
}
for(i=1;i<=n;i++){
if(a[i])printf("%d\n",w[i]*f[0][0]%mod);
else printf("%d\n",w[i]*g[0][0]%mod);
}
return 0;
}
F CF1175F - The Number of Subpermutations
题目描述
给定一个数列，称某个区间为好序列当且仅当其中所有数构成一个排列，求出其好序列个数。
解题思路
先求出每一个点$i$的$maxright_i$，保证$[i,maxright_i]$中没有相同的数字。这很容易通过从后向前递推实现。求出这个后，我们发现，$[i,j]$合法当且仅当$j<=maxright_i$且$max[i,j]=j-i+1$。
然后以每一个点为左端点，枚举合法的右端点，每次$RMQ$添加答案或者跳到这段区间对应最大值所对应长度的位置即可。
AC代码
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
typedef long long ll;
using namespace std;
int pos[N],a[N],mr[N],mx[20][N],lg[N];
int query(int l,int r){
int p=lg[r-l+1];
return max(mx[p][l],mx[p][r+1-(1<<p)]);
}
int main(){
int i,j,l,r,n,ans=0;
scanf("%d",&n);
for(i=2;i<N;i++)lg[i]=lg[i-1]+!(i&(i-1));
for(i=1;i<=n;i++)scanf("%d",&a[i]),mx[0][i]=a[i];mr[i]=n;
for(i=n;i;i--){
if(pos[a[i]])mr[i]=min(mr[i+1],pos[a[i]]-1);
else mr[i]=mr[i+1];
pos[a[i]]=i;
}
for(i=1;i<20;i++)
for(j=1;j+(1<<i-1)<=n;j++)
mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<i-1)]);
for(l=1;l<=n;l++){
r=l;
while(r<=mr[l]){
int d=query(l,r);
if(d==r-l+1)ans++,r++;
else r=l+d-1;
}
}
printf("%d",ans);
return 0;
}