Jackreturn的解题报告

这题就是分解质因数，不过这个数是大数，把这个大数拿来除以逐个质数（质数小于等于L的开平方），如果能整除，那么就找到了一个小于L的因数，就bad, 否则就good.

另外一个要注意的是如果你的大数的数组每一个只作为一位十进制数的话，会超时，你可以每一位存10^9.也就是说你的大数是10^9进制的。

#include <iostream>
#include <math.h>
#include <string>

using namespace std;

int prime[78500];
long long num[20];
int bound;
int len, seg;
int i, k;

void Compute()
{
    prime[0] = 2;
	int num = 1;
	bool goout;
	int sqr;
	
	for (int i=1; i<78500; i++)
	{
		num += 2;
		sqr = sqrt(double(num));
		for (int j=0; j<i; j++)
		{
			if (num % prime[j] == 0)
			{
				i--;
				goout = true;
				break;
			}
			else if(prime[j] > sqr)
			{
				goout = false;
				break;
			}
		}
		if (false == goout)
		{
			prime[i] = num;
		}
	}
}

void Good()
{
	int i, k;
	long long remainder;

	if (bound>2 && (num[seg-1]&1) == 0)
	{
		printf("BAD %d\n", 2);
		return;
	}
	for (k=1; prime[k]<bound; k++)
	{
		remainder = 0;
		for (i=0; i<seg; i++)
		{
			remainder = (remainder*1000000000000ll + num[i]) % prime[k];
		}
		if (0 == remainder)
		{
			printf("BAD %d\n", prime[k]);
			return;
		}
	}
	printf("GOOD\n");
}

int main() 
{
	Compute();
    int left;
	string ch;
    while(cin >> ch && scanf("%d", &bound) && bound != 0)
	{
		len = ch.length();;
		left = len % 12;
		if(left != 0)
		{
			for(i=len; i<len+12-left; i++)
			{
				ch = '0' + ch;
			}
			len = len + 12 - left;
		}
		seg = len / 12;
		for (i=0; i<seg; i++)
		{
			int temp = i*12;
			num[i] = 0;
			for(k=0; k<12; k++)
			{
				num[i] = (num[i] * 10) + ch[temp+k] - '0';
			}
		}
		Good();
	}
	return 0;
}

 

首先，我们可以找出能读多少，只要统计一下有几个不同的单词就可以了，用wstoread存起来。然后从前往后找，找到与wstoread相等时，再从当前向前找，直到找到与wstoread相等长度

 

附送几组测试数据

4

a

b

c

d

8

a

a

b

b

c

a

d

d

 

2

a

b

3

c

c

a

 

2

a

b

3

c

c

c

 

下面是带注释代码

#pragma warning (disable : 4786)
#include <iostream>
#include <bitset>
#include <map>

using namespace std;

//这题还可以不用位标记，那么只要计数就可以。应该是线性的。
struct String
{
    char s[11];
    bool operator < (const String &s2) const
    {
        return strcmp(s, s2.s) < 0;
    }
};

int len1, len2;
int wstoread, minlen;
bitset< 1001 > bs;
int c[1001], clen = 0;
int pos[100000];
map< String, int > sim;

void Init()
{
    scanf("%d\n", &len1);
    int i;
    String str;
    for(i=1; i<=len1; i++)
    {
        gets(str.s);
        sim[str] = i;
    }
    scanf("%d\n", &len2);
    for(i=0; i<len2; i++)
    {
        gets(str.s);
        if(sim.find(str) != sim.end())
        {
            pos[i] = sim[str];
            bs.set(pos[i]);
        }
    }
    wstoread = bs.count();
    minlen = 1000000;
}

void Compute()            //从前往后找，找到与wstoread相等时，再从当前向前找，直到找到与wstoread相等长度
{
    bs.reset();
    int i, k, temp;
    for(i=0, k=0; i<len2; i++)
    {
        if(pos[i])
        {
            c[pos[i]]++;
            if(c[pos[i]] == 1)
                clen++;
        }
        if(clen == wstoread)
        {
            while(clen == wstoread)
            {
                if(pos[k])
                {
                    c[pos[k]]--;
                    if(c[pos[k]] == 0)
                        clen--;
                }
                k++;
            }
            temp = i - k + 2;
            if(temp < minlen)
                minlen = temp;
        }
    }
}

int main()
{
    Init();
    if(wstoread == 0)
        printf("0\n0\n");
    else
    {
        Compute();
        printf("%d\n%d\n", wstoread, minlen);
    }
    return 0;
}

 

这题我用m[i][k]来表示1..i数中选出k个的最大值，从而进行记忆化搜索，你也可以把代码写成动态规划。

附送几组测试数据

3

2

10 20 30

4 5 6

 

3

1

10 20 30

4 5 6

 

3

2

10 30 20

4 6 5

 

4

4

5 10 30 20

3 4 6 5

 

4

3

5 10 30 20

3 4 6 5

 

4

2

5 10 30 20

3 4 6 5

 

1

1

1

1

 

带注释代码：

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

using namespace std;

struct Num
{
    int a, b;
};

inline bool cmp(Num n1, Num n2)
{
    return n1.b < n2.b;
}

int m[200][200];        //m[i][k]，表示1..i数中选出k个的最大值
Num n[200];
int ns, rounds;

inline int maxx(int a, int b)
{
    return a > b ? a : b;
}

inline int Max(int l, int k)        //表示在l<=i<n中选k个能得到的最大值
{
    if(m[l][k] < 0)
    {
        if(k == 0 || l+k > ns)        //注意不要越界了
            m[l][k] = 0;
        else
        {
            if(k == 1)
            {
                for(int i=l; i<ns; i++)   
                {
                    if(m[l][k] < n[i].a)
                        m[l][k] = n[i].a;
                }
            }
            else
            {
                m[l][k] = maxx(Max(l+1, k), n[l].a - (k - 1) * n[l].b + Max(l+1, k-1));
            }
        }
    }
    return m[l][k];
}

inline void Init()
{
    scanf("%d%d", &ns, &rounds);
    int i;
    for(i=0; i<ns; i++)
    {
        scanf("%d", &n[i].a);
    }
    for(i=0; i<ns; i++)
    {
        scanf("%d", &n[i].b);
    }
    sort(n, n+ns, cmp);
}

int main()
{
    memset(m, 255, sizeof(m));
    Init();
    int result = Max(0, rounds);
    printf("%d\n", result);
    return 0;
}