Post 56

Veröffentlicht am | Edited on

CF1102B Array K-Coloring

给出一个长为n的序列a和k种颜色,用这k种颜色给a中的元素染色，要求：

  1. 每个元素都要被染色
  2. 每种颜色都要被使用
  3. 每种颜色不会被用于相同的元素(即若颜色$c_i =c_j(i \neq j)$，必须保证$a_i \neq a_j$如果没有可行的方案，输出”NO”,否则输出”YES”和任何一种可行的方案

题解

非常水的一道题，联赛T2难度

对每个元素染色就行了，如果颜色数大于所有元素，或者某个元素个数多于颜色数都不行。

注意用k循环节染色否则有些颜色本来该出现却没有出现。

更要注意没说颜色数比$n$小！！联赛GG

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#define maxn 5005
std::vector<int> pos[maxn];

int n , k , a[maxn] , c[maxn] , cnt , mx = -0x7fffffff;

int main()
{
	scanf("%d%d",&n,&k);
	if(k > n){
		puts("NO");
		return 0;
	}
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&a[i]) , pos[a[i]].push_back(i) , mx = std::max(mx , a[i]);
	for(int i = 1 ; i <= mx ; ++i)
	{
		if((int)pos[i].size() > k)
		{
			puts("NO");
			return 0;
		}
		for(int j = 0 ; j < (int)pos[i].size() ; ++j)
			c[pos[i][j]] = cnt++ % k + 1;
	} 
	puts("YES");
	for(int i = 1 ; i <= n ; ++i)
		printf("%d ",c[i]);
}

数的划分递推好神奇啊，我不会普及组的题。。。。。。

但是我有生成函数！

P1025 数的划分

题目描述

将整数nn分成kk份，且每份不能为空，任意两个方案不相同(不考虑顺序)。

例如：n=7n=7，k=3k=3，下面三种分法被认为是相同的。

1,1,51,1,5;
1,5,11,5,1;
5,1,15,1,1.

问有多少种不同的分法。

输入输出格式

输入格式：

$n,k$($6<n \le 200$,$2 \le k \le 6$)

输出格式：

1个整数，即不同的分法。

输入输出样例

输入样例#1：

1
7 3

输出样例#1：

1
4

说明

四种分法为：
1,1,5;
1,2,4;
1,3,3;
2,2,3.

题解

只会生成函数。

设计如下

$f(x.y) = \Pi{i=1}^{n}\sum{j=1}^{n}x^{j}y^{ij}(ij \leq n)$

这个多项式不简化只有$O(nlogn)$项所以….应该跑的挺快，回家再仔细分析下复杂度。

[POI2011]LIZ-Lollipop

题目描述

Byteasar runs a confectionery in Byteburg.

Strawberry-vanilla flavoured lollipops are the favourite of local children.

These lollipops are composed of multiple segments of the same length, each segment of either strawberry or vanilla flavour.

The price of the lollipop is the sum of the values of its segments, where a vanilla segment costs one bythaler, while a strawberry segments costs two.

Fig. 1: An exemplary lollipop of five segments, three strawberry flavoured and two vanilla, alternately.

The price of this lollipop is 88 bythalers.

Currently Byteasar is left with only one lollipop, though possibly very long.

As a salesman, he knows only too well that probably no one will want to buy the whole lollipop. For this reason he thinks of breaking the lollipop at the joints of the segments in order to get a shorter lollipop. Each fragment for sale, of course, must stay in one piece.

Byteasar vast experience of a salesman, as well as his understanding of children psychology, tell him that his young customers will most likely want to spend all their money on a single lollipop. With this in mind, he wonders for which values of kk the lollipop he has can be broken down in such a way that as a result one would get, among other pieces, a lollipop worth exactly kk bythalers.

Naturally, he is interested in the way of breaking the lollipop as well.

As this task overwhelms him, he asks you for help.

给一个只有1和2的序列，每次询问有没有一个子串的和为x

输入输出格式

输入格式：

In the first line of the standard input there are two integers nn and mm (1\le n,m \le 1\ 000\ 0001≤n,m≤1 000 000), separated by a single space.

These denote, respectively, the number of segments of the last lollipop left in store, and the number of values of kk to consider.

The lollipop’s segments are numbered from 1 to nn.

The second line gives an nn-letter description of the lollipop, consisting of letters T and W, where T denotes a strawberry flavoured segment, while W - vanilla flavoured;the ii-th of these letters specifies the flavour of the ii-th segment.

In the following mm lines successive values of kk(1\le k\le 2\ 000\ 0001≤k≤2 000 000) to consider are given, one per line.

输出格式：

Your program should print out exactly mm lines, giving, one per line, the results for successive values of kk, to the standard output.

If for a given value of kk it is impossible to break the lollipop in such a way that there is a contiguous fragment worth exactly kk bythalers, then the word NIE (no in Polish) should be printed. Otherwise, two integers ll and rr (1\le l\le r\le n1≤l≤r≤n), separated by single spaces, should be printed, such that the fragment of the lollipop composed of the segments numbered from ll to rr inclusively is worth exactly kk bythalers. If there are multiple such pairs, your program is free to choose one arbitrarily.

输入输出样例

输入样例#1：

1
2
3
4
5
5 3
TWTWT
5
1
7

输出样例#1：

1
2
3
1 3
2 2
NIE

说明

给一个只有1和2的序列，每次询问有没有一个子串的和为x

SPJ对于格式的要求较为严格。对于每个询问后，应紧跟一个换行符。在最后一次输出你的答案以及一个换行符后不应有任何输出。

题解

有个很卡常的做法。。。

首先序列中都是1或者2意味着他们的项数和总和在渐进意义下是一样的。

然后再想到只要序列总和大于询问值，那么总能找到一个连续子串和它的差小于等于1.

这两个其实挺重要。。

考虑对所有询问根号分类。设大小标准为$T$。

对于所有小于$T$的值，我们暴力双指针预处理所有值！预处理复杂度为$O(nT)$,$O(1)$回答询问（这部分必定不会成为复杂度瓶颈，可省略）。

对于所有大于等于$T$的询问$x$，我们在前缀和上二分不大于$x$ , $2x$ …..的位置，由于他们和其期望二分的值的差必定不超过1 ， 所以只需要将相邻做差判断即可。 由于$x$大于等于$T$ , 所以$\frac{n}{x} \leq \frac{n}{T}$ , 每次二分复杂度$O(logn)$ , 所以每次回答这类询问的复杂度是$O(\frac{n}{T}logn)​$.

所以最后总复杂度是$O(nT+q\frac{n}{T}logn)$

$q$与$n$同级，分析（不会，胡乱猜然后发现两边相等）可得$T$应取$\sqrt{nlogn}$

最终时间复杂度为$O(n\sqrt{nlogn})​$

这个复杂度过$1e6​$确实有点困难，先写写试试。。。

突然想到后一部分的正确性好像有点问题，好像能水80分，但是确实是错误的。。。对于一个序列和一个询问，如果把它分成两部分，然后一个是$x-1$一个是$2x$，但是也许序列还存在一个为$x​$的子串。。。。不过这个好像通过微微调整就可以解决。。。

想了一下午还是没想出来。。。

所以把上面那个复杂度正确性两爆炸的做法扔在上面警示后人。。

最后还是看了$O(nlogn)$的正解，最后竟然真的是奇偶性讨论。。这道题只需要一个结论：对于一个$x$，其合法的区间对于和它奇偶性相同且比它小的询问，一定可以从这个区间得到。

这意味着单调性与双指针，线性的复杂度。

证明只需要分类讨论一下。

对于当前这个合法区间$[L,R]​$

  1. 左右都是1，$[L+1,R-1]$即为和它奇偶性相同的前驱。
  2. 左或者右有一个2，移出2的区间即为和它奇偶性相同的前驱。
  3. 都是2为第二条的平凡情况。

难点不是证明，而是如何去思考得到这个结论。。

多用笔绝对有用！！！好好推一推该想不出来还是想不出来

菜是原罪。