中国石油大学ACM俱乐部开放训练赛

问题 A: sciorz画画

题目描述
众所周知，sciorz会画画。某天，sciorz画了一个凸多边形，这个多边形的每个顶点都有一个权值a[i]。sciorz觉得这个凸多边形不够美丽，于是他决定在n个点之间连线，最终用n-3条不相交的线将这个凸n边形分割成n-2个三角形。sciorz认为，一个三角形的美丽值是三个顶点权值的乘积，凸多边形的美丽值是其内部三角形的美丽值的和。sciorz想找到一种分割方案，使得这个凸多边形的美丽值最大。sciorz忙着刷难题，所以他随手就把这个签到题扔给你，希望你帮sciorz算出最大的美丽值。

输入
第一行一个t,表示有t组样例。
每组样例的第一行是一个n,表示多边形的边数。
第二行n个数,第i个数表示多边形第i个顶点的权值a[i]，按逆时针顺序给出。

输出
对于每组样例，输出一行。格式为"Case #x: y"，x为样例编号，y为答案。

分析:
区间DP模板题，注意赋值-INF，题目范围数据给错了，导致一直wa。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 105;
int a[N];
int f[N][N];
int main()
{
	int t;
	scanf("%d", &t);

	int c = 0;
	while (t--)
	{
		int n;
		scanf("%d", &n);

		for (int i = 1; i <= n; ++i)
			scanf("%d", &a[i]);

		for (int len = 3; len <= n; ++len)
		{
			for (int i = 1; i + len - 1 <= n; ++i)
			{
				int l = i , r = i + len - 1;
				f[l][r] = -INF;
				for (int k = l + 1; k < r; ++k)
				{
					f[l][r] = max(f[l][r], f[l][k] + f[k][r] + a[l] * a[r] * a[k]);
				}
			}
		}
		printf("Case #%d: %d
", ++c, f[1][n]);
	}



	return 0;
}

问题 D: 大数

输入
一行 一个正整数n（n<=10^1000000）。

输出
一行
如果存在多种，输出最小的满足题意的数；
如果不存在，则输出-1．

分析
KMP求循环节

注意判断，要求求完美匹配，所以要整除。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
const int N = 1000005;
char s[N];
int ne[N];
int main()
{
    scanf("%s", s + 1);
    int len = strlen(s + 1);
 
    for (int i = 2, j = 0; i <= len; ++i)
    {
        while (j && s[i] != s[j + 1]) j = ne[j];
        if (s[i] == s[j + 1]) ++j;
        ne[i] = j;
    }
 
    int t = len - ne[len];
    if (len % (len - ne[len]) != 0 || len == (len - ne[len]))
        puts("-1");
    else
    {
        for (int i = 1; i <= t; ++i)
            cout << s[i];
    }
    return 0;
}