A - Vova and Train

Codeforces Round #515 (Div. 3)

题目大意

一条坐标轴上，1∼L上所有坐标是v的整数倍的地方有灯笼，但l∼r区间灯笼被挡着了看不见，求能看到多少灯笼？

思路

签到题，l∼r区间把整个区间分成了两部分，答案就是1∼(l-1)和(r+1)∼L两个区间v的倍数的数的个数之和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int len,v,l,r;
		scanf("%d%d%d%d",&len,&v,&l,&r);
		int ans1=(l-1)/v;
		int ans2=len/v-r/v;
		printf("%d\n",ans1+ans2);
	}
	return 0;
}

B - Heaters

Codeforces Round #515 (Div. 3)

题目大意

一个由0,1组成的数组，0为空，1为热源，热源的范围是r，即a[i-r+1] ∼a[i+r-1]都可以被温暖。热源位置固定，但你可决定其用或者不用，若不可使全部的数组温暖，输出"-1"，若可以使全部的数组温暖，输出最小的打开的热源的数目。

思路

如果一个取暖器不开，那么必须保证这个取暖器能温暖的最右的位置必须由前面或者后面的取暖器温暖（需要各自满足条件）。因为要找最小的数量，我们就尽可能要选靠右的，直接上贪心就好了。

代码

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
#include< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
const int maxn=1005;
int a[maxn],n,r,cnt=0;
struct node
{
	int l,r;
} b[maxn];
int main()
{
	scanf("%d%d",&n,&r);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]) b[++cnt].l=i-r+1,b[cnt].r=i+r-1;
	}
	int last=1,now=1,ans=0;
	bool flag=false;
	while(now<=n)
	{
		bool f=false;
		while(last<=cnt&&b[last].l<=now) last++,f=true;
		last--;
		if(!f||now>b[last].r||last>cnt)
		{
			flag=true;
			break;
		}
		now=b[last].r+1;
		ans++;
	}
	if(flag) return printf("-1\n"),0;
	printf("%d\n",ans);
	return 0;
}

C - Many Equal Substrings

Codeforces Round #506 (Div. 3)

题目大意

构造最短长度的字符串str，使得恰好k个位置出现字符串s。

思路

模拟，不断枚举已经添加了的字符串中的某个位置作为起点继续添加，看能不能形成s，如果不能就回退，要注意一下回退的位置，代码也有些细节方面要注意。

代码

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
#include&#60; cstdio &#62;
#include&#60; cstring &#62;
#include&#60; algorithm &#62;
using namespace std;
const int maxn=100005;
int n,k;
char s[maxn],str[maxn];
int main()
{
	scanf("%d%d",&n,&k);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++) str[i]=s[i];
	int cnt=1;
	int now=1;
	int len=n;
	while(cnt<k)
	{
		int t=1;now++;
		while(now<=len&&t<=n&&str[now]==s[t]) now++,t++;
		if(now<=len)
		{
			now=now-t+1;
			continue;
		}
		for(int i=t;i<=n;i++) str[now]=s[i],now++,len++;
		now=len-n+1;
		cnt++;
	}
	printf("%s",str+1);
	return 0;
}

D - Creating the Contest

Codeforces Round #506 (Div. 3)

题目大意

给出一个保证升序的数列，求最长上升子序列，要求子序列中的数满足：

ci+1≤2⋅ci  (1≤i<n)c_{i+1}\leq2\cdot c_i\;(1\leq i<n)

思路

  • 贪心

很明显的贪心，如果相邻的两个数都不满足，那么肯定和之前的数也不满足。

  • dp

按照lis的方法做dp就好了，加一个if判断一下是否满足条件即可（实则就是贪心……）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include&#60; cstdio &#62;
#include&#60; cstring &#62;
#include&#60; algorithm &#62;
using namespace std;
const int maxn=200005;
int a[maxn],f[maxn],n,ans=0;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	f[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(a[i]<=a[i-1]*2) f[i]=f[i-1]+1;
		else f[i]=1;
	}
	for(int i=1;i<=n;i++) ans=max(ans,f[i]);
	printf("%d\n",ans);
	return 0;
}

E - Maximal Intersection

Codeforces Round #506 (Div. 3)

题目大意

有n个区间，从这n个区间里面删去一个区间让其他区间的公共区间的区间长度最大，求这个最大值为多少。

思路

这道题最开始理解错题意了，害的我写了一大堆全删了……

我们先思考如果不删区间，怎么快速求出公共区间的长度。很显然，答案是所有区间中最靠左的右端点减去最靠右的左端点，如果值大于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
#include&#60; cstdio &#62;
#include&#60; cstring &#62;
#include&#60; algorithm &#62;
using namespace std;
const int maxn=500005;
struct node
{
	int l,r;
} seg[maxn],s[maxn];
int n,left[maxn],right[maxn],ans=0;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&seg[i].l,&seg[i].r);
		left[i]=seg[i].l;
		right[i]=seg[i].r;
	}
	sort(left+1,left+n+1);sort(right+1,right+n+1);
	for(int i=1;i<=n;i++)
	{
		int ls=left[n],rs=right[1];
		if(seg[i].l==ls) ls=left[n-1];
		if(seg[i].r==rs) rs=right[2];
		ans=max(ans,rs-ls);
	}
	printf("%d\n",ans);
	return 0;
}

F - Books Queries

Codeforces Round #515 (Div. 3)

题目大意

维护一个数据结构，支持以下三种操作：

  • L id：在现在序列的左边插一个编号为id的物品
  • R id：在现在序列的右边插一个编号为id的物品
  • ? id：查询该点左面有几个元素，右面有几个元素，并取min输出

思路

直接把数组向右平移maxn个单位，直接开两个指针模拟就好了……

代码

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
#include&#60; cstdio &#62;
#include&#60; cstring &#62;
#include&#60; algorithm &#62;
#include&#60; iostream &#62;
using namespace std;
const int maxn=500005;
int pos[maxn],q;
int main()
{
	cin>>q;
	int left=250000,right=250000-1;
	while(q--)
	{
		char opt;
		int val;
		cin>>opt>>val;
		if(opt=='L')
		{
			left--;
			pos[val]=left;
		}
		else if(opt=='R')
		{
			right++;
			pos[val]=right;
		}
		else if(opt=='?') cout<<min(pos[val]-left,right-pos[val])<<endl;
	}
	return 0;
}

总结

Day1比较温柔，难度顺序也是递升的。
要提高自己的英语水平了……

rank