本文合作者:laybxc

赛事信息

名称 出题人 开始时间 时长 官方题解
Codeforces Round #707 (Div. 2, based on Moscow Open Olympiad in Informatics) 4qqqq
Akulyat
Aleks5d
DebNatkh
Endagorion
GlebsHP
KiKoS
Nebuchadnezzar
NiceClock
Siberian
Zlobober
alexX512
biection
cdkrot
ch_egor
grphil
isaf27
ismagilov.code
meshanya
vintage_Vlad_Makeev
voidmax
wrg0ababd
Mar/13/2021
17:05 (UTC+8)
02:30 Codeforces Round #707 Editorial

A. Alexey and Train

题目

题目描述

从时间0开始出发,要依次经过在一条直线上的 nn 个站点,问到达站点n的时间。
每个站点 ii 都有对应的时间 ai,bi,tia_i,b_i,t_i
从站点 i1i-1 到站点i的路上需要花费时间 aibi1+tia_i-b_{i-1}+t_i
到达站点 ii 后,从站点 ii 出发到下个站点需要满足两个条件:
1.在站点 ii 至少需要等待 biai2⌈\frac {b_i-a_i} 2⌉ 的时间
2.出发的时间不能在 bib_i 时间前

输入格式

第一行包括一个整数 t(1t100)t(1≤t≤100) ,表示数据组数

每组数据的第一行包括一个整数 nn ,表示站台的数量。

接下来 nn 行包括两个整数: ai,bi(1ai<bi106)a_i , b_i(1≤ai<bi≤10^6) ,数据保证 bi<ai+1b_i<a_{i+1}

接下来一行包括 nn 个整数 t1,t2,...,tn(0ti106)t_1,t_2,...,t_n(0≤t_i≤10^6)

输出格式

对于每组数据,输出到达最后一个车站的时间

输入输出样例

输入
1
2
3
4
5
6
7
8
9
10
11
12
2
2
2 4
10 12
0 2
5
1 4
7 8
9 10
13 15
19 20
1 2 3 4 5
输出
1
2
12
32

解决方案

思路:

本题难点在读题环节,把题目理解清楚之后,按照题意来直接模拟即可。

代码:

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<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=150;
int n,T;
int a[N],b[N],t[N],x[N];
int main()
{
ios::sync_with_stdio(0);
cin>>T;
while(T--)
{
cin>>n;
int tim=0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(t,0,sizeof(t));
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
}
for(int i=1;i<=n;i++)
{
cin>>t[i];
}
for(int i=1;i<=n;i++)
{
x[i]=a[i]-b[i-1]+t[i];//发车时间
tim+=x[i];
int now=max(tim+(b[i]-a[i]+1)/2,b[i]);
if(i!=n)tim+=now-tim;//只要不是最后一站就加上路上的时间
}
cout<<tim<<endl;
}
return 0;
}

B. Napoleon Cake

题目

题目描述

给你 nn 层蛋糕 ,第 ii 层上面有 aia_i 层奶油,奶油会向下渗透,多余的会浪费掉。问最后有每一层是否有奶油。

输入数据

第一行一个整数 tt ,表示测试数据组数。

每组测试数据的第一行是一个整数 nn ,表示层数

接下来一行是 nn 个整数 aia_i ,表示每层蛋糕上的奶油层数

输出数据

每组数据输出 nn 个整数,分别表示第 ii 层的奶油有无情况,用0表示没有,1表示有。

输入输出样例

输入
1
2
3
4
5
6
7
3
6
0 3 0 0 1 3
10
0 0 0 1 0 5 0 0 0 2
3
0 0 0
输出
1
2
3
1 1 0 1 1 1 
0 1 1 1 1 1 0 0 1 1
0 0 0

解决方案

思路

  1. 直接模拟,从后往前考虑涂奶油的区间即可。
  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
35
36
37
38
39
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=2e5+20;
int n,t;
int a[N],b[N],ans[N],p[N];
int main()
{
ios::sync_with_stdio(0);
cin>>t;
while(t--)
{
cin>>n;
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i])
{
b[max(1,i-a[i]+1)]+=1;
b[i+1]-=1;
}
}
ans[0]=0;
for(int i=1;i<=n;i++)
{
ans[i]=ans[i-1]+b[i];
}
for(int i=1;i<=n;i++)
{
if(ans[i]>0)cout<<"1 ";
else cout<<"0 ";
}
cout<<endl;
}

return 0;
}

代码(直接模拟)

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 200500;
int t, n;
int a[maxn];
bool vis[maxn];

int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
memset(vis, 0, sizeof(vis));
for(int i=1; i<=n; i++)
{
scanf("%d", &a[i]);
}
for(int i=n; i>=1; i--)
{
int j = max(1, i - a[i] + 1);
if(!vis[j])
{
while (j <= i)
{
if(vis[j]) break;
vis[j] = true;
j++;
}
}
}
for(int i=1; i<=n; i++)
{
printf("%d ", vis[i]);
}
puts("");
}

return 0;
}

C. Going Home

题目

题目描述

给你一个整数序列,问你能不能找到下标不同的4个数使得 ax+ay=az+awa_x+a_y=a_z+a_w

输入格式

第一行包括一个整数 nn ,表示整数序列的长度

第二行包括 nn 个整数 a1,a2,...,ana_1,a_2,...,a_n

输出格式

如果能找到输出YES,否则输出NO

如果能找到,在第二行输出任意一组符合条件的 x,y,z,wx,y,z,w

输入输出样例

输入 #1
1
2
6
2 1 5 2 7 4
输出 #1
1
2
YES
2 3 1 6
输入 #2
1
2
5
1 3 1 9 20
输出 #2
1
NO

解决方案

思路

  1. 最先想到的一定是去直接枚举 x,y,z,wx,y,z,w ,复杂度 O(n3)O(n^3) 显然没戏。
  2. 一种简单的优化就是枚举序列中的 (i,j)( i , j ) 然后判断之前有没有出现过这样的和 sum=ai+ajsu m=a_i+a_j ,这样做的做法是 O(n2)O(n^2) 的复杂度,原本觉得显然过不了
  3. 但是实际上枚举的复杂度不是 O(n2)O(n^2) ,因为有: 1a[i]2.5e61 ≤ a [i] ≤ 2.5e6 ,于是有 $2 ≤ a [i] + a[j] ≤ 5e6 $ 。根据抽屉原理,如果我们枚举了 5e6+15e6+1 对两两不同的 (i,j)( i , j ) ,那么一定存在两对不同的 (i,j)( i , j ) 有相同的和。这样一来时间复杂度就是 O(min(n2,5e6))O(min(n^2,5e6)) ,完全可以接受!
  4. 实际上的复杂度会比 5e65e6 稍高一点,上界大约是 存在四对数等于同一个 sumsum 时出现,即 2.5e6×4=1e72.5e6\times4 = 1e7 ,仍然可以接受。

代码

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef pair<int,int> pii;
const int N=2e5+20;
const int M=5e6+20;
pii b[M];
int sum,n;
int a[N];
int ans=0;
int main()
{
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
sum=a[i]+a[j];
if(b[sum].first)
{
if(b[sum].first!=i and b[sum].second!=i and b[sum].first!=j and b[sum].second!=j)
{
cout<<"YES"<<endl;
cout<<b[sum].first<<" "<<b[sum].second<<" "<<i<<" "<<j;
ans=1;
break;
}
}
else b[sum]=make_pair(i,j);
}
if(ans==1)break;
}
if(!ans)cout<<"NO"<<endl;
return 0;
}

D.Two chandeliers

题目

题目描述

给出两个数组 aba,b ,长度分别为 nmn,m ,第 ii 时刻, aa 数组当前指向下标为 (i1)%n+1( i − 1 ) \% n + 1bb 数组指向下标为 (i1)( i − 1 ) % m + 1

若两个数不同,则计数,当计数到达 kk 时,求当前的时刻。

输入格式

第一行三个整数 nmkn,m,k ,表示两个灯光序列的长度和参数 kk

第二行 nn 个整数,表示第一个灯光序列。

第三行 mm 个整数,表示第二个灯光序列。

输出格式

输出一个整数,当计数到达 kk 时的时刻。

输入输出样例

输入 #1
1
2
3
4 2 4
4 2 3 1
2 1
输出 #1
1
5
输入 #2
1
2
3
3 8 41
1 3 2
1 6 4 3 5 7 2 8
输出 #2
1
47
输入 #3
1
2
3
1 2 31
1
1 2
输出 #3
1
62

解决方案

扩展中国剩余定理不会,之后再补…

请参阅