Atcoder Regular Contest #142 A - Reverse and Minimize

题目大意

定义操作 $f(x)$ ，使数字 x 首尾翻转并去除前导零。如 $f(142) = 241，f(2410)=142$.

给定正整数$N$，$K$，求$[1，N]$中有多少正整数$x$，使得经过有限次$f$操作后，$x=K$.

数据规模

$1 \leq N，K \leq 10^{12}$

我的思路

预处理$K$得到$k_1=K$和$k_2=f(K)$，然后将$k_1，k_2$不断乘以 10，直到大于 N，乘的次数和即为答案

反思与感悟

比赛代码 AC 29, WA 4

题目中说明Find the minimum possible value of x after operations.，即必须是至少进行 1 次操作。所以如果K%10==0，结果为零。同时，必须是the minimum,如果k2 < k1，结果也为零。

读题时不能漏掉每个细节。

tourist

复杂度是$lg(n)$，所以可以多循环以简化代码。

用to_string，atoll,reverse等函数减少编写难度。

珂朵莉树

适用于区间复制、拆分、查找和自定义操作

• 时间复杂度：
  • set实现：$O\left(nloglog_2n\right)$
  • 链表实现：$O\left(n log_2n\right)$

mutable的作用：

mutable 的意思是“可变的”，让我们可以在后面的操作中修改 v 的值。在 C++ 中，mutable 是为了突破 const 的限制而设置的。被 mutable 修饰的变量（mutable 只能用于修饰类中的非静态数据成员），将永远处于可变的状态，即使在一个 const 函数中。

这意味着，我们可以直接修改已经插入 set 的元素的 v 值，而不用将该元素取出后重新加入 set。

实现：

节点保存：

1
2
3
4
5
6
7
8
9

struct Node_t
{
	int l, r;
	mutable int v;

	Node_t(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {}
	inline bool operator<(const Node_t &o) const { return l < 0.l; }
};
set<Node_t> odt;

其中，v是附加数据。

分裂区间：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

set<Node_t>::iterator split(int x)
{
	if (x > n)
	{
		return odt.end();
	}

	auto it = --odt.upper_bound((Node_t){x, 0, 0});
	if (it->l == x)
	{
		return it;
	}

	int l = it->l;
	int r = it->r;
	int v = it->v;

	odt.erase(it);
	odt.insert(Node_t(l, x - 1, v));
	return odt.insert(Node_t(x, r, v)).first;
}

将包含点x的区间(设为[l, r]),分裂为两个区间[l, r)和[x, r],返回指向后者的迭代器。

任何对于==[l, r]的区间操作，都可以转换成set上对$[split(l),split(r+1)]$==的操作。

区间赋值：

1
2
3
4
5
6

void assign(int l, int r, int v) 
{
  auto itr = split(r + 1), itl = split(l);
  odt.erase(itl, itr);
  odt.insert(Node_t(l, r, v));
}

其余操作套模板：

1
2
3
4
5
6
7
8

void performance(int l, int r) 
{
  auto itr = split(r + 1), itl = split(l);
  for (; itl != itr; ++itl) 
  {
    // Perform Operations here
  }
}

拓扑排序

概念

对一个有向无环图(Directed Acyclic Graph 简称 DAG)G 进行拓扑排序，是将 G 中所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v，若边<u,v>∈E(G)，则 u 在线性序列中出现在 v 之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。

实现

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def topologicalSort()

	"""将所有节点的color[u]设置为WHITE"""
	"""设置所有节点u的入度indeg[u]"""

	for u from 0 to |V| - 1
		if indeg[u] == 0 && color[u] == WHITE
			bfs(u)

def bfs(int s)
	Q.push(s)
	color[s] = GRAY
	while Q isn't empty
		u = Q.dequeue
		out.push_back(u) """将度为0的顶点加入链表"""

		for v is the neighbour of u
			indeg[v]--
			if indeg[v] == 0 && color[v] == WHITE
				color[v] = GRAY
				Q.enqueue(v)

上述算法根据BFS的顺序依次访问入度为0的顶点，并将访问过的顶点添加至链表末尾。

该算法将访问过的顶点u视为“已结束”，同时将下一顶点v（从u出发的边指向的顶点）的入度减1。这一操作相当于删除边。不断地删除边可以是v的入度逐渐降为0，此时我们便可以访问顶点v，然后将v加入链表。

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13

def topologicalSort()
	"""将所有节点的color[u]设置为WHITE"""

	for s from 0 to |V| - 1
		if color[s] == WHITE
			dfs(s)
	
def dfs(int u)
	color[u] = GRAY
	for v is the neighbour of u
		if color[v] == WHITE
			dfs(v)
	out.push_fronf(u)	"""将访问计数的顶点逆向添加只链表"""

上述算法通过DFS搜索访问顶点，并把访问完的顶点添加至链表开头。

注意： 由于深度优先搜索时逆向确定各顶点的拓扑排序，因此节点时添加至链表的开头

Educational Codeforces Round #133 C. Robot in a Hallway

题目大意

有一个$2*m$的网格，一个机器人在$(1,1)$的位置，现在想要走遍所有的格子，且每个格子最多只能经过一次。

对于每个格子$(i,j)$存在$a_{i,j}$，表示至少经过$a_{i,j}$秒后才能进入这个格子。

每一秒内，机器人有两种动作；

• 待在当前格子不动
• 去往上下左右任意相邻的格子

求出走遍每一个格子的最小时间。

数据规模

有$t$组数据: $1\leq t \leq 10^4$

$2 \leq m \leq 2 * 10^5$

$0 \leq a_{i,j} \leq 10^9$

$\Sigma m \leq 2 * 10^5$

我的思路（错）

由题意易得有三种遍历方法

• 1. 顺时针走， 如;

  1 2 3

  1 -> 2 -> 3 -> 4 | 8 <- 7 <- 6 <- 5

• 2. 逆时针走，如:

  1 2 3

  1 <- 8 <- 7 <- 6 | | 2 -> 3 -> 4 -> 5

• 3. 绕着走，如:

  1 2 3

  1 4 -> 5 8 | | | | 2 -> 3 6 -> 7

假设所有$a$均为零，可以得出每种方法走到每个格子对应的时间$s1_{i,j}$，$s2_{i,j}$，$s3_{i,j}$，

接着，对于每种方法，遍历每个格子，对于任意$(i,j)$，求出其中$a_{i, j} - s_{i, j}$的最大值，即等待时间的最大值，若$a_{i, j} \leq s_{i, j}$,则按0算

求出三种方法对应的最大等待时间后，则可以假设开始时等待到某一时刻后，直接畅通无阻地走完格子。所以，对于每种方法，花费的时间为$2 * n - 1 + max(s_{i, j})$

时间复杂度为$\Theta (n)$

代码链接

！！！不止三种方法！！！

可以先用第三种，再用第二或第三种。

大佬代码

Um_nik

对于每种走法，都能简化为先蛇行走，之后在某一结点按钩子形走。

所以可以得出状态转移方程。

Codeforces Round #812 C. Build Permutation

题目大意

一个满足如下规则的从零开始标号数列a可以称之为好：

$\forall i \in [0,n), a_i + i = y^2, y\in\mathbb{Z}$

给定数字$n$, 求出排列$[0,1,2 \dots n-1]$的排列$p$,使得$p$为一个好的数列

有T组数据

数据规模

$1\leq T\leq 10^4$

$1\leq n \leq 10^5$

$\Sigma n \leq 10^5$

我的思路(无)

大佬代码

jiangly

对于$n-1$，查找大于等于$n-1$的最小的完全平方数$v$,并将其与$v-n+1$相匹配，即:

1
2
3
4

for (int i = v - r + 1; i < r; i++)
{
	p[i] = v - i;
}

接着将n迭代为$v-n+1$,重复操作，直到n=0

时间复杂度:$\Theta(n)$