CF1186

Posted on | Views:

$Div.2$

冲上来就 $pp$ 了前 $4$ 个题,感觉终于可以上个分,然后就 $Unrated$ 了.

A Vus the Cossack and a Contest

  • 签到题.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
int main()
{
	int n=read(),m=read(),k=read();
	if(n<=m && n<=k)
		puts("Yes");
	else
		puts("No");
	return 0;
}

B Vus the Cossack and a Game

  • 题已经被爆破了.
  • 有一个 $n\times m$ 的网格,要在里面放上若干 $1\times 2$ 的骨牌,要求任意两个八连通的格子不能被同时占据,求最多放置的骨牌数目. $n,m\leq 10^9$ .
  • 暂时还不知道有没有可行的做法.

C Vus the Cossack and Strings

  • 其实可以直接算 $1$ 的个数是否相同,若相同,则不同的位置一定是偶数个.
  • 因为两个 $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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e6+10;
int n,m,a[MAXN],b[MAXN];
char buf[MAXN];
int k[MAXN];
void init()
{
	scanf("%s",buf+1);
	n=strlen(buf+1);
	for(int i=1;i<=n;++i)
		a[i]=buf[i]-'0';
	scanf("%s",buf+1);
	m=strlen(buf+1);
	for(int i=1;i<=m;++i)
		b[i]=buf[i]-'0';
}
int query(int l,int r)
{
	return k[r]^k[l-1];
}
int main()
{
	init();
	for(int i=2;i<=n;++i)
		if(a[i]!=a[i-1])
			k[i]^=1;
	for(int i=1;i<=n;++i)
		k[i]^=k[i-1];
	int ans=0,s=0;
	for(int i=1;i<=m;++i)
		if(a[i]!=b[i])
			s^=1;
	if(s==0)
		++ans;
	for(int i=2;i+m-1<=n;++i)
	{
		s^=query(i,i+m-1);
		if(s==0)
			++ans;	
	}	
	cout<<ans<<endl;
	return 0;
}

D Vus the Cossack and Numbers

  • 考虑如果将所有数都向下取整,得到的和为 $-sum$ ,那么显然需要将 $sum$ 个数改成向上取整.
  • 只要不是整数都能改,所以改掉 $sum$ 个就可以了.
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
43
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
const double eps=1e-8;
int n;
double a[MAXN],upv[MAXN],downv[MAXN],delta[MAXN];
bool flag[MAXN];
void pr()
{
	for(int i=1;i<=n;++i)
		printf("%d\n",flag[i]?(int)ceil(a[i]):(int)floor(a[i]));
}
int main()
{
	n=read();
	double sum=0;
	for(int i=1;i<=n;++i)
	{
		scanf("%lf",&a[i]);
		upv[i]=ceil(a[i])-a[i];
		downv[i]=floor(a[i])-a[i];
		delta[i]=upv[i]-downv[i];
		sum-=downv[i];
	}
	for(int i=1;i<=n && fabs(sum)>eps;++i)
		if(fabs(delta[i])>eps)
			flag[i]=true,sum-=1.0;
	pr();
	return 0;
}

E Vus the Cossack and a Field

  • 可以直接算二维前缀和再相减.记 $f(x,y)$ 表示以 $(1,1)$ 为左上角, $(x,y)$ 为右下角的子矩形的权值和.
  • 那么答案就是 $f(x_2,y_2)-f(x_2,y_1-1)-f(x_1-1,y_2)+f(x_1-1,y_1-1)$ .
  • 先预处理出 $x\leq n,y\leq m$ 内的 $f(x,y)$ ,就是二维前缀和.
  • 然后计算所有的 $f(x,y)$ ,就可以将它分割成整的块的不整的块,不整的块用预处理的前缀和算就好了.

F Vus the Cossack and a Graph

  • 待更.
  • 有个贪心的假做法,不知道为什么很多人都用这个水过去了.