whitedeath's Blog

 最小表示法是由IOI2003年冬令营的周源提出来的，今天学习了这后，写下自己的理解和感想~

什么叫最小表示呢，就是把这个字符串看作一个环，在转动的过程中，那个字典序最小的字符串即为字符串的最小表示，具体定义可以参照ZOJ 1729：acm.zju.edu.cn/onlinejudge/showProblem.do

        周源同学介绍的时候是以求两个字符串是否是同构的为中心介绍的，而在求单个字符串的最小表示法上没有细说，个人感觉这个更难以理解一点，因为它相当于自己和自己的下一个表示求是否同构，这个过程中，求出最小表达式，就像kmp算法的next数组，是自己匹配自己的结果~

       这个是网上最一般的最小表示法代码：

int MinimumRepresentation(char *s, int len)
{
    int i = 0, j = 1, count = 0, t;

    while (i < len && j < len && count < len)
    {
        if(s[(i + count) % len] == s[(j + count) % len])
            count++;
        else
        {
            if (s[(i + count) % len] > s[(j + count) % len]) 
                 i = i + count + 1;
            else 
                 j = j + count + 1;
            if (i == j) ++j;
            count = 0;
        }
    }
    return min(i,j);
}

       然而，我在理解这个算法的过程中、和同学讨论的过程中，逐渐发现一些可以改进的地方：

       首先，求余过程很费时间，尤其是字符串比较长的时候。而且本题中最多是len的2倍，所有变求余为作差；

       其次，最后的return min(i,j)可以改成直接return i，因为i <= j是肯定的....因为用通俗的说法，每次i都会把j拉到i+1的位置，所以最后，可以在改变i的时候，将j也拖过去....

      最终代码：

int MinimumRepresentation(char *s, int len)
{
    int i = 0, j = 1, count = 0, t;
    while (i < len && j < len && count < len)
    {
        x = i + count;
        y = j + count;

        if (x >= len) x -= len;          //用减法代替求余 
        if (y >= len) y -= len;          //用减法代替求余

        if (s[x] == s[y])
            count++;
        else
        {
            if (s[x] > s[y])
            {
                i = i + count + 1;
                j = i + 1;         /*将 j 拖至 i + 1 的地方*/
            }
            else
                j = j + count + 1;

            if (i == j) j++;
            count = 0;
        }
    }

    return i;                    //直接return i即可 
}

       思路：这个算法其实就是这样子的，就像刚才说的，是自己跟自己的下一个表示比较，其中i代表本身，j代表这个环的下一个表示方法，然后比较，如果j的表示方法比i小，i就更新了，同时j也更新至i的下一个表示方法，然后继续匹配，直到字符串尾。

 

Problem 6

#include<stdio.h>
int main()
{
	int i;
	long long ans;
	
	ans = 0;
	for(i = 1;i <= 100;i++)
       ans += (i * i);
    
	ans = 5050 * 5050 - ans;
    
    printf("%lld\n",ans);
    
    return 0;
}

Problem 7

#include<stdio.h>
#include<string.h>
#define Max 110000
int main()
{
    int a[Max+1];
    int temp,n,i,cnt;

    memset(a,0,sizeof(a)) ;
    a[0] = a[1] = 1;                       
    for (i = 2;i <= Max;i++)
    {
        if (a[i] == 0)
        {
            temp = 2 * i;                      
            while (temp <= Max)
            {
                a[temp] = 1;
                temp += i;
            }
        }
    }
   
    cnt = 0;
    for (i = 2;i <= Max;i++)
    {
	     if(a[i] == 0)
             cnt++;
         if(cnt == 10001)
           break;
	}
	
    printf("%d\n",i);
	
	return 0;
}

#include<iostream>
#include<string>
using namespace std;
string s = "73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450";
int main()
{
	int i,j,ans,max = -1;

	for(i = 0;i <= 996;i++)
	{
	   ans = 1;	 
	   for(j = i;j <= i + 4;j++)	
    	   ans *= (s[j] - '0');
    	   
	   if(ans > max) 
	       max = ans;  
	}
	
    cout << max <<endl;

    return 0;
}

Problem 9

#include<stdio.h>
#define Max 1000
int main()
{
	int a,b;
	
	for(a = 1; a <= Max;a++)
	  for(b = a + 1;b <= Max;b++)
	  	 if(a * a + b * b == (Max - a - b) * (Max - a - b))
		    goto end;

end: printf("%d\n",a * b * (Max - a - b));
    
    return 0;
}

Problem 10

#include<stdio.h>
#include<string.h>
#define Max 2000000
int main()
{
    int a[Max + 1];
    long temp,n,i;
	long long ans;

    memset(a,0,sizeof(a)) ;
    a[0] = a[1] = 1;                       
    for (i = 2;i <= Max;i++)
    {
        if (a[i] == 0)
        {
            temp = 2 * i;                      
            while (temp <= Max)
            {
                a[temp] = 1;
                temp += i;
            }
        }
    }
   
    ans = 0;
    for (i = 2;i < Max;i++)
	     if(a[i] == 0)
             ans += i;

    printf("%lld\n",ans);
	
	return 0;
}

今天发现一个很好玩的网站：projecteuler.net/，都是我喜欢的数论题

处理数字，我最喜欢！

Problem 1

#include<stdio.h>
int main()
{
 int i,ans;
 
 ans = 0;
 for(i = 3;i < 1000;i++)
    if(i % 3 == 0 || i % 5 == 0)
       ans += i; 
    printf("%d\n",ans);
    
    return 0;
}

Problem 2

#include<stdio.h>
int main()
{
	long long n,t,tmp,ans;
	
	t = 1;
	n = 1;
	ans = 0;
	while(n <= 4000000)
	{
	   tmp = n;
	   n = n + t;
	   t = tmp;

	   if(n % 2 == 0)
	     ans += n;	
	}
	
	printf("%lld\n",ans);

    return 0;
}

Problem 3

#include<stdio.h>
int main()
{
    long long num = 600851475143ll;
	int i = 2;
	
	while (num > 1)
	{
		while(num % i == 0)  num /= i;
		i++;
	}
	i--;
	printf("%d\n",i);
	return 0;
}

Problem 4

#include<stdio.h>
int check(int n)
{
	if(back(n) == n)
	  return 1;
    return 0;
}

int back(int n)
{
	int t;
	
	t = 0;
	while(n != 0)
	{
		t = t * 10 + n % 10;
		n /= 10;
	}
	return t;
}


int main()
{
	int n,m,ans,max;
	
	max = -1;
	for(n = 100;n <= 999;n++)
       for(m = n;m <= 999;m++)
       {
       	  ans = m * n;
       	  if(check(ans) && ans > max)
       	     max = ans; 
       }
	printf("%d\n",max);   
       
    return 0;
}

Problem 5

#include<stdio.h>
int main()
{
	int ans;
	
	ans = 1 * 16 * 9 * 5 * 7 * 11 * 13 * 17  * 19; 
	printf("%d\n",ans);

    return 0;
}

whitedeath is programmer，我喜欢这个名字，嗯嗯嗯~

以后就在这里贴程序、码感悟、写人生了~~