Codeforces Round #707 --Div. 2

A. Alexey and Train

链接：https://codeforces.com/contest/1501/problem/A

题目大意

给你一个火车的时间表（包括预计到达时间，预计出发时间），再给你一个组数，表示每站到达的延迟时间。火车出发需要满足两个条件。

1.最少等待（预计出发时间-预计到达时间）/2的时间（向上取整）。

2.出发时间>=预计出发时间

解题思路

每次实际出发时间＞预计出发时间才对后续到站出站有影响，存一下实际出发时间-预计出发时间的差值，加在下一站到站时间上。

代码

#include
#include
#define x first
#define y second

using namespace std;

const int N = 110;

typedef pair PII;

PII que[N];
int c[N],to[N];
int n,t,res;

void solve()
{
	int last = 0;
	for( int i = 1 ; i <= n ; i++ )
	{
		int l = que[i].x , r = que[i].y;
		int d = (r-l+1)/2;//等待时间
		l += c[i] + d + last;//等待时间+上一站延迟时间+预计到达时间 = 下一次出发时间
		if( l >= r )
		{
			last = l - r;//实际出发时间和预计出发时间的差值
		}
		else last = 0;//不符合条件则下一站正常
		if( i == n )
			cout<>t;
	while( t-- )
	{
		cin>>n;
		for( int i = 1; i <= n ; i++ )
		{
			int a,b;
			cin>>a>>b;
			que[i].x = a, que[i].y = b;
			to[i] = b - a;
		}
		for( int i = 1 ; i <= n ; i++ ) cin>>c[i];
		
		solve();
		
	}
	return 0;
} 

B. Napoleon Cake

链接：https://codeforces.com/contest/1501/problem/B

题目大意

层层垒面包，面包上有抹奶油和不抹奶油两种选择，如果抹奶油会给出该层奶油可以向下渗透多少层，问最后蛋糕奶油渗透情况，被渗透为1，不被渗透为0。

解题思路

直接模拟

倒推面包情况，在抹奶油的过程中遇到新的抹奶油情况时，二者渗透层数取最大值接着往下走。注意下标不要越界。

差分

求出左右边界，分别标记一下，再对差分数组求前缀和，对于差分数组里大于1的部分一律视作1打印。

模拟代码

#include
#include
#include
#include
#define x first
#define y second
 
using namespace std;
 
const int N = 2*(1e5+10);
 
int q[N];
int a[N];
 
int main(void)
{
	int t;
	cin>>t;
	while( t-- )
	{
		int n;
		cin>>n;
		for( int i = 1 ; i <= n ; i++ )
		{
			scanf("%d",&a[i]);
		}
		for( int i = n , k = 1; i >= 1 ;  )
		{
			if( a[i] == 0 )
			{
				q[k++] = 0;
				i--;
			}
			else
			{
				int cnt = a[i]-1;
				q[k++] = 1;
				i--;
				while( cnt--&&i>=1 )//一直RE，原来是数组下标一直减少越界了。
				{
					if( a[i]!=0 )
					{
						cnt = max(cnt,a[i]-1);
						q[k++] = 1;
						i--;
					}
					else
					{
						q[k++] = 1;
						i--;
					}
				}
			}
		}
 
		
		for( int i = n ; i >= 1 ; i-- ) cout<

#include
#include
#include
#include
#define x first
#define y second
 
using namespace std;
 
const int N = 2*(1e5+10);
 
int q[N];
int a[N];

void insert(int l,int r)
{
	q[l] += 1;
	q[r+1] -= 1;
}
 
int main(void)
{
	int t;
	cin>>t;
	while( t-- )
	{
		int n;
		cin>>n;
		for( int i = 1; i <= n ;i++ )	scanf("%d",&a[i]);
		
		for( int i = 1; i <= n ; i++ )
		{
			if( a[i]!=0 )
			{
				int cnt = a[i]-1;
				int l = i - cnt;
				if( l < 0 ) l = 1;
				insert(l,i);
			}
		}
		
		for( int i = 1 ; i <= n ; i++ )	q[i] += q[i-1];
		
		for( int i = 1 ; i <= n ; i++ )
		{
			if( q[i] >= 1 ) cout<<1<<" ";
			else cout<