CodeForces760 解题报告

思路

A

算一算就好了

注意周日算最后一天,感觉这很不西方啊233333

B

二分答案,然后贪心地算一下两边最少要放多少枕头

C

哇,这题的题意真的是

首先我们需要保证所有人能走到所有位置

考虑排列所代表的有向图

由于$n$个点,$n$条边,所以必然是若干个环,先将若干个环操作成一个环

然后考虑翻转的问题,由于有两面,因此被翻面的总数保证是奇数就好了

D

线性DP,我们需要考虑转移

对于时间$t_i$,设$s_i$表示前$i$次旅行的最小花费

$si=min(s{i-1}+20,s_j+50,s_k+120)$

其中$s_j$和$s_k$分别为90分钟之内和1440分钟之外的最靠前的一次旅行

E

非常好的线段树应用题目

我们这么考虑,从后往前遍历当前的所有操作,如果到达某个操作时,已有的push数比已有的pop数多1

那么此次push必为当前的栈顶元素

因此我们用区间修改线段树

考虑c为从后往前到达当前操作时,push数目和pop数目的差

则每次操作需要更改$1$到$p_i$的c值

然后二分第一个c为1的位置,这里可以通过区间查询后缀最大值进行二分

二分到的位置必然是一个push,输出此次push对应的值即可

F

又是一个好题

我们先考虑最小表示,即将相邻的重复字母进行合并

得到合并后的串S,称去重合并操作为comp

观察发现,我们对原串进行若干次攻击之后,comp得到的串必然为S的一个子序列

且对于任意S的子序列,我们都有攻击方案使得comp后得到该子序列(相邻字母不同)

接下来,考虑任意子序列T,我们需要将串还原

考虑到comp操作的性质,我们可以任意填充使得还原串与原串长度相等,且还原串comp之后得到T

这部分可以用隔板法和组合数进行处理

自此问题得以解决

另外这题卡了常数,复杂度若为$O(26\times n^2)$会Time Limit Exceeded

我的做法是利用dp数组和sum数组交叉维护,削减了常数

整体复杂度$O(n^2)$

代码

A

1
2
3
4
5
6
7
8
9
10
int a[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int n,m;

int main()
{
scanf("%d%d",&n,&m);
a[n]-=(7-m+1);
printf("%d",(a[n]+6)/7+1);
return 0;
}

B

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
LL n,m,k;

bool judge(LL x)
{
LL l=k-1,r=n-k;
LL s=x*(x-1)/2;
LL sl=s,sr=s;
if(l<x-1)sl-=(x-1-l)*(x-l)/2;
if(l>x-1)sl+=l-x+1;
if(r<x-1)sr-=(x-1-r)*(x-r)/2;
if(r>x-1)sr+=r-x+1;
return sl+sr+x<=m;
}

int main()
{
scanf("%lld%lld%lld",&n,&m,&k);
LL l=0,r=m;
while(r-l>1)
{
LL mid=(l+r)>>1;
if(judge(mid))l=mid;else r=mid;
}
if(judge(l+1))l++;
printf("%lld",l);
return 0;
}

C

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
const int maxn=200005;

int g[maxn],a[maxn];
int n,i,j,tot,k;

int main()
{
scanf("%d",&n);tot=0;
for(i=1;i<=n;i++)scanf("%d",&g[i]);
for(i=1;i<=n;i++)
{
scanf("%d",&k);
tot+=k;
}
k=0;
for(i=1;i<=n;i++)
{
if(a[i]>0)continue;
a[i]=++k;
j=g[i];while(a[j]==0){a[j]=k;j=g[j];}
}
if(k==1)k--;
if(tot%2==0)k++;
printf("%d",k);
return 0;
}

D

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
const int maxn=100005;

int a[maxn];
LL s[maxn];
int i,j,k,n;
LL ans=0;

int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
s[0]=0;
for(i=1;i<=n;i++)
{
s[i]=s[i-1]+20;
if(a[i]<90)s[i]=min(s[i],50ll);
if(a[i]<90)continue;
k=lower_bound(a,a+i,a[i]-89)-a;
s[i]=min(s[i],s[k-1]+50);
if(a[i]<1440)s[i]=min(s[i],120ll);
if(a[i]<1440)continue;
k=lower_bound(a,a+i,a[i]-1439)-a;
s[i]=min(s[i],s[k-1]+120);
}
for(i=1;i<=n;i++)
{
printf("%lld\n",max(0ll,s[i]-ans));
ans=max(ans,s[i]);
}
return 0;
}

E

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
const int maxn=100005;

struct tree
{
int mi,ls,rs,ll,rr,add;
}a[3*maxn];

int b[maxn];
int k,n;

void update(int x)
{
if(a[x].ls+a[x].rs==0)return;
a[x].mi=max(a[a[x].ls].mi,a[a[x].rs].mi);
}

void downdate(int x)
{
if(a[x].ls+a[x].rs==0)return;
if(a[x].add==0)return;
a[a[x].ls].add+=a[x].add;
a[a[x].ls].mi+=a[x].add;
a[a[x].rs].add+=a[x].add;
a[a[x].rs].mi+=a[x].add;
a[x].add=0;
}

void mt(int l,int r)
{
if(l==r)
{
a[k].ll=a[k].rr=l;
a[k].mi=0;
a[k].ls=a[k].rs=0;
return;
}
int t=k;
int mid=(l+r)>>1;
a[t].ll=l;a[t].rr=r;
k++;a[t].ls=k;mt(l,mid);
k++;a[t].rs=k;mt(mid+1,r);
update(t);
}

void add(int l,int r,int nu,int x)
{
if(a[x].ll==l && a[x].rr==r)
{
a[x].add+=nu;
a[x].mi+=nu;
return;
}
downdate(x);
int mid=(a[x].ll+a[x].rr)>>1;
if(mid<l)add(l,r,nu,a[x].rs);
else if(mid>=r)add(l,r,nu,a[x].ls);
else
{
add(l,mid,nu,a[x].ls);
add(mid+1,r,nu,a[x].rs);
}
update(x);
}

int find(int l,int r,int x)
{
if(a[x].ll==l && a[x].rr==r)return a[x].mi;
downdate(x);
update(x);
int mid=(a[x].ll+a[x].rr)>>1;
if(mid<l)return find(l,r,a[x].rs);
if(mid>=r)return find(l,r,a[x].ls);
return max(find(l,mid,a[x].ls),find(mid+1,r,a[x].rs));
}

inline void read(int &x) {
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
x=0;
while(ch<='9'&&ch>='0'){
x=x*10+ch-'0';
ch=getchar();
}
}

int main()
{
read(n);
k=1;mt(1,n);
int u=0;
while(n--)
{
int p,c,m;
read(p);read(c);
if(c==1)read(m);
b[p]=m;u=max(p,u);
if(c==1)add(1,p,1,1);else add(1,p,-1,1);
int l=1,r=u;
if(find(1,u,1)<=0){printf("-1\n");continue;}
while(r-l>1)
{
int mid=(l+r)>>1;
if(find(mid,u,1)>=1)l=mid;else r=mid;
}
if(find(r,u,1)<1)r--;
printf("%d\n",b[r]);
}
return 0;
}

F

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
const LL mod=1e9+7;

LL sum[5005];
bool b[27];
LL c[5005];
char s[5005],s1[5005];
LL dp[5005][27];
int i,j,k,l,m,n;
LL ans;

LL mi(LL x,LL y)
{
LL aa=1;
while(y>0)
{
if(y&1)aa=(aa*x)%mod;
x=(x*x)%mod;
y>>=1;
}
return aa;
}

int main()
{
scanf("%d\n",&n);
if(n-1<=1)c[0]=c[1]=1;
else
{
l=n-1;c[0]=1;c[1]=l;
for(i=2;i<=l;i++)
{
c[i]=c[i-1];
c[i]*=(LL)(l-i+1);
c[i]%=mod;
c[i]*=mi((LL)i,mod-2);
c[i]%=mod;
}
}
gets(s1+1);m=1;
s[1]=s1[1];
for(i=2;i<=n;i++)
if(s1[i]!=s1[i-1])s[++m]=s1[i];
memset(b,0,sizeof(b));
for(i=1;i<=m;i++)
{
int t=s[i]-96;
if(!b[t]){sum[1]++;dp[1][t]=1;b[t]=true;}
for(k=2;k<=m;k++)
{
LL t1=(sum[k-1]-dp[k-1][t]+mod)%mod;
LL t2=dp[k][t];
dp[k][t]=t1;
sum[k]=(sum[k]+mod+t1-t2)%mod;
}
}
for(i=1;i<=m;i++)
{
ans+=(sum[i]*c[i-1])%mod;
ans%=mod;
}
printf("%lld",ans);
return 0;
}