首页 > 专题系列 > Java解POJ > POJ 2887 Big String [解题报告] Java
2013
11-12

POJ 2887 Big String [解题报告] Java

Big String

问题描述 :

You are given a string and supposed to do some string manipulations.

输入:

The first line of the input contains the initial string. You can assume that it is non-empty and its length does not exceed 1,000,000.

The second line contains the number of manipulation commands N (0 < N 2,000). The following N lines describe a command each. The commands are in one of the two formats below:

  1. I ch p: Insert a character ch before the p-th character of the current string. If p is larger than the length of the string, the character is appended to the end of the string.
  2. Q p: Query the p-th character of the current string. The input ensures that the p-th character exists.

All characters in the input are digits or lowercase letters of the English alphabet.

输出:

For each Q command output one line containing only the single character queried.

样例输入:

ab
7
Q 1
I c 2
I d 4
I e 2
Q 5
I f 1
Q 3

样例输出:

a
d
e

解题代码:

//* @author: [email protected]
import java.io.*;
public class Main
{
 public static void main(String[] args) throws IOException
 {
   InputStreamReader is=new InputStreamReader(System.in);
   BufferedReader in=new BufferedReader(is);
   int[] s=new int[1000010];
   int size=0;
   while(true)
   {
	int u=in.read();
	if(u=='\n')break;
	s[size++]=u;
    }
   int n=Integer.parseInt(in.readLine());
   int[] arr=new int[n];
   char[] crr=new char[n];
   int l=0;
   for(int i=0;i< n;i++)
   {
	int ww=in.read();
	if(ww=='Q')
	{
        in.read();
	 int u=0;
	 while(true)
	 {
	  int temp=in.read();
	  if(temp>='0'&&temp<='9')
	  {
		u*=10;
		u+=temp-'0';
	  }
	  else break;
	 }
	 char ans='\0';
	 for(int j=l-1;j>=0;j--)
	 {
	  if(arr[j]< u) u--;
	  else if(arr[j]==u){
		ans=crr[j];
		break;
	  }
	 }
	if(ans=='\0')
		ans=(char)s[u-1];
	System.out.println(ans);
     }
    else if(ww=='I')
    {
	in.read();
	crr[l]=(char)in.read();
	in.read();
	int u=0;
	while(true)
	{
	   int temp=in.read();
	   if(temp>='0'&&temp<='9')
	   {
		u*=10;
		u+=temp-'0';
	   }
	   else break;
	 }
	if(u>l+size) u=l+size+1;
	arr[l]=u;
	l++;
     }
     in.readLine();
   }
 }
}

  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮