// MyFirstApp.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

typedef __int64 lld;

const int MAXN = 20010;

struct BigNum
{
	int dig[512];//题目说最多200位，平方之后最多400位
	int len;
	BigNum() {}
	BigNum(int arr[], int size) 
	{
		clr();
		len = size;
		for (int i = 0; i < len; i++)
		{
			dig[len - i - 1] = arr[i];
		}
	}
	void clr()
	{
		memset(dig, 0, sizeof(int) * 512);
		len = 1;
	}

	void operator --()
	{
		dig[0]--;
		int bit=0;
		while (dig[bit] < 0)
		{
			dig[bit] += 10;
			dig[bit + 1] --;
		}

		while (len > 1 && dig[len - 1] == 0)
		{
			len--;
		}
	}

	bool operator<(const BigNum& other) const
	{
		if (len < other.len)
		{
			return true;
		}

		if (other.len < len)
		{
			return false;
		}

		for (int i = 0; i < len; i++)
		{
			if (dig[i] != other.dig[i])
			{
				return dig[i] < other.dig[i];
			}
		}

		return false;
	}

	void operator ++()
	{
		dig[0]++;
		int bit = 0;
		while (dig[bit] > 9)
		{
			dig[bit] -= 10;
			dig[bit + 1] ++;
		}

		if (dig[len])
		{
			len++;
		}
	}

};

bool IsSuffix(const BigNum& num, int* pat, int size)
{
	if (size > num.len)
	{
		return false;
	}

	for (int i = 0; i < size; i++)
	{
		if (num.dig[i] != pat[size - i - 1])
		{
			return false;
		}
	}

	return true;
}

bool Match(int* pat, int patlen, const BigNum& tmp, int last)
{
	int i = 0;
	for (i = 0; i < tmp.len && last + i < patlen; i++)
	{
		if (tmp.dig[i] != pat[last + i])
		{
			return false;
		}
	}

	return i == tmp.len || last + i == patlen;
}

void FindSeperateSeveralSegments(int patlen, int* pat, BigNum& ans, int& offset)
{
	//把pat分解成前后两部分，后面一部分是由n,n+1,n+2...堆起来的，那么后面的开头数字长度不能小于第一部分
	for (int i = 0; patlen - (i + 1) >= i + 1; i++)
	{
		if (pat[i + 1] == 0)
		{
			//首位数字必须非0
			continue;
		}
		//枚举后面数字[i+1,j]区间为第一个数字
		//j-i>=i+1
		for (int j = i + i + 1; j < patlen; j++)
		{
			BigNum head = BigNum(pat + i + 1, j - i);
			BigNum pre = head;
			--pre;
			//判断前面部分是否为head-1的后缀
			if (!IsSuffix(pre, pat, i + 1))
			{
				continue;
			}

			int last = j + 1;
			BigNum tmp = head;
			//tmp一直++，把last后面的数字依依匹配，看看能不能配完
			while (last < patlen)
			{
				++tmp;
				if (!Match(pat, patlen, tmp, last))
				{
					break;
				}

				last += tmp.len;
			}

			if (last >= patlen)//匹配成功
			{
				//记录一下现在的答案
				if (pre < ans)
				{
					ans = pre;
					int newOffset = 1 + pre.len - (i + 1);
					offset = newOffset;
				}
			}
		}
	}
}

int main()
{
	char str[512];
	int pat[512];
	int patlen = 0;
	while (cin.getline(str, 1024))
	{
		patlen = strlen(str);
		for (int i = 0; i < patlen; i++)
		{
			pat[i] = str[i] - '0';
		}

		//一个初始解，也就是仅由于段组成的
		BigNum ans = BigNum(pat, patlen);
		int offset = 1;

		if (ans.dig[ans.len - 1] == 0)
		{
			//最高位为0，需要添加一位,比如0，是10后面来的，01应该是101后面来的
			offset++;
			ans.dig[ans.len] = 1;
			ans.len++;
		}

		//假设由若干个数字拼成，寻找答案
		FindSeperateSeveralSegments(patlen, pat, ans, offset);

		//假设只由两个数字拼成，寻找答案
		//FindSeperateTwoSegments(patlen, pat, ans, offset);
	}
	return 0;
}

/*
http://poj.org/problem?id=1863
Subnumber
要考虑前导0，一堆0的情况
*/

• Re:保存代码 (5598) yygy 2023-05-12 23:24:00
  • test data (312) yygy 2023-05-12 23:26:37
    • Re:test data (8434) yygy 2023-05-13 13:00:27
      • 写了12K的代码，1A了，高兴。 (9572) yygy 2023-05-14 21:29:43