1.Mathematical Problem

题意

给定奇数\(n\)，求出\(n\)个长度为\(n\)的完全平方数满足：
组成这 \(n\) 个数的数字（\([0,9]\) 内数字）组成的可重集相同。
输出任意一种方案。

思路

进行打表

• \(n=3\) --> \(169,196,961\)
• \(n=5\) --> \(16900,19600,96100,10609,90601\)

发现规律

• 每次在已有的数后加2个零，并在\(169，961\) 的 \(9,1\) 与 \(6\) 中间加\((n-3)/2\)个零

证明

已知\(n=3\)时有\(169,196,961\)
分别为\(13^2,31^2,14^2\)
\(n\)每增加\(2\)，在已有数\(x\)后加\(2\)个零,即
$x * 100 = (\sqrt{x})^2 * 100 = (\sqrt{x}*10)^2 $
为完全平方数，且有 \(1\)个\(6\), \(1\)个\(9\), \(1\)个\(1\), \(n-3\)个\(0\)
设\(2x+1=n\)
在\(169\) 的 \(9,1\) 与 \(6\) 中间加 \((n-3)/2=x-1\) 个零,即
\(1*10^{x}*10^{x}+6*10^{x}+9=(1*10^{x})^2+2*3*1*10^{x}+3^2=(1*10^{x}+3)^2\)
为完全平方数，且有 \(1\)个\(6\), \(1\)个\(9\), \(1\)个\(1\), \(n-3\)个\(0\)
满足条件

时间复杂度

预处理\(n=1至99\)的情况 \(O(n^2)\)
T组询问，\(O(nT)\)
总复杂度 \(\theta(nT+n^2),O(nT)\)

2.Evaluate It and Back Again

题意

请找出一个算术表达式，从左到右读，结果为 \(p\) ，从右到左读，结果为 \(q\) 。其长度最多为 \(1000\) 个字符。它只能包含数字 0 到 9、"+"、"-"和"*"字符 不允许使用数字前导零 不允许使用一元 "+"或"-"。表达式在两个方向上都必须格式正确

思路

特殊到一般

设\(x\)为某表达式，思考何时\(x=x'\)(\(x'\)为\(x\)反串)？
尝试几组特例

• 29+3 = 3+92
• 234+9=9+432

发现若a只包含一位数即加号或乘号，则x=x'

设\(q\)为某表达式，思考何时\(-q=q'\)？
发现若q=0-a，a=a',则\(-q=q'\).

解题

将表达式\(o\)分为 \(a + b(a+b=p,a-b=q)\)
\(a+b=p~~~~~a'+b'=q\)
\(a=a',-b=b'\)
按9进制构造即可

复杂度

\(O(log p)\)