2015 ACM/ICPC Asia Regional Changchun Online Solutions

 


1001 Alisha’s Party

HDU 5437 

题意: \(k\) 个数 \(v_i\) 依次入队, \(m\) 次出队操作, \(q\) 次询问。

每次出队操作有两个参数 \(t\)\(p\) 表示在第 \(t\) 个数入队后出队 \(p\) 个最大的数,如果队内个数不足 \(p\) 个,则全部出队。

在所有数入队后,所有数按从大到小依次出队。

\(q\) 次询问第 \(n_i\) 个出队的数是多少。

\(1\leqslant k\leqslant 150,000,1\leqslant v_i \leqslant 10^8 \)

用优先队列模拟整个过程。注意队列为空的情况。

PS: \(t\) 不为非递减,且可能有相同的 \(t\)

 

 


 

 

 

1002 Ponds

HDU 5438

题意:在一个无向图中有 \(p\) 个点, \(m\) 条边,每个点有一个值 \(v_i\) 。不断的删去度数小于2的点直到不能删为止。求新图中所有点个数为奇数的连通分量的点值的和。

\(1\leqslant p\leqslant 10^4,1\leqslant m\leqslant 10^5\)

用类似拓扑排序的方法删掉所有满足条件的点。注意点的标记。最后一次DFS求出答案。

 

 


 

 

 

1003 Aggregated Counting

HDU 5439

题意:现有一个数列 \(a:1,2,2,3,3,4,4,4,5,5,5,6,6,6,6,\cdots \)\(a_i\) 表示数字 \(i\) 在数列中出现了 \(a_i\) 次。现给出一个数 \(n\) ,求满足 \(a_k=n\) 的最大 \(k\) 值。

\(1\leqslant n\leqslant 10^9\)

\(G_n\) 表示满足 \(a_k=n\) 的最大 \(k\)

\(G_n=\sum_{i=1}^n (i \times a_i) \)

对于求 \(a_n\) ,我们可以设 \(p_n\) 表示数列 \(a\) 中最后一个数 \(n\) 的位置

\(a_n=lower\_bound(p+1,p+N,n)-p\)

\(p_n=p_{n-1}+a_n\)

如果直接求 \(G_n\) 明显超时,展开 \(G_8\) 会发现:

\(\begin{split} G_8 & =1\times 1+2\times 2+3\times 2+4\times 3+5\times 3+6\times 4+7\times 4+8\times 4\\ & =1\times 1+(2+3)\times 2+(4+5)\times 3+(6+7+8)\times 4 \end{split}\)

其中括号内数的个数为 \(a_i\) ,其和可以用求和公式算出。

\(g_n\) 表示 \(G_{p_i}\) 的值。

\(g_n=g_{n-1}+( p_n\times a_n - \frac{a_n(a_n-1)}{2} ) \times n\)

\(G_n=g_{a_{n-1}}+[ (p_{a_{n-1}}+1) \times (n-p_{a_{n-1}}\ ) + \frac{(n-p_{a_{\ n-1}}\ \ )(n-p_{a_{\ n-1}}\ \ -1)}{2} ] \times a_n \)

其中 \(p_n,g_n\) 都可以预处理

 

 


 

 

 

1005 Travel

HDU 5441

题意:在一个无向图中有 \(n\) 个点, \(m\) 条边。现在有 \(q\) 次询问,每次询问有多少个有序对 \((a,b)\) 满足a,b之间存在一条路径满足路径上的每条边长度都不超过x

\(1\leqslant n\leqslant 20,000,1\leqslant m\leqslant 10^6,1\leqslant q\leqslant 5,000\)

离线+并查集

先对边和询问同时按升序排序。然后将满足条件的边相连的点加入集合。对于每次询问可以通过集合中的点的个数算出答案。

 

 


 

 

1006 Favorite Donut

HDU 5442

题意:将一个长度为 \(n\) 的字符串首位相连形成一个环。从环上任意一个点开始沿顺时针或逆时针绕一周可形成 \(2n\) 个新的字符串。求字典序最大的是哪个,输出起始位置和方向(顺时针为0,逆时针为1)。若有多个答案,则让起始位置最小;若起始位置相同,则优先输出顺时针。

\(1\leqslant n\leqslant 20,000\)

后缀数组

先将字符串重复一次,然后加入一个没出现过的字符,在加上翻转后的字符串。形成一个长度为 \(4n+1\) 的新字符串。再用后缀数组进行处理。

字典序最大可能有多个,所以从sa[]末尾开始将所有height[i]>=n的加入一个结构体数组。计算出起始位置和方向。再进行一次排序,得到最优答案。

 

 


 

 

1007 The Water Problem

HDU 5443

题意: \(n\) 个数, \(q\) 次询问,每次询问区间 \([l,r]\) 的最大值。

\(1\leqslant n\leqslant 10^3,1\leqslant q\leqslant 10^3\)

直接RMQ水过。

 

 


 

 

1008 Elven Postman

HDU 5444

题意:在最初为空的二叉树中不断的插入n个数。对于每个数,从根节点开始判断,如果当前节点为空,就插入当前节点,如果当前节点不为空,则小于当前节点的值,插入右子树,否则插入左子树。

接着q次询问,每次询问一个值在二叉树中从根节点开始的查找路径。

\(1\leqslant n\leqslant 10^3\)

直接用二叉树模拟整个插入和询问的过程

 

 


 

 

1010 Unknown Treasure

HDU 5446

题意:求 \(C^m_n \mod M\) ,其中 \(M\)\(k\) 个不同素数 \(p_i\) 的乘积。

\(1\leqslant m\leqslant n\leqslant 10^{18},1\leqslant k\leqslant 10,M\leqslant 10^{18},p_i\leqslant 10^5\)

Lucas+中国剩余定理

用lucas分别求出

\(A_i =C^m_n \mod p_i\)

得到同余方程组

\(x \equiv A_i(mod \ p_i)\)

用中国剩余定理可求出 \(x\)

 

 


 

 

(待续...)

 

Categories: ACM