题目描述#

从时间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;
}

题目描述#

给你 $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;
}

题目描述#

给你一个整数序列，问你能不能找到下标不同的4个数使得 $a_x+a_y=a_z+a_w$

输入格式#

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

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

输出格式#

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

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

输入输出样例#

6
2 1 5 2 7 4

YES
2 3 1 6 

5
1 3 1 9 20

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

题目描述#

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

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

输入格式#

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

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

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

输出格式#

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

输入输出样例#

4 2 4
4 2 3 1
2 1

5

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

47

1 2 31
1
1 2

62