【Codeforces】 题解 - Round 707 (Div.2)

本文合作者：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开始出发，要依次经过在一条直线上的 $n$ 个站点，问到达站点n的时间。
每个站点 $i$ 都有对应的时间 $a_i,b_i,t_i$
从站点 $i-1$ 到站点i的路上需要花费时间 $a_i-b_{i-1}+t_i$
到达站点 $i$ 后，从站点 $i$ 出发到下个站点需要满足两个条件:
1.在站点 $i$ 至少需要等待 $⌈\frac {b_i-a_i} 2⌉$ 的时间
2.出发的时间不能在 $b_i$ 时间前

输入格式

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

每组数据的第一行包括一个整数 $n$ ，表示站台的数量。

接下来 $n$ 行包括两个整数： $a_i , b_i(1≤ai<bi≤10^6)$ ，数据保证 $b_i<a_{i+1}$ 。

接下来一行包括 $n$ 个整数 $t_1,t_2,...,t_n(0≤t_i≤10^6)$

输出格式

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

输入输出样例

输入

2
2
2 4
10 12
0 2
5
1 4
7 8
9 10
13 15
19 20
1 2 3 4 5

输出

12
32

解决方案

思路：

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

代码：

#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

题目

题目描述

给你 $n$ 层蛋糕 ，第 $i$ 层上面有 $a_i$ 层奶油，奶油会向下渗透，多余的会浪费掉。问最后有每一层是否有奶油。

输入数据

第一行一个整数 $t$ ，表示测试数据组数。

每组测试数据的第一行是一个整数 $n$ ，表示层数

接下来一行是 $n$ 个整数 $a_i$ ，表示每层蛋糕上的奶油层数

输出数据

每组数据输出 $n$ 个整数，分别表示第 $i$ 层的奶油有无情况，用0表示没有，1表示有。

输入输出样例

输入

3
6
0 3 0 0 1 3
10
0 0 0 1 0 5 0 0 0 2
3
0 0 0

输出

1 1 0 1 1 1 
0 1 1 1 1 1 0 0 1 1 
0 0 0 

解决方案

思路

1. 直接模拟，从后往前考虑涂奶油的区间即可。
2. 考虑区间处理，注意到 我们只关心奶油有没有，不关心有多少。根据题意考虑区间修改，并且题目背景是离线的，因此不需要使用线段树来维护，使用前缀和与差分的技巧即可。

代码（差分做法）：

#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;
}

代码（直接模拟）

#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个数使得 $a_x+a_y=a_z+a_w$

输入格式

第一行包括一个整数 $n$ ，表示整数序列的长度

第二行包括 $n$ 个整数 $a_1,a_2,...,a_n$

输出格式

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

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

输入输出样例

输入 #1

6
2 1 5 2 7 4

输出 #1

YES
2 3 1 6 

输入 #2

5
1 3 1 9 20

输出 #2

NO

解决方案

思路

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

代码

#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

题目

题目描述

给出两个数组 $a，b$ ，长度分别为 $n，m$ ，第 $i$ 时刻， $a$ 数组当前指向下标为 $( i − 1 ) \% n + 1$ ， $b$ 数组指向下标为 $( i − 1 )$ 。

若两个数不同，则计数，当计数到达 $k$ 时，求当前的时刻。

输入格式

第一行三个整数 $n，m，k$ ，表示两个灯光序列的长度和参数 $k$ 。

第二行 $n$ 个整数，表示第一个灯光序列。

第三行 $m$ 个整数，表示第二个灯光序列。

输出格式

输出一个整数，当计数到达 $k$ 时的时刻。

输入输出样例

输入 #1

4 2 4
4 2 3 1
2 1

输出 #1

5

输入 #2

3 8 41
1 3 2
1 6 4 3 5 7 2 8

输出 #2

47

输入 #3

1 2 31
1
1 2

输出 #3

62

解决方案

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

请参阅

• https://blog.csdn.net/WedsonLin/article/details/114786591
• https://blog.csdn.net/weixin_45755679/article/details/114952203