臨江仙 送錢穆父

蘇軾

传送门： 2018 Multi-University Training Contest 2 1007 Naive Operations

题目

Naive Operations

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 502768/502768 K (Java/Others)

Problem Description

In a galaxy far, far away, there are two integer sequence a and b of length n.
b is a static permutation of 1 to n. Initially a is filled with zeroes.
There are two kind of operations:
1. add l r: add one for $a_l,a_{l+1}…a_r$
2. query l r: query $\sum_{i=l}^r \lfloor a_i / b_i \rfloor$

求逆序对数有多种方法，如归并排序法、线段树 \ 树状数组法、离散化。

归并排序法几乎就是归并排序。

白书讲解

归并排序思路很简单， 但自己一直不会敲， 也没敲过。 大学算法课本上的代码丑得不行， 嫌弃得要死。 所以自己只知道它的思想。 这几天打高校遇到了求逆序数对的问题，用树状数组来写会爆内存，需要用到归并的思想。于是自己打算好好看一下归并排序，发现紫书上的代码非常简洁，心喜，很快就记住了这段代码，并用自己喜欢的风格敲了一遍。

传送门：https://www.nowcoder.com/acm/contest/141/H

题目描述

Eddy has solved lots of problem involving calculating the number of coprime pairs within some range. This problem can be solved with inclusion-exclusion method. Eddy has implemented it lots of times. Someday, when he encounters another coprime pairs problem, he comes up with diff-prime pairs problem.

传送门：https://www.nowcoder.com/acm/contest/141/A

题目描述

Eddy was a contestant participating in ACM ICPC contests. ACM is short for Algorithm, Coding, Math. Since in the ACM contest, the most important knowledge is about algorithm, followed by coding(implementation ability), then math. However, in the ACM ICPC World Finals 2018, Eddy failed to solve a physics equation, which pushed him away from a potential medal.

当元素较少时，可以使用二进制码来表示集合。集合 ${0， 1， 2， \ldots，n-1}$ 的子集可以用如下方式编码成整数。$$f (S) = \sum_{i \in S} 2^i$$

像这样表示之后，一些集合运算可以对应地写成如下方式。

• 空集 $\phi$——0
• 只含有第 $i$ 个元素的集合 ${i}$——$1<<i$
• 含有全部 $n$ 个元素的集合 ——$(1<<n)-1$
• 判断第 $i$ 个元素是否属于集合 $S$—— if( S>>i&1 ) 或 if(S & (1<<i))
• 向集合 $S$ 加入第 $i$ 个元素 ——S |= 1<<i
• 从集合 $S$ 中去除第 $i$ 个元素 ——S&~(1<<i)
• 集合 $S​$ 和集合 $T​$ 的交集 ——S&T
• 集合 $S$ 和集合 $T$ 的并集 ——S|T
• 切换第 i 位 ——S ^= 1<<i
• 判断某状态是否有相邻的两者相同 ——if( S & S<<1 )
• 把一个数字二进制下最靠右的第一个 1 去掉 ——S = S&(S-1)

此外，想要将集合 {0,1,….,n-1} 所有子集枚举出来的话，可以像下面这样写

1
2
3
4

for(int S=0; S < 1<<n; S++)
{
	//对子集的操作    
}

1001 Maximum Multiple

Problem Description

Given an integer n, Chiaki would like to find three positive integers x, y and z such that: $n=x+y+z$, $x\mid n$, $y \mid n$, $z \mid n$ and $xyz$ is maximum.

Input

There are multiple test cases. The first line of input contains an integer $T$ ($1 \le T \le 10^6$), indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($1 \le n \le 10^{6}$).

Output

For each test case, output an integer denoting the maximum $xyz$. If there no such integers, output $-1$ instead.

题目链接

前言

&emsp;&emsp; 在很多情况下，我们希望在 Hexo 中写的一篇文章能够同时属于多个分类，例如我写一篇 《Servlet 笔记》，我既想将它放在 Java 这个分类中，又想将它放入 Servlet 这个分类。