Educational Codeforces Round 28

A. Curriculum Vitae

题意

给定一个只包含$0$和$1$的序列,要求你保留最多的元素使得没有一个0在1后面

题解

由于终态一定是很多0后面跟很多1,枚举断点即可。

复杂度

$O(n)$

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int a[100+5];
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int ans=0;
for(int i=0;i<=n+1;i++){
int cnt=i>=1 && i<=n;
for(int j=1;j<=i-1;j++) if(a[j]==0) cnt++;
for(int j=i+1;j<=n;j++) if(a[j]==1) cnt++;
ans=max(ans,cnt);
}
printf("%d\n",ans);
return 0;
}

B. Math Show

题意

有$n$个任务,每个任务有$k$个子任务,分别画$t_j$的时间,每解决一个得1分,一个任务全解决多得1分,问给出$M$的时间,最多得多少分

题解

枚举有多少题是完全做完的,剩下的时间去挑最少时间的子任务完成,然后更新答案。

复杂度

$O(n^2k)$

程序

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=55;
int a[maxn],sum[maxn];
int n,k,m;
int main()
{
scanf("%d%d%d",&n,&k,&m);
for(int i=1;i<=k;i++) {
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
sort(a+1,a+1+k);
int Ans=0;
for(int pos=0;pos<=n;pos++){
int now=pos*(k+1),lev=m-pos*sum[k];
if(lev<0) break;
for(int j=1;j<=k;j++){
for(int i=1;i<=n-pos;i++){
if(lev>=a[j]) lev-=a[j],now+=(1+(j==k));
}
}
Ans=max(Ans,now);
}
printf("%d\n",Ans);
return 0;
}

C. Four Segments

题意

给你一个序列有$n$个数,($n\leq 5000$),要求你选出三个数$a,b,c$,记$sum(l,R)$为区间$[l,r)$的和,使得$sum(0,a)-sum(a,b)+sum(b,c)-sum(c,n)$最小。

题解

考虑一下这个式子本质其实是$sum(0,a)\times 2 +sum(b,c) \times 2-sum(0,n)$,那么我们先求最大子段和,然后根据字段和的左端点确定小于左端点的最大前缀和即可。

复杂度

$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;
typedef long long ll;
const int maxn=5000+5;
int n;
ll a[maxn],dp[maxn];
ll sum[maxn];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) {scanf("%lld",&a[i]);sum[i]=i==0?a[i]:sum[i-1]+(ll)a[i];}
int A=0,B=0,C=0;
dp[n+1]=0;
ll tmpmax=LLONG_MIN;
int tmp=0,tmp2=0;
for(int i=n-1;i>=0;i--) {
dp[i]=max(dp[i+1]+a[i],a[i]);
}
for(int i=-1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(tmpmax<(i==-1?0:sum[i])+dp[j]){
tmpmax=(i==-1?0:sum[i])+dp[j],tmp=i,tmp2=j;
}
}
}
int tmp3=0;
if(tmp2==n) tmp3=n-1;
else for(int i=tmp2;i<=n;i++)
if(dp[tmp2]==sum[i]-(tmp2>=1?sum[tmp2-1]:0))
{tmp3=i;break;}
A=tmp+1,B=tmp2,C=tmp3+1;
printf("%d %d %d\n",A,B,C);
return 0;
}

D. Monitor

题意

有一个$w \times h$的屏幕($w,h \leq 500$),给出$q$($q\leq 250000$)个像素点的坐标和坏掉的时间,规定一个屏幕坏了当且仅当是在$k \times k$个像素都坏了的情况,问最小在什么时候这个屏幕坏了,或者它永远不会坏。

题解

考虑用两个二位前缀和,一个$sum(i,j)$记$1\leq x \leq i$,$1\leq y \leq j$的屏幕中会坏的像素个数,一个$max(i,j)$$1\leq x \leq i$,$1\leq y \leq j$的屏幕中会坏的像素最多的时间(因为整个$k\times k$坏掉是以最后一个坏掉的为准),然后扫一遍更新答案即可。

复杂度

$O(nmlog_k)$

程序

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
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
const int maxn=500+5;
int a[maxn][maxn],sum[maxn][maxn],t[maxn][maxn],maxx[maxn][maxn],maxt[maxn][maxn];
int n,m,k,q;
struct pqu{
priority_queue<int> pq,del;
void ini(){
while(!pq.empty()) pq.pop();
while(!del.empty()) del.pop();
}
void add(int x){
pq.push(x);
}
void delet(int x){
del.push(x);
}
int gettop(){
while(!del.empty() && del.top()==pq.top()) del.pop(),pq.pop();
return pq.top();
}
};
int getsum(int i,int j){
int prei=max(0,i-k),prej=max(0,j-k);
return sum[i][j]-sum[i][prej]-sum[prei][j]+sum[prei][prej];
}
int main()
{
scanf("%d%d%d%d",&n,&m,&k,&q);
memset(t,-1,sizeof(t));
memset(maxx,-1,sizeof(maxx));
memset(maxt,-1,sizeof(maxt));
if(q<k*k){printf("-1\n");exit(0);}
for(int i=1;i<=q;i++){
int x,y,T;
scanf("%d%d%d",&x,&y,&T);
t[x][y]=maxx[x][y]=T;
a[x][y]++;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) sum[i][j]=sum[i][j-1]+a[i][j];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) sum[i][j]+=sum[i-1][j];
}
for(int i=1;i<=n;i++){
pqu pq;
pq.ini();
for(int j=1;j<=m;j++){
pq.add(t[i][j]);
if(j>k) pq.delet(t[i][j-k]);
maxx[i][j]=pq.gettop();
}
}
for(int j=1;j<=m;j++){
pqu pq;
pq.ini();
for(int i=1;i<=n;i++){
pq.add(maxx[i][j]);
if(i>k) pq.delet(maxx[i-k][j]);
maxt[i][j]=pq.gettop();
}
}
int Ans=0x3f3f3f3f;
for(int i=k;i<=n;i++){
for(int j=k;j<=m;j++){
if(getsum(i,j)==k*k) {
Ans=min(Ans,maxt[i][j]);
assert(maxt[i][j]!=-1);
}
}
}
assert(Ans!=-1);
printf("%d\n",Ans==0x3f3f3f3f?-1:Ans);
return 0;
}

E. Chemistry in Berland

题意

有$n$种($n\leq 100000$)材料,然后告诉你材料现有的供应和做实验需要的量,告诉你$n-1$个对应关系,第$i+1$个关系告诉你$x_{i+1}$和$k_{i+1}$,表明你可以用$k_{i+1}$量的$x_{i+1}$替换1的量的$i+1$材料,也可以用1的量的$i+1$材料替换1的量的$x_{i+1}$材料,保证$x_{i+1}\leq i+1$。然后问你能否替换材料使得这个实验能够进行

题解

由于$x_i$小于$i$,这样的关系可以构成一棵树,例如下图的形式

image

对于叶子结点而言,只有他们的父亲才能转移用料给他们。因而考虑从叶子入手,如果不够就削剥他们的父亲,如果用料有多的就转移到他们的父亲,依次往上这样操作。这样做的正确性显然,因为这样能保证父亲花费了最少的“以$k$换$1$”的交易,自然中间流失的量是最少的。最后到了根节点,如果根节点供不应需,那么肯定是不行的,因为这时已经没有任何用料可以转移给他了。

复杂度

$O(n)$

其外

这个题某些数据会有减多了以后甚至超出$long long$范围的情况,所以需要提前判定一下,防止溢出后答案变得很奇怪

程序

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100000+5;
const ll inf=(1ll<<60)-1;
vector<int > g[maxn];
ll a[maxn],b[maxn];
ll k[maxn];
int n;
#define MP make_pair
int fa[maxn];
bool flag=true;
void handle(int v,int pa)
{
if(!flag) return;
for(int i=0;i<(int)g[v].size();i++){
int u=g[v][i];
if(u!=pa) handle(u,v);
}
if(pa==-1){
if(b[v]>=a[v]) return;
else{
flag=false;
return;
}
}else{
if(b[v]-a[v]>=0) b[pa]+=b[v]-a[v],b[v]=a[v];
else{
ll del=0;
if(a[v]-b[v]>inf) del=inf;
else del=(a[v]-b[v])*k[v];
b[v]=a[v];
if(del>=inf) b[pa]=-inf;
else b[pa]-=del;
if(b[pa]<-inf) b[pa]=-inf;
}
}
}
int main()
{
scanf("%d",&n);
ll sumb=0,suma=0;
for(int i=1;i<=n;i++) {scanf("%I64d",&b[i]);sumb+=b[i];}
for(int i=1;i<=n;i++) {scanf("%I64d",&a[i]);suma+=a[i];}
if(sumb<suma) {
printf("NO\n");
exit(0);
}
for(int i=2;i<=n;i++){
int x;
scanf("%d%I64d",&x,&k[i]);
fa[i]=x;
g[x].push_back(i);g[i].push_back(x);
}
handle(1,-1);
if(flag){
printf("YES\n");
}else printf("NO\n");
return 0;
}

F. Random Query

题意

给一个序列有$n$个数($n\leq 1000000$),任意确定一个$l,r$($l \leq n,r \leq n$)(如果$l \le r$就交换),问这个区间$[l,r]$中有多少个不同的数,求随意取区间后不同数字的期望。

题解

考虑每个数他对几个区间有贡献,如果这个数在这个序列只出现一次那肯定会对$n$个有贡献;但会有重复的元素,考虑一个区间中,有重复元素时,记第一个出现的是这个数的贡献,那么就可以计算每个数在几个区间里第一次出现,统计答案后再除以总的选法$n^2$种即可。

复杂度

$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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1000000+5;
int a[maxn],cnt[maxn];
vector<int > pos[maxn];
set<int > val;
ll n;
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
cnt[a[i]]++;
pos[a[i]].push_back(i);
val.insert(a[i]);
}
ll Ans=0;
for(set<int >::iterator ite=val.begin();ite!=val.end();++ite)
{
int x=*ite;
if(pos[x].size()==1) {
Ans+=(pos[x][0])*(n-pos[x][0]+1)-1;
continue;
}
else{
ll pre=0,now=pos[x][0];
for(int i=0;i<(int)pos[x].size();i++){
now=pos[x][i];
Ans+=(now-pre)*(n+1-now)-1;
pre=now;
}
}
}
Ans=Ans*2+n;
printf("%lf\n",(double)Ans/((double)(n*n)));
return 0;
}

more

这场教做人场感觉考的技巧主要是序列(一维或者二维)的处理技巧(C,D,F),以及考虑终态或是从边界入手的贪心(A,B,E),大概是这期的主导思路吧。