<?xml version="1.0"?>
<api>
  <query-continue>
    <allpages gapcontinue="Sgu/179" />
  </query-continue>
  <query>
    <pages>
      <page pageid="464" ns="0" title="Sgu/111">
        <revisions>
          <rev contentformat="text/x-wiki" contentmodel="wikitext" xml:space="preserve">[[分类:高精度]]
==摘要==
{{信息题|Very simple problem|http://acm.sgu.ru/problem.php?contest{{=}}0&amp;problem{{=}}111|1|100|表示错误|3|time=2015-2-18 00:59:55}}
（AC 1817）
==题意==
高精度开方。
==题解==
这一题和[[CodeVS/3119]]是相同的，可是那题的代码莫名其妙PE了……我也不造为什么，也许是io流的问题，不想研究了。不过，高精度神魔的听说java有大整数/小数类，于是顺手开了个java的小坑。之前配置过Android环境了，环境也就不多提了。入个门，写个二分的高精度开方也不算太难的事了。
===Java的a+b程序===
先来个sgu官方java的a+b
&lt;pre&gt;
//引用相关库//
import java.util.*;
import java.io.*;
//主程序类：Solution//
public class Solution 
{
  //主程序，参数是String[] arg//
  public static void main (String[] argv) throws IOException
  {
    //创建一个类似于cin的流//
    BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    //读入一行//
    StringTokenizer st = new StringTokenizer(cin.readLine());
    //从一行中解析//
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    int c = a + b;
    //输出//
    System.out.println(c);
  }
}
&lt;/pre&gt;
===Java的输入输出===
首先先调教输入输出，java中输出常见有几种：
 System.out.print(); //cout&lt;&lt;...;//
 System.out.println(); //cout&lt;&lt;...&lt;&lt;endl;//
 System.out.printf(); //printf(...);注意换行用%n表示//


输入先要创建一个流：
 Scanner cin = new Scanner(System.in); 
或者
 Scanner cin = new Scanner(new BufferedInputStream(System.in));//据说会更快一点//


然后进行输入：
 变量=cin.next类型名();
如
 a=cin.nextInt();

但是听说这种cin就和C++的cin一样容易超时，如果想要快应该用StreamTokenizer和PrintWriter，不过由于我只是用用高精度就无所谓这个了，有兴趣请阅读http://blog.csdn.net/mingchaoyan/article/details/6301858。
===Java的数据类型===
常见的有：int,double,boolean,String,BigDecimal（高精度浮点数）,BigInteger（高精度整数），注意区分大小写。
===Java的高精度和进制转换===
居然没有重载运算符，差评！

用法大概这几种：
 c=a.add(b);//c=a+b;//
 c=a.subtract(b);//c=a-b;//
 c=a.multiply(b);//c=a*b;//
 c=a.divide(b);//c=a/b;//
 c=a.mod(b);//c=a%b;//
 a.compareTo(b);//a和b:相等返回0,小于返回-1,大于返回1//
 c=a.pow(n);//c=a^n;//
 str=a.toString();//对应十进制字符串//
 str=a.toString(n);//对应n进制字符串//
 a=valueOf(n);//a=(int)n;//
 c=a.gcd(b);//abs(a)和abs(b)的最大公约数//
 c=a.abs();//c=abs(a);//
 i=a.hashCode();//a的哈希码//
 p=a.isProbablePrime(int certainty);//是否可能为素数（估计）//
 c=a.nextProbablePrime();//大于a的可能为素数的第一个整数//
 p=a.signum();//正负号函数//
 c=BigInteger.ZERO;//c=0;//
 c=BigInteger.ONE;//c=1;//
 c=BigInteger.TEN;//c=10;//
 c=new BigInteger(st, base);//通过base进制的字符串st构造高精度整数//
 st=Integer.toString(num, base);//把10进制的数num转成base进制的st(base &lt;= 35)//
 i=Integer.parseInt(st, base); //把base进制的st，转成10进制的int//

==代码==
{{折叠|111.java代码已折叠
|&lt;pre&gt;
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Solution{
    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        BigInteger N, l, r, mid;
        N = cin.nextBigInteger();
        l = BigInteger.ZERO;
        r = N.abs().add(BigInteger.ONE);
        while (l.compareTo(r) &lt;= 0) {
            mid = l.add(r).divide(BigInteger.valueOf(2));
            if (mid.multiply(mid).compareTo(N) &gt;= 0) 
                r = mid.subtract(BigInteger.ONE);
            else
                l = mid.add(BigInteger.ONE);
        }
        while (l.multiply(l).compareTo(N) &gt; 0) {
            l = l.subtract(BigInteger.ONE);
        }
        System.out.println(l);
    }
}
&lt;/pre&gt;
|sgu111}}
==参考资料和拓展阅读==
&lt;references/&gt;</rev>
        </revisions>
      </page>
      <page pageid="454" ns="0" title="Sgu/142">
        <revisions>
          <rev contentformat="text/x-wiki" contentmodel="wikitext" xml:space="preserve">[[分类:广度优先搜索]][[分类:搜索与枚举]]
==摘要==
{{信息题|Keyword|http://acm.sgu.ru/problem.php?contest{{=}}0&amp;problem{{=}}142|2|100|time=2015-2-15 23:54:21}}
（AC 1237）

==题意==
已知一个只有a,b的字符串，求最短的只有a,b的非子串。
==题解==
感觉像是枚举，但是直接枚举500W肯定T，所以需要缩小枚举范围。我们容易知道：
#对于长度为n的字符串，最多只有&lt;m&gt;M_1=n-L+1&lt;/m&gt;个长度为L的子串；
#长度为L的串一共有&lt;m&gt;M_2=2^L&lt;/m&gt;个；
#当&lt;m&gt;M_1&lt;M_2&lt;/m&gt;即&lt;m&gt;n&lt;2^L+L-1&lt;/m&gt;的时候，根据抽屉原理，该字符串一定存在长度为L的非子串；
由n≤500000，要保证(3)，只要&lt;m&gt;2^L+L-1\geq500000&lt;/m&gt;，由单调性知道L≥19。也就是说，L=19时，一定能保证存在要求的解&lt;ref&gt;http://wenku.baidu.com/link?url=ErBAJnhqgrHq_mvy2dNmPMvlJNQ5SwsHoILjFv-47Ae24q4aDJTgo8gWSPnY89rxfYaS0Zkl5DByoEQiKoBoImxdAHPZ74iUNewCAyQ9yXa&lt;/ref&gt;。
容易知道&lt;m&gt;2^{19}=524288&lt;/m&gt;，这在可枚举范围内，用类似广搜的方式枚举即可（或者二进制压位直接枚举）。
==代码==
{{折叠|142.cpp代码已折叠
|&lt;pre&gt;
#include&lt;cstdio&gt;
#include&lt;string&gt;
#include&lt;iostream&gt;
bool b[500001]={},a[20][(1&lt;&lt;19)+1]={};
int main()
{
    int n;
    scanf(&quot;%d\n&quot;,&amp;n);
    char c;
    for(int i=1;i&lt;=n;++i)
        b[i]=(getchar()=='b');
    for(int i=1;i&lt;=n;++i)
    {
        int t=0;
        for(int j=1;j&lt;=19&amp;&amp;i+j-1&lt;=n;++j)
        {
            t&lt;&lt;=1;
            t|=b[i+j-1];
            a[j][t]=1;
        }
    }
    for(int w=1;w&lt;=19;++w)
        for(int i=0;i&lt;(1&lt;&lt;w);++i)
            if(!a[w][i])
            {
                std::string c=&quot;&quot;;
                for(int t=1;t&lt;=w;++t)
                {
                    if(i&amp;1)
                        c='b'+c;
                    else
                        c='a'+c;
                    i&gt;&gt;=1;
                }
                std::cout&lt;&lt;w&lt;&lt;std::endl&lt;&lt;c;
                return 0;
            }
}
&lt;/pre&gt;
|sgu142}}

==参考资料和拓展阅读==
&lt;references/&gt;</rev>
        </revisions>
      </page>
    </pages>
  </query>
</api>